2007年第2期空间电子技术收稿日期：2006-04-03；收修改稿日期：2006-04-30粒子群算法和蚁群算法的结合及其在组合优化中的应用张长春苏昕易克初（西安电子科技大学综合业务网国家重点实验室，西安710071）摘要文章首次提出了一种用于求解组合优化问题的PAAA 算法。
该算法有效地结合了粒子群算法和蚁群算法的优点，先利用粒子群算法的随机性、快速性、全局性得到初始信息素分布（即粗搜索），再利用蚁群算法的并行性、正反馈性、求解精度高等优点求精确解（即细搜索）。
将文中提出的算法用于经典TSP 问题的求解，仿真结果表明PAAA 算法兼有两种算法的优点，同时抛弃了各自的缺点。
该算法在时间效率上优于蚁群算法，在求精效率上优于粒子群算法，是综合了两种算法长处的一种新的启发式算法，达到时间性能和优化性能上的双赢，获得了非常好的效果。
主题词蚁群算法粒子群算法旅行商问题PAAA0引言近年来对生物启发式计算（Bio-inspired Computing ）的研究，越来越引起众多学者的关注和兴趣，产生了神经网络、遗传算法、模拟退火、粒子群算法、蚁群算法等许多用于解决复杂优化问题的新方法。
然而，面对各种问题的特殊性和复杂性，每种算法都表现出了自身的优势和缺陷，都存在时间性能和优化性能不能兼得的矛盾。
粒子群优化（Particie Swarm Optimization ，PSO ）算法[1，2]是由Eberhart 和Kennedy 于1995年提出的一种全局优化算法，该算法源于对鸟群觅食行为的模拟。
它的优势在于：（1）算法简洁，可调参数少，易于实现；（2）随机初始化种群，具有较强的全局搜索能力，类似于遗传算法；（3）利用评价函数衡量个体的优劣程度，搜索速度快；（4）具有较强的可扩展性。
其缺点是：不能充分利用系统中的反馈信息，求解组合优化问题的能力不强。
蚁群算法[3，4]（Ant Coiony Optimization ，ACO ）是由意大利学者M.Dorigo ，V.Maniezzo 和A.Coiorni 于20世纪90年代初提出的一种新型的智能优化算法，已经被应用到TSP 问题[5，6]、二次分配问题、工件调度问题、图着色问题等许多经典组合优化问题中，取得了很好的效果。
它的优点是：（1）采用一种正反馈机制，通过信息素的不断更新，达到最终收敛于最优路径上的目的；（2）是一种分布式的优化方法，易于并行实现；（3）是一种全局优化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（4）适合于求解离散优化问题；（5）鲁棒性强。
但由于在算法的初始阶段信息素匮乏，所以求解速度较慢。
文章将粒子群算法和蚁群算法有机地结合，提出了PAAA 算法。
它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解，汲取各自的优势，以达空间电子技术SPACE ELECTRONIC TECHNOLOGY !"2007年第2期到优势互补。
最后，将该算法用于经典旅行商（TSP ）问题的求解，获得了很好的效果。
1旅行商（TSP ）问题TSP（Traveling Salesman Problem ）问题[7]属于NP 完全问题，如用穷举搜索算法，则需要考虑所有可能的情况，找出所有的路径，再对其进行比较，以找到最佳的路径。
这种方法随着城市数I 的上升，算法时间随I 按指数规律增长，即存在“指数爆炸”问题。
TSP 问题描述十分简单，即寻找一条最短的遍历N 个城市的路径，其数学描述为：设有N 个城市的集合c ={c 1，c 2，…，c N }，每两个城市之间的距离为i （c 1，c 2） R +，其中c i ，c j c（1!i ，j !N ），求使目标函数：T i =N -1i =1Z i（c H （i ），c H （i +1））+i （c H（N ），c H （1））（1）达到最小的城市序列{CH （1），C H （2），…，C H （N ）}，其中H （1），H （2），…，H （N ）是1，2，3，……，N 的全排列。
2蚁群算法描述2.1蚁群算法的忧化思想蚂蚁在觅食的途中会留下一种信息素，蚂蚁利用信息素与其他蚂蚁交流，找到较短路径；经过某地的蚂蚁越多，信息素的强度也就越大。
蚂蚁择路偏向选择信息素较强的方向，又因为通过较短路径往返于食物和蚁穴之间的蚂蚁能以更短的时间经过这条路径上的点，所以这些点上的信息素就会因蚂蚁经过的次数增多而增多，这样就会有更多的蚂蚁选择此路径，这条路径上的信息素就会越来越强，选择此路径的蚂蚁也越来越多，直到最后，几乎所有蚂蚁都选择这条最短的路。
这是一种正反馈机制。
2.2蚁群忧化原理分析假如路径（i ，j ）在I 时刻信息素强度为 ij ，蚂蚁k 在路径（i ，j ）上留下的信息素强度为A k ij ，信息素的挥发系数为 ，则该路径上的信息素强度按下式更新：ij （I +1）=（1- ）・ ij （I ）+"A k ij （I ）（2）设L k 为第k 只蚂蚁在本次周游中所走的路径长度，则A k ij （I ）=O L k ，O 为常数；设1ij =1i ij 为启发式因子，i ij 为路径（i ，j ）的长度，启发式因子和信息素强度的相对重要程度分别为O 、B ，设U 为蚂蚁下一步运动的候选集，则蚂蚁k 在I 时刻的转移概率为：p k ij （I ）= ij （I []）O 1ij []B "l U ij （I []）O 1ij []B j U 0其他\<\L（3）2.3MMAS 算法对基本蚁群算法进行改进得到的算法有许多种，其中最大-最小蚂蚁系统（MMAS ）是到目前为止解决TSP 、OAP 等问题最好的ACO 算法。
它直接来源于AS 算法，主要做了如下改进： 每次迭代结束后只有最优解路径上的信息素被更新，更好地利用了历史信息； 将各条路径的信息素强度限制在[ min ， max ]，有效地避免了算法过早的收敛及不扩散； 各路径的信息素初始值设为 max ，有利于算法发现更好的解。
张长春等：粒子群算法和蚁群算法的结合及其在组合忧化中的应用!!!"2007年第2期空间电子技术3粒子群优化算法3.l基本粒子群忧化算法描述在某一空间中初始化一群随机粒子，粒子的位置代表问题可能的解，每个粒子都在以一定的速度飞行，粒子群通过多次飞行，即迭代，逐步逼近最优位置，从而得到问题的最优解。
在每一次迭代中，粒子根据两个极值来更新自己：一个是单个粒子找到的最优解，即个体极值；另一个是整个粒子群找到的最优解，即全局极值。
粒子根据上述两个极值，按照下面两个公式更新自己的速度和位置：V=!!V+c1!rand（）!（pbest-X）+c2!rand（）!（gbest-X）（4）X=X+V（5）其中，V=[1l，12，…，1d]是粒子的速度，X=[x l，x2，…，x d]是粒子的当前位置，d是解空间的维数。
pbest 是个体极值。
gbes t是全局极值。
rand（）是（0，l）之间的随机数。
c l，c2被称为学习因子，用于调整粒子更新的步长，!是加权系数。
粒子通过不断的学习更新，粒子群逐渐靠近最优解所在位置，最终得到的gbest就是算法找到的全局最优解。
3.2对基本PSO的改造PSO算法成功地应用于连续优化问题，但如果引入交换子和交换序[8]的概念，对基本的PSO算法进行改造，它也可以对TSP问题进行求解。
改造后，速度更新公式为：V*id=V id""（P id-X id）"#（P gd-X id）（6）其中"、#为随机数，"（P id-X id）表示基本交换序（P id-X id）中的交换子以概率"保留；同理，#（P gd-X id）表示基本交换序（P gd-X id）中的交换子以概率#保留。
"为两个交换序的合并因子。
4粒子群算法和蚁群算法的结合4.l PAAA（Particle Algorithm-Ant Algorithm）算法原理分析虽然粒子群算法更适合于求解连续优化问题[2]，在求解组合优化问题上显得逊色了一些，但是由于初始粒子的随机分布，将其用于求解组合优化问题时，该算法仍具有较强的全局搜索能力和较快的求解速度；蚁群算法在求解组合优化问题时优于粒子群优化算法，但由于信息素的初始分布为均匀分布（对于MMAS而言，强度均为$max），使得蚁群算法在算法的早期具有盲目性，不能很快地收敛。
文章首次提出的PAAA算法就综合了这两种算法的优势，其基本思想是：在PAAA算法的第一阶段，采用改造的粒子群优化算法，充分利用其随机性、快速性、全局性，经过一定的迭代次数（如20代）得到问题的次优解（粗搜索），利用问题的次优解调整蚁群算法中的信息素的初始分布；在算法的第二阶段，PAAA利用第一阶段得到的信息素的分布，充分利用蚁群算法的并行性、正反馈性、求解精度高等优点，从而完成整个问题的求解（细搜索）。
粒子群算法和蚁群算法相结合，汲取了两种算法的优点，克服了各自的缺点，优势互补，在时间效率上优于蚁群算法，在求精效率上优于粒子群算法，是综合了两种算法长处的一种新的启发式算法。
它与MMAS算法的不同之处在于：MMAS算法把各路径的信息素初值设为最大值$max，而在PAAA算法中，首先通过粒子群算法得到一定的路径信息素分布，然后在蚁群算法中将信息素的初值设为：$S=$C+$P（7）其中，$C为根据具体问题而规定的一个信息素常数，相当于MMAS算法中的$min，而$P就是由粒2007年第2期子群算法得到的信息素值。
图l 表示了PAAA 算法的构成方法。
图l PAAA 算法的构成方法4.2仿直试验以TSP 的经典问题eil5l 、st70和eil76为例，文中采用MATLAB 对所提算法的有效性进行验证。
首先，粒子群算法进行20次迭代，得到问题的次优解，然后利用次优解的路径长度，根据式（7）得到蚁群算法中的初始信息素分布；在蚁群算法中，!=0.02，蚂蚁个数等于城市个数，"=l.0，#=5.0，$min =0.000l 。
表l 显示了PAAA 算法和基本MMAS 算法在求解能力和时间效率上的对比情况。
表!仿真试验结果对比从仿真结果可以看出，PAAA 算法中的MMAS 的进化代数明显要比基本MMAS 算法少，这是因为经过粒子群算法后，信息素的初始分布得到了改善，避免了基本MMAS 算法初期由于信息素均匀分布而造成的搜索的盲目性，这样有利于蚁群算法对更精确解的搜索。
图2形象地表示了该算法搜索到的最优路径的情况。
图2PAAA 算法找到的最短路径5结论从对文中算法的分析以及仿真结果可以看出，该算法在时间性能和优化性能上都取得了非常好的效果，是一种切实可行的算法。