遗传算法(Genetic Algorithm, GA)是一种随机搜索算法, 具有全局搜索能力和较强的鲁棒性, 但是, 系统中的反馈信息得不到充分利用, 容易陷入“早熟”^[1-2], 而且算法中的遗传操作比较耗时.

人工蜂群算法(Artificial Bee Colony Algorithm, ABCA)是Karaboga^[3]在2005年提出的一种基于蜜蜂采蜜的群体智能优化算法, 在搜索过程中仅以适应度函数作为进化依据^[4], 反馈信息得到充分利用, 在每次的迭代过程中都进行全局和局部搜索, 极大地提高了找到最优解的概率, 但是, 算法在初期寻优速度较慢.

遗传-人工蜂群融合算法(Genetic-Artificial Bee Colony Algorithm, G-ABCA)正是基于遗传算法与人工蜂群算法的优缺点, 在初期采用改进的遗传算法得到“蜜源”分布, 在后期采用人工蜂群算法寻找最优解, 实现二者的互补, 以提升算法的有效性.

遗传-人工蜂群融合算法的基本原理是:与袁艳花^[5]提出的融合思想不同, 不是将遗传算法的交叉和变异算子融合到人工蜂群算法的搜索过程中, 而是首先采用改进的遗传算法过程得到“蜜源”分布, 然后根据得到的“蜜源”分布, 采用人工蜂群算法进行最优解搜索.通过这种融合, 避免遗传算法发生“早熟”, 并加速人工蜂群算法的寻优速度.

G-ABCA中的遗传算法采用表达精确的实数编码, 以克服二进制编码的换算占用计算时间的问题^[6]; 计算编码后的染色体适应度值, 通过适应度比例法^[7]、自适应的交叉和变异概率公式^[8]进行遗传操作; 同时采用最优保存策略, 以防止优良的个体在遗传操作中过早的丢失^[9].记遗传算法过程的最大迭代次数为$\mbox{maxgen}$, 初始的交叉概率和变异概率为$\mbox{pc}$和$\mbox{pm}$, 则其自适应的交叉和变异概率公式为

$ \begin{eqnarray}\label{eq:1} &&{pcross}={Pcross}-\frac{\mbox{pc}-0.6}{\mbox{maxgen}}, \end{eqnarray} $

(2.1)

$ \begin{eqnarray}\label{eq:2} &&{pmutation}={Pmutation}+\frac{0.1-\mbox{pm}}{\mbox{maxgen}}, \end{eqnarray} $

(2.2)

其中${pcross}$和${pmutation}$表示新一代的交叉和变异概率, ${Pcross}$和${Pmutation}$表示当代的交叉和变异概率.显然, $\mbox{pc}$、$\mbox{pm}$和$\mbox{maxgen}$是固定的常数, 由交叉和变异概率公式可知, 新的个体是否进行交叉或变异只与当前的交叉或变异概率有关, 而与之前的交叉或变异概率以及时刻（即迭代次数）无关, 因此具有Markov性.

G-ABCA中的人工蜂群算法采用标准模型^[10], 分别记${N}_{s}$、${N}_{e}$为蜜蜂总数、采蜜蜂种群规模, 令跟随蜂种群规模与采蜜蜂相同, 记${D}$为个体向量维数, ${S}$为个体搜索空间, $X(m)$为第${m}$代采蜜蜂种群, 初始采蜜蜂种群$X(0)$为改进的遗传算法得到的结果.首先, 由采蜜蜂寻找新蜜源, 搜索公式为

$ \begin{equation}\label{eq:3} V_{i}^{j}=X_{i}^{j}+\varphi_{i}^{j}(X_{i}^{j}-X_{k}^{j}), \end{equation} $

(2.3)

其中, $j\in\{1, 2, \cdots, D\}$, $k\in\{1, 2, \cdots, N_{e}\}$且$k\neq j$, $\varphi_{i}^{j}$为区间$[-1, 1]$上的随机数, $V\in S$.显然, 该搜索只与当前的蜜源位置有关, 而与之前的蜜源及时刻$m$无关.

然后, 采用贪婪选择算子在新蜜源和原蜜源之间选出适应度更优的(这里以适应度越小越优为例)并保留, 记作$T_{gs}:S^{2}\rightarrow S$, 其概率分布与时刻无关, 为

