微正则退火的双向蚁群优化算法*

周浩理， 李太君， 肖　沙， 徐宁敏

(1.海南大学 信息科学技术学院，海南 海口 570228；2.海南省公安厅 科技通信处，海南 海口 570228)

微正则退火的双向蚁群优化算法*

周浩理1， 李太君1， 肖沙1， 徐宁敏2

(1.海南大学 信息科学技术学院，海南 海口 570228；2.海南省公安厅 科技通信处，海南 海口 570228)

摘要:双向蚁群搜索算法可以提高算法的搜索速度，并可以选择搜索的空间；微正则退火算法具有准确度高、速度快等优点，可以实现全局路径优化搜索。结合两种算法的优点，提出了双向蚁群微正则退火算法，用来求解海量数据网络下的旅行商问题。通过实验表明：双向蚁群微正则退火算法不容易陷入局部最优解，且在寻找全局最优解和运行效率上都比其他算法更有优势。

关键词：双向蚁群算法； 微正则退火算法； 大规模； 全局最优解

0引言

蚁群算法作为群集智能算法的一种，在求解组合优化问题中有重要的应用，但其容易陷入局部最优而使算法停滞，收敛速度较慢使算法执行时间过长。学者们提出了多种改进策略以改进蚁群算法，王沛栋在改进蚁群算法的基础上，解决了智能体路径规划、车辆路由、多智能体的编队控制、旅行售货员等问题[1]；HeYueshun等人基于移动代理和蚁群算法，对无线传感器网络的路由算法进行了改进，具有良好的实际应用效果[2]；段海滨等人提出了一种改进的蚁群算法用于求解连续空间优化问题[3]；WangJ等人从涵盖人、车、物等影响因子在内的实际情况出发，定义路网分割算法，改进了蚁群算法解决实际问题的能力[4]；另外，考虑蚁群算法和其他算法的结合，也提出了多种算法，申利民等人提出一种基于遗传蚁群融合算法的测试用例最小化方法，降低了回归测试成本和缩减了测试用例规模[5]，王宪等人提出了一种基于蚁群粒子群融合算法，解决了复杂环境下移动机器人路径规划问题[6]，李敬花提出基于遗传蚁群融合算法，提高了多项目资源能力平衡优化的效率[7]。

本文考虑到双向蚁群快速求解局部最优和微正则退火高效全局寻优的特性，提出了求解大规模旅行商问题的双向蚁群微正则退火优化算法。

1旅行商问题求解模型

旅行商问题是近代组合优化领域的一个典型难题，现实生活中的网络通信问题、交通调度问题、电路板钻孔问题和邮路问题等都可以转化为旅行商问题，这些问题本身就是旅行商问题或者可以直接转化为旅行商问题的原型。旅行商问题一直是测试组合优化新算法的标准问题。

旅行商问题就是指一个商人从自己所在的城市出发，希望找到一条最短路径，能够经过给定的城市集合中的所有城市，最后返回家乡，并且每个城市都被访问有且仅有一次。旅行商问题用数学语言可描述如下：设G=(V,E)为一个城市图，V={V1,V2,…,Vn}为n个城市的集合，E={eij|Vi,Vj∈V}为V中元素两两连线的集合，旅行商问题的目的是从中找出长度最短的回路，即哈密顿回路，也就是找出对V中n个城市访问有且仅有一次的最短封闭曲线。

2蚁群算法

2.1蚁群算法思想

20世纪90年代初，意大利学者DorigoM等人受到大自然中蚂蚁觅食行为的启发，提出了蚁群算法，仿生蚂蚁在没有事先告诉食物在什么地方的前提下开始寻找食物。当一只蚂蚁找到食物以后，它会向周围释放信息素(pheromone)，信息素会随着时间的推移而逐渐消失，路径的远近由信息素浓度的大小来表征，其他蚂蚁会被信息素吸引过来，从而会有更多蚂蚁找到食物。在这个过程中，会有特殊的蚂蚁不会像其他蚂蚁总是重复同一条路，而会另外开辟一条道路，如果这条路比其他路更短，那么，随着时间的推移会慢慢地吸引更多的蚂蚁走这条更短的路。最后，随着时间的推移，可能会有一条最短的路径被大部分蚂蚁重复着[8]。

2.2蚂蚁系统

蚂蚁系统(AS)是由LiuBo,QingZheng和WangRui最先提出的蚁群优化(ACO)算法形式[9]。按照信息素轨迹更新方式不同，给出了三种AS算法，分别称为蚂蚁圈(ant-cycle)、蚂蚁数量(ant-quantity)、蚂蚁密度(ant-density)。

3双向蚁群微正则退火算法

3.1小生境双向蚁群搜索策略

从旅行商的小生境性质出发，可以限定蚂蚁在每个城市可以“看到”的下一个城市的数目，或者可以对蚂蚁的每次移动的范围进行限定，能够缩小搜索范围、提出劣质解，从而可以对蚁群的搜索效率进行提高。在算法中为每个城市建一个数组 ，保存window个距离最近的城市，window值随迭代次数动态调整。

