计算智能大作业--蚁群算法解决TSP问题

实用标准文案

的个数，蚂蚁总数ｍ＝?bi?t?，?ij?t?表示ｔ时刻在ｉｊ连线

i?1n上残留的信息量，初始时刻各条路径上的信息量为?ij?0?＝Ｃ（Ｃ为常数）。用参数?表示信息量的保留度，则经过ｎ个时刻后，路径ｉｊ上的信息量根据下式作调整：

?ij(t?n)????ij(t)???ij ⑴

m??ij????ijkk?1k??ij ⑵

表示第ｋ只蚂蚁在本次循环中留在路径ｉｊ上的

信息量，??ij表示本次循环所有经过的蚂蚁留在ｉｊ上的信息量。

?Qk?ij＝?Lk?０???当第ｋ只蚂蚁经过ｉｊ时当不经过时 ⑶

定义?ij＝１／dij。蚂蚁ｋ（ｋ＝１，２，…，ｍ）在运动过程中，pijk表示在ｔ时刻蚂蚁ｋ由位置ｉ转移到位置ｊ的概率：

????ij?ij?t???????iskpij＝?s?allowdk?is?t????0j?allowedk ⑷

其他 我们用tabuk(k?1,2,?,m)记录蚂蚁ｋ目前已经走过的城市集合，allowdk表示蚂蚁ｋ下一步允许选择的城市集合，它等

精彩文档

实用标准文案

于全部的城市集合除去第ｋ只蚂蚁已走过的集合tabuk。 定义

L为第ｋ只蚂蚁在本次循环中走过的路径和。

k用蚁群算法解决ＴＳＰ问题是一个递推过程 ，当ｔ＝０时，将蚂蚁放在各城市，设定每条路径上的信息量初值?ij?0?＝Ｃ，每只蚂蚁根据公式⑷决定的概率从城市ｉ到城市ｊ。；?说明较近??t?表示曾经有多少蚂蚁经过路径（ｉ，ｊ）

ijij的城市有更大的可能性被选中。α，β用来控制两者对蚂蚁选择的影响力程度。经过一个循环后，根据公式⑴⑵⑶计算更新每条路径的信息量?ij?t?。将所有的tabuk(k?1,2,?,m)复原，最后求出本次循环的最短路径minLk。这个过程不断重复，直到所有的蚂蚁都选择同样的路径，或者循环次数达到预先设定的最高次数NCmax。

四、解决ｎ个城市的TSP问题的算法步骤

1.初始化：设定t=0，循环计数器nc=0，对每条路径设定初始信息量?ij?0?＝C,??ij＝０将ｍ只蚂蚁放在ｎ个城市上（为了使问题简化，设定ｍ＝ｎ）。

2.设定taub集合的索引ｓ＝１，对ｋ从１到ｍ，把第ｋ只蚂蚁放在起始位置，对应的设定集合tabu?s?

k3.重复下面的步骤，直到集合tabu满为止（这一步将重复ｎ－１次）：设定ｓ＝ｓ＋１；对ｋ从１到ｍ，根据公式⑷确定的概率，选择下一步移动的目标城市ｊ｛在时间ｔ

精彩文档

实用标准文案

时，第ｋ只蚂蚁所在的城市是ｉ＝tabuk?s?1?｝；将第ｋ只蚂蚁移到城市ｊ；把ｊ加入到集合tabuk?s?中。

4.对ｋ从１到ｍ：将第ｋ只蚂蚁从tabuk?n?移动到

tabu?1?；计算第ｋ只蚂蚁所走过的路程和L，并更新最小

kk路径minLk；对每条路径（ｉ,ｊ）：

?Q?k＝ ?Lk??ij?０?当第ｋ只蚂蚁经过ｉｊ时当不经过时

k ??ij???ij???ij5.对每条路径（ｉ,ｊ）根据?ij(t?n)????ij(t)???ij计算

?ij?t?n?；设定ｔ＝ｔ＋ｎ；设定ＮＣ＝ＮＣ＋１；对每条路

径（ｉ,ｊ），设定??ij＝０。

6.如果ＮＣ＜NC，则清空所有的集合tabu,转到第二步；

max否则,得出最短的路径。 算法的流程如下图:

精彩文档

实用标准文案

五、程序实现

一：

Matlab实现程序如下： %一始化变量 clear;

Alpha=1; %信息素重要程度的参数(对路径选择有很大影响) Beta=5; %启发式因子重要程度的参数(对路径选择有很大影响) Rho=0.95; %信息素蒸发系数

NC_max=200; %最大迭代次数(循环多结果更优适度即可) Q=100; %信息素增加强度系数 (对结果影响小)

精彩文档