紮爾庫荅．元

#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 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] 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