《蚁群算法的改进及其在tsp问题中的应用》由会员分享，可在线阅读，更多相关《蚁群算法的改进及其在tsp问题中的应用（5页珍藏版）》请在金锄头文库上搜索。
1、蚁 群 算 法 的 改 进 及 其 在 TSP 问 题 中 的 应用雷德明 吴智铭上海交通大学 自动化研究所 200030 上海摘要：在过去的 10 多年，蚁群算法（ACO）的研究和应用取得了很大的进展，大量结果证明了算法的有效性和在某些领域的优势。算法的基本缺陷：搜索时间过长和容易陷入局部解也得到了一定程度的解决，提出了一些有效的方法。但问题并未完全消除。本文首先分析了 ACO 中产生停滞现象的原因，然后给出了一种解决方案，通过直接交换部分边上的信息素和合理设定每条边的信息素挥发率，来克服算法停滞现象。仿真结果表明上述方法是可行和有效的。关键词：蚁群算法 信息素 旅行商问题The Impro
2、vement of Ant Colony Optimization Algorithm and its Application to TSP problemLei Deming Wu Zhiming(Shanghai Jiaotong University , Institute of Automation ,20030,Shanghai)Abstract: The researches and applications on ACO algorithm have made great progresses in the past more than ten years. A number o
3、f results prove the validity of the algorithm and its advantages in some fields. Its basic shortcomings, which are long searching time and easily jumping into local optimal solution, also have been overcome partially and some effective methods are introduced. However, the problems arent completely s
4、olved. This paper first analyzes the grounds producing stagnation and then introduces a new solution for excluding stagnation, which includes the direct exchange of pheromone on some edges and dynamically setting evaporation rate for each edge .The simulation results demonstrate that the above appro
5、ach is reasonable and efficient.Keyword: Ant Colony Optimization algorithm pheromone TSP problem1引论蚁群算法（ACO）是受自然界中蚂蚁搜索食物行为启发而提出的一种智能优化算法。单个蚂蚁是脆弱的，但整个蚁群的群居生活却能完成许多单个个体无法承担的工作，蚂蚁间借助于信息素这种化学物质进行信息的交流和传递，并表现出正反馈现象：某段路径上经过的蚂蚁越多，该路径被重复选择的概率就越高。正反馈机制和通讯机制是蚁群算法的两个重要基础。正反馈作用能加快算法的搜索，也会导致算法出现停滞现象，而通讯机制能使个体相互协
6、作，有利于算法搜索到更优解。目前，该算法在组合优化包括 TSP, QAP 等、车辆路径问题、电力系统中故障点的估计以及通讯网络等诸多领域得到应用。蚁群算法是一种本质并行的算法，和其它智能算法不同，其搜索时间比较长，新解的产生不是直接在已有解的基础上通过变换如 GA 的交叉算子而得到的，和其他算法一样，该算法也容易陷于局部最优解，使搜索停滞。本文给出了一种改进方案，通过直接交换部分边上的信息素和合理设定每条边的信息素挥发速度，来避免算法出现停滞现象。仿真结果表明新方法是可行和有效的。2蚁群算法基本原理和遗传算法不同，关于蚁群算法的介绍往往要结合具体问题进行，通常选择的问题是 TSP 问题。该问题
7、可以描述如下：设有 个城市集 ，任意两个城市 之间的距离为 ，求一条经过每个城市仅n),21(nCLji,ijd一次的路径 ，使得),(最小)1(1)(niid表示 t 时刻位于城市 的蚂蚁的个数， 为蚂蚁的总数。 表示 t 时刻边 上)(bi initbm1)()(ijij的信息素量， ( 为常数) 。随着时间的推移，新的信息素 加进来，旧的信息素要挥发，0ij0表示信息素的挥发快慢。当所有蚂蚁完成一次周游后，各条边上的信息素按下式调整：1（1）ijijij tnt)()(2 )kijij1表示本次周游中路径 上的信息素增量，初始时刻， 0。 表示第 只蚂蚁在ij ijkij周游过程中释放在
8、边 上的信息素。ij（3）els ijkKLQij0过 边只 蚂 蚁 在 本 次 周 游 中 经若 第为常数， 表示本次周游第 只蚂蚁所形成的回路的长度。蚂蚁在周游时，向那个城市转移k由转移概率 决定。ijp（4）elsaowdjkalowedsisjikijk0其中 表示蚂蚁 当前能选择的城市集合， 为禁忌表，它kal ktbun1,L ktabu记录蚂蚁 已路过的城市，用来说明人工蚂蚁的记忆性。 是某种启发信息。在 TSP 问题中，ij。 体现了信息素和启发信息对蚂蚁决策的影响。1),(jiijcd,蚁群算法基本的运行过程是这样的： 只蚂蚁同时从某个城市出发，根据（4）选择下一次旅m行的城
9、市，已去过的城市放入 中，一次循环完成后，由公式（1） ， （2） ， （3）更新每条边上的ktabu信息素，反复重复上述过程，直到终止条件成立。蚁群算法研究包括算法的应用和算法的改进，利用蚁群算法解决实际优化问题是整个研究的主流，每年都要发表许多这类论文。关于算法的改进。可以从以下 3 个方面对算法进行。1. 将算法和其它搜索方法结合，提高算法的搜索效率，例如：在算法中引入逆转变异方式，通过随机变异，增大搜索所需的信息量，克服了搜索慢的缺点。2opt 和 ACO 的混合也明显地改进了算法的计算效率。2. 自适应调整参数 等。 Fabio Abbattista 等提出由 GA 优化 AS 的参
10、数 ，将两种Q, Q,算法的优势结合在一起。而在文献3中， 不再保持固定，而是随着搜索的进行动态地调整。文献4提出了自适应改变 值的方法。3设计 ， 和 等新的计算公式。SeungGwan Lee 等给出了一种信息素全局更新规kijijkijp则，根据该规则，高级个体经过的边要增加信息素，而低级个体路过的边要减少信息素。所谓高级个体是那些获得较优解的个体，两类个体各占一半。 的公式也很多。kijp和 GA 相比，蚁群算法相对简单，能加以改进的地方比较少，但现有的改进还不尽如人意，需进一步研究新方法和措施。3蚁群算法的改进对 ACO 来说， 之间的相对大小会直接影响城市 到城市 的转移概),21
11、)(njitij L ij率 ，从而直接影响可行解的质量。在搜索早期，信息素的分布是分散的，随着搜索进行，信息kijp素慢慢地集中到部分边上，搜索方向也随之基本确定。当某些边上地信息素强度明显高于其它边，导致在构造可行解时，总是使用少数几条边，就会使解的结构过于相似，搜索也会停顿下来，算法陷入局部最优解。虽然不同的智能算法出现停滞现象的原因各不相同，但结果是相同的，即所求的解越来越相似，避免这种现象的方法也是一致的，那就是增加解的多样性。并且有些增加多样性的手段也是通用的。例如：结合智能算法和局部搜索方法，就是一种常见的方法。当分别用 GA 和 ACO 求解 TSP 问题时，2opt，3opt
12、 等就曾分别和两种算法结合，并且效果明显。如何在 ACO 中增加解的多样性呢？关键是形成和保持一个合理的信息素分布，让较多的边能以较高概率用于构造可行解，也就是在“探索”和“利用”之间建立一个平衡点，既充分利用正反馈机制加快搜索，又尽可能地扩大算法的搜索区域，使用更多的边形成新解。通过加入新搜索方式，根据新解改变 之间的相对大小和信息素分布，可以让算法逃离局)(tij部最优解。本文引入另一种通过直接交换部分边上的信息素避免搜索停滞的方法。其具体过程如下：对于 个城市的 TSP 问题，每个城市设定交换概率 ，产生（0，1）上均匀分n nipL,2布随机数 ，如果 ，则在城市 （起点）与其它城市可
13、以形成的 条边中，随机选出一定iriipi 数量的边，然后两两互换相应边上的信息素。若 ，则不作上述处理。iir交换概率 （ 0.15）不能过大，过大会抑止正反馈作用。通过直接互换部分边上的信息素，i改变了 的分布，从而使人工蚂蚁在确定转移城市时有较多的选择，避免算法过早地陷入局部解。)(tij信息素的挥发率也会影响信息素分布。如何确定 的大小，是应用 ACO 的关键。通常， 被设置成常数，由经验或实验而定，且每条边的挥发率相同。实际上，在以城市 为起点与其它城市形i成的 条边中，不一定每次每条边上的信息素都要挥发，例如：在搜索开始后很长一段时间内，1n让所有边上的信息素都不减少，能加快搜索。
14、各个边之间也要有差别。一般情况下， 较大的边)(tij用于构造可行解的概率较高，为了防止部分边上的信息素浓度过大，相应地，这些边上的信息素应挥发快一些。而为了避免最优路径上的某些边由于信息素强度过低而失去选择机会，这些边的 值应该较大。的计算公式如下：)(tij（5）earlyij t1（6）earlyijij tlskCt 2)()(表示 t 时刻边 上信息素挥发率。 是早期搜索时间， ，1ijijearlyt )1,0(,21k但两者的差别不能太大。 介于 个 的平均值与最大值之间。,2k1n)(ij当所有蚂蚁完成一次周游后，先根据 对各边的信息素强度进行调整，然后互换部分边上ij的信息素
15、，改变现有的信息素分布。算法的具体步骤如下 Begin初始化， ， ， ， 0，对任意边 。,1,0NCtip)(tij10ijijdijijwhile ( )max只蚂蚁从初始城市出发，根据（4）将所有城市周游一次。计算可行解，若新解优于旧解，则替换，否则，保留旧解2-opt 等局部优化（option）利用包括最优回路在内的少量解更新 ， ，ij)(tij根据交换概率 选择城市，对选中的城市，在以该城市为起点的 条ip 1n边随机确定部分边，两两互换这些边上的信息素。, 0, 对任意边 .1NCijij输出最终结果End4仿真实验本文选用文献7中列出的两个 TSP 问题：50city 和 75city 问题。这两个问题目前已知的最优长度为 426.14 和 542.3。分别用基本蚁群算法 BACO、没有信息素交换的 Improved ACO1 和有信息素交换的 Improved ACO2 对两问题进行求解，每个程序各运行 20 次，计算结果如表一所示。Improved ACO 2 所获得的最优回路如图一、图二所示。表一：三种算法的计算结果 590,7,75,490,50,50,9.,1.0,51 maxmax2 NCcityTSPNCcityTSPkpai 算法 50-city 问题 75-city 问题平均值 最好结果 最差结果 平均值 最好结果
