人工蜂群(ABC)算法

又一个群体智能算法，因为最近有项目需求，让我不得不研究这个很早就了解一点皮毛的算法。维基上面还没有中文词条，只能才各种博客上学习了解。标准的ABC算法很简单，所以我花了点时间，整理了一下该算法。

　　人工蜂群算法是由Karaboga在2005年提出来的一种新颖的基于群体智能的全局优化算法，其直观背景来源于蜂群的采蜜行为，蜜蜂根据各自的分工进行不同的活动，并实现蜂群信息的共享和交流，从而找到问题的最优解。人工蜂群算法属于群智能算法的一种。 -CSDN

二、ABC 算法原理：

　　标准的ABC算法将人工蜂群分为三类：采蜜蜂，观察蜂以及侦察蜂。采蜜蜂主要负责采蜜，与蜜源一一对应，负责搜索蜜源周围邻域内的其他蜜源；观察蜂刚开始什么都不干，躺在蜂巢里面等采蜜蜂回到蜂巢后，根据其提供的信息，使用贪婪策略选择去哪一个蜜源采蜜（当然，去了蜜源之后，也会在其领域周围随机搜索新蜜源）；当某个蜜源在限定的次数内都没有搜索到其周围更好的蜜源时，需要抛弃该蜜源，采蜜蜂成为侦察蜂，随机搜索新的蜜源。整个蜂群的目标是：寻找最大的蜜源，即多目标问题的全局最优。

三、ABC算法的流程：

1.初始化

　　刚开始，对整个蜂群进行初始化。蜂群的规模为2SN，采蜜蜂和观察蜂的数量相等，均为SN。蜜源的数量与采蜜蜂相等，也为SN。设定蜜源位置的维数D，以及各维度的上下界，蜜源侦查限度limit和循环次数。然后，给出蜜源的初始位置：x=low+rand()(high−low)x=low+rand()(high−low)。

2.开始循环：

　　循环阶段可以分为三个步骤：采蜜蜂行为、观察蜂行为以及侦察蜂行为。每一层循环都要对这三种蜜蜂的行为进行执行。

采蜜蜂行为：

　　采蜜蜂是和蜜源一一对应的，因此，为了蜜源的更优化，它需要在自己对应的蜜源位置进行邻域随机搜索，其搜索的公式如下：
$$X{id}’=X{id}+\Phi{id}\cdot(X{id}-X_{kd})$$

其中，XX表示蜜源的位置，ii 表示第ii 个蜜源，dd 表示蜜源位置的第dd维，是随机选择的，kk表示第kk个蜜源，是在1，2，…,SN1，2，…,SN中随机选择的一个与ii 不相等的数。ΦΦ表示[-1,1]上面的随机数。在搜索到新的位置X’之后，算法使用贪婪策略，选择适应度函数更优（max或者min）的蜜源位置作为该蜜源的新位置。如果该蜜源位置没有更新，则对一个变量count自加一。同时记录下全局最优蜜源。

观察蜂行为：

　　对于每个观察蜂而言，其需要找到一个自己认为最优的蜜源去采蜜。根据所有采蜜蜂回来给出的信息，主要是各个蜜源的适应度fit，按照概率公式选择：
$$P_i={fiti\over\sum{i=1}^{SN} fit_{i}}$$

采用轮盘旋转的方法选择该观察蜂将要去往的蜜源，选定蜜源之后，采用上面采蜜蜂行为的方法对该蜜源进行邻域寻优。同时记录下全局最优最优蜜源。

侦察蜂行为：

　　刚开始并没有侦察蜂的存在。只有当某个蜜源的count变量达到了事先设置的limit限制的时候，蜂群将抛弃该蜜源，同时对应的采蜜蜂变为侦察蜂，并对该侦察蜂配备一个新的蜜源。主要是采用初始化的方法进行配备，其计算公式如下：

其中，minmin和maxmax 分别表示在位置XX 的第dd 维度的最小值和最大值。rr 为[0,1]上的随机数。

四、ABC算法的实例源码

　　有一个网址上面详细地分析了ABC算法的一个实例的运行过程，如果你有兴趣，可以看看。

　　下面，结合一个具体实例，并上面的分析，给出我自己写的ABC算法源码。

给一个比较简单的实例，这样可以自己算出答案，可以进行比较。求解:

具体代码如下：

#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<cmath>
#include<fstream>
#include<iomanip>
using namespace std;

const int NP = 40;//种群的规模，采蜜蜂+观察蜂
const int FoodNumber = NP / 2;//食物的数量，为采蜜蜂的数量
const int limit = 20;//限度，超过这个限度没有更新采蜜蜂变成侦查蜂
const int maxCycle = 10000;//停止条件

/*****函数的特定参数*****/
const int D = 2;//函数的参数个数
const double lb = -100;//函数的下界 
const double ub = 100;//函数的上界

double result[maxCycle] = { 0 };

