基于自适应模拟退火的改进混合粒子群算法

杨文光，严 哲，隋丽丽

(华北科技学院基础部，北京东燕郊 101601)

0 引言

旅行商问题(TSP)是一个多局部最优的复杂NP难问题，即对于n个城市，要寻找到走遍每个城市的最短闭合路径，并且每个城市只能经过一次，随着城市数n的增大，问题的计算复杂度和时空复杂度呈指数倍增长。采用传统的动态规划技术，我们可以在O(n22n)［1］时间内解决问题，但是算法的效率太低计算时间难以承受。随着计算智能算法的大量出现，借助巧妙的智能算法和计算机的快速迭代计算，TSP问题的求解变得相对容易，现如今求解TSP问题的方法很多，主要包括遗传算法、蜂群算法、贪心法、模拟退火法、粒子群法、蚁群算法等［2－5］。

在伴有多局部极值的求解问题上，全局收敛的模拟退火法［2－3］(Simulated Annealing，SA)无疑是这类问题的有效选择。模拟退火算法最早由Metropolis等提出，其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性，逐渐发展成一种迭代自适应启发式概率性搜索算法，使其具有更好的收敛性。粒子群算法(Particle Swarm Optimization，PSO)［4］是由 Eberhart和Kennedy于1995年提出的一种群体智能进化算法，该算法通过比较新粒子的适应度值、个体极值与群体极值的适应度值来更新个体极值和群体极值，PSO算法的概念简单，易于实现，调整参数少，正在受到越来越广泛的关注和应用。

本文拟利用粒子群算法的全局寻优能力，并结合模拟退火算法加以改进，建立具有自适应性的采用蕴含交叉和变异的混合粒子群算法［5］。在具体寻优过程中，本文设计的混合粒子群算法依靠自适应寻优策略既可以跳出局部极值，又能兼顾到局部精细搜索。最后进行旅行商问题(TSP)优化求解实验，验证了算法的有效性。

1 模拟退火

模拟退火法通过温升温降来控制算法的搜索过程。其算法实现的循环过程基本为:产生新解→计算适应度值→是否满足条件，按一定速率进行降温到既定值，最终寻找到近似最优值。其主要参数和迭代准则为:

1)主要控制参数有降温速率q，初始温度T0，结束温度Tend。

2)Metropolis准则:设f(X)为模拟退火的评价函数，f(Xi)为第i次迭代后的评价函数，令df=f(Xi)－f(Xi)，则对 X 接受概率为［4］:

按概率P来选择新个体。

该算法有如下特点:(1)以一定概率结束恶化解;(2)引进算法控制参数;(3)使用适应度值进行搜索;(4)搜索区域复杂。

2 混合粒子群算法

在混合粒子群算法中，粒子总数为N，每个粒子的空间位置为X，利用个体极值、全局极值和本身信息，指导下一步粒子状态。标准粒子群算法的更新公式为［5］:

其中，xk为第k步粒子的状态，vk为粒子更新的速度，pbestk为第k步粒子本身所找到的最好解的位置，gbestk为第k步整个种群目前找到的最好解的位置。作为混合粒子群算法，可将更新公式理解为:covk为粒子变异，c1(pbestk－xk)为个体现在状态与个体极值交叉操作，c2(gbestk－xk)为个体现在状态与全局极值交叉操作。

在TSP问题中，交叉算子为:首先选择两个交叉位置，个体现值分别与个体极值和全局极值交叉。比如，交叉的位置为2和7，操作如下:

个体现值与全局极值交叉一样。对于新的个体，采用保留优秀个体策略。

变异操作:随机选取个体变异位置p1和p2，然后交换两位置，设p1=3，p2=5，交换如下:

同样，也采用保留优秀个体策略。

3 自适应寻优策略

为了使算法跳出局部极值，使算法更加稳定，在本算法连续△k次降温，一直保持 gbestk－1－gbestk＜a(gbestk为第k次降温的全局最优适应度值，a为某一设定正数)，将此作为陷入局部极值的判定依据［6］。当△k≥K(K为设定的某正整数)时，采用自适应寻优，获得新个体;否则，继续按原来算法进行降温。

自适应搜索阶段:

新点X在取值空间A中最佳点pbest邻域按正态分布随机扰动产生［6］:

XU和XL分别为X的上下限;为了保证X1∈［XL，XU］，引入以下方法进行修正:

