人工蜂群算法

蜂群算法介绍

基本介绍

人工蜂群算法(Artificial Bee Colnony, ABC) 是模仿蜜蜂行为提出的一种优化方法，是集群智能思想的一个具体应用，它的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。

蜜蜂是一种群居昆虫，虽然单个昆虫的行为极其简单，但是由单个简单的个体所组成的群体却表现出极其复杂的行为。真实的蜜蜂种群能够在任何环境下，以极高的效率从食物源（花朵）中采集花蜜；同时，它们能适应环境的改变。

三个基本组成部分

雇佣蜂、非雇佣蜂、食物源；雇佣蜂和非雇佣蜂负责寻找更优良的食物源。

食物源的位置代表了可行解，而食物源的食物含量代表该解的质量。

雇佣蜂(employed bees)：与特定的食物源相联系(该食物源枯竭之后该雇佣蜂变成侦查蜂)
跟随蜂(on-looker bees)：观察雇佣蜂传递的信息并依据其选择一个食物源
侦察蜂(scout bees)：由食物源枯竭的雇佣蜂生成，随机查找食物源

两个自组织集群模式

对优良食物源的正反馈和对劣质食物源的负反馈；

注意：在其他仿生算法中生物对象都有具体实体存在，如遗传算法中的染色体向量、蚁群算法中的蚂蚁访问矩阵、免疫算法中的抗体种群矩阵，而在蜂群算法中蜜蜂群体没有实体矩阵出现，是以对蜜源矩阵进行不同的操作而体现出来的。

蜂群算法的基本过程

描述：

初始时，所有的食物源位置都是由侦查蜂发现的，然后食物源的食物开始被雇佣蜂和跟随蜂开采，待食物源枯竭之后，对应该食物源的雇佣蜂变为侦察蜂来搜寻更远处的食物源。

伪代码如下：

Initialization Phase;
while(i < iter_max){
    Employed Bees Phase;
    Onlooker Bees Phase;
    Scout Bees Phase;
    Memorize the best solution;
}
print(the final best solution);

初始化阶段

需要初始化的参数有：

代价函数计算函数CostFunction; 代价函数参数数目nVar; 代价函数各参数上下界[VarMin,VarMax]
最大迭代次数iter_max
单次保存的蜜源最大数量nPop
跟随蜂数目nOnLooker
蜜源抛弃上界L(一般为round(0.6*nVar*nPop))
蜜源搜索范围扩大系数a(一般为1)
蜜源位置矩阵PopPositon(nPop行nVar列，每一行代表一个可行解)
蜜源代价矩阵PopCost(nPop行1列，保存每个可行解的质量值)
蜜源选择概率矩阵Probability(nPop行1列，保存跟随蜂选择各蜜源的概率)
历史最优蜜源矩阵BestSol(iter_max+1行nVar列，保存每次迭代中的最优蜜源位置)
蜜源开采量矩阵Mine(nPop行1列，保存每个蜜源被跟随蜂开采的轮数，该数量达到L值后对应该蜜源的雇佣蜂会变成侦查蜂)

初始化蜜源位置：
随机对每个蜜源位置矩阵的每个元素上生成符合该范围的随机数，填充蜜源位置矩阵。

计算初始蜜源代价：
遍历所有蜜源节点，将每个节点的各个参数代入代价函数计算出每个蜜源的代价值（可能还需要代换函数代换成正值），填充蜜源代价矩阵，同时将第0代最优蜜源位置保存到BestSol[0]向量中去。

雇佣蜂阶段

寻找下一个蜜源：
遍历所有蜜源节点，对于节点i，随机选取另一个不为i的节点k，按下式随机计算出雇佣蜂找到的下一个蜜源：

phi = a*rand([-1,1],[1,nVar])
NewPosition = PopPosition[i] + phi*(PopPosition[i]-PopPosition[k])

注：rand([a,b],[x,y])表示产生每个元素在a到b之间，x行y列的矩阵。
第二行代码中的*表示对应元素相乘，而不是矩阵乘法，对应MATLAB中的.*

贪婪选择：
计算新蜜源代价值，并在当前蜜源i和新蜜源中进行贪婪选择，如果选择了新密源，则更新蜜源位置矩阵和蜜源代价矩阵中的节点i，否则在蜜源开采量矩阵Mine中第i位上递增1。

跟随蜂阶段

更新蜜源选择概率矩阵：
根据下式计算并更新Probability矩阵：

$M = \frac{1}{n}*\sum^{n}_{i=1}C_i$

$F_i = e^{-\frac{C_i}{M}} \qquad i = 1,2,...,n$

$P_i = \frac{F_i}{\sum_{k=1}^{n}F_i} \qquad i = 1,2,...,n$

注：M表示各个蜜源代价的算术平均；n为nPop， $C_i$ 为蜜源节点i的代价值； $P_i$ 表示计算得到的Probability矩阵的第i个元素。

跟随蜂选择：
遍历每个跟随蜂，对于每个跟随蜂，先利用计算出的选择概率矩阵执行轮盘赌选择法从所有蜜源中选择一个蜜源(如蜜源k)，并对该蜜源重复雇佣蜂阶段的贪婪选择操作。

侦察蜂阶段

抛弃某些蜜源：
遍历所有蜜源节点，查找Mine值大于阈值L的节点，对这些节点执行随机选择覆盖，并重新计算代价值，并将Mine值归零。伪代码如下：

for i in range(1,nPop):
    if Mine[i] >= L:
        PopPosition[i] = rand([VarMin,VarMax],[1,nVar])
        PopCost[i] = CostFunction(PopPosition[i])
        Mine[i] = 0

更新历史最优蜜源矩阵

遍历所有蜜源节点，将最优节点保存在历史最优蜜源矩阵BestSol的第iter+1行中(第一行是第0代，初始值)。

代码实现

准备使用差分进化算法求解

$f(x,y) = -20 e^{-0.2 \sqrt{\frac{x^2+y^2}{2}}} - e^{\frac{cos \ 2 \pi x \ +\ cos \ 2\pi y}{2}} + 20 + e$

这个神一般的函数在区间 $[-4,4]$ 上的最小值。该函数的图像如下，根据图像易知最小值点为 $(0,0)$ ，最小值为0。