优化算法——人工蜂群算法(ABC)

1、优化算法人工蜂群算法(ABC)一、人工蜂群算法的介绍    手机微信关注公众号ID：datadw 学习数据挖掘，研究大数据，关注你想了解的，分享你需要的。人工蜂群算法(Artificial Bee Colony, ABC)是由Karaboga于2005年提出的一种新颖的基于群智能的全局优化算法，其直观背景来源于蜂群的采蜜行为，蜜蜂根据各自的分工进行不同的活动，并实现蜂群信息的共享和交流，从而找到问题的最优解。人工蜂群算法属于群智能算法的一种。二、人工蜂群算法的原理    1、原理        标准的ABC算法通过

2、模拟实际蜜蜂的采蜜机制将人工蜂群分为3类: 采蜜蜂、观察蜂和侦察蜂。整个蜂群的目标是寻找花蜜量最大的蜜源。在标准的ABC算法中，采蜜蜂利用先前的蜜源信息寻找新的蜜源并与观察蜂分享蜜源信息；观察蜂在蜂房中等待并依据采蜜蜂分享的信息寻找新的蜜源；侦查蜂的任务是寻找一个新的有价值的蜜源，它们在蜂房附近随机地寻找蜜源。        假设问题的解空间是维的，采蜜蜂与观察蜂的个数都是，采蜜蜂的个数或观察蜂的个数与蜜源的数量相等。则标准的ABC算法将优化问题的求解过程看成是在维搜索空间中进行搜索。每个蜜源的位置代表问题的一个可能解，蜜源的花蜜量对应于相应的解的适应度

3、。一个采蜜蜂与一个蜜源是相对应的。与第个蜜源相对应的采蜜蜂依据如下公式寻找新的蜜源：其中，是区间上的随机数，。标准的ABC算法将新生成的可能解与原来的解作比较，并采用贪婪选择策略保留较好的解。每一个观察蜂依据概率选择一个蜜源，概率公式为其中，是可能解的适应值。对于被选择的蜜源，观察蜂根据上面概率公式搜寻新的可能解。当所有的采蜜蜂和观察蜂都搜索完整个搜索空间时，如果一个蜜源的适应值在给定的步骤内(定义为控制参数“limit”) 没有被提高, 则丢弃该蜜源，而与该蜜源相对应的采蜜蜂变成侦查蜂，侦查蜂通过已下公式搜索新的可能解。其中，是区间上的随机数，和是第维的下界和上界。   

4、 2、流程· 初始化；· 重复以下过程：o 将采蜜蜂与蜜源一一对应，根据上面第一个公式更新蜜源信息，同时确定蜜源的花蜜量；o 观察蜂根据采蜜蜂所提供的信息采用一定的选择策略选择蜜源，根据第一个公式更新蜜源信息，同时确定蜜源的花蜜量；o 确定侦查蜂，并根据第三个公式寻找新的蜜源；o 记忆迄今为止最好的蜜源；· 判断终止条件是否成立；三、人工蜂群算法用于求解函数优化问题    对于函数其中。代码：cpp view plaincopy1. #include<iostream>  2. #include<

5、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

6、60;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=-1

7、00;/函数的下界   17. const double ub=100;/函数的上界  18.   19. double resultmaxCycle=0;  20.   21. /*种群的定义*/  22. struct BeeGroup  23.   24.     double codeD;/函数的维数  25.

8、     double trueFit;/记录真实的最小值  26.     double fitness;  27.     double rfitness;/相对适应值比例  28.     int trail;/表示实验的次数，用于与limit作比较  29. BeeFoodNumber;  

9、30.   31. BeeGroup NectarSourceFoodNumber;/蜜源，注意：一切的修改都是针对蜜源而言的  32. BeeGroup EmployedBeeFoodNumber;/采蜜蜂  33. BeeGroup OnLookerFoodNumber;/观察蜂  34. BeeGroup BestSource;/记录最好蜜源  35.   36. /*函数的声明*/  37. double&#

10、160;random(double, double);/产生区间上的随机数  38. void initilize();/初始化参数  39. double calculationTruefit(BeeGroup);/计算真实的函数值  40. double calculationFitness(double);/计算适应值  41. void CalculateProbabilities();/计算轮盘赌的概率  42. void e

11、valueSource();/评价蜜源  43. void sendEmployedBees();  44. void sendOnlookerBees();  45. void sendScoutBees();  46. void MemorizeBestSource();  47.   48.   49. /*主函数*/  50. int main()  51.

12、  52.     ofstream output;  53.     output.open("dataABC.txt");  54.   55.     srand(unsigned)time(NULL);  56.     initilize();/初始化  57.  &#

