人工蜂群算法（源码）

人工蜂群算法（源码）

AN IDEA BASED ON HONEY BEE SWARM FOR NUMERICAL OPTIMIZATION

这篇论文没有讲到具体如何实现，但是大家可以通过去官网学习一下这个算法。

算法主要的变化，由三种蜜蜂的行为决定。

适应度值修正

       fitness  
     
     
     
       ( 
      
      
       
       
         X 
        
       
         m 
        
       
      
        → 
       
      
     
       ) 
      
     
    
      = 
     
     
     
       { 
      
      
       
        
         
          
          
            1 
           
          
            / 
           
           
           
             ( 
            
           
             1 
            
           
             + 
            
           
             f 
            
            
            
              ( 
             
             
              
              
                X 
               
              
                m 
               
              
             
               → 
              
             
            
              ) 
             
            
           
             ) 
            
           
          
         
        
        
         
          
          
             if  
           
          
            f 
           
           
           
             ( 
            
            
             
             
               X 
              
             
               m 
              
             
            
              → 
             
            
           
             ) 
            
           
          
            ≥ 
           
          
            0 
           
          
         
        
       
       
        
         
          
          
            1 
           
          
            + 
           
          
            a 
           
          
            b 
           
          
            s 
           
           
           
             ( 
            
           
             f 
            
            
            
              ( 
             
             
              
              
                X 
               
              
                m 
               
              
             
               → 
              
             
            
              ) 
             
            
           
             ) 
            
           
          
         
        
        
         
          
          
             if  
           
          
            f 
           
           
           
             ( 
            
            
             
             
               X 
              
             
               m 
              
             
            
              → 
             
            
           
             ) 
            
           
          
            < 
           
          
            0 
           
          
         
        
       
      
     
       } 
      
     
    
   
     \text { fitness }\left(\overrightarrow{X_m}\right)=\left\{\begin{array}{cl}1 /\left(1+f\left(\overrightarrow{X_m}\right)\right) & \text { if } f\left(\overrightarrow{X_m}\right) \geq 0 \\1+a b s\left(f\left(\overrightarrow{X_m}\right)\right) & \text { if } f\left(\overrightarrow{X_m}\right)<0\end{array}\right\} 
    
   
  fitness (Xm​​)=⎩⎨⎧​1/(1+f(Xm​​))1+abs(f(Xm​​))​ if f(Xm​​)≥0 if f(Xm​​)<0​⎭⎬⎫​

首先，人工蜂群算法做的是求解最小值的问题，为了使得后面的轮盘赌算法能更好的运行，所以使用了这个修正函数，当原来的适应度值越小的时候，修正后的适应度值就会变得更大，并且修正过后的适应度值都为正数，同时，当适应度值为正数时候他修改后的适应度值小于等1，适应度值为负数的时候，适应度值大于1。

雇佣蜂(employed bee)

雇佣蜂负责在蜜源的附近搜索

