人工蜂群演算法簡介與程式分析
- 2019 年 10 月 3 日
- 筆記
目前人工蜂群演算法主要分為基於婚配行為與基於釆蜜行為兩大類，本文研究的是基於釆蜜行為的人工蜂群演算法。
蜜蜂采蜜
自然界中的蜜蜂總能在任何環境下以極高的效率找到優質蜜源，且能適應環境的改變。蜜蜂群的采蜜系統由蜜源、僱傭蜂、非僱傭蜂三部分組成，其中一個蜜源的優劣有很多要素，如蜜源花蜜量的大小、離蜂巢距離的遠近、提取的難易程度等；僱傭蜂和特定的蜜源聯繫並將蜜源資訊以一定概率形式告訴同伴；非僱傭蜂的職責是尋找待開採的蜜源，分為跟隨蜂和偵查蜂兩類，跟隨峰是在蜂巢等待而偵查蜂是探測蜂巢周圍的新蜜源。蜜蜂采蜜時，蜂巢中的一部分蜜蜂作為偵查蜂，不斷並隨機地在蜂巢附近尋找蜜源，如果發現了花蜜量超過某個閾值的蜜源，則此偵査蜂變為僱傭蜂開始釆蜜，采蜜完成後飛回蜂巢跳搖擺舞告知跟隨峰。搖擺舞是蜜蜂之間交流資訊的一種基本形式，它傳達了有關蜂巢周圍蜜源的重要資訊如蜜源方向及離巢距離等，跟隨峰利用這些資訊準確評價蜂巢周圍的蜜源品質。當僱傭蜂跳完搖擺舞之後，就與蜂巢中的一些跟隨蜂一起返回原蜜源采蜜，跟隨蜂數量取決於蜜源品質。以這種方式，蜂群能快速且有效地找到花蜜量最高的蜜源。
蜜蜂采蜜的群體智慧就是通過不同角色之間的交流轉換及協作來實現的。具體采蜜過程如圖所示。在最初階段，蜜蜂是以偵查蜂的形式出現，且對蜂巢周闈的蜜源沒有任何了解，由於蜜蜂內在動機和外在的條件不同偵查蜂有兩種選擇：①成為僱傭蜂，開始在蜂巢周圍隨機搜索蜜源，如圖中路線②成為跟隨峰，在觀察完搖擺舞后開始搜索蜜源，如圖中路線。假設發現兩個蜜源和，在發現蜜源後，該偵查蜂變成一隻僱傭蜂，僱傭蜂利用其自身屬性記住蜜源的位置，並立刻投入到采蜜中。采蜜完成後蜜蜂帶著滿載花蜜返回蜂巢，將花蜜卸載到卸蜜房，卸載完成後僱傭蜂有三種可能的行為①放棄自己發現的花蜜量不高的蜜源，變成一個不受約束的非僱傭蜂，如圖中的路線；②在
招募區跳搖擺舞，招募一些待在蜂巢中跟隨峰，帶領其再次返回所發現的蜜源如圖中的路線；③不招募其他蜜蜂，繼續回到原來的蜜源采蜜如圖中的路線。在現實生活中並不是所有的蜜蜂一開始就立刻采蜜，另外大多數蜜蜂在一次采蜜完成後都會選擇回到招募區跳搖擺舞來招募更多的蜜蜂去采蜜。
演算法模型
人工蜂群演算法就是模擬蜜蜂的采蜜過程而提出的一種新型智慧優化演算法，它也是由食物源、僱傭蜂和非僱傭蜂三部分組成。
食物源：食物源即為蜜源。在任何一個優化問題中，問題的可行解都是以一定形式給出的。在人工蜂群演算法中，食物源就是待求優化問題的可行解，是人工蜂群演算法中所要處理的基本對象。食物源的優劣即可行解的好壞是用蜜源花蜜量的大小即適應度來評價的。
僱傭蜂：僱傭蜂即為引領蜂與食物源的位置相對應，一個食物源對應一個引領蜂。在人工蜂群演算法中，食物源的個數與引領蜂的個數相等；引領蜂的任務是發現食物源資訊並以一定的概率與跟隨蜂分享；概率的計算即為人工蜂群演算法中的選擇策略，一般是根據適應度值以輪盤賭的方法計算。
非僱傭蜂：非僱傭蜂包括跟隨蜂和偵査蜂跟隨蜂在蜂巢的招募區內根據引領蜂提供的蜜源資訊來選擇食物源，而偵查蜂是在蜂巢附近尋找新的食物源。在人工蜂群演算法中，跟隨蜂依據引領蜂傳遞的資訊，在食物源附近搜索新食物源，並進行貪婪選擇。若一個食物源在經過次後仍未被更新，則此引領蜂變成偵査蜂，偵查蜂尋找新的食物源代替原來的食物源。
演算法搜索過程
人工蜂群演算法中將人工蜂群分為引領蜂、跟隨蜂和偵查蜂三類，每一次搜索過程中，引領蜂和跟隨蜂是先後開採食物源，即尋找最優解，而偵查蜂是觀察是否陷入局部最優，若陷入局部最優則隨機地搜索其它可能的食物源。每個食物源代表問題一個可能解，食物源的花蜜量對應相應解的品質（適應度值fiti）。
一、人工蜂群演算法搜索過程中，首先需要初始化，其中包括確定種群數、最大迭代次數MCN、、控制參數limit和確定搜索空間即解的範圍，在搜索空間中隨機生成初始解xi(i=1,2,3,……,SN)，SN為食物源個數，每個解xi是一個D維的向量，D是問題的維數。初始化之後，整個種群將進行引領蜂、跟隨蜂和偵查蜂搜尋過程的重複循環，直到達到最大迭代次數MCN或誤差允許值 ε。
二、在搜索過程開始階段，每個引領蜂由式(2-3)產生一個新解即新食物源，
vij=xij+Φij(xij-xkj) (2-3)
式中，k∈﹛1,2,…,SN﹜,j∈{1,2,…,D},且k ≠i;Φij為[-1,1]之間的隨機數。計算新解的fiti並評價它，若新解的fiti優於舊解，則引領蜂記住新解忘記舊解。反之，它將保留舊解。
三、在所有引領蜂完成搜尋過程之後，引領蜂會在招募區跳搖擺舞把解的資訊及資訊與跟隨蜂分享。跟隨蜂根據式計算每個解的選擇概率，
pi=fiti/∑k=1SNfitk。 (2-4)
然後在區間[-1,1]內隨機產生一個數，如果解的概率值大於該隨機數，則跟隨蜂由式(2-3)產生一個新解，並檢驗新解的fiti，若新解的fiti比之前好，則跟隨蜂將記住新解忘掉舊解；反之，它將保留舊解。
四、在所有跟隨蜂完成搜尋過程之後，如果一個解經過limit次循環仍然沒有被進一步更新，那麼就認為此解陷入局部最優，該食物源就會被捨棄。設食物源xi被捨棄，則此食物源對應的引領蜂轉成一個偵查蜂。偵察蜂由(2-5)式產生一個新的食物源代替它。
xij=xminj+rand(0,1)(xmaxj-xminj) (2-5)
其中j∈{1,2….,D}。然後返回引領蜂搜索過程，開始重複循環。
五、人工蜂群演算法的食物源品質一般是越大越好，即適應度值越大越好，而對應於要優化的問題，需要分兩種情況考慮：即最小值問題、最大值問題。設fi是優化問題的目標函數，所以若優化最小值問題時，適應度函數為fi的變形，一般用式(2-6)表示；若優化最大值問題，適應度函數即目標函數。
fiti={1+abs(fi) fi>=01/1+fi fi>0 (2-6)
人工蜂群演算法在評價食物源時一般進行貪婪選擇按式(2-7)進行。
vi={xi fit(xi)<=fit(vi)vi fit(vi)>fit(xi) (2-7)
人工蜂群演算法就是通過循環搜索，最終找到最優食物源或最優解。
演算法步驟
人工蜂群演算法具體實現步驟：
步驟1：初始化種群：初始化各個參數，蜂群總數SN、食物源被採集次數即最大迭代次數MCN及控制參數limit，確定問題搜索範圍，並且在搜索範圍內隨機產生初始解xi(i=1,2,…SN) 。
步驟2：計算並評估每個初始解的適應度。
步驟3：設定循環條件並開始循環
步驟4：引領蜂對解xi按照式（2-3）進行鄰域搜索產生新解（食物源）vi，並計算其適應度值；
步驟5：按照式(2-7)進行貪婪選擇：如果vi的適應度值優於xi，則利用vi替換xi，將vi作為當前最好的解，否則保留xi不變；
步驟6：根據式(2-4)計算食物源的概率pi；
步驟7：跟隨蜂依照概率pi選擇解或食物源，按照式(2-3)搜索產生新解（食物源）vi，並計算其適應度。
步驟8：按式(2-7)進行貪婪選擇；如果vi的適應度優於xi，則用vi代替xi，將vi作為當前最好解，否則保留xi不變；
步驟9：判斷是否有要放棄的解。若有，則偵查蜂按式(2-5)隨機產生新解將其替換；
步驟10：記錄到目前為止的最優解；
步驟11：判斷是否滿足循環終止條件，若滿足，循環結束，輸出最優解，否則返回步驟4繼續搜索。
程式分析xi
程式中的采蜜蜂就是引領蜂也是僱傭蜂，都表達一個含義。
1 #include<iostream> 2 #include<time.h> 3 #include<stdlib.h> 4 #include<cmath> 5 #include<fstream> 6 #include<iomanip> 7 using namespace std; 8 9 const int NP=40;//種群的規模，采蜜蜂+觀察蜂 10 const int FoodNumber=NP/2;//食物的數量，為采蜜蜂的數量 11 const int limit=20;//限度，超過這個限度沒有更新采蜜蜂變成偵查蜂 12 const int maxCycle=10000;//停止條件 13 14 /*****函數的特定參數*****/ 15 const int D=2;//函數的參數個數 16 const double lb=-100;//函數的下界 17 const double ub=100;//函數的上界 18 19 double result[maxCycle]={0}; 20 21 /*****種群的定義****/ 22 struct BeeGroup 23 { 24 double code[D];//函數的維數 25 double trueFit;//記錄真實的最小值 26 double fitness; 27 double rfitness;//相對適應值比例 28 int trail;//表示實驗的次數，用於與limit作比較 29 }Bee[FoodNumber]; 30 31 BeeGroup NectarSource[FoodNumber];//蜜源，注意：一切的修改都是針對蜜源而言的 32 BeeGroup EmployedBee[FoodNumber];//采蜜蜂 33 BeeGroup OnLooker[FoodNumber];//觀察蜂 34 BeeGroup BestSource;//記錄最好蜜源 35 36 /*****函數的聲明*****/ 37 double random(double, double);//產生區間上的隨機數 38 void initilize();//初始化參數 39 double calculationTruefit(BeeGroup);//計算真實的函數值 40 double calculationFitness(double);//計算適應值 41 void CalculateProbabilities();//計算輪盤賭的概率 42 void evalueSource();//評價蜜源 43 void sendEmployedBees(); 44 void sendOnlookerBees(); 45 void sendScoutBees(); 46 void MemorizeBestSource(); 47 48 49 /*******主函數*******/ 50 int main() 51 { 52 ofstream output; //輸出定義 53 output.open("dataABC.txt"); 54 55 srand((unsigned)time(NULL)); //根據時間產生隨機種子 56 initilize();//初始化 57 MemorizeBestSource();//保存最好的蜜源 58 59 //主要的循環 60 int gen=0; 61 while(gen<maxCycle) 62 { 63 sendEmployedBees(); 64 65 CalculateProbabilities(); 66 67 sendOnlookerBees(); 68 69 MemorizeBestSource(); 70 71 sendScoutBees(); 72 73 MemorizeBestSource(); 74 75 output<<setprecision(30)<<BestSource.trueFit<<endl; //輸出30個有效數字 76 77 gen++; 78 } 79 80 output.close(); 81 cout<<"運行結束!!"<<endl; 82 return 0; 83 } 84 85 /*****函數的實現****/ 86 double random(double start, double end)//隨機產生區間內的隨機數 87 { 88 return start+(end-start)*rand()/(RAND_MAX + 1.0); 89 } 90 91 void initilize()//初始化參數 92 { 93 int i,j; 94 for (i=0;i<FoodNumber;i++) 95 { 96 for (j=0;j<D;j++) 97 { 98 NectarSource[i].code[j]=random(lb,ub); 99 EmployedBee[i].code[j]=NectarSource[i].code[j]; 100 OnLooker[i].code[j]=NectarSource[i].code[j]; 101 BestSource.code[j]=NectarSource[0].code[j]; 102 } 103 /****蜜源的初始化*****/ 104 NectarSource[i].trueFit=calculationTruefit(NectarSource[i]); 105 NectarSource[i].fitness=calculationFitness(NectarSource[i].trueFit); 106 NectarSource[i].rfitness=0; 107 NectarSource[i].trail=0; 108 /****采蜜蜂的初始化*****/ 109 EmployedBee[i].trueFit=NectarSource[i].trueFit; 110 EmployedBee[i].fitness=NectarSource[i].fitness; 111 EmployedBee[i].rfitness=NectarSource[i].rfitness; 112 EmployedBee[i].trail=NectarSource[i].trail; 113 /****觀察蜂的初始化****/ 114 OnLooker[i].trueFit=NectarSource[i].trueFit; 115 OnLooker[i].fitness=NectarSource[i].fitness; 116 OnLooker[i].rfitness=NectarSource[i].rfitness; 117 OnLooker[i].trail=NectarSource[i].trail; 118 } 119 /*****最優蜜源的初始化*****/ 120 BestSource.trueFit=NectarSource[0].trueFit; 121 BestSource.fitness=NectarSource[0].fitness; 122 BestSource.rfitness=NectarSource[0].rfitness; 123 BestSource.trail=NectarSource[0].trail; 124 } 125 126 double calculationTruefit(BeeGroup bee)//計算真實的函數值 127 { 128 double truefit=0; 129 /******測試函數1******/ 130 truefit=0.5+(sin(sqrt(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))*sin(sqrt(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))-0.5) 131 /((1+0.001*(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))*(1+0.001*(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))); 132 133 return truefit; 134 } 135 136 double calculationFitness(double truefit)//計算適應值 137 { 138 double fitnessResult=0; 139 if (truefit>=0) 140 { 141 fitnessResult=1/(truefit+1); 142 }else 143 { 144 fitnessResult=1+abs(truefit); 145 } 146 return fitnessResult; 147 } 148 149 void sendEmployedBees()//修改采蜜蜂的函數 150 { 151 int i,j,k; 152 int param2change;//需要改變的維數 153 double Rij;//[-1,1]之間的隨機數 154 for (i=0;i<FoodNumber;i++) 155 { 156 157 param2change=(int)random(0,D);//隨機選取需要改變的維數 158 159 /******選取不等於i的k********/ 160 while (1) 161 { 162 k=(int)random(0,FoodNumber); 163 if (k!=i) 164 { 165 break; 166 } 167 } 168 169 for (j=0;j<D;j++) 170 { 171 EmployedBee[i].code[j]=NectarSource[i].code[j]; //在之前初始化對EmployedBee進行初始化了，程式之後有對蜜源改變在此對EmployedBee進行更新 172 } 173 174 /*******采蜜蜂去更新資訊*******/ 175 Rij=random(-1,1); 176 EmployedBee[i].code[param2change]=NectarSource[i].code[param2change]+Rij*(NectarSource[i].code[param2change]-NectarSource[k].code[param2change]); //根據公式(2-3) 177 /*******判斷是否越界********/ 178 if (EmployedBee[i].code[param2change]>ub) 179 { 180 EmployedBee[i].code[param2change]=ub; 181 } 182 if (EmployedBee[i].code[param2change]<lb) 183 { 184 EmployedBee[i].code[param2change]=lb; 185 } 186 EmployedBee[i].trueFit=calculationTruefit(EmployedBee[i]); 187 EmployedBee[i].fitness=calculationFitness(EmployedBee[i].trueFit); 188 189 /******貪婪選擇策略*******/ 190 if (EmployedBee[i].trueFit<NectarSource[i].trueFit) 191 { 192 for (j=0;j<D;j++) 193 { 194 NectarSource[i].code[j]=EmployedBee[i].code[j]; 195 } 196 NectarSource[i].trail=0; 197 NectarSource[i].trueFit=EmployedBee[i].trueFit; 198 NectarSource[i].fitness=EmployedBee[i].fitness; 199 }else 200 { 201 NectarSource[i].trail++; 202 } 203 } 204 } 205 206 void CalculateProbabilities()//計算輪盤賭的選擇概率 (計算的適應度比例)與後面 sendOnlookerBees中的選擇R_choosed進行比較 207 { 208 int i; 209 double maxfit; 210 maxfit=NectarSource[0].fitness; 211 for (i=1;i<FoodNumber;i++) 212 { 213 if (NectarSource[i].fitness>maxfit) 214 maxfit=NectarSource[i].fitness; 215 } 216 217 for (i=0;i<FoodNumber;i++) 218 { 219 NectarSource[i].rfitness=(0.9*(NectarSource[i].fitness/maxfit))+0.1; 220 } 221 } 222 223 void sendOnlookerBees()//采蜜蜂與觀察蜂交流資訊，觀察蜂更改資訊 224 { 225 int i,j,t,k; 226 double R_choosed;//被選中的概率 227 int param2change;//需要被改變的維數 228 double Rij;//[-1,1]之間的隨機數 229 i=0; 230 t=0; //是否超出食物源個數 231 while(t<FoodNumber) 232 { 233 234 R_choosed=random(0,1); 235 if(R_choosed<NectarSource[i].rfitness)//根據被選擇的概率選擇 （演算法搜索過程三的實現） 236 { 237 t++; 238 param2change=(int)random(0,D); 239 240 /******選取不等於i的k********/ 241 while (1) 242 { 243 k=(int)random(0,FoodNumber); 244 if (k!=i) 245 { 246 break; 247 } 248 } 249 250 for(j=0;j<D;j++) 251 { 252 OnLooker[i].code[j]=NectarSource[i].code[j]; 253 } 254 255 /****更新******/ 256 Rij=random(-1,1); 257 OnLooker[i].code[param2change]=NectarSource[i].code[param2change]+Rij*(NectarSource[i].code[param2change]-NectarSource[k].code[param2change]); 258 259 /*******判斷是否越界*******/ 260 if (OnLooker[i].code[param2change]<lb) 261 { 262 OnLooker[i].code[param2change]=lb; 263 } 264 if (OnLooker[i].code[param2change]>ub) 265 { 266 OnLooker[i].code[param2change]=ub; 267 } 268 OnLooker[i].trueFit=calculationTruefit(OnLooker[i]); 269 OnLooker[i].fitness=calculationFitness(OnLooker[i].trueFit); 270 271 /****貪婪選擇策略******/ 272 if (OnLooker[i].trueFit<NectarSource[i].trueFit) 273 { 274 for (j=0;j<D;j++) 275 { 276 NectarSource[i].code[j]=OnLooker[i].code[j]; 277 } 278 NectarSource[i].trail=0; 279 NectarSource[i].trueFit=OnLooker[i].trueFit; 280 NectarSource[i].fitness=OnLooker[i].fitness; 281 }else 282 { 283 NectarSource[i].trail++; 284 } 285 } 286 i++; 287 if (i==FoodNumber) 288 { 289 i=0; 290 } 291 } 292 } 293 294 295 /*******只有一隻偵查蜂（主程式進行一次循環該函數就判斷一次偵查蜂是否出現）（如果有兩個及以上超過limit限制，該函數能將他們都找到嗎？在循環結束之前）**********/ 296 void sendScoutBees()//判斷是否有偵查蜂的出現，有則重新生成蜜源 297 { 298 int maxtrialindex,i,j; 299 double R;//[0,1]之間的隨機數 300 maxtrialindex=0; 301 for (i=1;i<FoodNumber;i++) 302 { 303 if (NectarSource[i].trail>NectarSource[maxtrialindex].trail) 304 { 305 maxtrialindex=i; 306 } 307 } 308 if(NectarSource[maxtrialindex].trail>=limit) 309 { 310 /*******重新初始化*********/ 311 for (j=0;j<D;j++) 312 { 313 R=random(0,1); 314 NectarSource[maxtrialindex].code[j]=lb+R*(ub-lb); //此處蜜源進行更新（這就是為什麼在初始化引領蜂和偵查蜂之後，還要在相應的函數地方再初始化一次） 315 } 316 NectarSource[maxtrialindex].trail=0; 317 NectarSource[maxtrialindex].trueFit=calculationTruefit(NectarSource[maxtrialindex]); 318 NectarSource[maxtrialindex].fitness=calculationFitness(NectarSource[maxtrialindex].trueFit); 319 } 320 } 321 322 void MemorizeBestSource()//保存最優的蜜源 323 { 324 int i,j; 325 for (i=1;i<FoodNumber;i++) 326 { 327 if (NectarSource[i].trueFit<BestSource.trueFit) 328 { 329 for (j=0;j<D;j++) 330 { 331 BestSource.code[j]=NectarSource[i].code[j]; 332 } 333 BestSource.trueFit=NectarSource[i].trueFit; 334 } 335 } 336 }
另附實驗生成數據資料以及演算法源碼以供參考 https://pan.baidu.com/s/1iIPfQUSpJHp7_pjJ1SSBEg
請大家斧正
2019-08-17 10:22:31
