人工蜂群算法

1、原理

        最常见的基于蜜蜂采蜜行为的蜂群算法是Karaboga(2005)提出的人工蜂群算法，通常称该算法为标准（或原始）人工蜂群算法，其主要是为了解决多维和多模的函数优化问题。
        标准的人工蜂群算法通过模拟实际蜜蜂的采蜜机制将人工蜂群分为三类：雇佣蜂、观察蜂和侦察蜂。整个蜂群的目标是寻找花蜜量最大的蜜源。在标准的ABC算法中，雇佣蜂利用先前的蜜源信息寻找新的蜜源并与跟随蜂分享蜜源信息；观察蜂在蜂房中等待并依据雇佣蜂分享的信息寻找新的蜜源；侦查蜂的任务是寻找一个新的有价值的蜜源，它们在蜂房附近地寻找蜜源。
        算法主要包括以下四个部分。
        （1）蜜源初始化：初始化时，随机生成$SN$个可行解（等于雇佣蜂的数量）并计算适应度函数值。随机产生可行解的公式为$$x_{ij}=x_{min,j}+rand(0,1)(x_{max,j}-x_{min,j)}$$其中，$x_i$(i=1,2,…,SN)表示$D$维向量，$D$表示优化参数的个数；$j\in 1,2,...,D$。
        （2）新蜜源的更新搜索：蜜蜂记录自己到目前为止的最优值，并在当前蜜源邻域内展开搜索，基本ABC在蜜源附近搜索新蜜源的公式为$$v_{ij}=x_{ij}+{\phi }_{ij}(x_{ij}-x_{kj})$$其中，$j\in 1,2,...,D$，$k\in 1,2,...,SN$，$k$表示随机生成且$k\ne i$；$\phi$表示[-1,1]的随机数。
        （3）观察蜂选择蜜源的概率为$$P_i=\frac{fit(x_i)}{{\sum }_{n=1}^{SN}fit(x_n)}$$其中，$fit(x_i)$表示第$i$个解的适应度，对应蜜源的丰富程度。蜜源越丰富，被跟随蜂选择的概率越大，按以下式子计算适应度：$$fit(x_i)=\{\begin{array}{ll}\frac{1}{1+f_i},& \text{fi>0}\\ 1+abs(f_i)& \text{fi<0}\end{array}$$其中，$f_i$是蜜源的适应值。

        （4）侦察蜂的产生：为防止算法陷入局部最优，当某蜜源迭代$limit$次没有改进时，便放弃该蜜源，并且将该蜜源记录在禁忌表中，同时该蜜源对应的雇佣蜂转变为侦察蜂，随机产生一个新的位置代替原蜜源。
        人工蜂群算法就是通过不断地角色转换和执行行为模式，最终找到最丰富食物源。在人工蜂群算法中，雇佣蜂有保持优良食物源的作用，具有精英特性；跟随蜂增加较好食物源对应的蜜蜂数，加快算法的收敛；侦察蜂随机搜索新食物源，帮助算法跳出局部最优。

2、算法流程

        人工蜂群算法的算法流程如下：
        步骤1：根据第一个式子初始化种群解$x_i，i=1,...,SN$
        步骤2：计算种群中各个蜜蜂的适应值
        步骤3：cycle=1
        步骤4：repeat
        步骤5：雇佣蜂根据第二个式子产生新的解$v_i$并计算适应值
        步骤6：雇佣蜂根据贪心策略选择蜜源
        步骤7：根据第三个式子计算选择蜜源$x_i$的概率$P_i$
        步骤8：跟随蜂根据概率$P_i$选择蜜源$x_i$，根据第二个式子在该蜜源附近产生新的蜜源$v_i$，并计算新蜜源$v_i$的适应值
        步骤9：跟随蜂根据贪心策略选择蜜源
        步骤10：决定是否存在需要放弃的蜜源，如果存在，根据第一个式子随机产生一个蜜源替代它
        步骤11：记录最优解
        步骤12：cycle=cycle+1
        步骤13：until cycle = MCN ,MCN表示终止代数。

3、函数优化实例

$$minf(x_1,x_2)=0.5+\frac{{sin}^2\sqrt{x_1^2+x_2^2}-0.5}{{(1+0.001(x_1^2+x_2^2))}^2}$$
其中，$-100\le x_1,x_2\le 100（i=1,2,...,30)$