publicvoidemployeeMove(){for(int i =0;i<employeeBeeSize;i++){int j =(int)(Math.random()*employeeBeeSize);while(j==i){
                j =(int)(Math.random()*employeeBeeSize);//i!=j}//遍历所有的蜜源， 并且从里面挑出一个不是自己的蜜源的蜜源，i!=jint d =(int)(Math.random()*dimension);//随机挑一个维度进行变异Individual oldInd = honey.get(i);double xid = oldInd.getPosition().get(d);double xjd = honey.get(j).getPosition().get(d);double phi =Math.random()*2-1;//[-1,1)double vid = xid+phi*(xid-xjd);Position newPos = oldInd.getPosition().clone();
            newPos.set(d,vid);Individual newInd =newIndividual(newPos);updateFitness(newInd);if(newInd.modifyFitness>oldInd.modifyFitness){//修正过以后越大越好
                honey.set(i,newInd);//贪婪交换
                trail[i]=0;}else{
                trail[i]++;}}}

这里是雇佣蜂的搜索

• 遍历所有的雇佣蜂，由于直接将蜜源当成雇佣蜂来写比较方便，所以后面不管是雇佣蜂还是旁观蜂都用蜜源（honey表示）
• 随机挑一个和自己不一样的蜜源，并且挑选一个维度使用公式 x i d = x i d + ϕ ∗ ( x i d − x k d ) x_{id} = x_{id}+\phi *(x_{id}-x_{kd}) xid​=xid​+ϕ∗(xid​−xkd​)进行变异，其中i是当前的蜜源，k是随机挑出来的蜜源，d代表着要变异的维度， ϕ \phi ϕ为(-1,1)上面均匀分布的随机数。
• 假如更新过后的蜜源比原来的蜜源要好，就替换，假如不是则 t r a i l trail trail增加， t r a i l trail trail是记录当前的蜜源有多久没有变化的。 t r a i l trail trail具有上限，当 t r a i l trail trail超过 l i m i t limit limit值的时候就会进行侦察峰的行为， l i m i t = d i m e n s i o n ∗ 10 limit = dimension * 10 limit=dimension∗10

旁观蜂(onlooker bee)

publicvoidonlookerMove(){double sum =0;for(int i =0;i<employeeBeeSize;i++){
            sum+=honey.get(i).getModifyFitness();}for(int i =0;i<onlookersSize;i++){double prob =Math.random()*sum;int select =0;double curProb =0;for(int j =0;j<employeeBeeSize;j++){
                curProb+=honey.get(j).getModifyFitness();if(prob<curProb){
                    select = j;break;}}int selectDimension =(int)(dimension*Math.random());Individual oldInd = honey.get(i);double xid = oldInd.getPosition().get(selectDimension);double xjd = honey.get(select).getPosition().get(selectDimension);double phi =Math.random()*2-1;//[-1,1)double vid = xid+phi*(xid-xjd);Position newPos = oldInd.getPosition().clone();
            newPos.set(selectDimension,vid);Individual newInd =newIndividual(newPos);updateFitness(newInd);if(newInd.modifyFitness>oldInd.modifyFitness){//最大化修正过的适应度值，mini
                honey.set(i,newInd);//贪婪交换
                trail[i]=0;}else{
                trail[i]++;}}}

旁观蜂阶段大致是和雇佣蜂阶段相同的，最大的不同点就是，雇佣蜂阶段使用的是随机挑选一个雇佣蜂进行跟随，但是在旁观蜂阶段使用的是贪心形选择，将修正过后的适应度值作为选取轮盘赌的依据

轮盘赌的公式为:

       p 
      
     
       m 
      
     
    
      = 
     
     
      
      
        f 
       
      
        i 
       
       
       
         t 
        
       
         m 
        
       
       
       
         ( 
        
        
         
         
           X 
          
         
           m 
          
         
        
          → 
         
        
       
         ) 
        
       
      
      
       
       
         ∑ 
        
        
        
          m 
         
        
          = 
         
        
          1 
         
        
        
        
          ∣ 
         
        
          P 
         
        
          ∣ 
         
        
       
      
        f 
       
      
        i 
       
       
       
         t 
        
       
         m 
        
       
       
       
         ( 
        
        
         
         
           X 
          
         
           m 
          
         
        
          → 
         
        
       
         ) 
        
       
      
     
    
   
     p_m=\frac{f i t_m\left(\overrightarrow{X_m}\right)}{\sum_{m=1}^{|P|} f i t_m\left(\overrightarrow{X_m}\right)} 
    
   
 pm​=∑m=1∣P∣​fitm​(Xm​​)fitm​(Xm​​)​

注意这里的fit为修改过后的适应度值，修改过后的适应度值越大，则在该轮被选取的概率越大。

同样的，这里变化的公式为

      x 
     
     
     
       i 
      
     
       d 
      
     
    
   
     = 
    
    
    
      x 
     
     
     
       i 
      
     
       d 
      
     
    
   
     + 
    
   
     ϕ 
    
   
     ∗ 
    
   
     ( 
    
    
    
      x 
     
     
     
       i 
      
     
       d 
      
     
    
   
     − 
    
    
    
      x 
     
     
     
       k 
      
     
       d 
      
     
    
   
     ) 
    
   
  
    x_{id} = x_{id}+\phi *(x_{id}-x_{kd}) 
   
  
xid​=xid​+ϕ∗(xid​−xkd​)，k为根据轮盘赌选出的蜜蜂。

侦察峰（scout bee）

侦察峰

publicvoidscoutMove(){int selectMaxTrail =0;int limit = dimension*10;for(int i =0;i<employeeBeeSize;i++){//find max trail beeif(trail[i]>limit&&trail[selectMaxTrail]< trail[i]){
                selectMaxTrail = i;}}if(trail[selectMaxTrail]>limit){Individual scout =newIndividual(positionFactory.initRandomPosition());updateFitness(scout);
            trail[selectMaxTrail]=0;
            honey.set(selectMaxTrail,scout);}}

这里就是每一轮都挑出最大的trail的蜜源出来，假如蜜源超过上限的话，就重新初始化这个蜜源。

总体流程就是这样↓

将侦察蜂送到初始化的食物源
重复
    雇佣蜂行为
    旁观蜂行为
    侦察峰行为
    记录下最优解
直到（需求被满足）

总体流程代码

