蚁群算法解决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];//标记矩阵
    
23. 
    
24. //返回指定范围内的随机整数
    
25. int rnd(int low,int upper)
    
26. {
    
27.     return low+(upper-low)*rand()/(RAND_MAX+1);
    
28. }
    
29. 
    
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. }
    
36. 
    
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;//已走城市数量
    
44. 
    
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.     }
    
55. 
    
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.     }
     
105. 
     
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.     }
     
116. 
     
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. };
     
129. 
     
130. struct TSP
     
131. {
     
132.     Ant ants[ANT_NUM];//定义蚁群
     
133.     Ant ant_best;//最优路径蚂蚁
     
134. 
     
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.     }
     
151. 
     
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. }

复制代码