1、基于蚁群算法的TSP问题基于蚁群算法的 TSP 问题求解1 引言1.1 问题描述设计求解以下两个 TSP 问题的蚁群优化( ACO )算法。其中城市的坐标见 附件( kroA100.tsp 和 kroB100.tsp)。1.2 理论基础1.2.1 蚁群算法简介蚁群算法是由意大利学者 M.Dorigo 等人于 20 世纪 90年代初提出的一种新 的模拟进化算法，其真实地模拟了自然界蚂蚁群体的觅食行为。 M.Dorigo 等人 将其用于解决旅行商问题(traveling salesman problem, TSP,并取得了较好的实 验结果。近年来,许多专家学者致力于蚁群算法的研究,并将其应用于交通
2、、通信、化工、电力等领域，成功解决了许多组合优化问题，如调度问题( job -hopscheduling problem) 指派问题(quadratic assignment problem)、旅行商问题(traveling salesman problem 等。1.2.2 蚁群算法基本思想生物学家研究发现， 自然界中的蚂蚁觅食是一种群体性行为， 并非单只蚂蚁 自行寻找食物源。蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素， 并能够感知其它蚂蚁释放的信息素。 信息素浓度的大小表征路径的远近， 信息素 浓度越高， 表示对应的路径距离越短。 通常， 蚂蚁会以较大的概率优先选择信息 素浓度较高
3、的路径，并释放一定量的信息素，以增强该条路径上的信息素浓度， 这样会形成一个正反馈。最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径， 即是最短距离。 值得一提的是， 生物学家同时发现， 路径上的信息素浓度会随着 时间的推进而逐渐衰减。将蚁群算法应用于解决优化问题的基本思路为： 用蚂蚁的行走路径表示待优 化问题的可行解， 整个蚂蚁群体的所有路径构成待优化问题的解空间。 较短的路 径上蚂蚁释放的信息素量较多， 随着时间的推进， 较短的路径上积累的信息素浓 度逐渐增高， 选择该路径的蚂蚁个数也愈来愈多。 最终， 整个蚂蚁会在正反馈的 作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。123
4、蚁群算法解决TSP问题的基本原理为不失一般性，设整个蚂蚁群体中蚂蚁的数量为 m，城市的数量为n,城市i与城市j之间的距离为dj (i, j =1,2,.,m)，t时刻城市i与城市j连接路径上的信 息素浓度为j(t)。初始时刻，各个城市连接路径上的信息素浓度相同，不妨设 为-ij (0)=o。蚂蚁k(k =1,2.,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设p：(t)表示t时刻蚂蚁k从城市j的概率，其计算公式为：j(t)= ijt() “,s alloWk工【(t)Fs t()s Wallowk0,s 一一 allowk其中ij(t)为启发函数，ij(t) =1/ dij，
5、表示蚂蚁从城市i转移到城市j的期望程度；allowk(k =1,2,，m)为蚂蚁k待访问城市的集合，开始时，allowk中有(n-1)个元素，即包括除了蚂蚁k出发城市的其它所有城市，随着时间的推进，allowk中 的元素不断减少，直至为空，即表示所有的城市均访问完毕；:为信息素重要程 度因子，其值越大，表示信息素的浓度在转移中起的作用越大；-为启发函数重 要程度因子，其值越大，表示启发函数在转移中的作用越大， 即蚂蚁会以较大的 概率转移到距离短的城市。如前文所述，在蚂蚁释放信息素的同时，各个城市间连接路径上的信息素逐 渐消失，设参数(0：1)表示信息素的挥发程度。因此，当所有蚂蚁完成一次循环后
6、，各个城市间连接路径上的信息素浓度需进行实时更新，即:其中，/表示第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度;.： .j表示所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和。针对蚂蚁释放信息素问题，M.Dorigo等人曾给出了三种不同的模型，分别 称之为 Ant cycle system，Ant quantity system 和 Ant density system，其计算公式 分别如下。（1） Ant cycle system 模型Ant cycle system模型中，二的计算公式为：(1-3).k Q/Lk,第k只蚂蚁从城市i访问城市j j 二 0,其他其中，Q为常数，
7、表示蚂蚁循环一次所释放的信息素总量； Lk为第k只蚂蚁经过路径的长度。（2） Ant qua ntity system 模型Ant quantity system模型中，匚k的计算公式为:(3)Ant den sity system 模型Ant density system模型中，jk的计算公式为:k Q,第k只蚂蚁从城市i访问城市j(1-5)打=j 0,其他上述3种模型中，Ant cycle system模型利用蚂蚁经过路径的整体信息（经 过路径的总长）计算释放的信息素浓度； An t qua ntity system模型则利用蚂蚁经过路径的局部信息（经过各个城市间的距离）计算释放的信息素浓
8、度；而 Antdensity system模型则更为简单地将信息素释放的浓度取为恒值，并没有考虑不 同蚂蚁经过路径长短的影响。因此，一般选用 Ant cycle system模型计算释放的信息素浓度，即蚂蚁经过的路径越短，释放的信息素浓度越高。1.2.4蚁群算法的特点基于蚁群算法的基本思想及解决 TSP问题的基本原理，不难发现，与其它优化算法相比，蚁群算法具有以下几个特点：（1） 采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解。（2） 每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周 围环境的实时变化，个体间通过环境进行间接地通讯。（3） 搜索过程采用分布式计算方式，多个
9、个体同时进行并计算，大大提高了算 法的计算能力和运行效率。（4） 启发式的概率搜索方式不容易陷入局部最优，易于寻找到全局最优解。1算法设计蚁群算法应用于解决TSP问题一般需要以下几个步骤，如图1所示图1蚁群算法解决TSP问题的基本步骤（1）初始化参数在计算之初，需要对相关的参数进行初始化，如蚁群规模（蚂蚁数量） m、信息素重要程度因子:、启发函数重要程度因子1、信息素挥发因子、信息素释放总量Q、最大迭代次数iter_max、迭代次数初值iter=1（2）构建解空间计算其下一个待访问的城市，直到所有蚂蚁访问完所有的城市（3）更新信息素计算各个蚂蚁经过的路径长度Lk（k =1,2.,m），记录当前
10、迭代次数中的最优 解（最短路径）。同时，根据式（1-2）和式（1-3）对各个城市连接路径上的信 息素浓度进行更新。（4）判断是否终止若iterruGl图3 KroA优化路径ACA optima re suit:23537.43943500 WOO 1500 2000 2500 3CS3D 3500 4000The Jtcoordinle of CityLJUOOOOOOOOOOOO 2-0-8642 Al_oJomlEEpo3CULI12O1B1E图4 KroB优化路径图5 KroA各代最短距离与平均距离图6 KroB各代最短距离与平均距离4.2参数对优化结果的影响(1)蚂蚁数量m的影响为研究
11、蚂蚁数m对计算结果的影响，比较10组不同蚂蚁数的计算结果，每 组计算10次取平均值。同时，由于计算次数多达100次，为提高程序运行速度, 暂将最大迭代次数减少为20次，仅对m变化引起结果变化的趋势作以研究(下 同)。取0=1，=5，p=0.1，Q=1，研究结果如图7和图8所示。L Oe+04 *2. 88322. 83602. 78862. 74072. 86312. 32232. 84582. 88082. 76902. 75332. 81632. 84922. 8D872. 73692. 76792.77712. 93052. 84772. 75612.79512.12272. 79922
12、. 84002. 80502. 7B652. 85992. 80582. 82222. 79642. 74542. 72052. 70092-78832.71752. 72092.71142. 842823 845J2a T69S2.81722, 76672, 79J552.17312. 79432. 827&2. 71ES2. 72062. 67462. 70562.16582.73372. 76902. 7ES62.74602 74172.72642. 76492. 79362. 78572. 80822. 74332. 77962. 75242.76912.76652. TQ552. 7
13、 22S2,77022-71162. 70492. 738S2. 7T732. 74 W2a 7Q582.80712-73852. 74322.70532, 53492. 77662. 7D222. 74122, G4322, fflOE2. 77352.15292.72232. 68522. 72592. 67302. 62822. 75862. 60522. 73372. 73622. 73892.17182.70662. 69E12.71712. 75372. 32392. 69032.12212. 80362. 75632. 66P72.76012. 7395图7蚂蚁数对计算结果的影响
14、图8蚂蚁数对平均最短距离的影响可见，随着蚂蚁数的增加，平均最短距离呈减小的趋势，图中蚂蚁数为 45时，得到最小的平均最短距离为 27056。(2)信息素重要程度因子a的影响为研究信息素重要程度因子 a对计算结果的影响，比较10组不同a值的计 算结果，每组计算10次取平均值。取m=45, 3=5, p=0.1, Q=1，研究结果如图 9和图10所示。1. Oe+04 *2. 72382. 74S42. 64802.14692.70752. U142. 75662. 74962,81272. 70262.73652.71232. 73492.72152. 70192. 79122.70642. 0
15、7152. 76062.73502.76712.73022.71152. 67862. 6S542.19322. 84442. 82272. 75322. 80282. 77332.76022. 76352-7412占 74542. 73832. 82202. 77652.69612.61512. 67452b 77142b 7 0932. 72912.81902. 67682.B1262. 75962.64872. 68912. 77952. 72662. 70602. B9682. 72152. 72582.77412.74742.66612.73442. 73352.77022. 641
16、12. 72C92. 72562.72292-74452 689T2. 75132. 76302. 72642. 6BG52. T2952.68552. 77492. 64852. 72022, 67S52.77T0?. 7C012.1H52.69252. 84茹2. 0702. 77372, 70862.2. 7DS22.61772. 67812.76672. 6S392.71922.71102.81632. 65632.72942. 64682.70262- 56432. 69462. 74252. 76392. 67262. 76702. 72532. 64412.71322.71602
17、. 7004图9信息素重要程度因子对计算结果的影响图10信息素重要程度因子对平均最短距离的影响可见，随a增大，平均最短距离大体呈下降趋势，当 a=10时，得到最小的平均最短距离为27004。(3)启发函数重要程度因子B的影响为研究启发函数重要程度因子3对计算结果的影响，比较10组不同3值的计算结果，每组计算10次取平均值。取m=45,a=10，尸0.1,Q=1,研究结果如图11和图12所示。L.0e+04 B. S5I4B.4568& 5354.4914& 3817& 709& 58302 0381乱 93728.4215& 62094. 81934.9B66J 82114. 80834-7H
18、14.9B11丄 69D14. 39B84.6812L 30344. 30E73. 59313.46263.42233.4436X4S083.41053. 52D03.45B73. 60933.dt773.47992.91412- 88902-M24X01513, 03562.91422, 7329瓷 93403- 027S2. 9066瓷 93122. 30662.14152.58U62. ? 97込 65782. G4S12.$008I, T佃2.71972,03032, 08352. B7462.B0492.B9032.63)02.66082.69702.64782.61032. 647
19、02. 68702.61612. 56502.53912.48B72.53852.50872.51812.49952.53912. 53642. 56152. 52942. EMO. 43C0.41862. 533329452.&4Q42,73423542.4409益就朋28452. 391E2.45502.49962. 50S32.42812. 38342.47182.49502.49642.46472.40T62.43232.44T72.47712.46322.42592.42182.43362. 44862.48992.4438图11启发函数重要程度因子对计算结果的影响图12启发函数重要
20、程度因子对平均最短距离的影响可见，随B增大，平均最短距离呈下降趋势，而当 3=10时，得到最小的平均最短距离为24438。(4)信息素挥发因子p的影响为研究信息素挥发因子p对计算结果的影响，比较10组不同p值的计算结果，每组计算10次取平均值。取 m=45, 和图14所示。L Qe+042.43E62.40682.42052.41972.41622.43292.45302. 3B4E2. 39632. 36962-42192. 36322.41662. 39782.43152. 39022.46452. 3912艺 41262-42202-42972-45U2.40022-4 3 992.40
21、532.40632.46522.46012.45442. 38350=10，3=10，Q=1，研究结果如图132.458B2. 50932,0702.46E12.44252.43512. 396?2.42942.4L212.406S2.41092.45372.40243.43S12.198L 43032-43242.4322N 374E2.42562.4T832. 44032.4190.41112.4323图13信息素挥发因子对计算结果的影响图14信息素挥发因子对平均最短距离的影响可见，随p增大，平均最短距离呈先下降后上升趋势，而当 尸0.2时，得到最小的平均最短距离为24068。(5)信息素
22、释放量Q的影响为研究信息素释放总量Q对计算结果的影响，比较10组不同Q值的计算结 果，每组计算10次取平均值。取 m=45, 0=10，3=10，尸0.2，研究结果如图15和图16所示。图16信息素释放量对平均最短距离的影响可见，随Q增大，平均最短距离大致呈上升趋势，而当 Q=10时，得到最小 的平均最短距离为24179。综合分析以上参数的影响，可以看出，随着研究的进行，通过控制变量法， 得到的平均最短距离有下降趋势， 但最后一次的24179却比倒数第二次的24068 要大。我们分析这里可能有两个原因，一是因为我们为尽快运行程序，降低了迭 代次数，算法寻优过程的偶然性增大；二是由于蚁群算法本身
23、的偶然性， 即使将 迭代次数调整回 200 次，运行结果有时也会偏大， 但增大迭代次数， 得到最优解 的概率会越大。4 总结与展望本文详细叙述了应用蚁群优化算法解决 TSP 问题的一般过程，并将其应用 于题中所给出的具体问题。算法使用 MATLAB 编写程序实现，给出了程序运行 的仿真结果并对其进行了分析。 考虑程序运行的结果与效率， 可以看出蚁群优化 算法可以很好的解决 TSP 等组合优化问题。 但是算法中的参数一般由人为确定， 导致方法的优化性能往往与人的经验密切相关。 因此本文接下来分析了蚁群算法 中参数的选取对结果的影响，通过仿真实验得到了求解该 TSP 问题的最佳参数。蚁群算法以其分布并行式计算、 启发式搜索方式等特点， 在各个领域中取得 了广泛的应用， 解决了诸多组合优化方面的难题。 针对其可能陷入局部最优的缺 点，不少专家和学者提出了许多改进的方法，并将其它算法（如遗传算法、粒子 群算法等）与蚁群