旅行商问题的解是哈密顿回路，采用双向蚁群策略高效搜索：将蚂蚁(分泌相同的信息素)成对分配在各个城市，成对的蚂蚁共用一个禁忌表，分头搜索直至访问完所有城市而相遇。双向蚁群搜索策略，使得算法搜索空间约减小50 %左右，进一步提高了搜索效率。

(1)

在自然环境中，可挥发物质的浓度越大，挥发系数也越大，因此,可以根据路径上信息素的多少来调整挥发系数的大小，使其符合自然规律，可以避免信息素堆积的现象，增强后期算法的启发性，所有最短路径的信息素更新方式

(2)

式中E(i,j)包含在最短路径中，Lbest为最短路径长度。

3.2微正则退火算法

1983年，CreutzM基于微正则蒙特卡罗仿真方法提出了微正则退火概念。在此概念中，令一种能量载体“妖”在系统中不断移动，实现能量的交换[10]。在一定的时段内，系统表现为能量守恒状态，但是能量载体在算法模型中不断移动会使系统的能量出现波动，并使热系统的能量发生变化，从而脱离亚稳态模式。应用于旅行商问题的微正则退火算法，初始解空间为双向蚁群搜索的结果S，能量E为目标函数值，巡游路径长度L。

3.3算法的实现过程

在得到最优路径的过程中，蚁群算法有时会陷入局部最优解，表现为陷入停滞状态。因此，关键问题就是如何避免算法陷入局部最优，得到全局最优解。许智宏等人提出对蚁群算法和模拟退火算法的优点进行结合，用该算法求解旅行商问题，首先使用蚁群算法得到较优的局部解，而后利用模拟退火算法跳出局部最优的情况，从而可以得到最优解[11]。但是模拟退火算法有一个缺点，其需要生成随机数，再按照Metropolis准则拒绝或者接受新状态，而微正则退火算法摆脱了这一限制，其采用了确定性的状态转移机制，不需要用随机数来进行判断拒绝或接受新状态，故在大规模问题上要比模拟退火算法更有时间效率[12]。因此，本文提出将微正则退火算法与蚁群算法结合，继而解决旅行商的局部最优问题。

双向蚁群微正则退火算法的具体步骤如下：

1)为n个城市分别建立数组cityWin[window]，置迭代次数N=0，初始参数Nmax。

2)将m对蚂蚁随机置于n个城市中，所在城市编号加入相应禁忌表tabu[k]。

3)将m对蚂蚁循环直至所有蚂蚁对完成巡游。

①最短路径长度Lmin=0，tabu[k]=0。

②蚂蚁对K(假设第K对蚂蚁在城市i)，巡游路径长度L=0，循环直至禁忌表满；

a.第一只蚂蚁从cityWin[window]和allowedk={C-tabu[k]}的交集中按式(1)选择j为下一个旅行城市。若交集为空，则只在allowedk={C-tabu[k]}中选择。更新路径长度L+=L(i,j)，若L大于Lmin，停止搜索；否则，更新路径序列，并将城市j加入禁忌表tabu[k]继续搜索。

b.第二只蚂蚁从cityWin[window]和allowedk={C-tabu[k]-j}的交集中按公式(1)选择jj为下一个旅行城市。若交集为空，则只在allowedk={C-tabu[k]}中选择。更新路径长度L+=L(i,jj)，若L大于Lmin，停止搜索；否则，更新路径序列，并将城市jj加入禁忌表tabu[k]继续搜索。

③若L

4)更新最短路径上的信息素，并用min—max准则限定信息素含量。

5)N=N+1，若N=Nmax或者出现Nmax×5次最短路径结果相同(算法停滞)，停止迭代；否则,继续。

6)将小生境双向蚁群搜索的结果S作为退火的解空间。初始化循环变量i=1，j=1。

7)初始化系统能量E0，并释放一个在状态空间中行走的“妖”，令其能量初值为ED=0。

8)循环，直到i>N即遍历完S中的所有结果。

①设定“妖”的能量上界Emax，即Emax=Emax·p(p为能量下降参数)，设定三个初始最优状态t1，t2，t3。

②重复如下步骤，直到j>jmax,即执行完2-opt的所有可能变换。

a.“妖”在状态空间中移动一步(产生新解)，计算系统相邻状态的差值ΔE。

b.当ED过大，实行能量缩减ED=ED×(1-p)。如果ED>ΔE，则接受新的系统状态，更新最优状态数组，并检查妖的能量是否已越界；否则拒绝新解，当ED过小，实行奖励ED=ED(1+q)。

c.如果连续若干次拒绝新解，将状态回溯，重新移动。

9)输出最优结果。

4算法仿真

本文采用Matlab仿真上述求解旅行商问题的双向蚁群微正则退火算法，实验结果与分析如下：

首先利用Matlab仿真随机生成30个点代表目的旅行城市，然后计算各座城市的小生境窗口并利用双向蚁群算法寻找最优路径，如果寻优过程出现停滞，就以蚁群算法的结果作为微正则退火算法的初始解空间，继而退火寻找最优结果路径，避免系统陷入局部最优。图1为使用双向蚁群微正则退火算法得到的30座城市的旅行商问题优化的结果图，图示的结果最短路径：Shortest_Route=(1，3，5，7，10，13，14，15，17，23，28，21，25，27，22，24，30，29，26，12，11，16，19，20，18，8，6，9，4，2)，最短路径长度Shortest_Length=457.729 1。由图可知，该算法得到的是最优的路线图。