其中，mod(*)为取余运算;X=roundn(X1，0);将X中重复的元素保留一个，再将缺失的元素补充进去，最终得到X。其中“o”为Hadamard乘积，b为搜索半径调节半径，I为自适应因子，y为单位向量。

Tk为当前第 k次迭代的温度，mk为(0，5)的均匀随机分布。当Tk≥1时，搜索在一个较大的半径内进行，保证算法的全局搜索能力;当Tk＜1，相对搜索半径很小，使其在局部进行更精细的搜索，以提高精度。

I决定该算法以一定概率进行自适应寻优，αi取(0，1)均匀随机数，β自适应概率。

Gaussian是标准正态分布随机向量，‖＊‖为范数。

4 融入自适应模拟退火与混合粒子群的算法

利用模拟退火法的全局收敛特性，克服混合粒子群算法易于陷入局部最优值的缺陷，尤其在高维多峰值的情况下，模拟退火与粒子群的混合算法易造成算法不稳定，因此引入自适应寻优策略，在每降温一次的情况下，进行一次局部收敛性判断。

模拟退火算法是50年代初发展起来的一种随机性组合优化方法。它模拟高温金属降温的热力学过程，并广泛应用于组合优化问题。模拟退火在进行优化时先确定初始温度，随机选择一个初始状态并考察该状态的目标函数值;对当前状态附加一小扰动，并计算新状态的目标函数值;以概率1接受较好点，以某种概率Pr接受较差点作为当前点，直到系统冷却。模拟退火方法在初始温度足够高、温度下降足够慢的条件下，能以概率1收敛到全局最优值，由于它以某种概率接受较差点，从而具有跳出局部最优解的能力。其算法流程如下:

图1 算法流程

5 实验仿真

实验数据取51个城市，即n=51，初始温度T0=500，结束温度Tend=0.1，降温速率q=0.95;粒子个数individual=80，粒子群进化最大代数nMax=50。本实验运用MATLAB进行。将混合粒子群算法［10］和本文算法各随机运行15次，进行算法比较。图3为本文算法求解的最优路径，图4为本文算法迭代寻优过程。

图2 城市分布

图3 最优路径

图4 寻优过程

在城市规模达到51个的情况下，本文算法仅仅运行了100 s，降温次数在60次左右即达到稳定状态，表现出了强大的搜索能力。为了说明本文算法的有效性，表1给出了混合粒子群算法与本文算法的对比情况。从表1可以看到，本文设计的算法在最优路径长度和平均路径长度都要优于混合粒子群算法。

表1 算法结果比较

6 结论

本文针对混合粒子群算法在求解TSP问题中存在的缺陷，将模拟退火法引入到混合粒子群中，达到了改善优化求解和避免陷入局部最优的目的。首先将自适应寻优策略应用于模拟退火的每次降温，便于跳出局部最优。而在进行完粒子群既定迭代次数后，自适应寻优策略将会判断所得最优极值是否为局部极值，最后在一定概率下进行自适应寻优。这样既避免算法陷入局部极值，也可让算法较精确地进行局部搜索。通过仿真实验验证，表明该算法具有良好的全局收敛性能，对于TSP问题的实际优化求解具有很好的借鉴意义。

［1］ HELD M，KARP R M.A Dynamic Programming Approach to Sequencing Problems［J］.Journal of the Society for Industrial and Applied Mathematics，1962，10(1):196 －210.

［2］ 冯剑，岳琪.模拟退火算法求解TSP问题［J］.森林工程，2008，24(01):94 －96.

［3］ 杨艳霞.一种基于模拟退火操作的混合差分进化算法［J］.智能系统学报，2014，9(1):1－6.

［4］ 张建航，李国.模拟退火算法及其在求解TSP中的应用［J］. 现代电子技术，2006(22):157－158.

［5］ 高尚，韩斌，等.求解旅行商问题的混合粒子群优化算法［J］. 控制与决策，2004，19(11):1286 －1289

［6］ 孙士平，吴建军.直接搜索模拟退火法的自适应改进［J］.计算机工程与应用，2014，

［7］ 冯玉荣，朱均燕.模拟退火法算法收敛性研究［J］.福建电脑，2006(12):46－47.

［8］ 高海昌，冯博琴，朱利.智能优化算法求解TSP问题［J］.控制与决策，2006，21(3):241－247，252.

［9］ 王凌.智能算法及其应用［M］.北京:清华大学出版社.2001.

［10］ 史峰，王辉，等.MATLAB智能算法30案列分析［M］.北京:北京航天航空大学出版社，2011.