【原创】蚁群算法最短路径通用Matlab程序（附图）

aiwa

GreenSim团队的博客开通了，更多原创程序请访问我们的博客
http://blog.sina.com.cn/greensim

    下面的程序是蚁群算法在最短路中的应用，稍加扩展即可应用于机器人路径规划

1. function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q)
   
2. %% ---------------------------------------------------------------
   
3. % ACASP.m
   
4. % 蚁群算法动态寻路算法
   
5. % ChengAihua,PLA Information Engineering University,ZhengZhou,China
   
6. % Email:aihuacheng@gmail.com
   
7. % All rights reserved
   
8. %% ---------------------------------------------------------------
   
9. % 输入参数列表
   
10. % G 地形图为01矩阵，如果为1表示障碍物
    
11. % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素）
    
12. % K 迭代次数（指蚂蚁出动多少波）
    
13. % M 蚂蚁个数（每一波蚂蚁有多少个）
    
14. % S 起始点（最短路径的起始点）
    
15. % E 终止点（最短路径的目的点）
    
16. % Alpha 表征信息素重要程度的参数
    
17. % Beta 表征启发式因子重要程度的参数
    
18. % Rho 信息素蒸发系数
    
19. % Q 信息素增加强度系数
    
20. %
    
21. % 输出参数列表
    
22. % ROUTES 每一代的每一只蚂蚁的爬行路线
    
23. % PL 每一代的每一只蚂蚁的爬行路线长度
    
24. % Tau 输出动态修正过的信息素
    
25. 
    
26. %% --------------------变量初始化----------------------------------
    
27. %load
    
28. D=G2D(G);
    
29. N=size(D,1);%N表示问题的规模（象素个数）
    
30. MM=size(G,1);
    
31. a=1;%小方格象素的边长
    
32. Ex=a*(mod(E,MM)-0.5);%终止点横坐标
    
33. if Ex==-0.5
    
34. Ex=MM-0.5;
    
35. end
    
36. Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标
    
37. Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数
    
38. %下面构造启发式信息矩阵
    
39. for i=1:N
    
40. if ix==-0.5
    
41. ix=MM-0.5;
    
42. end
    
43. iy=a*(MM+0.5-ceil(i/MM));
    
44. if i~=E
    
45. Eta(1,i)=1/((ix-Ex)^2+(iy-Ey)^2)^0.5;
    
46. else
    
47. Eta(1,i)=100;
    
48. end
    
49. end
    
50. ROUTES=cell(K,M);%用细胞结构存储每一代的每一只蚂蚁的爬行路线
    
51. PL=zeros(K,M);%用矩阵存储每一代的每一只蚂蚁的爬行路线长度
    
52. %% -----------启动K轮蚂蚁觅食活动，每轮派出M只蚂蚁--------------------
    
53. for k=1:K
    
54. disp(k);
    
55. for m=1:M
    
56. %% 第一步：状态初始化
    
57. W=S;%当前节点初始化为起始点
    
58. Path=S;%爬行路线初始化
    
59. PLkm=0;%爬行路线长度初始化
    
60. TABUkm=ones(1,N);%禁忌表初始化
    
61. TABUkm(S)=0;%已经在初始点了，因此要排除
    
62. DD=D;%邻接矩阵初始化
    
63. %% 第二步：下一步可以前往的节点
    
64. DW=DD(W,:);
    