importjava.util.*;//人工蜂群优化算法publicclass ABC{int populationSize =40;int onlookersSize = populationSize/2;//跟随蜂int employeeBeeSize = populationSize/2;//雇佣蜂Individual scout;List<Individual> honey;PositionFactory positionFactory;Individual bestBee;int dimension;int trail[];//记录迭代次数publicABC(int dimension,int ub,int lb){this.dimension = dimension;
        positionFactory =newPositionFactory(dimension,ub,lb);init();int iterTime =0;int maxIterTime =1000;while(iterTime<maxIterTime){employeeMove();onlookerMove();recordBest();scoutMove();recordBest();
            iterTime++;System.out.println(bestBee.fitness+"   "+bestBee.modifyFitness);}}publicstaticvoidmain(String[] args){newABC(2,4,-2);}publicvoidinit(){
        scout =newIndividual(positionFactory.initRandomPosition());updateFitness(scout);
        honey =newArrayList<>(onlookersSize);for(int i =0; i < onlookersSize; i++){Position p = positionFactory.initRandomPosition();Individual individual =newIndividual(p);updateFitness(individual);
            honey.add(individual);}
        trail =newint[onlookersSize];Arrays.fill(trail,0);}publicvoidemployeeMove(){for(int i =0;i<employeeBeeSize;i++){int j =(int)(Math.random()*employeeBeeSize);while(j==i){
                j =(int)(Math.random()*employeeBeeSize);//i!=j}int d =(int)(Math.random()*dimension);Individual oldInd = honey.get(i);double xid = oldInd.getPosition().get(d);double xjd = honey.get(j).getPosition().get(d);double phi =Math.random()*2-1;//[-1,1)double vid = xid+phi*(xid-xjd);Position newPos = oldInd.getPosition().clone();
            newPos.set(d,vid);Individual newInd =newIndividual(newPos);updateFitness(newInd);if(newInd.modifyFitness>oldInd.modifyFitness){//修正过以后越大越好
                honey.set(i,newInd);//贪婪交换
                trail[i]=0;}else{
                trail[i]++;}}}publicvoidonlookerMove(){double sum =0;for(int i =0;i<employeeBeeSize;i++){
            sum+=honey.get(i).getModifyFitness();}for(int i =0;i<onlookersSize;i++){double prob =Math.random()*sum;int select =0;double curProb =0;for(int j =0;j<employeeBeeSize;j++){
                curProb+=honey.get(j).getModifyFitness();if(prob<curProb){
                    select = j;break;}}int selectDimension =(int)(dimension*Math.random());Individual oldInd = honey.get(i);double xid = oldInd.getPosition().get(selectDimension);double xjd = honey.get(select).getPosition().get(selectDimension);double phi =Math.random()*2-1;//[-1,1)double vid = xid+phi*(xid-xjd);Position newPos = oldInd.getPosition().clone();
            newPos.set(selectDimension,vid);Individual newInd =newIndividual(newPos);updateFitness(newInd);if(newInd.modifyFitness>oldInd.modifyFitness){//最大化修正过的适应度值，mini
                honey.set(i,newInd);//贪婪交换
                trail[i]=0;}else{
                trail[i]++;}}}publicvoidscoutMove(){int selectMaxTrail =0;int limit = dimension*10;for(int i =0;i<employeeBeeSize;i++){//find max trail beeif(trail[i]>limit&&trail[selectMaxTrail]< trail[i]){
                selectMaxTrail = i;}}if(trail[selectMaxTrail]>limit){Individual scout =newIndividual(positionFactory.initRandomPosition());updateFitness(scout);
            trail[selectMaxTrail]=0;
            honey.set(selectMaxTrail,scout);}}//求解最小值问题publicvoidrecordBest(){Individual curBestBee =Collections.min(honey,newComparator<Individual>(){@Overridepublicintcompare(Individual o1,Individual o2){returnnewDouble(o1.getFitness()).compareTo(newDouble(o2.getFitness()));}});if(bestBee==null){
            bestBee = curBestBee;}elseif(bestBee.fitness>curBestBee.fitness){
            bestBee = curBestBee;}}publicvoidupdateFitness(Individual individual){
        individual.fitness =sinsin(individual.getPosition());
        individual.modifyFitness =modifyFitness(individual.fitness);}publicstaticdoubleMichalewicz(Position position){double res =0;double m =10;for(int i =0; i < position.size(); i++){double x = position.get(i);
            res+=-Math.sin(x)*Math.pow(Math.sin((i+1)*x*x/Math.PI),2*m);}return res;}publicstaticdoublesinsin(Position position){double res =0;for(int i =0;i<position.size();i++){double x = position.get(i);
            res+=Math.sin(x);}return res;}publicstaticdoublemodifyFitness(double value){if(value>=0){return1.0/(1.0+value);}else{return1+Math.abs(value);}}}

总结

这篇算法有粒子群算法的影子，在旁观蜂阶段使用轮盘赌算法，同时也有差分进化算法的影子：雇佣蜂阶段搜索猎物。而且这个算法没有什么需要调参的地方，感觉还行，这篇算法要注意的地方是适应度修正的地方然后就没有了。