tij(t+1)=(1-r)tij(t)+Dtij,Dtij=
其中:
Dtijk表示蚂蚁k在城市i与城市j的连接路径上,释放的信息素浓度
Dtij表示所有蚂蚁在城市i与城市j的连接路径上,释放的信息素浓度。
(2)、Dtijk的计算方法
Dtijk=
其中:
Q为常数,表示蚂蚁循环一次释放的信息素的总量;
dij为第k只蚂蚁经过路径的长度,Length;
3.算法实现步骤
1、初始化参数
蚂蚁数量m,信息素重要程度a,启发函数重要程度b,信息素挥发因子r,信息素释放总量Q,最大迭代次数iter_max。
获取各城市之间的距离dij,为了保证启发式函数hij=1/dij能顺利进行,对于i=j即自己到自己的距离不能给为0,而是给成一个很小的距离,如10-4或10-5。
2、构建解空间
将各个蚂蚁随机地置于不同出发点,对每个蚂蚁按归照下式,确定下一城市。
3、更新信息素
计算各个蚂蚁经过的路径长度Lk,记录当前迭代次数中的最优解(即最短路径),根据如下公式更新信息素:
tij(t+1)=(1-r)tij(t)+Dtij,Dtij=
Dtijk=
4、判断是否终止
若没有到最大次数,则清空蚂蚁经过路径的记录表,返回步骤2。
4.相关实验
4.1实验内容
1、访问我国每个省会城市一次也仅一次的最短路径,共有31个
2、如果采用枚举法,巡回路径可能1.326´1032种。
3、城市的坐标citys,这是直角坐标,根据二个城市的坐标值,可以用D=可计算出任意二个城市间的距离。
citys=13042312
36391315
41772244
37121399
34881535
33261556
32381229
41961004
4312790
4386570
30071970
25621756
27881491
23811676
1332695
37151678
39182179
40612370
37802212
36762578
40292838
42632931
34291908
35072367
33942643
34393201
29353240
31403550
25452357
27782826
23702975
4.2实验代码
%%清空环境变量
clearall
clc
loadcitys_data.mat%%导入数据
%%计算城市间相互距离
n=size(citys,1);%城市的个数
D=zeros(n,n);%n行n列的矩阵,即任意二个城市之间的距离
fori=1:
n
forj=1:
n
ifi~=j
D(i,j)=sqrt(sum((citys(i,:
)-citys(j,:
)).^2));
else
D(i,j)=1e-4;
end
end
end
%%初始化参数
m=50;%蚂蚁数量
alpha=1;%信息素重要程度因子
beta=5;%启发函数重要程度因子
rho=0.1;%信息素挥发因子
Q=1;%常系数
Eta=1./D;%启发函数
Tau=ones(n,n);%信息素矩阵,全1矩阵
Table=zeros(m,n);%路径记录表,全0矩阵,每只蚂蚁依次走过的城市
iter=1;%迭代次数初值
iter_max=200;%最大迭代次数
Route_best=zeros(iter_max,n);%各代最佳路径
Length_best=zeros(iter_max,1);%各代最佳路径的长度
Length_ave=zeros(iter_max,1);%各代路径的平均长度
%%迭代寻找最佳路径
whileiter<=iter_max
%随机产生各个蚂蚁的起点城市
start=zeros(m,1);%m是蚂蚁的个数,m行1列的矩阵,记录每个蚂蚁的城市编号
fori=1:
m
temp=randperm(n);
start(i)=temp
(1);
end
Table(:
1)=start;%路径记录表的1列,为每个蚂蚁的起点城市
%构建解空间
citys_index=1:
n;
%逐个蚂蚁路径选择
fori=1:
m
%逐个城市路径选择
forj=2:
n
tabu=Table(i,1:
(j-1));%已访问的城市集合(禁忌表)
allow_index=~ismember(citys_index,tabu);%不是tabu的城市就是要访问的城市
allow=citys_index(allow_index);%待访问的城市集合
P=allow;
fork=1:
length(allow)%计算城市间转移概率
P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;
end
P=P/sum(P);%规一化
%轮盘赌法选择下一个访问城市
Pc=cumsum(P);%依次累加,是实现轮盘赌法选择的方法
target_index=find(Pc>=rand);
target=allow(target_index
(1));
Table(i,j)=target;
end
end
%%结果显示
[Shortest_Length,index]=min(Length_best);
Shortest_Route=Route_best(index,:
);
disp(['最短距离:
'num2str(Shortest_Length)]);
disp(['最短路径:
'num2str([Shortest_RouteShortest_Route
(1)])]);
%%绘图
figure
(1)
plot([citys(Shortest_Route,1);citys(Shortest_Route
(1),1)],...
[citys(Shortest_Route,2);citys(Shortest_Route
(1),2)],'o-');
gridon
fori=1:
size(citys,1)
text(citys(i,1),citys(i,2),[''num2str(i)]);
end
text(citys(Shortest_Route
(1),1),citys(Shortest_Route
(1),2),'起点');
text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'终点');
xlabel('城市位置横坐标')
ylabel('城市位置纵坐标')
title(['蚁群算法优化路径(最短距离:
'num2str(Shortest_Length)')'])
figure
(2)
plot(1:
iter_max,Length_best,'b',1:
iter_max,Length_ave,'r:
')
legend('最短距离','平均距离')
xlabel('迭代次数')
ylabel('距离')
title('各代最短距离与平均距离对比')
4.3实验结果与分析
使用不同的蚁群数量和迭代次数后求得的最短距离和最短路径如下所示:
1.蚁群数50,迭代次数200
最短距离:
15601.9195
最短路径:
1412131123165672489103181719242520212226282730312911514
2.蚁群数50,迭代次数100
最短距离:
15972.7648
最短路径:
115131214291123165672489103181719242520212226282730311
3.蚁群数100,迭代次数100
最短距离:
15601.9195
最短路径:
1412131123165672489103181719242520212226282730312911514
4.蚁群数50,迭代次数300
最短距离:
15601.9195
最短路径:
115141213112316567248910318171924252021222628273031291
5.蚁群数100,迭代次数200
最短距离:
15601.9195
最短路径:
1412131123165672489103181719242520212226282730312911514
6.蚁群数100,迭代次数300
最短距离:
15553.0468
最短路径:
1098425671312141512931302728262122183171924202511231610
7.蚁群数150,迭代次数300
最短距离:
15601.9195
最短路径:
115141213112316567248910318171924252021222628273031291
从以上的实验结果可看出,蚁群数量和迭代次数对算法的实验结果有一定影响,当蚁群数确定时,随着迭代次数的增加,最短距离会有所减小,但增加到一定的程度,最短距离将不再变化;当迭代次数不变,随着蚁群数量的增加,最短距离也有一定的改进。
但增加到一定程度,最短距离还可能有所增加。
5.总结
本次实验是通过matlab编程来实现蚁群优化算法,通过实验结果,我们发现虽然我们找到了问题的最优解,但是最优解的收敛性并不乐观,并不能求得问题的精确解,并且随着参数的调节运行结果有随机性。
另外,在蚁群算法求解过程中,蚂蚁的数量和城市的数量差距对结果也是具有一定影响的。
当城市规模较大的时候,问题的复杂度呈指数增长,仅仅靠这样一个基础单一的信息素更新机制引导搜索偏向,搜索效率有瓶颈。
总的来说,该算法具有较强的自适应性,易于与其他方法组合,适用于解决组合优化问题。