65. DW1=find(DW
    
66. for j=1:length(DW1)
    
67. if TABUkm(DW1(j))==0
    
68. DW(j)=inf;
    
69. end
    
70. end
    
71. LJD=find(DW
    
72. Len_LJD=length(LJD);%可选节点的个数
    
73. %% 觅食停止条件：蚂蚁未遇到食物或者陷入死胡同
    
74. while W~=E&&Len_LJD>=1
    
75. %% 第三步：转轮赌法选择下一步怎么走
    
76. PP=zeros(1,Len_LJD);
    
77. for i=1:Len_LJD
    
78. PP(i)=(Tau(W,LJD(i))^Alpha)*(Eta(LJD(i))^Beta);
    
79. end
    
80. PP=PP/(sum(PP));%建立概率分布
    
81. Pcum=cumsum(PP);
    
82. Select=find(Pcum>=rand);
    
83. %% 第四步：状态更新和记录
    
84. Path=[Path,to_visit];%路径增加
    
85. PLkm=PLkm+DD(W,to_visit);%路径长度增加
    
86. W=to_visit;%蚂蚁移到下一个节点
    
87. for kk=1:N
    
88. if TABUkm(kk)==0
    
89. DD(W,kk)=inf;
    
90. DD(kk,W)=inf;
    
91. end
    
92. end
    
93. TABUkm(W)=0;%已访问过的节点从禁忌表中删除
    
94. for j=1:length(DW1)
    
95. if TABUkm(DW1(j))==0
    
96. DW(j)=inf;
    
97. end
    
98. end
    
99. LJD=find(DW
    
100. Len_LJD=length(LJD);%可选节点的个数
     
101. end
     
102. %% 第五步：记下每一代每一只蚂蚁的觅食路线和路线长度
     
103. ROUTES{k,m}=Path;
     
104. if Path(end)==E
     
105. PL(k,m)=PLkm;
     
106. else
     
107. PL(k,m)=inf;
     
108. end
     
109. end
     
110. %% 第六步：更新信息素
     
111. Delta_Tau=zeros(N,N);%更新量初始化
     
112. for m=1:M
     
113. if PL(k,m) ROUT=ROUTES{k,m};
     
114. TS=length(ROUT)-1;%跳数
     
115. PL_km=PL(k,m);
     
116. for s=1:TS
     
117. x=ROUT(s);
     
118. Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;
     
119. end
     
120. end
     
121. end
     
122. Tau=(1-Rho).*Tau+Delta_Tau;%信息素挥发一部分，新增加一部分
     
123. end
     
124. %% ---------------------------绘图--------------------------------
     
125. plotif=1;%是否绘图的控制参数
     
126. if plotif==1
     
127. %绘收敛曲线
     
128. meanPL=zeros(1,K);
     
129. minPL=zeros(1,K);
     
130. for i=1:K
     
131. PLK=PL(i,:);
     
132. Nonzero=find(PLK
     
133. PLKPLK=PLK(Nonzero);
     
134. meanPL(i)=mean(PLKPLK);
     
135. minPL(i)=min(PLKPLK);
     
136. end
     
137. figure(1)
     
138. plot(minPL);
     
139. hold on
     
140. plot(meanPL);
     
141. grid on
     
142. title('收敛曲线（平均路径长度和最小路径长度）');
     
143. xlabel('迭代次数');
     
144. ylabel('路径长度');
     
145. %绘爬行图
     
146. figure(2)
     
147. axis([0,MM,0,MM])
     
148. for i=1:MM
     
149. for j=1:MM
     
150. if G(i,j)==1
     
151. x1=j-1;y1=MM-i;
     
152. x2=j;y2=MM-i;
     
153. x4=j-1;y4=MM-i+1;
     
154. fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]);
     
155. hold on
     
156. else
     
157. x1=j-1;y1=MM-i;
     
158. x2=j;y2=MM-i;
     
159. x3=j;y3=MM-i+1;
     
160. x4=j-1;y4=MM-i+1;
     
161. fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]);
     
162. hold on
     
163. end
     
164. end
     
165. end
     
166. hold on
     
167. LENROUT=length(ROUT);
     
168. Rx=ROUT;
     
169. Ry=ROUT;
     
170. for ii=1:LENROUT
     
171. Rx(ii)=a*(mod(ROUT(ii),MM)-0.5);
     
172. if Rx(ii)==-0.5
     
173. Rx(ii)=MM-0.5;
     
174. end
     
175. Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM));
     
176. end
     
177. plot(Rx,Ry)
     
