人工蜂群算法简介与程序分析
- 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