MATLAB绘制上述函数图像代码如下：

X=-100:4:100;
Y=-100:4:100;
[XX,YY]=meshgrid(X,Y);
Z=0.5+(power(sin(sqrt(XX.*XX+YY.*YY)),2)-0.5)./power(1+0.001.*power(XX.*XX+YY.*YY,2),2);
figure
subplot(221)
mesh(X,Y,Z)
subplot(222)
surf(X,Y,Z)
subplot(223)
surfc(X,Y,Z)
subplot(224)
surfl(X,Y,Z)
shading interp;
colormap(gray);

4、求解函数优化的ABC源代码C++

        人工蜂群算法中输入参数：
        蜜源数量$SN=20$
        解向量的维数$Dimension=2$
        最大循环次数$MCN=10000$
        蜜源没改进的最大次数$limit=20$
main.cpp

#include <iostream>
#include <random>
#include <time.h>
using namespace std;
double Xmax = 100, Xmin = -100;
std::default_random_engine random((unsigned int)time(NULL));
std::uniform_real_distribution<double> u(Xmin, Xmax); //随机数分布对象
std::uniform_real_distribution<double> u0(0, 1); //随机数分布对象
std::uniform_real_distribution<double> u1(-1, 1); //随机数分布对象

struct Bee
{
    
public:
	int dimension;//变量的维数
	double *X;//蜜蜂
	double fitdegreevalue = 0;
	double selectprobability = 0;
	int limitcishu = 0;
	void Init(int Dimension)//初始化函数
	{
    
		dimension = Dimension;
		X = new double[dimension];
		for (int j = 0; j < dimension; j++)
			*(X + j) = u(random);
	}
};
struct BeeQun
{
    
public:
	Bee *miyuan, bestmiyuan, *employedbee, *onlookerbee;//蜜源、最好蜜源、雇佣蜂、观察蜂
	int SN;//雇佣蜂的数量、蜜源的数量、观察蜂的数量相等
	int Dimension;//可行解的维数
	int MCN;//终止代数
	int Limit;//为防止算法陷入局部最优，蜜源最大改进次数
	void Init(int sn, int dimension, int mcn, int limit)
	{
    
		SN = sn;
		Dimension = dimension;
		MCN = mcn;
		Limit = limit;
		miyuan = new Bee[SN];
		employedbee = new Bee[SN];
		onlookerbee = new Bee[SN];
		for (int i = 0; i < SN; i++)//蜜源、雇佣峰、观察蜂初始化：随机产生SN个可行解，并计算适应度函数值
		{
    
			(miyuan + i)->Init(Dimension);
			double beefunvalue = CalculateFitValue(*(miyuan + i));
			(miyuan + i)->fitdegreevalue = CalculateFitDegree(beefunvalue);

			(employedbee + i)->Init(Dimension);
			double employedbeefunvalue = CalculateFitValue(*(employedbee + i));
			(employedbee + i)->fitdegreevalue = CalculateFitDegree(employedbeefunvalue);

			(onlookerbee + i)->Init(Dimension);
			double onlookerbeefunvalue = CalculateFitValue(*(onlookerbee + i));
			(onlookerbee + i)->fitdegreevalue = CalculateFitDegree(onlookerbeefunvalue);
		}
		bestmiyuan.Init(Dimension);//最好蜜源初始化
		for (int j = 0; j < Dimension; j++)
		{
    
			bestmiyuan.X[j] = miyuan->X[j];
		}
		bestmiyuan.fitdegreevalue = miyuan->fitdegreevalue;
	}
	double CalculateFitValue(Bee be)//计算蜜蜂的目标函数值
	{
    
		double funvalue = 0;
		for (int j = 0; j < Dimension; j++)
			funvalue += be.X[j] * be.X[j];
		funvalue = 0.5 + (pow(sin(sqrt(funvalue)), 2) - 0.5) / pow((1 + 0.001*funvalue), 2);
		return funvalue;
	}
	double CalculateFitDegree(double fi)//由目标函数值计算适应度
	{
    
		double fitnessdu = 0;
		if (fi > 0) fitnessdu = 1.0 / (1 + fi);
		else fitnessdu = 1.0 + abs(fi);
		return fitnessdu;
	}
	void EmployedBeeOperate()//雇佣蜂操作函数
	{
    
		std::uniform_int_distribution<int> uD(1, Dimension); //随机数分布对象
		std::uniform_int_distribution<int> uSN(1, SN); //随机数分布对象
		for (int i = 0; i < SN; i++)
		{
    
			for (int j = 0; j < Dimension; j++)//雇佣峰利用先前的蜜源信息寻找新的蜜源
			{
    
				(employedbee + i)->X[j] = (miyuan + i)->X[j];
			}
			int k, jie;//随机生成且 k≠i k∈[1,SN]
			jie = uD(random) - 1;//jie为【1，Dimension】上的随机数
			double φ = u1(random);//φ表示[-1,1]之间的随机数
			while (true)
			{
    
				k = uSN(random) - 1;
				if (k != i)break;
			}
			(employedbee + i)->X[jie] = (miyuan + i)->X[jie] + φ*((miyuan + i)->X[jie] - (miyuan + k)->X[jie]);//搜索新蜜源
																											   //保证蜜源位置不越界
			if ((employedbee + i)->X[jie] > Xmax) (employedbee + i)->X[jie] = Xmax;
			else if ((employedbee + i)->X[jie] < Xmin) (employedbee + i)->X[jie] = Xmin;
			(employedbee + i)->fitdegreevalue = CalculateFitDegree(CalculateFitValue(*(employedbee + i)));//计算适应值
																										  //雇佣蜂根据贪心策略选择蜜源
			if (CalculateFitValue(*(employedbee + i)) < CalculateFitValue(*(miyuan + i)))
			{
    
				for (int j = 0; j < Dimension; j++)
					(miyuan + i)->X[j] = (employedbee + i)->X[j];
				(miyuan + i)->limitcishu = 0;
				(miyuan + i)->fitdegreevalue = (employedbee + i)->fitdegreevalue;
			}
			else
				(miyuan + i)->limitcishu++;//蜜源未改进次数加一
		}
	}
	void CalculateProbability()//计算蜜源概率的函数
	{
    
		for (int i = 0; i < SN; i++)
		{
    
			(miyuan + i)->fitdegreevalue = CalculateFitDegree(CalculateFitValue(*(miyuan + i)));
		}
		double sumfitdegreevalue = 0;
		for (int i = 0; i < SN; i++)
		{
    
			sumfitdegreevalue += (miyuan + i)->fitdegreevalue;
		}
		for (int i = 0; i < SN; i++)
		{
    
			(miyuan + i)->selectprobability = (miyuan + i)->fitdegreevalue / sumfitdegreevalue;
		}
	}
	void OnLookerBeeOperate()//观察蜂操作
	{
    
		std::uniform_int_distribution<int> uD(1, Dimension); //随机数分布对象
		std::uniform_int_distribution<int> uSN(1, SN); //随机数分布对象
		int m = 0;
		while (m < SN)//为所有的观察蜂按照概率选择蜜源并搜索新蜜源，计算新蜜源适应值
		{
    
			double m_choosedprobability = u0(random);//0~1之间的随机数
			for (int i = 0; i < SN; i++)
			{
    
				if (m_choosedprobability < (miyuan + i)->selectprobability)
				{
    
					int k, jie;//随机生成且 k≠i k∈[1,SN]
					jie = uD(random) - 1;//jie为【1，Dimension】上的随机数
					double φ = u1(random);//φ表示[-1,1]之间的随机数
					while (true)
					{
    
						k = uSN(random) - 1;
						if (k != i)break;
					}
					for (int j = 0; j < Dimension; j++)
						(onlookerbee + m)->X[j] = (miyuan + i)->X[j];
					(onlookerbee + m)->X[jie] = (miyuan + i)->X[jie] + φ*((miyuan + i)->X[jie] - (miyuan + k)->X[jie]);//搜索新蜜源
					if ((onlookerbee + m)->X[jie] > Xmax) (onlookerbee + m)->X[jie] = Xmax;
					else if ((onlookerbee + m)->X[jie] < Xmin) (onlookerbee + m)->X[jie] = Xmin;//判断是否越界
					(onlookerbee + m)->fitdegreevalue = CalculateFitDegree(CalculateFitValue(*(onlookerbee + m)));
					//贪心策略选择蜜源
					if (CalculateFitValue(*(onlookerbee + m)) < CalculateFitValue(*(miyuan + i)))
					{
    
						for (int j = 0; j < Dimension; j++)
							(miyuan + i)->X[j] = (onlookerbee + m)->X[j];
						(miyuan + i)->fitdegreevalue = (onlookerbee + m)->fitdegreevalue;
					}
					else
						(miyuan + i)->limitcishu++;
					m++;
				}break;
			}
		}
	}
	void ScoutBeeOperate()//侦查蜂操作,决定蜜源是否放弃，并随机产生新位置替代原蜜源
	{
    
		for (int i = 0; i < SN; i++)
		{
    
			if ((miyuan + i)->limitcishu >= Limit)
			{
    
				for (int j = 0; j < Dimension; j++)
				{
    
					(miyuan + i)->X[j] = u(random);//随机产生可行解
				}
				(miyuan + i)->limitcishu = 0;
				(miyuan + i)->fitdegreevalue = CalculateFitDegree(CalculateFitValue(*(miyuan + i)));
			}
		}
	}
	void SaveBestMiyuan()//记录最优解的函数
	{
    
		for (int i = 0; i < SN; i++)
		{
    
			if (CalculateFitValue(*(miyuan + i)) < CalculateFitValue(bestmiyuan))
			{
    
				for (int j = 0; j < Dimension; j++)
					bestmiyuan.X[j] = (miyuan + i)->X[j];
			}
		}
	}
	void shuchumiyuan()
	{
    
		for (int i = 0; i<SN; i++)
			for (int j = 0; j < Dimension; j++)
			{
    
				if (j == Dimension - 1)std::cout << (miyuan + i)->X[j] << endl;
				else std::cout << (miyuan + i)->X[j] << ", ";
			}
	}
	void ShuchuBestmiyuan()
	{
    
		for (int j = 0; j < Dimension; j++)
		{
    
			if (j == Dimension - 1) std::cout << bestmiyuan.X[j] << ")" << "对应的函数值为：" << CalculateFitValue(bestmiyuan) << endl;
			else if (j == 0) std::cout << "(" << bestmiyuan.X[j] << ",";
			else std::cout << bestmiyuan.X[j] << ",";
		}
	}
	void DoABC(int sn, int dimension, int mcn, int limit)//运行人工蜂群算法的函数
	{
    
		Init(sn, dimension, mcn, limit);//初始化
		shuchumiyuan();
		SaveBestMiyuan();//保存最好蜜源
		for (int k = 0; k < MCN; k++)
		{
    
			EmployedBeeOperate();
			CalculateProbability();
			OnLookerBeeOperate();
			SaveBestMiyuan();
			ScoutBeeOperate();
			SaveBestMiyuan();
			std::cout << "第" << k + 1 << "次迭代的最优解为：";
			ShuchuBestmiyuan();
		}
	}
};
int main()
{
    
	int itetime = 0;
	while (true)
	{
    
		std::cout << "请输入迭代次数：";
		std::cin >> itetime;
		BeeQun bq;
		bq.DoABC(20, 2, itetime, 20);
	}
	system("pause");
	return 0;
}

运行结果：