/*****种群的定义****/
struct BeeGroup
{
    double code[D];//函数的维数
    double trueFit;//记录真实的最小值
    double fitness;
    double rfitness;//相对适应值比例
    int trail;//表示实验的次数，用于与limit作比较
}Bee[FoodNumber];

BeeGroup NectarSource[FoodNumber];//蜜源，注意：一切的修改都是针对蜜源而言的
BeeGroup EmployedBee[FoodNumber];//采蜜蜂
BeeGroup OnLooker[FoodNumber];//观察蜂
BeeGroup BestSource;//记录最好蜜源

/*****函数的声明*****/
double random(double, double);//产生区间上的随机数
void initilize();//初始化参数
double calculationTruefit(BeeGroup);//计算真实的函数值
double calculationFitness(double);//计算适应值
void CalculateProbabilities();//计算轮盘赌的概率
void evalueSource();//评价蜜源
void sendEmployedBees();
void sendOnlookerBees();
void sendScoutBees();
void MemorizeBestSource();


/*******主函数*******/
int main()
{
    ofstream output;
    output.open("dataABC.txt");

    srand((unsigned)time(NULL));
    initilize();//初始化
    MemorizeBestSource();//保存最好的蜜源

    //主要的循环
    int gen = 0;
    while (gen < maxCycle)
    {
        sendEmployedBees();

        CalculateProbabilities();

        sendOnlookerBees();

        MemorizeBestSource();

        sendScoutBees();

        MemorizeBestSource();

        output << setprecision(30) << BestSource.trueFit <<",the answer is: "<< BestSource.code[0]<<","<<BestSource.code[1]<<endl;

        gen++;
    }

    output.close();
    cout << "运行结束!!" << endl;
    return 0;
}

/*****函数的实现****/
double random(double start, double end)//随机产生区间内的随机数
{
    return start + (end - start)*rand() / (RAND_MAX + 1.0);
}

void initilize()//初始化参数
{
    int i, j;
    for (i = 0; i < FoodNumber; i++)
    {
        for (j = 0; j < D; j++)
        {
            NectarSource[i].code[j] = random(lb, ub);        /****蜜源的初始化*****/
            EmployedBee[i].code[j] = NectarSource[i].code[j];/****采蜜蜂的初始化*****/
            OnLooker[i].code[j] = NectarSource[i].code[j];/****观察蜂的初始化****/
            BestSource.code[j] = NectarSource[0].code[j];/*最优蜜源记录*/
        }
        /****蜜源的初始化*****/
        NectarSource[i].trueFit = calculationTruefit(NectarSource[i]);
        NectarSource[i].fitness = calculationFitness(NectarSource[i].trueFit);
        NectarSource[i].rfitness = 0;
        NectarSource[i].trail = 0;
        /****采蜜蜂的初始化*****/
        EmployedBee[i].trueFit = NectarSource[i].trueFit;
        EmployedBee[i].fitness = NectarSource[i].fitness;
        EmployedBee[i].rfitness = NectarSource[i].rfitness;
        EmployedBee[i].trail = NectarSource[i].trail;
        /****观察蜂的初始化****/
        OnLooker[i].trueFit = NectarSource[i].trueFit;
        OnLooker[i].fitness = NectarSource[i].fitness;
        OnLooker[i].rfitness = NectarSource[i].rfitness;
        OnLooker[i].trail = NectarSource[i].trail;
    }
    /*****最优蜜源的初始化*****/
    BestSource.trueFit = NectarSource[0].trueFit;
    BestSource.fitness = NectarSource[0].fitness;
    BestSource.rfitness = NectarSource[0].rfitness;
    BestSource.trail = NectarSource[0].trail;
}

double calculationTruefit(BeeGroup bee)//计算真实的函数值
{
    double truefit = 0;
    /******测试函数1******/
    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)
        / ((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])));

    return truefit;
}

double calculationFitness(double truefit)//计算适应值
{
    double fitnessResult = 0;
    if (truefit >= 0)
    {
        fitnessResult = 1 / (truefit + 1);
    }
    else
    {
        fitnessResult = 1 + abs(truefit);
    }
    return fitnessResult;
}

void sendEmployedBees()//修改采蜜蜂的函数
{
    int i, j, k;
    int param2change;//需要改变的维数
    double Rij;//[-1,1]之间的随机数
    for (i = 0; i < FoodNumber; i++)
    {

        param2change = (int)random(0, D);//随机选取需要改变的维数

        /******选取不等于i的k********/
        while (1)
        {
            k = (int)random(0, FoodNumber);
            if (k != i)
            {
                break;
            }
        }

        for (j = 0; j<D; j++)
        {
            EmployedBee[i].code[j] = NectarSource[i].code[j];
        }

        /*******采蜜蜂去更新信息*******/
        Rij = random(-1, 1);
        EmployedBee[i].code[param2change] = NectarSource[i].code[param2change] + Rij*(NectarSource[i].code[param2change] - NectarSource[k].code[param2change]);
        /*******判断是否越界********/
        if (EmployedBee[i].code[param2change]>ub)
        {
            EmployedBee[i].code[param2change] = ub;
        }
        if (EmployedBee[i].code[param2change] < lb)
        {
            EmployedBee[i].code[param2change] = lb;
        }
        EmployedBee[i].trueFit = calculationTruefit(EmployedBee[i]);
        EmployedBee[i].fitness = calculationFitness(EmployedBee[i].trueFit);

        /******贪婪选择策略*******/
        if (EmployedBee[i].trueFit < NectarSource[i].trueFit)
        {
            for (j = 0; j < D; j++)
            {
                NectarSource[i].code[j] = EmployedBee[i].code[j];
            }
            NectarSource[i].trail = 0;
            NectarSource[i].trueFit = EmployedBee[i].trueFit;
            NectarSource[i].fitness = EmployedBee[i].fitness;
        }
        else
        {
            NectarSource[i].trail++;
        }
    }
}

