声振论坛

 找回密码
 我要加入

QQ登录

只需一步,快速开始

查看: 3644|回复: 13

[编程技巧] 蚁群算法的MATLAB编程方面问题

[复制链接]
发表于 2006-3-26 10:17 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?我要加入

x

各位大虾:
小妹最近在研究蚁群算法,由于天生愚顿,总是不能开窍,困于MATLAB编程中不能自拔,望各位大哥大姐能够前来营救。
回复
分享到:

使用道具 举报

发表于 2006-4-1 06:59 | 显示全部楼层
该程序试图对具有31个城市的VRP进行求解,已知的最优解为784.1,我用该程序只能优化到810左右,应该是陷入局部最优,但我不知问题出在什么地方。请用过蚁群算法的高手指教。


蚁群算法的matlab源码,同时请指出为何不能优化到已知的最好解



  1. %
  2. %
  3. % the procedure of ant colony algorithm for VRP
  4. %
  5. % % % % % % % % % % %

  6. %initialize the parameters of ant colony algorithms
  7. load data.txt;
  8. d=data(:,2:3);
  9. g=data(:,4);

  10. m=31; % 蚂蚁数
  11. alpha=1;
  12. belta=4;% 决定tao和miu重要性的参数
  13. lmda=0;
  14. rou=0.9; %衰减系数
  15. q0=0.95;
  16. % 概率
  17. tao0=1/(31*841.04);%初始信息素
  18. Q=1;% 蚂蚁循环一周所释放的信息素
  19. defined_phrm=15.0; % initial pheromone level value
  20. QV=100; % 车辆容量
  21. vehicle_best=round(sum(g)/QV)+1; %所完成任务所需的最少车数
  22. V=40;

  23. % 计算两点的距离
  24. for i=1:32;
  25. for j=1:32;
  26. dist(i,j)=sqrt((d(i,1)-d(j,1))^2+(d(i,2)-d(j,2))^2);
  27. end;
  28. end;

  29. %给tao miu赋初值
  30. for i=1:32;
  31. for j=1:32;
  32. if i~=j;
  33. %s(i,j)=dist(i,1)+dist(1,j)-dist(i,j);
  34. tao(i,j)=defined_phrm;
  35. miu(i,j)=1/dist(i,j);
  36. end;
  37. end;
  38. end;

  39. for k=1:32;
  40. for k=1:32;
  41. deltao(i,j)=0;
  42. end;
  43. end;

  44. best_cost=10000;
  45. for n_gen=1:50;


  46. print_head(n_gen);

  47. for i=1:m;
  48. %best_solution=[];
  49. print_head2(i);
  50. sumload=0;
  51. cur_pos(i)=1;
  52. rn=randperm(32);
  53. n=1;
  54. nn=1;
  55. part_sol(nn)=1;
  56. %cost(n_gen,i)=0.0;
  57. n_sol=0; % 由蚂蚁产生的路径数量
  58. M_vehicle=500;
  59. t=0; %最佳路径数组的元素数为0

  60. while sumload<=QV;

  61. for k=1:length(rn);
  62. if sumload+g(rn(k))<=QV;
  63. gama(cur_pos(i),rn(k))=(sumload+g(rn(k)))/QV;
  64. A(n)=rn(k);
  65. n=n+1;
  66. end;
  67. end;

  68. fid=fopen('out_customer.txt','a+');
  69. fprintf(fid,'%s %i\t','the current position is:',cur_pos(i));
  70. fprintf(fid,'\n%s','the possible customer set is:')
  71. fprintf(fid,'\t%i\n',A);
  72. fprintf(fid,'------------------------------\n');
  73. fclose(fid);

  74. p=compute_prob(A,cur_pos(i),tao,miu,alpha,belta,gama,lmda,i);
  75. maxp=1e-8;
  76. na=length(A);
  77. for j=1:na;
  78. if p(j)>maxp
  79. maxp=p(j);
  80. index_max=j;
  81. end;
  82. end;

  83. old_pos=cur_pos(i);
  84. if rand(1)<q0
  85. cur_pos(i)=A(index_max);
  86. else
  87. krnd=randperm(na);
  88. cur_pos(i)=A(krnd(1));
  89. bbb=[old_pos cur_pos(i)];
  90. ccc=[1 1];
  91. if bbb==ccc;
  92. cur_pos(i)=A(krnd(2));
  93. end;
  94. end;

  95. tao(old_pos,cur_pos(i))=taolocalupdate(tao(old_pos,cur_pos(i)),rou,tao0);%对所经弧进行局部更新

  96. sumload=sumload+g(cur_pos(i));

  97. nn=nn+1;
  98. part_sol(nn)=cur_pos(i);
  99. temp_load=sumload;

  100. if cur_pos(i)~=1;
  101. rn=setdiff(rn,cur_pos(i));
  102. n=1;
  103. A=[];
  104. end;

  105. if cur_pos(i)==1; % 如果当前点为车场,将当前路径中的已访问用户去掉后,开始产生新路径
  106. if setdiff(part_sol,1)~=[];
  107. n_sol=n_sol+1; % 表示产生的路径数,n_sol=1,2,3,..5,6...,超过5条对其费用加上车辆的派遣费用
  108. fid=fopen('out_solution.txt','a+');
  109. fprintf(fid,'%s%i%s','NO.',n_sol,'条路径是:');
  110. fprintf(fid,'%i ',part_sol);
  111. fprintf(fid,'\n');
  112. fprintf(fid,'%s','当前的用户需求量是:');
  113. fprintf(fid,'%i\n',temp_load);
  114. fprintf(fid,'------------------------------\n');
  115. fclose(fid);

  116. % 对所得路径进行路径内3-opt优化
  117. final_sol=exchange(part_sol);

  118. for nt=1:length(final_sol); % 将所有产生的路径传给一个数组
  119. temp(t+nt)=final_sol(nt);
  120. end;
  121. t=t+length(final_sol)-1;

  122. sumload=0;
  123. final_sol=setdiff(final_sol,1);
  124. rn=setdiff(rn,final_sol);
  125. part_sol=[];
  126. final_sol=[];
  127. nn=1;
  128. part_sol(nn)=cur_pos(i);
  129. A=[];
  130. n=1;

  131. end;
  132. end;

  133. if setdiff(rn,1)==[];% 产生最后一条终点不为1的路径
  134. n_sol=n_sol+1;
  135. nl=length(part_sol);
  136. part_sol(nl+1)=1;%将路径的最后1位补1

  137. % 对所得路径进行路径内3-opt优化
  138. final_sol=exchange(part_sol);

  139. for nt=1:length(final_sol); % 将所有产生的路径传给一个数组
  140. temp(t+nt)=final_sol(nt);
  141. end;

  142. cost(n_gen,i)=cost_sol(temp,dist)+M_vehicle*(n_sol-vehicle_best); %计算由蚂蚁i产生的路径总长度

  143. for ki=1:length(temp)-1;
  144. deltao(temp(ki),temp(ki+1))=deltao(temp(ki),temp(ki+1))+Q/cost(n_gen,i);
  145. end;

  146. if cost(n_gen,i)<best_cost;
  147. best_cost=cost(n_gen,i);
  148. old_cost=best_cost;
  149. best_gen=n_gen; % 产生最小费用的代数
  150. best_ant=i; %产生最小费用的蚂蚁
  151. best_solution=temp;
  152. end;

  153. if i==m;  %如果所有蚂蚁均完成一次循环,,则用最佳费用所对应的路径对弧进行整体更新
  154. for ii=1:32;
  155. for jj=1:32;
  156. tao(ii,jj)=(1-rou)*tao(ii,jj);
  157. end;
  158. end;

  159. for kk=1:length(best_solution)-1;
  160. tao(best_solution(kk),best_solution(kk+1))=tao(best_solution(kk),best_solution(kk+1))+deltao(best_solution(kk),best_solution(kk+1));
  161. end;
  162. end;

  163. fid=fopen('out_solution.txt','a+');
  164. fprintf(fid,'%s%i%s','NO.',n_sol,'路径是:');
  165. fprintf(fid,'%i ',part_sol);
  166. fprintf(fid,'\n');
  167. fprintf(fid,'%s %i\n','当前的用户需求量是:',temp_load);
  168. fprintf(fid,'%s %f\n','总费用是:',cost(n_gen,i));
  169. fprintf(fid,'------------------------------\n');
  170. fprintf(fid,'%s\n','最终路径是:');
  171. fprintf(fid,'%i-',temp);
  172. fprintf(fid,'\n');
  173. fclose(fid);
  174. temp=[];
  175. break;
  176. end;
  177. end;

  178. end;
  179. end;
