蚁群算法原理及在TSP中的应用
1 蚁群算法（ACA）原理
1.1 基本蚁群算法的数学模型
以求解平面上一个n阶旅行商问题(Traveling Salesman Problem，TSP)为例来说明蚁群算法ACA（Ant Colony Algorithm）的基本原理。对于其他问题，可以对此模型稍作修改便可应用。TSP问题就是给定一组城市，求一条遍历所有城市的最短回路问题。
设
表示
时刻位于元素
的蚂蚁数目，
为
时刻路径
上的信息量，n表示TSP规模，m为蚁群的总数目，则
；
是
时刻集合C中元素(城市)两两连接
上残留信息量的集合。在初始时刻各条路径上信息量相等，并设
，基本蚁群算法的寻优是通过有向图
实现的。
蚂蚁
在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表
来
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
蚂蚁
当前所走过的城市，集合随着
进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。
表示在
时刻蚂蚁
由元素(城市)
转移到元素(城市)
的状态转移概率。
(1)
式中，
表示蚂蚁
下一步允许选择的城市；
为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强；
为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的重视程度，其值越大，则该状态转移概率越接近于贪心
规则
编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf
；
为启发函数，其表达式如下：
(2)
式中，
表示相邻两个城市之间的距离。对蚂蚁
而言，
越小，则
越大，
也就越大。显然，该启发函数表示蚂蚁从元素(城市)
转移到元素(城市)
的期望程度。
为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有
个城市的遍历(也是一个循环结束)后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存入大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，
时刻在路径
上的信息量可按如下规则进行调整：
(3)
(4)
式中
表示信息挥发系数，则
表示信息素残留因子，为了防止信息的无限积累，
的取值范围为：
；
表示本次循环中路径
上的信息素增量，初始时刻
，
表示第k只蚂蚁在本次循环中留在路径
上的信息量。
根据信息素更新策略的不同，Dorigo M提出了三种不同的基本蚁群算法模型，分别称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型，其差别在于
求法的不同。
在Ant-Cycle模型中
(5)
式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；
表示
只蚂蚁在本次循环中所走路径的总长度。
在Ant-Quantity模型中
(6)
在Ant-Density模型中
(7)
区别：式(6)和式(7)中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而式(5)中利用的是整体信息，即蚂蚁完成一个循环后更新所有路径上的信息素，在求解TSP时性能较好，因此通常采用式(5)作为蚁群算法的基本模型。
1.2 基本蚁群算法的实现
以下是解决TSP问题的蚁群算法的基本
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
描述，其中的参数设置来自于Dorigo等人的试验。基本蚁群算法的具体实现步骤如下：
(1) 参数初始化。令时间t=0和循环次数
，设置最大循环次数
，将m蚂蚁置于n个元素(城市)上，另有向图上每条边
的初始化信息量
，其中const表示常数，且初始时刻
。
(2) 循环次数
。
(3) 蚂蚁等禁忌表索引号k=1。
(4) 蚂蚁数目
。
(5) 蚂蚁个体根据状态转移概率
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
(1)计算的概率选择元素(城市)
并前进，
(6) 修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素(城市)，并把该元素(城市)移动到该蚂蚁个体的禁忌表中。
(7) 若集合C中元素(城市)未遍历完，即k
=rand); %当累积概率和大于给定的随机数，则选择个被加上的最后一个城市作为即将访问的城市
to_visit=J(Select(1)); %to_visit表示即将访问的城市
Tabu(i,j)=to_visit; %将访问过的城市加入禁忌表中
end
end
if NC>=2 %如果迭代次数大于等于2，则将上一次迭代的最佳路线存入Tabu的第一行中
Tabu(1,:)=R_best(NC-1,:);
end
%% 第四步：记录本次迭代最佳路线
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1)); %求路径距离
end
L(i)=L(i)+D(R(1),R(n)); %加上最后一个城市与第一个城市之间的距离
end
L_best(NC)=min(L); %最优路径为距离最短的路径
pos=find(L==L_best(NC)); %找出最优路径对应的位置：即是哪只个蚂蚁
R_best(NC,:)=Tabu(pos(1),:); %确定最优路径对应的城市顺序
L_ave(NC)=mean(L); %求第k次迭代的平均距离
NC=NC+1;
%% 第五步：更新信息素
Delta_Tau=zeros(n,n); %Delta_Tau（i,j）表示所有的蚂蚁留在第i个城市到第j个城市路径上的信息素增量
for i=1:m
for j=1:(n-1) %建立了完整路径后路径后在释放信息素：蚁周系统Q/L
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau; %信息素更新公式
%% 第六步：禁忌表清零
Tabu=zeros(m,n); %每迭代一次都将禁忌表清零
end
%% 第七步：输出结果
Pos=find(L_best==min(L_best)); %找到L_best中最小值所在的位置并赋给Pos
Shortest_Route=R_best(Pos(1),:); %提取最短路径
Shortest_Length=L_best(Pos(1)); %提取最短路径的长度
C: 函数文件2
%% 绘制各个位置坐标即利用ACA找到的最优路径的函数 DrawCity.m
function DrawCity(C,T,R)
%% C Coordinate 节点坐标，由一个N×2的矩阵存储
%% T text 各城市的说明
%% R Route 路线
%%====================================================================
N=length(R);
scatter(C(:,1),C(:,2),'*','LineWidth',3);hold on; %绘制散点图
scatter(C(:,1),C(:,2),'r','LineWidth',2);hold on; %绘制散点图
%[C(R(1),1),C(R(N),1)]最佳路径第一个城市和最后一个城市的横坐标
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)],'m','LineWidth',2);hold on;
for ii=2:N %绘制其他城市之间的连线
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'-','LineWidth',2); hold on;
end
for k=1:length(C(:,1)) %城市标注
text(C(k,1)+0.2,C(k,2)+0.3,T(2*k-1:2*k)); hold on;
浙公网安备 33021202002483