$ \begin{equation}\label{eq:4} P\{T_{gs}(X_{i}, V_{i})=V_{i}\}=\left\{\begin{array} {r@{\quad}l} 1, & f(V_{i})\leq f(X_{i});\\ 0, & f(V_{i})> f(X_{i}). \end{array} \right. \end{equation} $

(2.4)

跟随蜂依照采蜜蜂种群的适应度值选择一个采蜜蜂, 并在其邻域内按式(2.3) 进行新蜜源搜索并执行贪婪选择算子.当某只采蜜蜂在蜜源周围搜索的次数达到一定阈值仍未找到最优位置时, 重新随机初始化该采蜜蜂的位置, 初始化公式为

$ \begin{equation}\label{eq:5} X_{i}(m+1)=X_{\min}+\mbox{rand}(0, 1)(X_{\max}-X_{\min}). \end{equation} $

(2.5)

该步骤通过增加种群的多样性, 防止了算法陷入局部最优, 同时保证了搜索始终在邻域内进行.

设$S^{N}=\{X=(X_{1}, X_{2}, \cdots, X_{N}), X_{i}\in S(i\leq N)\}$为种群空间, $S^{2}=\{(X_{1}, X_{2}), X_{i}\in S(i=1, 2)\}$为母体空间, $S$为个体空间, 个体$X_{i}$的长度$l$称为链长, $N$为种群规模.记$n$为遗传算法过程的迭代次数, $m$为人工蜂群算法的迭代次数, $P$为$S^{N}$上的概率分布.融合算法可以看作是改进遗传算法的扩展, 其中共包括四个过程:选择算子$T_{s}$、交叉算子$T_{c}$、变异算子$T_{m}$、蜜源算子$T_{b}$, 其基本定义如下:

定义3.1^[11]  适应度函数为$f:S\rightarrow R$, 即为个体空间到实数空间的映射; 全局最优解为$G=\{X, \forall Y\in S, f(X)\leq f(Y)\}$; 满意解$B=\{X\in B, \forall Y\notin B, f(X)\leq f(Y)\}$.

定义3.2^[11]  选择算子$T_{s}:S^{N}\rightarrow S$, 即在种群中随机选择一个个体的映射, 母体选择算子的概率为

$ P\{T_{s}(X)=(X_{i}, X_{j})\}=\frac{f(X_{i})}{\sum\limits_{k=1}^{N}f(X_{k})}\cdot\frac{f(X_{j})}{\sum\limits_{m=1}^{N}f(X_{m})}. $

(3.1)

定义3.3^[11]  交叉算子$T_{c}:S^{2}\rightarrow S$, 即母体空间到个体空间的映射, 记$k$为可生成$Y$的基因位置的个数, 单点交叉算子的概率为

$ P\{T_{c}(X_{1}, X_{2})=Y\}=\left\{\begin{array} {c@{\quad}l} \frac{k}{l}{pcross}, & Y\neq X_{1};\\ (1-{pcross})+\frac{k}{l}{pcross}, & Y=X_{1}. \end{array}\right. $

(3.2)

定义3.4^[11]  变异算子$T_{m}:S\rightarrow S$, 即个体空间到个体空间的随机映射, 变异算子的概率为

$ P\{T_{m}(X)=Y\}={pmutation}^{d(X, Y)}(1-{pmutation})^{1-d(X, Y)}, $

(3.3)

其中, $d(X, Y)$为$X$与$Y$的Hamming距离.

定义3.5  蜜源算子$T_{b}:S^{N}\rightarrow S$, 即在蜜源位置序列中选择最优个体的映射, 蜜源算子的概率为

$ P\{T_{b}(X)=X_{i}\}=\frac{f(X_{i})}{\sum\limits_{j=1}^{N}f(X_{j})}. $

(3.4)

引理3.1  改进的遗传算法种群序列$\{X(n);n\geq0\}$是有限齐次Markov链, 且以概率1收敛到满意种群集$G^{*}$的子集$G_{0}^{*}=\{Y=(Y_{1}, Y_{2}, \cdots, Y_{N});Y_{N}\in G\}$, 即

$ \mathop {\lim }\limits_{n \to \infty } P\{ X(n) \in G_0^*/X(0) = {X_0}\} = 1. $

(3.5)

证  因为采用最优保存策略的遗传算法的种群序列是有限齐次Markov链, 并且以概率1收敛到满意种群集的子集^[12-14], 改进的遗传算法采用了最优保存策略, 并且其改进的交叉和变异概率公式对算法的收敛性没有影响, 能保持Markov性, 因此, 改进的遗传算法种群序列仍是有限齐次Markov链, 且以概率1收敛到满意种群集$G^{*}$的子集.

引理3.2  引入适应度函数的人工蜂群系统序列$\{X(m), f^{*}(m);m=1, 2, \cdots\}$是有限齐次Markov链.

证  因为人工蜂群算法序列$\{X(m);m=1, 2, \cdots\}$是有限齐次Markov链且以概率1收敛^[15], 适应度函数序列具有Markov性, 因此, 类比引入适应度函数的蚂蚁系统序列^[16]仍是有限齐次Markov链可知, 引入适应度函数的人工蜂群系统序列是有限齐次Markov链.

定理3.1  G-ABCA算法的种群序列$\{X(n);n\geq0\}$是有限齐次Markov链.

证  由引理3.1知, 改进的遗传算法$X(n+1)$只与$X(n)$有关, 与迭代次数$n$无关.由引理3.2知, 人工蜂群系统$\{X(m+1), f^{*}(m+1)\}$只与$\{X(m), f^{*}(m)\}$有关, 而与迭代次数$m$无关.同时, 由人工蜂群算法的设置可知, 算法每一次只更新最优蜜源位置, 具有改进的遗传算法的所有特征.因此取

$ \begin{eqnarray}\label{eq:6} &&T=T_{b}\circ T_{m}\circ T_{c}\circ T_{s}, \end{eqnarray} $

(3.6)

$ \begin{eqnarray}\label{eq:7} &&X(n+1)=(X_{i}(n+1)=T_{b}^{i}\circ T_{m}^{i}\circ T_{c}^{i}\circ T_{s}^{i}(X(n));i\leq N-1;\nonumber\\ &&X_{N}(n+1)=X_{i_{0}}(n)), \end{eqnarray} $

(3.7)

其中, $i_{0}=\arg\min\limits_{j}{\{f(X_{j}(n))\}}$表示使$f(X_{j}(n))$取最小值的个体为$X_{j}(n)$, 种群转移概率矩阵:

$ \begin{equation}\label{eq:8} \begin{array}{rcl} P\{X, Y\}&=&P\{X(n+1)=Y|X(n)=X\}\\ &=&\left\{\begin{array} {c@{\quad}l} \prod\limits_{k=1}^{N}P\{T(X(n+1)_{k})=Y_{k}\}, & \exists i_{0}\in \{i|f(X_{i})=\min f(X_{j})\}\text{使}Y_{N}=X_{i_{0}};\\ 0, & \text{其它}. \end{array}\right. \end{array} \end{equation} $

(3.8)

上述表明$X(n+1)$只与$X(n)$有关, 而与迭代次数$n$无关.因此, G-ABCA算法的种群序列$\{X(n);n\geq0\}$是有限齐次Markov链.

定理3.2  G-ABCA算法Markov链的适应度函数值序列是单调不增的, 即$\forall n\geq0, f(X(n+1))\leq f(X(n))$.

证  由于G-ABCA中采用的是改进的遗传算法, $i_{0}=\arg\min\limits_{j}\{f(X_{j}(n))\}$, 所以

$ \begin{eqnarray*} &&X_{N}(n+1)=X_{i_{0}}(n), \\ &&f(X(n+1))\leq f(X_{N}(n+1))\leq f(X(n)). \end{eqnarray*} $

同理, 由于G-ABCA采用了人工蜂群算法, $i_{0}=\arg\min\limits_{j}\{f(X_{j}(m))\}$, 故有

$ \begin{eqnarray*}&&X_{N}(m+1)=X_{i_{0}}(m), \\ &&f(X(m+1))\leq f(X_{N}(m+1))\leq f(X(m)).\end{eqnarray*} $

又由于人工蜂群算法以改进的遗传算法结果为初始蜜源分布, 具有优值继承性, 因此$\forall n\geq 0$, $f(X(n+1))\leq f(X(n))$, 即G-ABCA算法Markov链的适应度函数值序列是单调不增的.

定理3.3  G-ABCA算法的Markov序列以概率1收敛到满意解集$B$的子集$B_{0}^{*}=\{Y=(Y_{1}, Y_{2}, \cdots, Y_{N});Y_{N}\in B\}$, 即

$ \begin{equation}\label{eq:9} \mathop {\lim }\limits_{n \to \infty } P\{ X(n) \in B_0^*/X(0) = {X_0}\} = 1. \end{equation} $

(3.9)

证  设$X'$是$f(X)$的唯一最小值解, 由引理3.1、定理3.1以及人工蜂群算法也以概率1收敛可知$P\{X, Y\}$具有如下性质:

(1) 当$X, Y\in B_{0}^{*}$时, $P\{X, Y\}>0$, $P\{Y, X\}>0$, 即$X\leftrightarrow Y$;

(2) 当$X\in B_{0}^{*}, Y \notin B_{0}^{*}$时, $P\{X, Y\}=0$, 即$X\rightarrow Y$.

因此$B_{0}^{*}$为正常返、非周期的不可约闭集, ${S^{N}}\setminus{B_{0}^{*}}$为非常返的状态集, 即

$ \begin{equation}\label{eq:10} \mathop {\lim }\limits_{n \to \infty } P\{ X(n) = Y/X(0) = {X_0}\} = \left\{ {\begin{array}{*{20}{c}} {\pi (Y),}&{Y \in B_0^*;}\\ {0,}&{Y \notin B_0^*.} \end{array}} \right. \end{equation} $

(3.10)

故

$ \lim\limits_{n\rightarrow\infty}P\{X(n)\in B_{0}^{*}/X(0)=X_{0}\}=1. $

推论3.1  G-ABCA算法的种群序列$\{X(n);n\geq0\}$如果对于任意满意解集收敛, 则必收敛到全局最优解集.

证  因为对于任意的$\varepsilon>0$, 有满意解集

$ B(\varepsilon)=\{Y;f(Y)\leq f(X^{*})+\varepsilon\}, $

其中$X^{*}$表示最优解, 即$X^{*}\in M$, 也即全局最优解集$M$是所有满意解集的交集, $M$为最小满意解集.所以, 若$\{X(n);n\geq0\}$对于任意满意解集收敛, 则必收敛到全局最优解集.

因为多峰数值函数求极值问题是常见的优化问题, 更是测试连续优化算法的试金石, 所以这里借助Matlab编程, 利用四个经典的多峰测试函数^[17]: Sphere函数、Griewank函数、Rosenbrock函数、Rastrigin函数来测试G-ABCA算法的寻优性能, 并与改进的GA和ABCA进行寻优性能对比.这四个经典的测试函数的全局极小值均为0, 其搜索空间均为$(-100, 100)^{d}$, 并均将维数设置为$d=50$. G-ABCA算法中遗传算法的最大迭代次数设为100, 编码精度设为$10^{-5}$, 初始的交叉、变异概率分别设为0.9和0.005, G-ABCA算法中人工蜂群算法的蜜蜂总数设为20, 采蜜蜂数设为10, 最大搜索次数设为100, 最大迭代次数设为800;改进的GA和ABCA最大迭代次数均为800, 其余参数设置与G-ABCA算法一致.实验结果见表 1至表 4、图 1至图 4.

表 1至表 4反映三种算法对于各测试函数极小值解的一次寻优结果.可以看出, 对于四个测试函数, 改进的GA收敛到最优解的进化代数都非常小, 得到的最优解与测试函数的全局极小值都相差很大, 说明均出现“早熟”; ABCA虽然仅在Griewank函数测试中得到的最优解与其全局极小值有较小的偏差, 但是其收敛到最优解的进化代数显著高于G-ABCA算法.由此可见, G-ABCA算法确实有效避免了遗传算法的“早熟”, 并且通过加快ABCA的初始搜索速度, 提高了算法的整体收敛速度.另外, 从计算时间上可以看出, 虽然G-ABCA算法是改进的GA与ABCA的融合, 但是其并没有比ABCA算法多费时很多, 甚至其在Sphere函数测试中的计算时间略低于ABCA算法; 而改进的GA由于“早熟”导致其计算时间很短, 因此不具有可比性.

图 1至图 4反映三种算法对于各测试函数极小值解的一次寻优过程对比结果.可以直观地看出, G-ABCA算法是逐步收敛的, 其收敛性能显著优于GA(即改进的GA)算法和ABCA算法, 而且GA算法明显过早收敛, 发生“早熟”.

结论:改进的遗传算法与人工蜂群算法的融合, 实现了两种算法的互补, 不仅避免了遗传算法发生“早熟”, 而且解决了人工蜂群算法初始搜索速度慢的问题.数值实验结果表明, G-ABCA算法在经过改进的遗传算法得到“蜜源”分布之后, ABCA算法以极快的速度逼近全局最优解, 验证了G-ABCA算法具有收敛性以及良好的寻优性能.