178. end
     
179. plotif2=1;%绘各代蚂蚁爬行图
     
180. if plotif2==1
     
181. figure(3)
     
182. axis([0,MM,0,MM])
     
183. for i=1:MM
     
184. for j=1:MM
     
185. if G(i,j)==1
     
186. x1=j-1;y1=MM-i;
     
187. x2=j;y2=MM-i;
     
188. x4=j-1;y4=MM-i+1;
     
189. fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]);
     
190. hold on
     
191. else
     
192. x1=j-1;y1=MM-i;
     
193. x2=j;y2=MM-i;
     
194. x3=j;y3=MM-i+1;
     
195. x4=j-1;y4=MM-i+1;
     
196. fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]);
     
197. hold on
     
198. end
     
199. end
     
200. end
     
201. for k=1:K
     
202. PLK=PL(k,:);
     
203. minPLK=min(PLK);
     
204. pos=find(PLK==minPLK);
     
205. m=pos(1);
     
206. ROUT=ROUTES{k,m};
     
207. LENROUT=length(ROUT);
     
208. Rx=ROUT;
     
209. Ry=ROUT;
     
210. for ii=1:LENROUT
     
211. Rx(ii)=a*(mod(ROUT(ii),MM)-0.5);
     
212. if Rx(ii)==-0.5
     
213. Rx(ii)=MM-0.5;
     
214. end
     
215. Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM));
     
216. end
     
217. plot(Rx,Ry)
     
218. hold on
     
219. end
     
220. end

复制代码

将上述算法应用于机器人路径规划，优化效果如下图所示

【GreenSim团队简介】

——更多原创程序，请访问GreenSim团队的主页→http://blog.sina.com.cn/greensim

    GreenSim团队长期从事建模仿真、算法设计、代写程序等业务，为您提供实验、课题、论文、项目等方面的仿真服务。
    GreenSim团队擅长的学科领域主要有
【智能算法】遗传算法、模拟退火、神经网络、蚁群算法、免疫优化、支持向量机、拟物拟人
【运筹优化】数学建模、数值优化算法、大规模/非线性问题、组合优化、NP完全问题
【信息与通信】无线通信、信号处理、计算机网络
【其它学科】任何问题，只要能归结为数学问题或者算法仿真，我们都有实力和信心解决
    GreenSim团队的联系方式：
QQ: 330264704，535115369  Email：greensim@163.com（来 信 必 复）

[ 本帖最后由 aiwa 于 2007-3-18 13:37 编辑 ]

lp03041138

非常谢谢楼主啊

chinahaozi

我正结合蚁群算法准备创新一下，看看能否突破

dolphinyu

:) 好东西　收下了

wtfl65805357

非常谢谢楼主啊

chuzhongkuangke

中间有些子函数怎么没带啊？能不能给个说明阿

aiwa

原帖由 chuzhongkuangke 于 2007-8-18 06:12 发表
中间有些子函数怎么没带啊？能不能给个说明阿

就一个子函数没带而已，D=G2D(G); 它是把01形式存储的地图转化为图的赋权邻接矩阵的一个函数，你如果已经有了图的邻接矩阵，可不必用此函数。

CHENYJ821001

非常感谢！

jiangda06

什么叫土的邻接矩阵啊？:L :L

aiwa

原帖由 jiangda06 于 2007-8-27 12:11 发表
什么叫土的邻接矩阵啊？:L :L

请参看任何一本图论或者数据结构的书！

luck316girl

非常感谢，谢谢楼主

sunsbsbsb

不知道迭代学习算法的仿真怎么做，关于matlab编程的问题，楼主怎么没提到阿？

catyujian

xiexie !!!!!:lol

daimcwhut

Thank you!

笑少书

支持楼主！！！

liufumin123

非常谢谢楼主啊，分享了这么好的资料

gww0119

太高深了， 我这种低智商的人还用不着啊

小星星

中间有些子函数怎么没带啊？能不能给个说明阿