13、160;  MemorizeBestSource();/保存最好的蜜源  58.           59.     /主要的循环  60.     int gen=0;  61.     while(gen<maxCycle)  62.   

14、    63.         sendEmployedBees();  64.               65.         CalculateProbabilities();  66.   

15、            67.         sendOnlookerBees();  68.               69.         Memor

16、izeBestSource();  70.               71.         sendScoutBees();  72.               73.   

17、      MemorizeBestSource();  74.   75.         output<<setprecision(30)<<BestSource.trueFit<<endl;  76.              

18、 77.         gen+;  78.       79.       80.     output.close();  81.     cout<<"运行结束!"<<endl;  82. 

19、0;   return 0;  83.   84.   85. /*函数的实现*/  86. double random(double start, double end)/随机产生区间内的随机数  87.      88.     return start+(end-start)*rand()/(RAND_MAX&#

20、160;+ 1.0);  89.   90.   91. void initilize()/初始化参数  92.   93.     int i,j;  94.     for (i=0;i<FoodNumber;i+)  95.       96.   

21、;      for (j=0;j<D;j+)  97.           98.             NectarSourcei.codej=random(lb,ub);  99.       &

22、#160;     EmployedBeei.codej=NectarSourcei.codej;  100.             OnLookeri.codej=NectarSourcei.codej;  101.             BestSource.c

23、odej=NectarSource0.codej;  102.           103.         /*蜜源的初始化*/  104.         NectarSourcei.trueFit=calculationTruefit(NectarSourcei);  10

24、5.         NectarSourcei.fitness=calculationFitness(NectarSourcei.trueFit);  106.         NectarSourcei.rfitness=0;  107.         NectarSourcei.trail=0; &#

25、160;108.         /*采蜜蜂的初始化*/  109.         EmployedBeei.trueFit=NectarSourcei.trueFit;  110.         EmployedBeei.fitness=NectarSourcei.fitness;  111.

26、         EmployedBeei.rfitness=NectarSourcei.rfitness;  112.         EmployedBeei.trail=NectarSourcei.trail;  113.         /*观察蜂的初始化*/  114.  

27、60;      OnLookeri.trueFit=NectarSourcei.trueFit;  115.         OnLookeri.fitness=NectarSourcei.fitness;  116.         OnLookeri.rfitness=NectarSourcei.rfitness; 

28、60;117.         OnLookeri.trail=NectarSourcei.trail;  118.       119.     /*最优蜜源的初始化*/  120.     BestSource.trueFit=NectarSource0.trueFit;  121.   

