蚁群算法（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
    
49. 
    
50. 
    
51. #include<bits/stdc++.h>
    
52. #define Read() freopen("data.in","r",stdin)
    
53. #define Write() freopen("autocomplete.out","w",stdout)
    
54. 
    
55. 
    
56. using namespace std;
    
57. 
    
58. 
    
59. const int City_Num = 48;//城市数目
    
60. const int Ant_Num = 20;//蚂蚁数目
    
61. const int Total_Num = 2000;//迭代次数
    
62. 
    
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;
    
71. 
    
72. double Alpha = 1.0;
    
73. double Beta = 5.0;
    
74. double Rho = 0.5;
    
75. double Min_Length = 0x3f3f3f3f;
    
76. 
    
77. struct node
    
78. {
    
79.         int x, y;
    
80. }Node[City_Num+5];
    
81. 
    
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. }
    
86. 
    
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. }
     
103. 
     
104. int Rand()
     
105. {
     
106.         return rand()%48;
     
107. }
     
108. 
     
109. double Rand_Double()
     
110. {
     
111.         return (rand()%10000)/10000.0;
     
112. }
     
113. 
     
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. }
     
167. 
     
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. }
     
179. 
     
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. }
     
192. 
     
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. }
     
200. 
     
201. 
     
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. }
     

复制代码