蚁群算法解决TSP问题(c++)

admin

1. #include<iostream>
2. #include<stdio.h>
3. #include<string>
4. #include<string.h>
5. #include<cmath>
6. #include<ctime>
7. #include<stdlib.h>
8. using namespace std;
9. int seed=(int)time(0);//产生随机种子
10. int CityPos[30][2]= {{87,7},{91,38},{83,46},{71,44},{64,60},{68,58},{83,69},{87,76},{74,78},{71,71},{58,69},{54,62},{51,67},{37,84},{41,94},{2,99},{7,64},{22,60},{25,62},{18,54},{4,50},{13,40},{18,40},{24,42},{25,38},{41,26},{45,21},{44,35},{58,35},{62,32}};
11. #define CITY_NUM 30//城市数量
12. #define ANT_NUM 30//蚁群数量
13. #define TMAC 10000//迭代最大次数
14. #define ROU 0.5//误差大小
15. #define ALPHA 1//信息素重要程度的参数
16. #define BETA 4//启发式因子重要程度的参数
17. #define Q 100//信息素残留参数
18. #define maxn 100
19. #define inf 0x3f3f3f3f
20. double dis[maxn][maxn];//距离矩阵
21. double info[maxn][maxn];//信息素矩阵
22. bool vis[CITY_NUM][CITY_NUM];//标记矩阵
24. //返回指定范围内的随机整数
25. int rnd(int low,int upper)
26. {
27.     return low+(upper-low)*rand()/(RAND_MAX+1);
28. }
30. //返回指定范围内的随机浮点数
31. double rnd(double low,double upper)
32. {
33.     double temp=rand()/((double)RAND_MAX+1.0);
34.     return low+temp*(upper-low);
35. }
37. struct Ant
38. {
39.     int path[CITY_NUM];//保存蚂蚁走的路径
40.     double length;//路径总长度
41.     bool vis[CITY_NUM];//标记走过的城市
42.     int cur_cityno;//当前城市
43.     int moved_cnt;//已走城市数量
45.     //初始化
46.     void Init()
47.     {
48.         memset(vis,false,sizeof(vis));
49.         length=0;
50.         cur_cityno=rnd(0,CITY_NUM);
51.         path[0]=cur_cityno;
52.         vis[cur_cityno]=true;
53.         moved_cnt=1;
54.     }
56.     //选择下一个城市
57.     int Choose()
58.     {
59.         int select_city=-1;//所选城市编号
60.         double sum=0;
61.         double prob[CITY_NUM];//保存每个城市被选中的概率
62.         for(int i=0; i<CITY_NUM; i++)
63.         {
64.             if(!vis[i])
65.             {
66.                 prob[i]=pow(info[cur_cityno][i],ALPHA)*pow(1.0/dis[cur_cityno][i], BETA);
67.                 sum=sum+prob[i];
68.             }
69.             else
70.             {
71.                 prob[i]=0;
72.             }
73.         }
74.         //进行轮盘选择
75.         double temp=0;
76.         if(sum>0)//总的信息素大于0
77.         {
78.             temp=rnd(0.0,sum);
79.             for(int i=0; i<CITY_NUM; i++)
80.             {
81.                 if(!vis[i])
82.                 {
83.                     temp=temp-prob[i];
84.                     if(temp<0.0)
85.                     {
86.                         select_city=i;
87.                         break;
88.                     }
89.                 }
90.             }
91.         }
92.         else //信息素太少就随便找个没走过的城市
93.         {
94.             for(int i=0; i<CITY_NUM; i++)
95.             {
96.                 if(!vis[i])
97.                 {
98.                     select_city=i;
99.                     break;
100.                 }
101.             }
102.         }
103.         return select_city;
104.     }
106.     //蚂蚁的移动
107.     void Move()
108.     {
109.         int nex_cityno=Choose();
110.         path[moved_cnt]=nex_cityno;
111.         vis[nex_cityno]=true;
112.         length=length+dis[cur_cityno][nex_cityno];
113.         cur_cityno=nex_cityno;
114.         moved_cnt++;
115.     }
117.     //蚂蚁进行一次迭代
118.     void Search()
119.     {
120.         Init();
121.         while(moved_cnt<CITY_NUM)
122.         {
123.             Move();
124.         }
125.         //回到原来的城市
126.         length=length+dis[path[CITY_NUM-1]][path[0]];
127.     }
128. };
130. struct TSP
131. {
132.     Ant ants[ANT_NUM];//定义蚁群
133.     Ant ant_best;//最优路径蚂蚁
135.     void Init()
136.     {
137.         //初始化为最大值
138.         ant_best.length = inf;
139.         //计算两两城市间距离
140.         for (int i = 0; i < CITY_NUM; i++)
141.         {
142.             for (int j = 0; j < CITY_NUM; j++)
143.             {
144.                 info[i][j]=1.0;
145.                 double temp1=CityPos[j][0]-CityPos[i][0];
146.                 double temp2=CityPos[j][1]-CityPos[i][1];
147.                 dis[i][j] = sqrt(temp1*temp1+temp2*temp2);
148.             }
149.         }
150.     }
152.     //更新信息素
153.     void UpdateInfo()
154.     {
155.         double temp_info[CITY_NUM][CITY_NUM];
156.         memset(temp_info,0,sizeof(temp_info));
157.         int u,v;
158.         for(int i=0; i<ANT_NUM; i++) //遍历每一只蚂蚁
159.         {
160.             for(int j=1; j<CITY_NUM; j++)
161.             {
162.                 u=ants[i].path[j-1];
163.                 v=ants[i].path[j];
164.                 temp_info[u][v]=temp_info[u][v]+Q/ants[i].length;
165.                 temp_info[v][u]=temp_info[u][v];
166.             }
167.             //最后城市和开始城市之间的信息素
168.             u=ants[i].path[0];
169.             temp_info[u][v]=temp_info[u][v]+Q/ants[i].length;
170.             temp_info[v][u]=temp_info[u][v];
171.         }
172.         for(int i=0; i<CITY_NUM; i++)
173.         {
174.             for(int j=0; j<CITY_NUM; j++)
175.             {
176.                 info[i][j]=info[i][j]*ROU+temp_info[i][j];
177.             }
178.         }
179.     }
180.     void Search()
181.     {
182.         //迭代TMAC次
183.         for(int i=0; i<TMAC; i++)
184.         {
185.             //所有蚂蚁都进行一次遍历
186.             for(int j=0; j<ANT_NUM; j++)
187.             {
188.                 ants[j].Search();
189.             }
190.             //保存所有蚂蚁遍历的最佳结果
191.             for(int j=0; j<ANT_NUM; j++)
192.             {
193.                 if(ant_best.length>ants[j].length)
194.                 {
195.                     ant_best=ants[j];
196.                 }
197.             }
198.             UpdateInfo();
199.             printf("第%d次迭代最优路径长度是%lf\n", i,ant_best.length);
200.             printf("\n");
201.         }
202.     }
203. };
204. int main()
205. {
206.     srand(seed);
207.     TSP tsp;
208.     tsp.Init();
209.     tsp.Search();
210.     printf("最短路径如下\n");
211.     for(int i=0;i<CITY_NUM;i++)
212.     {
213.         printf("%d",tsp.ant_best.path[i]);
214.         if(i<CITY_NUM-1)
215.             printf("->");
216.         else
217.             printf("\n");
218.     }
219.     return 0;
220. }

复制代码