29、60; BestSource.fitness=NectarSource0.fitness;  122.     BestSource.rfitness=NectarSource0.rfitness;  123.     BestSource.trail=NectarSource0.trail;  124.   125.   126. double calculationTruefit(BeeGro

30、up bee)/计算真实的函数值  127.   128.     double truefit=0;  129.     /*测试函数1*/  130.     truefit=0.5+(sin(sqrt(bee.code0*bee.code0+bee.code1*bee.code1)*sin(sqrt(bee.code0*bee.code0+bee.code1*bee.co

31、de1)-0.5)  131.         /(1+0.001*(bee.code0*bee.code0+bee.code1*bee.code1)*(1+0.001*(bee.code0*bee.code0+bee.code1*bee.code1);  132.   133.     return truefit;  134.   135.   

32、;136. double calculationFitness(double truefit)/计算适应值  137.   138.     double fitnessResult=0;  139.     if (truefit>=0)  140.       141.      

33、;   fitnessResult=1/(truefit+1);  142.     else  143.       144.         fitnessResult=1+abs(truefit);  145.       146.   

34、60; return fitnessResult;  147.   148.   149. void sendEmployedBees()/修改采蜜蜂的函数  150.   151.     int i,j,k;  152.     int param2change;/需要改变的维数  153.   

35、0; double Rij;/-1,1之间的随机数  154.     for (i=0;i<FoodNumber;i+)  155.       156.           157.         param2change=(int)ra

36、ndom(0,D);/随机选取需要改变的维数  158.   159.         /*选取不等于i的k*/  160.         while (1)  161.           162.     

37、;        k=(int)random(0,FoodNumber);  163.             if (k!=i)  164.               165.   &#

38、160;             break;  166.               167.           168.   169.     

39、    for (j=0;j<D;j+)  170.           171.             EmployedBeei.codej=NectarSourcei.codej;  172.        

40、   173.   174.         /*采蜜蜂去更新信息*/  175.         Rij=random(-1,1);  176.         EmployedBeei.codeparam2change=NectarSourcei.codeparam

41、2change+Rij*(NectarSourcei.codeparam2change-NectarSourcek.codeparam2change);  177.         /*判断是否越界*/  178.         if (EmployedBeei.codeparam2change>ub)  179.    

42、0;      180.             EmployedBeei.codeparam2change=ub;  181.           182.         if (EmployedBeei.

43、codeparam2change<lb)  183.           184.             EmployedBeei.codeparam2change=lb;  185.           186.  &#

44、160;      EmployedBeei.trueFit=calculationTruefit(EmployedBeei);  187.         EmployedBeei.fitness=calculationFitness(EmployedBeei.trueFit);  188.   189.        

45、60;/*贪婪选择策略*/  190.         if (EmployedBeei.trueFit<NectarSourcei.trueFit)  191.           192.             for (j=0

46、;j<D;j+)  193.               194.                 NectarSourcei.codej=EmployedBeei.codej;  195.      &

47、#160;        196.             NectarSourcei.trail=0;  197.             NectarSourcei.trueFit=EmployedBeei.trueFit;  198.

48、             NectarSourcei.fitness=EmployedBeei.fitness;  199.         else  200.           201.      

49、60;      NectarSourcei.trail+;  202.           203.       204.   205.   206. void CalculateProbabilities()/计算轮盘赌的选择概率  207.   208. 

50、0;   int i;  209.     double maxfit;  210.     maxfit=NectarSource0.fitness;  211.     for (i=1;i<FoodNumber;i+)  212.       213.  &

51、#160;      if (NectarSourcei.fitness>maxfit)  214.             maxfit=NectarSourcei.fitness;  215.       216.       217. &

52、#160;   for (i=0;i<FoodNumber;i+)  218.       219.         NectarSourcei.rfitness=(0.9*(NectarSourcei.fitness/maxfit)+0.1;  220.       221.   222.

53、  223. void sendOnlookerBees()/采蜜蜂与观察蜂交流信息，观察蜂更改信息  224.   225.     int i,j,t,k;  226.     double R_choosed;/被选中的概率  227.     int param2change;/需要被改变的维数  228. &

54、#160;   double Rij;/-1,1之间的随机数  229.     i=0;  230.     t=0;  231.     while(t<FoodNumber)  232.       233.       

55、60;   234.         R_choosed=random(0,1);  235.         if(R_choosed<NectarSourcei.rfitness)/根据被选择的概率选择  236.             

56、      237.             t+;  238.             param2change=(int)random(0,D);  239.         

57、      240.             /*选取不等于i的k*/  241.             while (1)  242.          &

58、#160;    243.                 k=(int)random(0,FoodNumber);  244.                 if (k!=i)  245

59、.                   246.                     break;  247.        

60、           248.               249.   250.             for(j=0;j<D;j+)  251.   

61、0;           252.                 OnLookeri.codej=NectarSourcei.codej;  253.              

62、 254.               255.             /*更新*/  256.             Rij=random(-1,1);  257.

63、             OnLookeri.codeparam2change=NectarSourcei.codeparam2change+Rij*(NectarSourcei.codeparam2change-NectarSourcek.codeparam2change);  258.               

64、259.             /*判断是否越界*/  260.             if (OnLookeri.codeparam2change<lb)  261.            

65、;   262.                 OnLookeri.codeparam2change=lb;  263.               264.        &#

66、160;    if (OnLookeri.codeparam2change>ub)  265.                  266.                 OnLookeri.

67、codeparam2change=ub;  267.               268.             OnLookeri.trueFit=calculationTruefit(OnLookeri);  269.       &

68、#160;     OnLookeri.fitness=calculationFitness(OnLookeri.trueFit);  270.               271.             /*贪婪选择策略*/  272. 

69、0;           if (OnLookeri.trueFit<NectarSourcei.trueFit)  273.               274.             &#

70、160;   for (j=0;j<D;j+)  275.                   276.                     Nect

71、arSourcei.codej=OnLookeri.codej;  277.                   278.                 NectarSourcei.trail=0;  279.

72、60;               NectarSourcei.trueFit=OnLookeri.trueFit;  280.                 NectarSourcei.fitness=OnLookeri.fitness;  28

73、1.             else  282.               283.                 NectarSourcei.trail

74、+;  284.               285.            286.         i+;  287.         if

75、60;(i=FoodNumber)  288.           289.             i=0;  290.           291.       292. &#

76、160; 293.   294.   295. /*只有一只侦查蜂*/  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 (NectarSourcei.trail>NectarSourc