蚁群算法（ACO）学习笔记

admin

1. [code]https://blog.csdn.net/fulongxu/article/details/99678958?ops_request_misc=&request_id=&biz_id=102&utm_term=c++%20%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~sobaiduweb~default-5-99678958.nonecase&spm=1018.2226.3001.4450

复制代码

[/code]

1. 1 6734 1453
2. 2 2233 10
3. 3 5530 1424
4. 4 401 841
5. 5 3082 1644
6. 6 7608 4458
7. 7 7573 3716
8. 8 7265 1268
9. 9 6898 1885
10. 10 1112 2049
11. 11 5468 2606
12. 12 5989 2873
13. 13 4706 2674
14. 14 4612 2035
15. 15 6347 2683
16. 16 6107 669
17. 17 7611 5184
18. 18 7462 3590
19. 19 7732 4723
20. 20 5900 3561
21. 21 4483 3369
22. 22 6101 1110
23. 23 5199 2182
24. 24 1633 2809
25. 25 4307 2322
26. 26 675 1006
27. 27 7555 4819
28. 28 7541 3981
29. 29 3177 756
30. 30 7352 4506
31. 31 7545 2801
32. 32 3245 3305
33. 33 6426 3173
34. 34 4608 1198
35. 35 23 2216
36. 36 7248 3779
37. 37 7762 4595
38. 38 7392 2244
39. 39 3484 2829
40. 40 6271 2135
41. 41 4985 140
42. 42 1916 1569
43. 43 7280 4899
44. 44 7509 3239
45. 45 10 2676
46. 46 6807 2993
47. 47 5185 3258
48. 48 3023 1942
51. #include<bits/stdc++.h>
52. #define Read() freopen("data.in","r",stdin)
53. #define Write() freopen("autocomplete.out","w",stdout)
56. using namespace std;
59. const int City_Num = 48;//城市数目
60. const int Ant_Num = 20;//蚂蚁数目
61. const int Total_Num = 2000;//迭代次数
63. double Distance[City_Num+5][City_Num+5];//保存距离
64. vector<int> Edge[City_Num+5][City_Num+5];//保存每条边有哪些蚂蚁走过
65. double Ant_length[Ant_Num+5];//保存每只蚂蚁一轮后走过的路径长度
66. double Edge_Info[City_Num+5][City_Num+5];//保存每条边的信息素
67. vector<int> Ant[Ant_Num+5];//保存每个蚂蚁的路径
68. int vis[Ant_Num+5][City_Num+5];//标记每个蚂蚁走过哪个城市
69. double Total_Length[Ant_Num+5];//记录每轮迭代后每只蚂蚁走的总路长
70. vector<int> Min_Path;
72. double Alpha = 1.0;
73. double Beta = 5.0;
74. double Rho = 0.5;
75. double Min_Length = 0x3f3f3f3f;
77. struct node
78. {
79.         int x, y;
80. }Node[City_Num+5];
82. double Get_distance(node a, node b)
83. {
84.         return sqrt((1.0*(a.x-b.x)*(a.x-b.x) + 1.0*(a.y-b.y)*(a.y-b.y))/10.0);
85. }
87. void Init()
88. {
89.        
90.         for(int i = 0; i < City_Num; i++)
91.         {
92.                 Distance[i][i] = 0;
93.                 Edge_Info[i][i] = 0;
94.                 for(int j = i+1; j < City_Num; j++)
95.                 {
96.                         Distance[i][j] = Get_distance(Node[i], Node[j]);
97.                         Distance[j][i] = Distance[i][j];
98.                         Edge_Info[i][j] = 0.1;
99.                         Edge_Info[j][i] = 0.1;
100.                 }
101.         }
102. }
104. int Rand()
105. {
106.         return rand()%48;
107. }
109. double Rand_Double()
110. {
111.         return (rand()%10000)/10000.0;
112. }
114. void Build_Path()
115. {
116.         for(int i = 0; i < Ant_Num; i++)
117.         {
118.                 while(Ant[i].size() != City_Num)
119.                 {
120.                         double sum = 0.0;
121.                         double p_go[City_Num+5];//计算访问下一个城市的概率
122.                         memset(p_go, 0, sizeof(p_go));
123.                        
124.                         int total_pos = Ant[i].size();
125.                         int now_pos = Ant[i][total_pos-1];
126.                        
127.                         for(int j = 0; j < City_Num; j++)
128.                         {
129.                                 if(vis[i][j]) continue;
130.                                 p_go[j] = pow(Edge_Info[now_pos][j], Alpha)*pow((1.0/Distance[now_pos][j]), Beta);
131.                                 sum += p_go[j];
132.                         }
133.                        
134.                         double p = Rand_Double();
135.                         double p_total = 0;
136.                        
137.                         for(int j = 0; j < City_Num; j++)
138.                         {
139.                                 if(vis[i][j]) continue;
140.                                
141.                                 if(p_total+(p_go[j]/sum) >= p)//下一个访问的城市是j
142.                                 {
143.                                         vis[i][j] = 1;//标记该城市已经走过
144.                                         Ant[i].push_back(j);//把这个城市加到城市列表中
145.                                         Total_Length[i] += Distance[now_pos][j];//计算第i只蚂蚁当前一共走的距离
146.                                         Edge[now_pos][j].push_back(i);//记录走过这条边的蚂蚁，用来更新信息素矩阵
147.                                         break;
148.                                 }
149.                                 else
150.                                 {
151.                                         p_total += (p_go[j]/sum);
152.                                 }
153.                         }
154.                 }
155.                 Total_Length[i] += Distance[Ant[i][City_Num-1]][Ant[i][0]];//将终点到起点的路长加入到总路长中
156.                 Edge[Ant[i][City_Num-1]][Ant[i][0]].push_back(i);//终点指向起点的路的蚂蚁记录一下
157.                 if(Min_Length > Total_Length[i])//寻找全局最短路径,并记录路径
158.                 {
159.                         Min_Length = Total_Length[i];
160.                         Min_Path.clear();
161.                         for(int k = 0; k < City_Num; k++)
162.                                 Min_Path.push_back(Ant[i][k]);
163.                         Min_Path.push_back(Ant[i][0]);
164.                 }
165.         }
166. }
168. double Get_Edge_P(int x, int y)
169. {
170.         int n = Edge[x][y].size();
171.         double sum = 0.0;
172.         for(int i = 0; i < n; i++)
173.         {
174.                 int ant = Edge[x][y][i];
175.                 sum += 1.0/Total_Length[ant];
176.         }
177.         return sum;
178. }
180. void Change_Info()
181. {
182.         for(int i = 0; i < City_Num; i++)
183.         {
184.                 for(int j = i+1; j < City_Num; j++)
185.                 {
186.                         double edge_p = Get_Edge_P(i, j);
187.                         Edge_Info[i][j] = (1.0-Rho)*Edge_Info[i][j] + edge_p;
188.                         Edge_Info[i][j] = Edge_Info[j][i];
189.                 }
190.         }
191. }
193. void Print()
194. {
195.         cout<<Min_Length<<endl;
196.         for(int i = 0; i < City_Num; i++)
197.                 cout<<Min_Path[i]<<"-->";
198.         cout<<Min_Path[City_Num]<<endl;
199. }
202. int main()
203. {
204.         srand(time(NULL));
205.         Read();
206.         for(int i = 0; i < City_Num; i++)
207.         {
208.                 int num, x, y;
209.                 cin >>num>>x>>y;
210.                 Node[i].x = x;
211.                 Node[i].y = y;
212.         }
213.        
214.         for(int i = 0; i < 48; i++)
215.                 cout<<i+1<<" "<<Node[i].x<<" "<<Node[i].y<<endl;
216.         cout<<endl<<endl;
217.        
218.         Init();
219.         int T = Total_Num;
220.        
221.         while(T--)
222.         {
223.                 memset(vis, 0, sizeof(vis));
224.                 for(int i = 0; i < Ant_Num; i++)
225.                 {
226.                         Ant[i].clear();
227.                         Total_Length[i] = 0;
228.                 }
229.                
230.                 for(int i = 0; i < Ant_Num; i++)
231.                 {
232.                         int start_city = Rand();
233.                         vis[i][start_city] = 1;
234.                         Ant[i].push_back(start_city);
235.                 }
236.                
237.                 Build_Path();//构建路径
238.                 Change_Info();//信息素更新
239.         }
240.        
241.         Print();//打印最优路径
242.        
243.         return 0;
244. }

复制代码