#include
2 #include
3 #include
4 #define BIG 999999
5 #define NumCities 8//共有8個作業//
6 #define NumAnts 4//螞蟻數為4//
7 #define RHO 0.8//費洛蒙蒸發係數=0.8//
8 #define q0 0.5
9 #define MAXITER 10//跑10圈//
10
11 float Tao[NumCities][NumCities];//初始費洛蒙//
12 int Tour[NumAnts][NumCities+1];//螞蟻的旅程//
13 int BestTour[NumCities+1];//最好的旅程//
14 int StartCity[NumAnts];//開始的作業//
15 int VisitedCities[NumAnts][NumCities];//走過的作業//
16 int AntInitInCity[NumCities];//螞蟻起點位於的作業//
17 int dist[NumCities][NumCities];//處理時間//
18 float SumLen[NumAnts];//路徑長//
19 float MinLenTour;//最小路徑長//
20 float Tao0; //初始費洛蒙//
21 int ChooseNextCity(int k, int antpos,int VisitedCities[NumAnts][NumCities],float Tao[NumCities][NumCities],int
22 dist[NumCities][NumCities]);
23 int NonVisitedCities(int k,int VisitedCities[NumAnts][NumCities]);
24
25 int finished;
26 int randcity;
27
28 int i,j,k,t;
29 int iter;
30
31 /* 預先宣告 */
32 float reentry_problem(int dist[NumCities][NumCities]);
33 float FindNewBestSolution(float MinLenTour, int Tour[NumAnts][NumCities+1],
34 float SumLen[NumAnts], int BestTour[NumCities+1]);
35 void PrintBestPath(int BestTour[NumCities+1]);
36
37
38 int main()
39 {
40
41 srand(12345);//起始亂數的產生//
42
43 MinLenTour = BIG;//最小路徑初始化//
44
45 Tao0 = 1.0/(reentry_problem(dist)*NumCities);//初始費洛蒙的值//
46 printf("Tao0 = %f Naivedist=%f\n",Tao0,reentry_problem(dist));
47
48 /* Init. pheromone level of each link */
49 for(i=0;i 50 for(j=0;j 51 Tao[i][j] = Tao0;//一開始每個作業路徑的費洛蒙都為Tao0//
52
53 /**************** main loop ******************/
54
55 for(iter=0;iter 56
57 /* 將每隻螞蟻放置在某個作業上*/
58
59 /* 目前沒有一個作業被螞蟻經過 */
60 for(k=0;k 61 for(j=0;j 62 VisitedCities[k][j] = 0;//螞蟻經過的作業陣列//
63 Tour[k][j] = 0;//螞蟻的旅程陣列,不懂幹嘛要+1//
64 }
65 Tour[k][j+1] = 0;//看沒有//
66 }
67
68 /* 置放螞蟻在某個作業 */
69 for(j=0;j 70 AntInitInCity[j] = 0; //能起始的作業只有0~3//
71
72 for(k=0;k 73 do {
74 randcity = rand()%NumCities;//起始的作業取亂數//
75 } while (AntInitInCity[randcity]);//do while為跑全部主體，再判斷條件，條件要加分號
76 //每隻螞蟻的最初起點為亂數的作業
77
78 AntInitInCity[randcity] = 1;//螞蟻起初位於的隨機作業=1?????????//
79 StartCity[k] = randcity;//螞蟻開始的作業//
80 VisitedCities[k][randcity] = 1;//已經經過的城市=1??????????//
81 Tour[k][0] = randcity;//第一個旅程為隨機的作業//
82 }
83
84 //----------------------------------------------------------------------------------------//
85
86 /* 螞蟻建立它們的旅程 */
87
88 t=0;//t=旅程的節點//
89 finished = 0;
90 do {
91 t = t+1;
92
93 /* 每隻螞蟻執行一個步驟 */
94 for(k=0;k 95
96 /* 選擇下一個作業 */
97 if(NonVisitedCities(k,VisitedCities)) {
98 Tour[k][t] = ChooseNextCity(k,Tour[k][t-1],VisitedCities,Tao,dist);
99 VisitedCities[k][Tour[k][t]] = 1;//???????????? //
100 }
101 else {
102 Tour[k][t] = StartCity[k]; /* 螞蟻回到初始的作業 */
103 finished = 1;
104 }
105 }
106
107 /* 區域費洛蒙更新 */
108 for(i=0;i 109 for(j=0;j 110 Tao[i][j] = (1-RHO)*Tao[i][j] + RHO*Tao0;
111
112 } while(!finished);//否定完成 //
113
114 //--------------------------------------------------------------------------------------//
115
116 /* 計算每隻螞蟻旅程的完成時間 */
117 for(k=0;k 118 SumLen[k] = 0;
119 for(t=0;t 120 SumLen[k] += dist[Tour[k][t]][Tour[k][t+1]];
121 }
122 //找出最好的一組解//
123 MinLenTour = FindNewBestSolution(MinLenTour,Tour,SumLen,BestTour);
124
125 printf("\n %f",MinLenTour);
126
127 //--------------------------------------------------------------------------------------//
128
129 /* 對最好的解做全域更新 */
130 for(i=0;i 131 Tao[BestTour[i]][BestTour[i+1]] = (1-RHO)*Tao[BestTour[i]][BestTour[i+1]] + RHO*(1.0/MinLenTour);
132
133 }
134 PrintBestPath(BestTour);
135
136 }
137 //---------------------------函數設定NonVisitedCities--------------------------------------------------//
138
139 int NonVisitedCities(int k,int VisitedCities[NumAnts][NumCities])
140 {
141 int i;
142
143 i = -1;
144 do {
145 i++;
146 } while(VisitedCities[k][i] && i 147
148 if(i==NumCities)
149 return(0);
150 else return(1);
151 }
152 //---------------------------函數設定ChooseNextCity--------------------------------------------------//
153
154 int ChooseNextCity(int k, int antpos,int VisitedCities[NumAnts][NumCities],float Tao[NumCities][NumCities],int dist[NumCities][NumCities])
155 {
156 int nonvisited;
157 int i;
158 int NextCity;//下一個作業//
159 int RndCity;//亂數作業???????//
160 float prob_explore; /* exploration探索的機率 */
161
162 float WeightedPheromone[NumCities][NumCities];
163 int ArgMaxWeightedPhero;
164
165
166 nonvisited = 0;//未經過為0//
167 /* 總共的權重費洛蒙 = 0.0 */
168 ArgMaxWeightedPhero = 0;
169 for(i=0;i 170 if(!VisitedCities[k][i]) {
171 nonvisited++;
172 WeightedPheromone[antpos][i] =Tao[antpos][i]/(dist[antpos][i]*dist[antpos][i]);//費洛蒙*(能見度)^2//
173
174 /* 總共的權重費洛蒙 += 權重費洛蒙[antpos][i] */
175 if (WeightedPheromone[antpos][i] >WeightedPheromone[antpos][ArgMaxWeightedPhero])
176 ArgMaxWeightedPhero = i;//找出最大權重費洛蒙//
177 }
178 else WeightedPheromone[antpos][i] = 0;
179
180 //-----------------------------------探索exploration-利用exploitation--------------------------//
181
182 prob_explore = rand()/RAND_MAX;//探索的機率為亂數//
183
184 if(prob_explore < q0)//如果探索的機率小於q0,下一個作業選最大權重費洛蒙的作業//
185 NextCity = ArgMaxWeightedPhero;
186 else {
187 if(nonvisited==1) RndCity = 1;//未經過 =1//
188 else RndCity = 1+rand()%(nonvisited-1);
189 i=-1;
190 j=0;
191 do {
192 i++;
193 if(!VisitedCities[k][i])
194 j++;
195 } while((i 196 NextCity = i;
197 }
198
199
200 return(NextCity);
201 }//結尾//
202
203 //------------------------問題主軸-------------------------------------------------------------//
204 float reentry_problem(int dist[NumCities][NumCities])
205 {
206
207 int i,j;
208 float TYPE0[3]={1,2,3};
209 float TYPE1[6]={2,3,6,4,6,4};
210 float TYPE2[6]={3,4,2,0,1,2};
211 float TYPE3[9]={2,6,8,6.0,1,4,0,3,1};
212 float x[8];
213 float SumNaiveDist;
214
215
216
217 x[0]= TYPE0[0]+TYPE0[1]+TYPE0[2];//TYPE0的level1//
218 x[1]= TYPE1[0]+TYPE1[1]+TYPE1[2];//TYPE1的level1//
219 x[2]= TYPE1[3]+TYPE1[4]+TYPE1[5];//TYPE1的level2//
220 x[3]= TYPE2[0]+TYPE2[1]+TYPE2[2];//TYPE2的level1//
221 x[4]= TYPE2[3]+TYPE2[4];//TYPE2的level2//
222 x[5]= TYPE3[0]+TYPE3[1]+TYPE3[2];//TYPE3的level1//
223 x[6]= TYPE3[3]+TYPE3[4]+TYPE3[5];//TYPE3的level2//
224 x[7]= TYPE3[6]+TYPE3[7];//TYPE3的level3//
225
226
227 for(i=0;i 228 for(j=0;j 229 if (i!=j)
230 dist[i][j] = x[j];
231 else
232 dist[i][j]=0;
233 }
234 }
235
236
237 SumNaiveDist = 0.0;
238 for(i=0;i 239 SumNaiveDist += dist[i][(i+1)%NumCities];
240
241 return(SumNaiveDist);
242 }
243 //-------------------------------------找出最佳解-----------------------------------------------//
244
245 float FindNewBestSolution(float MinLenTour, int Tour[NumAnts][NumCities+1],
246 float SumLen[NumAnts], int BestTour[NumCities+1])
247 {
248 float NewMinLenTour;
249
250 NewMinLenTour = MinLenTour;
251 for(k=0;k 252 if(SumLen[k] < NewMinLenTour) {
253 for(i=0;i 254 BestTour[i] = Tour[k][i];
255 NewMinLenTour = SumLen[k];
256 }
257
258 return(NewMinLenTour);
259 }
260
261 void PrintBestPath(int BestTour[NumCities+1])
262 {
263 int i;
264
265 printf("\n\n<<最好的路徑為>>\n");
266 for(i=0;i 267 printf("%d - ",BestTour[i]);
268 printf("\n\n");
269
270
271
272 system("pause");
273 }
274
2 #include
3 #include
4 #define BIG 999999
5 #define NumCities 8//共有8個作業//
6 #define NumAnts 4//螞蟻數為4//
7 #define RHO 0.8//費洛蒙蒸發係數=0.8//
8 #define q0 0.5
9 #define MAXITER 10//跑10圈//
10
11 float Tao[NumCities][NumCities];//初始費洛蒙//
12 int Tour[NumAnts][NumCities+1];//螞蟻的旅程//
13 int BestTour[NumCities+1];//最好的旅程//
14 int StartCity[NumAnts];//開始的作業//
15 int VisitedCities[NumAnts][NumCities];//走過的作業//
16 int AntInitInCity[NumCities];//螞蟻起點位於的作業//
17 int dist[NumCities][NumCities];//處理時間//
18 float SumLen[NumAnts];//路徑長//
19 float MinLenTour;//最小路徑長//
20 float Tao0; //初始費洛蒙//
21 int ChooseNextCity(int k, int antpos,int VisitedCities[NumAnts][NumCities],float Tao[NumCities][NumCities],int
22 dist[NumCities][NumCities]);
23 int NonVisitedCities(int k,int VisitedCities[NumAnts][NumCities]);
24
25 int finished;
26 int randcity;
27
28 int i,j,k,t;
29 int iter;
30
31 /* 預先宣告 */
32 float reentry_problem(int dist[NumCities][NumCities]);
33 float FindNewBestSolution(float MinLenTour, int Tour[NumAnts][NumCities+1],
34 float SumLen[NumAnts], int BestTour[NumCities+1]);
35 void PrintBestPath(int BestTour[NumCities+1]);
36
37
38 int main()
39 {
40
41 srand(12345);//起始亂數的產生//
42
43 MinLenTour = BIG;//最小路徑初始化//
44
45 Tao0 = 1.0/(reentry_problem(dist)*NumCities);//初始費洛蒙的值//
46 printf("Tao0 = %f Naivedist=%f\n",Tao0,reentry_problem(dist));
47
48 /* Init. pheromone level of each link */
49 for(i=0;i 50 for(j=0;j 51 Tao[i][j] = Tao0;//一開始每個作業路徑的費洛蒙都為Tao0//
52
53 /**************** main loop ******************/
54
55 for(iter=0;iter 56
57 /* 將每隻螞蟻放置在某個作業上*/
58
59 /* 目前沒有一個作業被螞蟻經過 */
60 for(k=0;k 61 for(j=0;j 62 VisitedCities[k][j] = 0;//螞蟻經過的作業陣列//
63 Tour[k][j] = 0;//螞蟻的旅程陣列,不懂幹嘛要+1//
64 }
65 Tour[k][j+1] = 0;//看沒有//
66 }
67
68 /* 置放螞蟻在某個作業 */
69 for(j=0;j 70 AntInitInCity[j] = 0; //能起始的作業只有0~3//
71
72 for(k=0;k 73 do {
74 randcity = rand()%NumCities;//起始的作業取亂數//
75 } while (AntInitInCity[randcity]);//do while為跑全部主體，再判斷條件，條件要加分號
76 //每隻螞蟻的最初起點為亂數的作業
77
78 AntInitInCity[randcity] = 1;//螞蟻起初位於的隨機作業=1?????????//
79 StartCity[k] = randcity;//螞蟻開始的作業//
80 VisitedCities[k][randcity] = 1;//已經經過的城市=1??????????//
81 Tour[k][0] = randcity;//第一個旅程為隨機的作業//
82 }
83
84 //----------------------------------------------------------------------------------------//
85
86 /* 螞蟻建立它們的旅程 */
87
88 t=0;//t=旅程的節點//
89 finished = 0;
90 do {
91 t = t+1;
92
93 /* 每隻螞蟻執行一個步驟 */
94 for(k=0;k 95
96 /* 選擇下一個作業 */
97 if(NonVisitedCities(k,VisitedCities)) {
98 Tour[k][t] = ChooseNextCity(k,Tour[k][t-1],VisitedCities,Tao,dist);
99 VisitedCities[k][Tour[k][t]] = 1;//???????????? //
100 }
101 else {
102 Tour[k][t] = StartCity[k]; /* 螞蟻回到初始的作業 */
103 finished = 1;
104 }
105 }
106
107 /* 區域費洛蒙更新 */
108 for(i=0;i 109 for(j=0;j 110 Tao[i][j] = (1-RHO)*Tao[i][j] + RHO*Tao0;
111
112 } while(!finished);//否定完成 //
113
114 //--------------------------------------------------------------------------------------//
115
116 /* 計算每隻螞蟻旅程的完成時間 */
117 for(k=0;k 118 SumLen[k] = 0;
119 for(t=0;t 120 SumLen[k] += dist[Tour[k][t]][Tour[k][t+1]];
121 }
122 //找出最好的一組解//
123 MinLenTour = FindNewBestSolution(MinLenTour,Tour,SumLen,BestTour);
124
125 printf("\n %f",MinLenTour);
126
127 //--------------------------------------------------------------------------------------//
128
129 /* 對最好的解做全域更新 */
130 for(i=0;i 131 Tao[BestTour[i]][BestTour[i+1]] = (1-RHO)*Tao[BestTour[i]][BestTour[i+1]] + RHO*(1.0/MinLenTour);
132
133 }
134 PrintBestPath(BestTour);
135
136 }
137 //---------------------------函數設定NonVisitedCities--------------------------------------------------//
138
139 int NonVisitedCities(int k,int VisitedCities[NumAnts][NumCities])
140 {
141 int i;
142
143 i = -1;
144 do {
145 i++;
146 } while(VisitedCities[k][i] && i 147
148 if(i==NumCities)
149 return(0);
150 else return(1);
151 }
152 //---------------------------函數設定ChooseNextCity--------------------------------------------------//
153
154 int ChooseNextCity(int k, int antpos,int VisitedCities[NumAnts][NumCities],float Tao[NumCities][NumCities],int dist[NumCities][NumCities])
155 {
156 int nonvisited;
157 int i;
158 int NextCity;//下一個作業//
159 int RndCity;//亂數作業???????//
160 float prob_explore; /* exploration探索的機率 */
161
162 float WeightedPheromone[NumCities][NumCities];
163 int ArgMaxWeightedPhero;
164
165
166 nonvisited = 0;//未經過為0//
167 /* 總共的權重費洛蒙 = 0.0 */
168 ArgMaxWeightedPhero = 0;
169 for(i=0;i 170 if(!VisitedCities[k][i]) {
171 nonvisited++;
172 WeightedPheromone[antpos][i] =Tao[antpos][i]/(dist[antpos][i]*dist[antpos][i]);//費洛蒙*(能見度)^2//
173
174 /* 總共的權重費洛蒙 += 權重費洛蒙[antpos][i] */
175 if (WeightedPheromone[antpos][i] >WeightedPheromone[antpos][ArgMaxWeightedPhero])
176 ArgMaxWeightedPhero = i;//找出最大權重費洛蒙//
177 }
178 else WeightedPheromone[antpos][i] = 0;
179
180 //-----------------------------------探索exploration-利用exploitation--------------------------//
181
182 prob_explore = rand()/RAND_MAX;//探索的機率為亂數//
183
184 if(prob_explore < q0)//如果探索的機率小於q0,下一個作業選最大權重費洛蒙的作業//
185 NextCity = ArgMaxWeightedPhero;
186 else {
187 if(nonvisited==1) RndCity = 1;//未經過 =1//
188 else RndCity = 1+rand()%(nonvisited-1);
189 i=-1;
190 j=0;
191 do {
192 i++;
193 if(!VisitedCities[k][i])
194 j++;
195 } while((i 196 NextCity = i;
197 }
198
199
200 return(NextCity);
201 }//結尾//
202
203 //------------------------問題主軸-------------------------------------------------------------//
204 float reentry_problem(int dist[NumCities][NumCities])
205 {
206
207 int i,j;
208 float TYPE0[3]={1,2,3};
209 float TYPE1[6]={2,3,6,4,6,4};
210 float TYPE2[6]={3,4,2,0,1,2};
211 float TYPE3[9]={2,6,8,6.0,1,4,0,3,1};
212 float x[8];
213 float SumNaiveDist;
214
215
216
217 x[0]= TYPE0[0]+TYPE0[1]+TYPE0[2];//TYPE0的level1//
218 x[1]= TYPE1[0]+TYPE1[1]+TYPE1[2];//TYPE1的level1//
219 x[2]= TYPE1[3]+TYPE1[4]+TYPE1[5];//TYPE1的level2//
220 x[3]= TYPE2[0]+TYPE2[1]+TYPE2[2];//TYPE2的level1//
221 x[4]= TYPE2[3]+TYPE2[4];//TYPE2的level2//
222 x[5]= TYPE3[0]+TYPE3[1]+TYPE3[2];//TYPE3的level1//
223 x[6]= TYPE3[3]+TYPE3[4]+TYPE3[5];//TYPE3的level2//
224 x[7]= TYPE3[6]+TYPE3[7];//TYPE3的level3//
225
226
227 for(i=0;i 228 for(j=0;j 229 if (i!=j)
230 dist[i][j] = x[j];
231 else
232 dist[i][j]=0;
233 }
234 }
235
236
237 SumNaiveDist = 0.0;
238 for(i=0;i 239 SumNaiveDist += dist[i][(i+1)%NumCities];
240
241 return(SumNaiveDist);
242 }
243 //-------------------------------------找出最佳解-----------------------------------------------//
244
245 float FindNewBestSolution(float MinLenTour, int Tour[NumAnts][NumCities+1],
246 float SumLen[NumAnts], int BestTour[NumCities+1])
247 {
248 float NewMinLenTour;
249
250 NewMinLenTour = MinLenTour;
251 for(k=0;k 252 if(SumLen[k] < NewMinLenTour) {
253 for(i=0;i 254 BestTour[i] = Tour[k][i];
255 NewMinLenTour = SumLen[k];
256 }
257
258 return(NewMinLenTour);
259 }
260
261 void PrintBestPath(int BestTour[NumCities+1])
262 {
263 int i;
264
265 printf("\n\n<<最好的路徑為>>\n");
266 for(i=0;i 267 printf("%d - ",BestTour[i]);
268 printf("\n\n");
269
270
271
272 system("pause");
273 }
274
全站熱搜
留言列表