复制代码

 楼主| 发表于 2006-4-4 20:40 | 显示全部楼层
感谢你的参与哦~大家一起来学习吧~加油!
发表于 2006-4-4 20:42 | 显示全部楼层
还没听说过蚁群算法,我是不是还没有入门??

发现MATLAB一个问题:为什么别人写的程序不大容易看懂呢?

[ 本帖最后由 ChaChing 于 2009-6-30 19:08 编辑 ]
发表于 2006-4-5 07:41 | 显示全部楼层

不是matlab的问题,是所有的程序都一样
每个人的编程思路都不一样

只不过matlab实现的方法更灵活一点,所以感觉更加强烈一些
发表于 2006-4-5 13:57 | 显示全部楼层
同感
发表于 2006-4-14 11:54 | 显示全部楼层

大家知道 怎么用遗传算法解决背包问题吗?

小弟目前在看有关遗传算法解决背包问题的MATLAB方法,但不知如何下手!请各位大侠指点小弟~~
发表于 2006-4-14 19:54 | 显示全部楼层
好像在一篇博士论文里有,查查去哦
发表于 2006-4-17 12:37 | 显示全部楼层
你自己看看吧 也不一定用的上
发表于 2008-5-29 21:55 | 显示全部楼层

回复 6楼 的帖子

请问下 你这个程序里边的
data.txt
能给发下么?
发表于 2008-5-29 22:03 | 显示全部楼层
加我QQ 396283379
有一些事情探讨!
发表于 2008-5-30 13:57 | 显示全部楼层

回复 2楼 的帖子

问下 你里边 调用了2个TXT,可以给我发下么
急用  谢谢了
邮箱:396283379@qq.com
麻烦了
发表于 2009-6-29 19:23 | 显示全部楼层

小女子同求data文件

邮箱是330761097@qq.com
不胜感激
发表于 2011-2-26 19:24 | 显示全部楼层
回复 13 # zzh121300 的帖子

同求data文件
邮箱是chen_jinguo@163.com
不胜感激
您需要登录后才可以回帖 登录 | 我要加入

本版积分规则

QQ|小黑屋|Archiver|手机版|联系我们|声振论坛

GMT+8, 2024-11-25 21:23 , Processed in 0.064429 second(s), 19 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表