图1　30座城市旅行商问题优化结果Fig 1　Optimization results of traveling salesman problem of 30 cities

图2表示使用双向蚁群微正则退火算法的200次迭代求解旅行商问题的平均距离和最短距离变化图。由图可知,本算法的效率很高，可以快速得到最短距离解，并且其平均距离一直是在变化的，表明本算法一直没有陷入局部最优解的情况。

算法收敛时间比较如图3所示。本文对算法的执行效率与基本蚁群算法、基于模拟退火的蚁群算法进行了比较。本文采用执行时间(CPU时间)来对算法的执行效率进行评测，图3显示各算法执行时间的比较结果。由图可知，基本蚁群算法的执行时间最长，其次是基于模拟退火的蚁群算法，而本文提出的算法执行时间明显低于这两种算法，由此说明本算法能快速有效地从局部优化解中摆脱，从而获得全局优化解，收敛性高。

图3　算法收敛时间比较Fig 3　Comparison of algorithm convergence time

5结束语

本文采用双向蚁群微正则退火算法求解旅行商问题，基于小生境的双向蚁群大大缩减了搜索时间，微正则退火算法具有强大的全局寻优能力。本文在Matlab平台下进行仿真，得到本文提出的算法相比于其他求解旅行商问题的方法，在运行效率和寻找全局最优解等方面都具有较大的优势，具有良好的实用性。

参考文献:

[1]王沛栋.改进蚁群算法及在路径规划问题的应用研究[D].青岛：中国海洋大学，2012.

[2]HeYueshun,DuPing.Mobileagentroutingalgorithmbasedonimprovedantcolonyalgorithm[J].InternationalFrequencySensorAssociation,2013,22(11)：15-21.

[3]段海滨，马冠军，王道波,等.一种求解连续空间优化问题的改进蚁群算法[J].系统仿真学报，2007，19(5)：974-977.

[4]WangJian,WangYanyan,LiHongyun.Improvedantcolonyalgorithmforlogisticsvehicleroutingproblemwithtimewindow[M].Berlin,Heidelberg:Springer,2012:41-48.

[5]申利民，高洁.基于遗传蚁群融合算法的测试用例最小化研究[J].计算机工程，2012，38(16)：57-64.

[6]王宪，王伟，宋书林,等.基于蚁群粒子群融合的机器人路径规划算法[J].计算机系统应用，2011，20(9)：98-102.

[7]李敬花.遗传蚁群融合算法求解多项目资源能力平衡问题[J].计算机集成制造系统，2010，16(3)：643-649.

[8]MarcoDorigo，LucaMariaGambardella．Antcoloniesforthetra-velingsalesmanproblem[J]．BioSystems，1996，43：73-81．

[9]LiuBo，QingZheng，WangRui，etal.Ahybridheuristicantcolonysystemforcoordinatedmulti-targetassignment[J].InformationTechnologyJournal，2009,8(2)：156-164.

[10]CreutzM.MicrocanonicalMonteCarlosimulation[J].PhysicalReviewLetters,1983,50(19):1411-1414.

[11] 许智宏，宋勃，郭艳艳.模拟退火与蚁群混合并行算法解旅行商问题[J].河北工业大学学报，2010，39(2)：48-51.

[12] 徐畅.大规模路网下基于蚁群微正则退火算法的路径优化方法研究[D].长春：吉林大学，2013.

Optimizationforbidirectionalantcolonyalgorithmbasedonmicrocanonicalannealing*

ZHOUHao-li1，LITai-jun1，XIAOSha1，XUNing-min2

(1.SchoolofInformationScienceandTechnology,Hai’nanUniversity,Haikou570228,China;2.ScienceandTechnologyCommunicationSection,Hai’nanPublicSecurityDepartment,Haikou570228,China)

Abstract:Bidirectional ant colony search algorithm can improve search speed and select search space;microcanonical annealing algorithm can realize global path optimization search with high speed and accuracy.Combine advantages of the two algorithms and propose bi-ACO microcanonical annealing algorithm for solving traveling salesman problem in massive data network.Experiments show that bi-ACO microcanonical annealing algorithm is not easy to fall into local optimal solution,and it has more advantages in searching for globally optimal solution and operating efficiency than other algorithms.

Key words:bidirectional ant colony algorithm; microcanonical annealing algorithm; large-scale; globally optimal solution

DOI:10.13873/J.1000—9787(2016)04—0127—03

收稿日期：2015—07—09

*基金项目：海南省社会发展科技专项项目(SF201455)； 海南大学2015年研究生实践创新项目

中图分类号：TP 301.6

文献标识码：A

文章编号：1000—9787(2016)04—0127—03

作者简介:

周浩理(1989-),男,湖南湘乡人,硕士研究生，主要研究方向为图像信息处理与检索。