1.一种求解无线网络基站切换极小化问题的变邻域搜索方法,其特征在于:所述方法包括如下步骤:步骤1,输入算例和参数,随机生成初始的可行解;
步骤2,进入扰动阶段,执行扰动程序;
步骤3,进入局部搜索阶段,使用邻域分解的变邻域下降VND算法对扰动的解进行优化;
步骤4,进入更新阶段,执行更新操作,同时,使用判别准则,判断是维持当前扰动强度,还是增加扰动强度;并根据判断条件转到步骤2和步骤5;
步骤5,满足停止条件,步骤停止。
2.根据权利要求1所述的一种求解无线网络基站切换极小化问题的变邻域搜索方法,其特征在于:步骤2所述的扰动程序,以扰动强度k对当前解S进行随机扰动,目的是使其跳出局部最优;扰动算法的具体步骤如下:连续地执行k次随机的顶点交换动作,其中每次交换动作交换两个随机选择的顶点的位置,使得交换后的解仍为合法解。
3.根据权利要求1所述的一种求解无线网络基站切换极小化问题的变邻域搜索方法,其特征在于:步骤3中,通过基于邻域分解的变邻域下降VND算法对步骤2扰动后的结果进行优化,其中VND算法的邻域的结构描述如下:基于邻域分解的变邻域下降算法使用了两个邻域结构,即单点移动邻域N1(s)和两点交换邻域N2(s);
单点移动邻域N1(s):N1(s)由单点移动算子生成;已知一个顶点集的划分,单点移动算子将一个顶点从它当前的类中移到另一个类中,从而得到一个新的合法解;N1(s)的数学表达式如下:其中,s表示当前解;
两点交换邻域N2(s):N2(s)由交换算子生成;已知一个顶点集的划分,两点交换动作将对两个处于不同类的顶点进行位置交换,以得到一个新的合法解;N2(s)的数学表达式如下:其中,s表示一个可行解,v表示类Ci中的一个顶点,u表示类Cj中的一个顶点,swap(.,.)表示一个交换动作, 表示在解s上进行两点交换动作。
4.根据权利要求1所述的一种求解无线网络基站切换极小化问题的变邻域搜索方法,其特征在于:步骤3中,所述的基于邻域分解的变邻域下降VND算法,对扰动结果进行优化,其中变邻域下降VND算法的主要构成部分包括领域分解、领域块标记和状态矩阵更新,具体的:领域的分解:将邻域N1(s)和邻域N2(s)划分成若干个由可行解构成的集合,即邻域块;
邻域N1(s)被划分成K×(K-1)个不相关的邻域块B1[i][j](s),即N1(s)=∪1≤i≠j≤KB1[i][j](s),其中邻域块B1[i][j](s)表示从类Ci中选一个顶点移到类Cj中所形成的可行解的集合;
形式上,B1[i][j](s)表示为
类似地,邻域N2(s)被分成K×(K-1)/2个不相关的邻域块B2[i][j](s)(i<j),即N2(s)=∪1≤i≠j≤KB2[i][j](s),其中邻域块B2[i][j](s)表示的是将类Ci中的一个顶点和类Cj中一个顶点进行交换所形成的可行解的集合,即邻域块的标记:当邻域N1(s)和邻域N2(s)被分成不相关的邻域块后,根据邻域块的下标顺序对邻域块进行逐块地扫描,分别使用两个K×K的0-1状态矩阵M1和M2对N1(s)和N2(s)的邻域块的状态进行标记;当邻域块B1[i][j](s)中有改进解的时候,将对应的元素M1[i][j]置为1;当邻域块B1[i][j](s)已经被扫描并不包括改进解的时候,将对应的元素M1[i][j]置为0;对于领域N2(s)中的邻域块B2[i][j](s)的状态矩阵中的元素M2[i][j]也进行类似操作;同时,在变邻域下降算法的初始化阶段,将状态矩阵M1和M2中的对角元素全部初始化为
0,非对角元素全部初始化为1。
状态矩阵的更新:对于邻域N1(s)和N2(s),在邻域搜索过程中,当其中一个邻域的邻域块中出现改进解时,需同时更新状态矩阵M1和M2中的一些相应元素的值,具体实施规则如下:对B1[i][j](s)进行扫描,先将状态矩阵M1中相应的M1[i][j]置为0,当邻域块B1[i][j](s)中出现改进的解时,将状态矩阵M1和M2中的元素M1[i][t]、M1[t][i]、M2[t][j]和M2[j][t](1≤t≤K)均置为1;当对B2[i][j](s)进行扫描时,状态矩阵M1和M2进行类似的更新。
5.根据权利要求1所述的一种求解无线网络基站切换极小化问题的变邻域搜索方法,其特征在于:步骤3中,基于邻域分解的变邻域下降VND算法的具体步骤为:步骤3-1,输入解存于S1;
步骤3-2,设置状态矩阵M1和M2的初值:将两个状态矩阵中的对角元素初值设为0,非对角元素的初值设为1;
步骤3-3,设置邻域编号θ值为1;
步骤3-4,对当前邻域Nθ中转态值为1的邻域块进行逐个地扫描,一旦遇到一个改进解,则用改进解替代当前解;当一个邻域块被扫描完时,更新状态矩阵;若出现改进解,转到步骤3-3;
步骤3-5,若邻域编号θ的值等于2且出现改进解时,转到步骤3-3;
步骤3-6,邻域编号θ的值增加1,当邻域编号θ的值大于2时,则转到步骤3-7,否则转到步骤3-4;
步骤3-7,变邻域下降算法停止,并输出所得的当前最优解S2。
6.根据权利要求1所述的一种求解无线网络基站切换极小化问题的变邻域搜索方法,其特征在于:步骤4中,将要求1中的步骤3中输出的所得解S2与之前得到的最好解S*进行比较,当解S2的目标函数值,即各个类中的边权重之和,大于解S*的目标函数值时,用解S2替换当前最好解S*;否则,保持当前最优解S*不变,同时将扰动强度k增加Kstep;若扰动强度大于最大扰动强度且未到达截止时间时,重设扰动强度k为Kmin并转到步骤2;若到达截止时间,转到步骤5,并输出最优解S*。