2. 中国联合网络通信有限公司 北京市分公司, 北京 100140
提出了一种改进的针对高维优化问题的自适应多粒子模拟退火(AMSA)算法, 通过多个粒子对整个高维空间进行随机分割和相对独立的局部退火.当每个局部于当前温度下达到稳态后, 随着温度的降低, 粒子依据自身状态和相互之间的关系自适应地减少粒子数目, 以降低复杂度.该算法用于解决通用移动通信系统自动小区规划问题.仿真结果显示, 对比其他用于解决高维优化问题的启发式算法, AMSA算法能在预定的时间内取得更理想的结果.
2. China United Network Communications Corporation Beijing Branch, Beijing 100140, China
An improved adaptive multi-particles simulated annealing (AMSA) was proposed to solve high-dimensional optimization problem. Thinking of multi particles, this new algorithm divides the entire high-dimensional space into several parts randomly as well as operates local annealing independently. Currently, when each local reaches steady state, with temperature decreasing, the particles are self-adaptively reduced for less complexity based on the relationship of the particles and their status. Consequently, AMSA can be used to settle high-dimensionally optimizing (universal mobile telecommunications system) automatic cell planning issue. Simulation shows that compared to other heuristic algorithms, it is good to settle high-dimensionally optimizing issue, and AMSA algorithm can achieve better results within a predetermined time.
模拟退火算法是一种常见的用来求解大规模组合优化问题的启发式随机搜索算法.针对高维优化问题具有规模大、非线性、非凸等复杂特性，同时存在大量局部最优值，王等[1-2]提出了一些改进的模拟退火算法或混合算法，但是处理高维问题时，会出现初始点敏感和局部收敛等问题.学习借鉴群智能算法在解决问题时的多个体同时搜索的特点和考虑到高维优化问题的特殊性，提出了一种自适应多粒子模拟退火(AMSA，adaptive multi-particles simulated annealing)算法，用于解决高维复杂优化问题.该算法主要在以下几个方面进行改进：1) 初始化模块根据问题规模初始化粒子(初始解)的数目；2) 在退火过程中引入了库的概念对粒子的搜索轨迹进行记录；3) 每次退火结束时根据粒子自身的适应度值和相互之间的关系自适应地删减粒子；4) 对粒子周围空间进行搜索时，采用丰富的扰动模型，以适应不同的搜索阶段.仿真测试中，算法用于解决优化维度超过1 800维的通用移动通信系统(UMTS，universal mobile telecommunications system) ACP问题，不仅效率高、优化性能好，而且对初始解具有很强的鲁棒性.
1 AMSA算法1.1 初始化多粒子在群智能算法中，如遗传算法，会有多个父代交叉变异产生子代，如粒子群算法[3]，会有全局最好粒子和局部最好粒子来引导多个粒子进行搜索，这样算法的下一代继承了上一代的优良特性，同时在全局空间中进行搜索.从群智能算法中得到启发，模拟退火算法可以在多个点同时进行退火，各个点的搜索空间相对独立，在保持一定搜索精度的同时又扩大了搜索的范围.
多个粒子较均匀地分布在整个空间中可以更好地进行全局搜索，可以降低初始解对算法结果的影响.产生的初始解需要满足在空间中分布相对分散这个条件，即各个粒子相互之间的欧氏距离需要达到一定的门限，对不符合要求的初始解重新生成.
1.2 子库与主库定义1 子库(sub-archive)：当前温度下粒子搜索轨迹的点的集合.
定义2 主库(archive)：整个问题在退火过程中每个温度下最好粒子的集合.
从各个子库中挑选出最优粒子来更新主库.主库中存储的是到目前为止，整个空间中搜索到的满足约束条件的性能最靠前的a个粒子.
1.3 自适应的粒子变化在搜索的前期，较多的粒子可以把整个空间划分得较细，可以更快地对整个搜索空间进行一个粗略的性能判断，在搜索的中后期需要对特定的区域进行精细的搜索，过多的粒子反而会增加搜索的负担.所以在整个搜索过程中合理地控制粒子数量就显得至关重要.算法主要从以下3个方面对粒子数量进行一个控制.
1) 初始化总粒子数应该要控制在一个合理范围内，因为每个粒子要达到特定的扰动次数，才能完成对其周围空间的粗略搜索，需要保证整体的复杂度在一个可以接受的范围之内.
2) 如果经过多次退火，个别子库中最好粒子的性能一直是劣于其他子库中的粒子，说明该粒子附近的解空间性能普遍较差，则舍弃该粒子.
3) 在下一次搜索之前，用欧氏距离计算个体之间的拥挤度.如果主库中任意两个粒子之间的欧氏距离小于一个特定的门限，则认为两个粒子是位于同一个搜索空间中的，舍去适应度值较差的粒子.
1.4 自适应的扰动模型一般根据扰动的幅度和维度可以将模型大致分为多样性扰动和精确性扰动两大类.针对高维复杂问题，为了达到更好的效果，提出算法中采用将不同的扰动模型结合在一起综合运用.在搜索前期，温度比较高，搜索的范围需要更宽，以较高的概率进行多样性搜索，更容易跳出局部最优；在搜索的后期，粒子数减少，最优解的范围缩小，需要进行更加精确的搜索，以便更快锁定最优粒子.
在搜索的中前期，如果新粒子连续多次没有被接受，该粒子很可能进入了局部最优.为避免情况的恶化，算法的扰动模型应该进行变化，应该选用多样性扰动模型以帮助该粒子跳出局部最优.当新粒子被接受后，扰动模型恢复到正常.
1.5 AMSA算法步骤AMSA算法相对于传统模拟退火算法的改进模块在1.1节至1.4节中已做详细描述. AMSA算法的具体步骤如下.
步骤1 初始化参数：起始温度、终止温度、退火系数和初始粒子.
步骤2 更新参数：粒子数、退火后当前温度、当前温度下扰动的次数M、多样性扰动与精确性扰动比例.
步骤3 选择一个粒子进行扰动，并将该粒子在当前温度下已经扰动的次数i与当前温度下需要扰动的总次数M和多样性扰动的次数M1比较.若0＜i＜M1，则该粒子选择多样性扰动模型进行搜索；若M1＜i＜M，则该粒子选择精确性扰动模型；若i＞M，则该粒子结束扰动.
步骤4 在子库中记录粒子的搜索轨迹，如果新粒子的适应度值优于旧粒子的适应度值，子库接受新粒子并删除旧粒子；否则根据Metropolis准则以一定概率接受适应度值并不好的新粒子，并将新粒子直接放入子库.如果新粒子连续多次没有被接受，则更改扰动模型，加大扰动幅度.
步骤5 判断该粒子在当前温度下扰动次数是否已经达到设置的上限，若是，则该粒子结束扰动，并切换其他粒子进行扰动，若全部粒子扰动结束则跳至步骤6，若扰动未结束则跳至步骤3.
步骤6 在主库中更新各个粒子，并依据1.3节的规则自适应地删除部分粒子.
步骤7 判断退火是否结束，若未结束则回到步骤2，若结束则退出并输出主库中性能最优的粒子.
多目标模拟退火算法在文献[2, 4]中有描述. AMSA算法同样可以运用于解决多目标高维优化问题.
2 算法在ACP问题中的运用UMTS自动扇区规划的主要功能是依据用户输入的工程信息，通过调整天线参数(包括机械下倾角、方位角、电子下倾角、发射功率、天线类型)和开关站，对测量报告(MR，measurement report)数据进行分析和优化，使得这些区域上的栅格的各项指标(接收信号码功率(RSCP，received signal code power)、载干比(Ec/Io)、1st-Nth导频污染(Nth=4th，5th)以及负载均衡指数)满足某种用户设定的要求.同时每次调整参数是会有一定开销的，整个网络的开销需要控制在预算之内.
整个问题的数学描述为
|
(1) |
其中：f(k)表示整个网络的等效性能，k表示一种网络配置方案.栅格集合为l={1，2，…，J}，已激活小区对的集合为P={1，2，…，P}. ωjq表示基于地物类型的权重，ωtrafic表示基于话务量密度的权重.每个优化目标存在一个权重值，表征每个优化目标的重要等级，其中RSCP、Ec/Io、RSCP1st-Nth和负载均衡指数的目标权重值分别为ωRSCP、ωEclo、ω1st-Nth、和ωload.上述目标权重值皆可由用户配置.
函数RjRSCP(k)、EjEclo(k)和θj(k)表示网络配置为k时的RSCP、Ec/Io和1st-Nth导频污染的等效性能，L(k)为基站对中两个基站之间的负载差值(恒为非负).
c(k)表示网络配置为k时的整体经费开销，b表示经费预算，g(k)表示经费的约束条件.
综合以上，这类问题就是指在成本预算和负载均衡约束条件下，小区数目确定的最大化网络性能的问题.
3 仿真与分析3.1 仿真场景仿真是以UMTS现网中的某市的一个区域的数据为基础，该仿真区域中有455个小区数据、1 597 142条MR数据、218类天线信息.数据经过地理平均后在地图区域内的20 m×20 m的栅格共包含205 650个.在优化过程中结果统计的是满足优化目标的栅格数目占总栅格数目的百分比.
可以调整的参数有机械下倾角、电子下倾角、方向角、发射功率.该问题的优化变量达到了1 820维，每个变量都有15~25个离散值可以选择，所以ACP问题属于高维优化问题.
3.2 仿真结果及分析表 1中每个算法仿真了10次，对性能进行了平均.可以看出，多粒子模拟退火算法每次的初始解集合都是不同的，初始性能也各异，但是经过一段时间的退火后性能提升都比较快，初始解各粒子满足一定欧氏距离的算法的最终性能相对于其他算法明显高很多，所以该方法产生的初始解集合具有很强的鲁棒性.
|
表 1 不同初始解的影响 |
图 1的仿真是新提出的算法AMSA与固定粒子数的模拟退火算法.不同粒子数的模拟退火算法的冷却表都是一样的，也都采用了自适应的扰动模型.直观地从性能上观察，AMSA算法优于固定粒子数的模拟退火算法，算法效率更高.
|
图 1 不同粒子数的模拟退火 |
在图 2中对比了不同算法解决ACP问题的结果.参与对比的算法有免疫算法[5](IA，immune algorithm)、基于岛屿的并行粒子群算法[3](IPPso，island based parallel particles warm optimization)、禁忌搜索算法[6](TS，tabu search algorithm).从图 2中可以看出，IA和IPPso算法在搜索中期都陷入了局部最优，不能找到最优解. TS算法因为有禁忌表，可以最大限度地避免算法陷入局部最优，但是相对于AMSA算法整体还是略逊一筹.
|
图 2 不同算法对比 |
图 3和图 4是采用AMSA算法对整个UMTS ACP问题优化前后的栅格的对比Ec/Io和RSCP累积分布曲线图.从两幅图中可以看出，Ec/Io和RSCP的性能都有了明显的提升.
|
图 3 优化前后栅格的Ec/Io累计分布函数曲线 |
|
图 4 优化前后栅格的RSCP累计分布函数曲线 |
为了解决高维优化问题，提出了一种改进的AMSA算法，并将该算法用于解决1 820维的UMTS小区自动规划问题. AMSA算法采用了自适应调整粒子数目的方法以适应不同搜索时期的需要，并采用了自适应的扰动模型帮助算法实现更精确的搜索和更容易跳出局部最优.仿真结果表明，AMSA算法相对于其他优化算法解决高维优化问题更具优势.
| [1] |
王忠贵, 罗亚中. 高维复杂函数的混合模拟退火全局优化策略[J]. 计算机工程与应用, 2004, 40(23): 36–39.
Wang Zhonggui, Luo Yazhong. SA-based hybrid global optimization approach for complex functions with high-dimension[J].Computer Engineering and Application, 2004, 40(23): 36–39. doi: 10.3321/j.issn:1002-8331.2004.23.012 |
| [2] | Bandyopadhyays S, Saha S, Maulik U, et al. A simulated annealing based multi-objective optimization algorithm: AMOSA[J].IEEE Transactions on Evolution, 2008, 7(22): 269–283. |
| [3] | Soliman O S, Mohamed S M, Ramadan E A. A bio-inspired memetic particle swarm optimization algorithm for multi-objective optimization problems[C]//Innovations in Bio-Inspired Computing and Applications (IBICA), 2012 Third International Conference on. HangZhou: IEEE, 2012: 127-132. |
| [4] | Chuai Gang, Zhao Dan, Sun Li. Novel adaptive simulated annealing algorithm for constrained multi-objective optimization[J].China Communication, 2012, 11(9): 68–78. |
| [5] | Gong Maoguo, Jiao Licheng, Ma Wenping. Large-scale optimization using immune algorithm[C]//Proceedings of the First ACM/SIGEVO Summit on Genetic and Evolutionary Computation. New York: ACM, 2009: 149-156. |
| [6] | Jin Jianyong, Crainic T G, Løkketangen A. A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems[J].European Journal of Operational Research, 2012, 222(3): 441–451. doi: 10.1016/j.ejor.2012.05.025 |