算法|蚁群算法简介及Matlab实现
概述 蚁群算法的基本思路很简单，即通过人工构造的蚂蚁去寻找最短路径。蚁群算法的基本假定如下：
- 开始时，蚁群随机寻找路径并释放信息素，信息量的多少与路径的长短成反比；
- 后续通过蚂蚁会偏向于走在信息素更多的路径上，同时释放信息素；
- 原有信息素会随时间推移而挥发；
- 重复几次后，越来越多的蚂蚁会聚集到最短的路径上。
流程 总流程图
否 是 开始 计算点之间距离 单次运行 运行次数已到? 输出最短路径最短长度平均长度 绘图 结束 运行结束条件，可以用次数判断，也可以用残差判断。
单次运行流程图
计算每只蚂蚁路径 否 是 否 是 否 是 给定一条路径起点和终点 计算剩余点中每个点被选中的概率 选择下一点 更新已经过的点和剩余点 剩余点数为0 输出该蚂蚁对应的路径 添加到该次运行路径集合 开始 所有蚂蚁都输出了路径? 更新蚂蚁路径上的信息素 所有路径上信息素都已经更新? 记录该次运行最短路径最短长度平均长度 更新最短路径及长度 结束 代码 本文用MATLAB来实现。
先生成供调用的方法ACO.m
function [Shortest_Route,Shortest_Length,ShortLengthList,MiddleLengthList]=ACO(cityList,originCityIndex,antCount,alpha,beta,rho,Q)
tic;
citySize=size( cityList);
ncityList=citySize(1);
distBetweenCity=zeros(ncityList);
%%城市之间距离矩阵
yitaBetweenCity=zeros(ncityList);
%%城市之间距离系数
tao=zeros(ncityList);
%%信息素浓度矩阵
for i=1:ncityList
for j=1:ncityList
distBetweenCity(i,j)=norm(cityList(i,:)-cityList(j,:));
if(i~=j)
yitaBetweenCity(i,j)=1/distBetweenCity(i,j);
end
end
endShortest_Length=sum(sum(distBetweenCity));
Shortest_Route=zeros(ncityList+1,1);
runsCount=200;
%%运行次数
ShortLengthList=zeros(runsCount,1);
MiddleLengthList=zeros(runsCount,1);
runsIndex=0;
%%运行次数
while(runsIndex<=runsCount)
allRoute=zeros(ncityList+1,antCount);
for kk=1:antCount%%对不同的蚂蚁循环
passedCity=zeros(ncityList+1,1);
%%经过的城市
passedCityIndex=1;
passedCity(passedCityIndex)=originCityIndex;
%%起点城市赋值
passedCity(ncityList+1)=originCityIndex;
%%终点城市赋值
for k=1:ncityList-1%%对剩余的点循环
selectionProbability=zeros(ncityList,1);
%%选择概率矩阵
for i=1:ncityList
seleced=1;
for j=1:ncityList
if(i==passedCity(j))
seleced=0;
break;
end
end
if(seleced==1)
selectionProbability(i)=tao(i,passedCity(passedCityIndex))^alpha*yitaBetweenCity(i,passedCity(passedCityIndex))^beta;
end
end
if(norm(selectionProbability)==0)
selectionProbability=ones(ncityList,1);
end
selectionProbability=selectionProbability/sum(selectionProbability);
totalProbability=zeros(ncityList,1);
totalProbability(1)=selectionProbability(1);
randValue=https://www.it610.com/article/rand(1,1);
nextCity=0;
%%下一个点的编号
if(randValue=totalProbability(i-1))
nextCity=i;
end
end
end
passedCityIndex=passedCityIndex+1;
passedCity(passedCityIndex)=nextCity;
end
allRoute(:,kk)=passedCity;
endtao=tao*(1-rho);
%%信息素挥发
lengthByEachAnt=zeros(antCount,1);
for kk=1:antCount%%更新信息素并选择最短路径
totalLength=0;
%%单条路径总长
passedCity=allRoute(:,kk);
for i=1:ncityList
totalLength=totalLength+distBetweenCity(passedCity(i),passedCity(i+1));
end
lengthByEachAnt(kk)=totalLength;
if(totalLength运行结果 在0
cityList=100*rand(100,2);
originCityIndex=5;
%%起点城市编号
alpha=1;
%%表征信息素重要程度的参数
beta=7;
%%表征启发式因子重要程度的参数
antCount=50;
%%蚂蚁数量
rho=0.3;
%%信息素蒸发系数
Q=1;
%%信息素增加强度系数
[Shortest_Route,Shortest_Length,ShortLengthList,MiddleLengthList]=ACO(cityList,originCityIndex,antCount,alpha,beta,rho,Q);
【算法|蚁群算法简介及Matlab实现】运行结果如下图示：
文章图片
最小距离为874.7373，非常接近理论上的最小路径长度。
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- java简介|Java是什么（Java能用来干什么？）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 7、前端--jQuery简介、基本选择器、基本筛选器、属性选择器、表单选择器、筛选器方法、节点操作、绑定事件