void CalculateProbabilities()//计算轮盘赌的选择概率
{
    int i;
    double maxfit;
    maxfit = NectarSource[0].fitness;
    for (i = 1; i<FoodNumber; i++)
    {
        if (NectarSource[i].fitness>maxfit)
            maxfit = NectarSource[i].fitness;
    }

    for (i = 0; i < FoodNumber; i++)
    {
        NectarSource[i].rfitness = (0.9*(NectarSource[i].fitness / maxfit)) + 0.1;
    }
}

void sendOnlookerBees()//采蜜蜂与观察蜂交流信息，观察蜂更改信息
{
    int i, j, t, k;
    double R_choosed;//被选中的概率
    int param2change;//需要被改变的维数
    double Rij;//[-1,1]之间的随机数
    i = 0;
    t = 0;  //代表第t只观察蜂
    while (t < FoodNumber)
    {

        R_choosed = random(0, 1);
        if (R_choosed < NectarSource[i].rfitness)//根据被选择的概率选择，（根据概率选择蜜源,蜜源的相对概率越大，被选中的概率也就越大）
        {
            t++;
            param2change = (int)random(0, D);
            //当该观察蜂t选择蜜源i时，根据公式1搜索该蜜源邻域，同时更新蜜源存蜜量
            /******选取不等于i的k********/
            while (1)
            {
                k = (int)random(0, FoodNumber);
                if (k != i)
                {
                    break;
                }
            }

            for (j = 0; j < D; j++)
            {
                OnLooker[i].code[j] = NectarSource[i].code[j];
            }

            /****更新******/
            Rij = random(-1, 1);
            OnLooker[i].code[param2change] = NectarSource[i].code[param2change] + Rij*(NectarSource[i].code[param2change] - NectarSource[k].code[param2change]);

            /*******判断是否越界*******/
            if (OnLooker[i].code[param2change]<lb)
            {
                OnLooker[i].code[param2change] = lb;
            }
            if (OnLooker[i].code[param2change]>ub)
            {
                OnLooker[i].code[param2change] = ub;
            }
            OnLooker[i].trueFit = calculationTruefit(OnLooker[i]);
            OnLooker[i].fitness = calculationFitness(OnLooker[i].trueFit);

            /****贪婪选择策略******/
            if (OnLooker[i].trueFit < NectarSource[i].trueFit)
            {
                for (j = 0; j < D; j++)
                {
                    NectarSource[i].code[j] = OnLooker[i].code[j];
                }
                NectarSource[i].trail = 0;
                NectarSource[i].trueFit = OnLooker[i].trueFit;
                NectarSource[i].fitness = OnLooker[i].fitness;
            }
            else
            {
                NectarSource[i].trail++;
            }

        }
        i++;
        if (i == FoodNumber)
        {
            i = 0;
        }
    }
}


/*******只有一只侦查蜂**********/
void sendScoutBees()//判断是否有侦查蜂的出现，有则重新生成蜜源
{
    int maxtrialindex, i, j;
    double R;//[0,1]之间的随机数
    maxtrialindex = 0;
    for (i = 1; i<FoodNumber; i++)
    {
        if (NectarSource[i].trail>NectarSource[maxtrialindex].trail)
        {
            maxtrialindex = i;
        }
    }
    if (NectarSource[maxtrialindex].trail >= limit)
    {
        /*******重新初始化*********/
        for (j = 0; j < D; j++)
        {
            R = random(0, 1);
            NectarSource[maxtrialindex].code[j] = lb + R*(ub - lb);
        }
        NectarSource[maxtrialindex].trail = 0;
        NectarSource[maxtrialindex].trueFit = calculationTruefit(NectarSource[maxtrialindex]);
        NectarSource[maxtrialindex].fitness = calculationFitness(NectarSource[maxtrialindex].trueFit);
    }
}

void MemorizeBestSource()//保存最优的蜜源
{
    int i, j;
    for (i = 1; i < FoodNumber; i++)
    {
        if (NectarSource[i].trueFit < BestSource.trueFit)
        {
            for (j = 0; j < D; j++)
            {
                BestSource.code[j] = NectarSource[i].code[j];
            }
            BestSource.trueFit = NectarSource[i].trueFit;
        }
    }
}