仿真的多目标优化（蚁群算法在旅行商问题中的应用）

四、符号说明

序号 1 2 3 4 5 6 7 8 9 10 符号 n个城市的坐标，n×2的矩阵 C: NC_max： 最大迭代次数各班人数 错误！未各专业所分配的名额数 找到引蚂蚁个数 用源。： 表征信息素重要程度的参数 m： 表征启发式因子重要程度的参数 Alpha： 信息素蒸发系数 Beta： 信息素增加强度系数 Rho: Q: R_best: L_best： 各代最佳路线 各代最佳路线的长度 4

五、模型的建立与求解

1.旅行商模型：

G?(V,E)为一个带权图,V?{1,2,?n}为顶点

集,E?{eij?{(i,j)i,j?V,i?j}为边集。dij(i,j?V,i?j)为顶点i到顶点j 的距离， 其中dij?0且dij??，同时dij?dji(i,j?V),则经典TSP的数学模型为：

minF??dijxxiji?j(1)

(2)

??1`,边eij在最优路径上st..xij????0，边eij不在最优路径上 ?xij?1,i?Vi?j(3) (4) (5)

?xi?jij?1,j?V ?s,s是G的子图i,j?s其中s是图s 的顶点数。（1）为ctsp的目标函数,求经过所有顶点的回路的最小距离。（2）-（4）限定回路上每个顶点仅有一条入边和一条出边。( 5 ) 限

定在回路中不出现子回路。模型实质上是在一个带权图中求一条H a m i l t o n回路。若对所有i，j,k ∈V， 不等式dij?djk?dik均成立， 则称该问题是满足三角不等式的。

2.蚂蚁算法求解TSP 问题的具体过程如下：

1（1）首先初始化，设迭代次数为NC。初始化NC=0，各?(i,j)初始化；?0?nL?nn

（2）将m 个蚂蚁置于n 个顶点上；

（3）构造解。每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条线路。蚂蚁任务是访问所有的城市后回到起点，生成一条回路。设蚂蚁k当前所在的顶点为i，那么，蚂蚁k 由点i 向点j 移动要遵循（1）式的状态变化规则而不断迁移，按不同概率来选择下一点。

???j?????

argJk?allowedmax?(???)(?)ijij?q?q0q?q0(Exloitation)(1)(Exloitation)（1）式中，alowedk?{0,1,?n?1}?tabuk表示蚂蚁k 当前能选择的城市集合，

5

tabuk为禁忌表，它记录蚂蚁k已路过的城市，用来说明人工蚂蚁的记忆性 ；式中?ij相当于真实蚂蚁沿途散播的信息素，是一个正实数，与图G中弧（i，j）关联，其值在运行时不断改变，用于表示蚂蚁从点i向点j移动的动力；?ij用于评价蚂蚁从点i 向点j 移动的启发函数，其值通常用距离的倒数来求得，即

?ij?d(ci,cj)?1。?,?体现了信息素和启发信息对蚂蚁决策的影响。?取值为1；

参数??0描述启发函数的重要性；参数q0(0?q0?1)决定利用和开发的相对重 要性，利用（Exploitation）是指走最好的路，开发（Exploration）是指按浓度高概率高的原则选路V，这样可以保证选择路径的多样性；q 是在[0，1] 取的随机数，当q?q0时，按（1）式选最好的路，否则按（2）式的概率进行选路：

?(?ij)?(?ij)?????k(?(t))(?)?ikikpij(t)???k?allowed??0ifj?allowedk

otherwise（4）局部更新信息素值。应用局部信息素更新规则来改变信息素值。在构

造解时，蚂蚁k 对其走过的每条弧用：

newold?ij?(1??)?ij???0

局部信息素更新规则来改变弧上关联的信息素值，其中0???1是信息素挥发参数。

（5）若所有的m个蚂蚁都构造完解，则转（6） ；否则转（3） ；

（6）全局更新信息素值。应用全局信息素更新规则来改变信息素值。当所有m 个蚂蚁生成了m 个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素值按下式更新：

gb?ij(t?1)?(1??)?ij(t)????ij(t)

gb?1/L(t)gb??ij(t)???0ifarc(i,j)?Tgbotherwise

其中0???1是挥发参数；Lgb(t)是目前得到的全局最优解的路线长度。 全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最短路线的弧上的信息素才能得到加强，这是一个正反馈的过程，也是一个强化学习的过程。在图中各弧上，伴随着信息素的挥发，全局最短路线上各弧的信息素值得到增加；

（7）终止。若终止条件满足，则结束；否则NC=NC+1，转（2）进行下一代

6

进化。终止条件可指定进化的代数，也可限定运行时间，或设定最短路长的下限。

例：一个商品推销员要去若干个城市推销商品， 该推销员从一个城市出发， 需要经过所有城市后，回到出发地。应如何选择行进路线， 以使总的行程最短。

城市坐标 城市 1 2 3 4 5 6 7 8 9 坐 标 行值 列植 城市 坐 标 304 312 10 639 315 11 177 712 488 326 238 196 312 244 399 535 556 229 104 790 12 13 14 15 16 17 18 行值 列植 城市 坐 标 386 570 19 107 562 788 381 332 715 918 161 970 756 491 676 695 678 179 370 20 21 22 23 24 25 26 27 行值 列植 城市 坐 标 780 212 28 676 578 29 329 838 30 263 931 31 429 908 507 367 394 643 439 201 935 240 行值 140 545 778 370 列植 550 357 826 975 应用上面的步鄹可以解出最短路径出来，相应的程序见附件，结果为： 最短路径图

10009008007006005004003002001001002003004005006007008009001000

7