一种求解TSP问题的改进遗传蚁群算法

２０１２年第４期　文章编号：１００９—２５５２（２０１２）０４—０１４０—０２　中图分类号：ＴＰ３０１．６　文献标识码：Ａ　改进的蚁群算法及其在ＴＳＰ问题中的应用　叶婷婷　，孙合明　，谢　伟　（１．河海大学理学院，南京２１１１００；２．北京航空航天大学计算机学院，北京１００１９１）　摘要：针对蚁群算法容易陷入局部最优解的缺点，提出了一种改进的蚁群算法。该算法通过　禁忌当前取得的最优路径，有选择地更新信息素，而后重新搜索，有效提高了基本蚁群算法的　寻优能力。文中将改进后的蚁群算法应用于ＴＳＰ问题，通过对典型的Ｅｉｌ５１．ｔｓｐ进行测试，证明　了改进后算法的可行性有和效性。　关键词：蚁群算法；最优路径；ＴＳＰ　Ｉｍｐｒｏｖｅｄ　ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　ＴＳＰ　ＹＥ　Ｔｉｎｇ．ｔｉｎｇ　．ＳＵＮ　Ｈｅ．ｍｉｎｇ　。ＸＩＥ　Ｗｅｉ　（１．ＣｏＨｅｇｅ　ｏｆＳｃｉｅｎｃｅ，Ｈｏｈａｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１１１００，Ｃｈｉｎａ；２．Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｅｉｊｉｎｇ　Ａｅｒｏｎａｕｔｉｃｓ　ａｎｄ　Ａｓｔｒｏｎａｕｔｉｃｓ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１００１９１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａｓ　ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｉｓ　ｅａｓｙ　ｔｏ　ｆａｌｌ　ｉｎｔｏ　ｔｈｅ　ｌｏｃａｌ　ｏｐｔｉｍａｌ，ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｔａｂｏｏｓ　ｔｈｅ　ｏｐｔｉｍａｌ　ｐａｔｈ，ｕｐｄａｔｅｓ　ｐｈｅｒｏｍｏｎｅ　ｂｙ　ｃｈｏｉｃｅ，ａｎｄ　ｔｈｅｎ　ｓｅａｒｃｈｅｓ　ａｇａｉｎ．Ｔｈｉｓ　ｐａｐｅｒ　ｓｕｃｃｅｓｓｆｕｌｌｙ　ｓｏｌｖｅｓ　ＥｉｌＳ　１．ｔｓｐ　ｐｒｏｂｌｅｍ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｆｅａｓｉｂｌｅ　ａｎｄ　ｅｆｆｅｃｔｉｖｅ．　Ｋｅｙ　ｗｏｒｄｓ：ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｏｐｔｉｍａｌ　ｐａｔｈ；ｔｒａｖｅｌｉｎｇ　ｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ　０　引言　蚁群优化算法（ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ，简称　ＡＣＯ）是二十世纪九十年代由意大利学者Ｍａｒｃｏ　Ｄｏｒｉｇｏ等人在蚂蚁觅食行为的启发下提出的一种元　启发式算法，主要针对解决离散的组合优化问。蚁　群算法具有鲁棒性，正反馈性，分布式计算等特点，　自提出以来受到了广泛的认可。目前，蚁群算法已　成为组合优化领域最具潜力的算法之一，也成为了　众多学者研究的焦点。但是基本的蚁群算法在解决　实际问题尤其是大规模问题时存在收敛速度慢，容　易出现停滞以及全局寻优能力差等缺点，本文针对　基本蚁群算法易陷人局部最优解的缺点，提出了一　种改进的蚁群算法。该算法通过禁忌当前取得的最　优路径，有选择地更新信息素，有效地提高了基本蚁　群算法的寻优能力。　ｌ　基本蚁群算法　蚂蚁在寻找食物的过程中会在它所经过的路径　上留下一种名为信息素的物质，该物质能够沉淀在　一１４Ｏ一　路径上，并且随着时间逐步挥发。当蚂蚁在选择路　径的时候，它能感知到信息素的存在及其浓度，研究　发现蚂蚁总是倾向于选择信息素浓度高的路径，而　蚂蚁在行进过程中又会留下信息素进一步增强其选　择路径上的信息素浓度，从而后续的蚂蚁选择该路　径的概率就会增加。通常越短的路径会被越多的蚂　蚁访问，该路径上的信息素浓度就会越来越强，因此　后续的蚂蚁选择该路径的概率就越大。最终，所有　的蚂蚁都会选择这条最短路径，蚂蚁群体也就找到　了蚁穴到食物源的最短路径。　以ＴＳＰ问题为例说明蚁群算法的工作原理。　设有ｎ座城市，ｍ只蚂蚁，每一次迭代开始时，蚂蚁　ｋ（ｋ＝１，２，…，ｍ）随机选择其中一座城市作为它的　起始点。在移动过程中，蚂蚁ｋ按概率选择下一个　城市，其由城市ｉ转移到城市　的概率为：　收稿日期：２０１１一Ｉ１—０８　作者简介：叶婷婷（１９８７一），女，硕士研究生，研究方向为蚁群优化　算法。

1 / 10 package GA;

import java.util.*;

public class Tsp {

private String cityName[]={"北京","上海","天津","重庆","哈尔滨","长春","沈阳","呼和浩特","石家庄","太原","济南","郑州","西安","兰州","银川","西宁","乌鲁木齐","合肥","南京","杭州","长沙","南昌","武汉","成都","贵州","福建","台北","广州","海口","南宁","昆明","拉萨","香港","澳门"};

//private String cityEnd[]=new String[34];

private int cityNum=cityName.length; //城市个数

private int popSize = 50; //种群数量

private int maxgens = 20000; //迭代次数

private double pxover = 0.8; //交叉概率

private double pmultation = 0.05; //变异概率

private long[][] distance = new long[cityNum][cityNum];

private int range = 2000; //用于判断何时停止的数组区间

private class genotype {

int city[] = new int[cityNum]; //单个基因的城市序列

long fitness; //该基因的适应度

中国科技信息２００７年第９期　ＣＨＩＮＡ　ＳＣＩＥＮＣＥ　ＡＮＤ　ＴＥＣＨＮＯＬＯＧＹ　ＩＮＦＯＲＭＡＴＩＯＮ　Ｍａｙ．２００７　豢　Ｓ　一种改进后的自适应蚁群算法　黄茜叶仲泉王书勤　为了提高传统的蚂蚁算法求解的质量，本文　对传统的蚁群算法中的信息素进行动态的自　适应调整，提出了一种新的自适应蚂蚁算　法。实验镣粟表明该算法具有更好的搜索全　局最优解的能力，并具有更好的稳定性和收　敛性。　蚂蚁算法≯自适应；信息素；旅行商问题　Ｂｅｃａｕｓｅ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ａｎｔ　ｃａｌｃｕｌａｔｅ　ｗａｙ　ｅａｓｉｌｙ　ａｐｐｓ＆ｒ８　ｐｒｅｃｏｃｉｏｕｓ　ａｎｄ　ｓｔａｇｎａｔｉｏｎ　ｂｅｈａｖｉｏｒ　ｐｈｅｎｏｍｅｎｏｎ，　Ｓ０　ｔｈｉｓ　ｔｅｘｔ　ｐｕｔ　ｆｏｒｗａｒｄ　ｏｎｅ　ｋｉｎｄ　Ｉａｔｅｌｙ　ｆｒｏｍ　ｏｒｉｅｎｔａｔｉ０１１　ａｎｔ　ｃａｌｃｕｌａｔｅ　ｗａｙ。ｉｔ　ｊ８　ｔｏ　ｆｎｆｏｒｒｎａｔｉｏｎ　ｐｈｅｒｏｍｏｎｅ　ｏｆ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａＩ　ａｎｔｓ　ｃａｌｃｕｌａｔｅ　ｗｉｔｈｉｎ　ｃａｌｃｕｌａｔｅ　ｗａｙ　ｔＯ　ｃａｒｒｙ　ｏｎ　ｄｙｎａｍｉｃ　ｓｔａｔｅ　ｏｆ　ａｄｊｕｓｔ　ｆｒｏｍ　ｔｈｅ　ｏｒｉｅｎｔａｔｌｏｎ，Ｔｅｓｔ　ｒｅｓｕＩｔ　ｅｎｕｎｃｉａｔｉｏｎ　ｔｈａｔ　ｃａｌｃｕｌ＆ｔｅ　ｗａｙ　ｔｏ　ｈａｖｅ　ｂｅｔｉｅｒ　ｓｅａｒｃｈ　ｔｈｅ　ａｂｉｌｉｔｙ　ｏｆ　ＳＵｐｅｒｉｏｒ　ｓｏｌＵｔｉｏｎ　ｏｆ　ｏｖｅｒａＩＩ　ｓｉｔｕａｔｉｏｎ．ａｎｄ　ｈａｖｅ　ｂｅｔｔｅｒ　ｓｔａｂｉｌｉｔｙ　ａｎｄ　ａｓｔｒｉｎＳｅｎｃｙ，　ａｎｔ　ｃａｃｕｌａｔ￣ｉ　ｓｅｌｆ—ａｄａｐｔｉｖｅ；ｐｈｅｒｏｍｏｎｅ；ＴＳＰ　ｐｒｏｂｌｅｍ　１引言　蚁群算法是由意大利学者Ｍ．Ｄｏｒｉｇｏ，　Ｖ．ｍａｎｉｅｚｚｏ和Ａ　ｃｏｌｏｒ￣于２０世纪９０年代　为了求解ＴＳＰ而提出的新型的智能优化算　法。它是一种基于种群的启发式搜索算　法，在求解调度问题、二次指派问　（ｑｕａｄｒａｔｉｃ　ａｓｓｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍ）、背包　问题上取得了不错的效果，目前已被广　泛地应用于求解组合优化、函数优化、　系统辨识、机器人路径规划等问题上。　ＴＳＰ（旅行商）问题用数学语言可　描述如下：　设ｃ：｛ｃ　，Ｃ　一，Ｃ　｝为ｎ个城市的集合，　Ｌ＝　ｌ　Ｃ．，Ｃ　∈ｃ｝是Ｃ中元素两两连接的集　合，Ｇ＝（Ｃ，Ｌ）是一个图，ＴＳＰ的目的是从　中找出长度最短Ｈａｍｉｌｔｏｎｉａｎ（哈密顿）圈，　即是找出对Ｃ＝｛ｃ　，Ｃ　一，Ｃ｝中个城市访问且ｎ　只访问一次的最短的一条封闭曲线。　２基本蚂蚁算法的原理　设有ｍ个城市，ｎ只蚂蚁，令ｄｉｉ（ｉ，　ｊ：１，２，…，ｍ）表示城市ｉ，ｊ之间的距离，Ｔ　（ｔ）　表示在ｔ时刻城市ｉ和城市ｊ之间的路径上　的残留信息素强度。蚂蚁ｋ在行进过程　中，根据各条路径上的信息素强度来决　定下一步所行进的路径，采用Ｐ　．．（ｔ）表示　在时刻蚂蚁由城市ｉ转移到城市ｊ的概率，　则有：　㈨＿』　，㈩　Ｐ＾ｉｌ（ｔ）：　（『】ｒ　（１）　ｊ　ｏ　否则　其中Ｊ　（ｉ）＝｛１，２，…，ｎ｝一ｔａｂｕ　表示蚂蚁　ｋ下一步允许选择的城市集合。列表ｔａｂｕ。　记录了蚂蚁ｋ当前走过的城市。当所有ｎ　座城市都加入到ｔａｂｕ　中时，蚂蚁ｋ便完　成了一次周游，此时蚂蚁ｋ所走过的路径　便是ＴＳＰ的一个可行解。ｎ，．是一个启发　２７４　式因子，表示蚂蚁ｋ从城市ｉ转移到城市　ｊ的期望程度，通常取ｄ的倒数。。【和ｐ　分别表示信息素和启发式因子的相对重要　程度。当所有蚂蚁完成一次周游后，各　路径上的信息素根据（２）式更新：　Ｔ　（ｔ＋１）＝（１一ｐ）’Ｔ　（ｔ）＋△Ｔ　（２）　△Ｔ　，＝　△Ｔ　（３）　ｋ＝Ｉ　其中Ｐ（０＜Ｐ＜１）表示路径上信息素的　蒸发系数，１一Ｐ表示信启、素的持久性系　数，△Ｔ　表示本次迭代边上信息素的增　量。△　表示第ｋ只蚂蚁在本次迭代中留　在边上的信息素量。如果蚂蚁ｋ没有经边　ｉｊ，则△　的值为零。　△　表示为　ｒ　ｒｌ　ＡＺ　ｋ｛　呲肌本诙用　蛳　１　０　否则　（４）　其中，Ｑ为常数，Ｌ。表示第ｋ只蚂　蚁在本次周游中所走过的路径的长度。　３改进后的自适应蚁群算法　蚂蚁算法在许多领域中被证明是有效　的，但存在着收敛速度慢和容易出现停　滞现象的缺陷，因此本文提出一种改进　后的自适应算法，它可动态地调整转移　概率和蒸发系数来避免算法出现停滞现　象，从而提高了算法的搜索好解的能　力。自适应算法使用自适应伪随机比率　

一　

康岚兰－曹文梁：　

Ｋａｎｇ　Ｌａｎｌａｎ　Ｃａｏ　Ｗｅｎｌｉａｎｇ　（１．江西理工大学应用科学学院，江西赣州３４１０００；２．东莞职业技术学院计算机工程系，广东东莞５２３８０８）　

（１．Ｆａｃｕｌｔｙ　ｏｆＡｐｐｌｉｅｄ　Ｓｃｉｅｎｃｅ，ＪｉａｎｇｘｉＵｎｉｖｅｒｓｉｔｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄＴｅｃｈｎｏｌｏｇｙ，ＪｉａｎｇｘｉＧａｎｚｈｏｕ　３４１０００；２．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒ　

Ｅｎｇｉｎｅｅｒｉｎｇ，Ｄｏｎｇｇｕａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ，Ｇｕａｎｇｄｏｎｇ　Ｄｏｎｇｇｕａｎ　５２３８０８）　

摘要：蚁群算法（ＡＣＡ）与遗传算法（ＧＡ）都属于仿生型优化算法，是解决组合优化问题的强有力工具，并都分别成功应　

用于旅行商问题（ＴＳＰ）中。本文将两种算法进行融合，并给出了新的融合方式。实验结果表明，新的遗传蚁群混合算法有效地改　

进了算法的全局收敛性，并加快了收敛速度。　关键词：蚁群算法；遗传算法；混合算法；旅行商问题　

中图分类号：ＴＰ３０１　文献标识码：Ａ　文章编号：１６７１－４７９２．（２０１０）７．００１０—０３　

Ａｂｓｔｒａｃｔ：Ａｎｔ　Ｃｏｌｏｎｙ　Ａｌｇｏｒｉｔｈｍ（ＡＣＡ）ａｎｄ　Ｇｅｎｅｒａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ（ＧＡ）ａｒｅ　ｔｗｏ　ｂｉｏｎｉｃ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ｔｈｅｙ　ａｒｅ　ａｌｓｏ　ｔｗｏ　ｐｏｗｅｒｆｕｌ　ａｎｄ　ｅｆｆｅｃｔｉｖｅ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｔｈｅ　ｃｏｍｂｉｎａｔｉｏｎ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ，ｍｏｒｅｏｖｅｒ　ｔｈｅｙ　ａｌｌ　ｗｅｒｅ　ｓｕｃｃｅｓｓｆｕｌｌｙ　ｕｓｅｄ　ｉｎ　ｔｒａｙ－　

ｅｌｉｎｇ　ｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ（ＴＳＰ）．Ｔｈｉｓ　ｐａｐｅｒ　ｓｙｎｃｒｅｔｉｚｅｓ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ，ｍｅａｎｗｈｉｌｅ，ａ　ｎｅｗ　ｓｙｎｃｒｅｔｉｃ　ｍｅｔｈｏｄ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌ￣