ISSN 
-
人工蜂群算法 (ABC) 是文献[1]为解决函数优化问题而提出的。其原理是模拟蜜蜂的采蜜机制，通过不同分工的蜂群间相互协作完成进化搜索工作，具有操作简单、设置参数少、收敛速度更快、收敛精度更高的优点，已逐步应用到智能优化、模式识别、工业控制、图像识别、神经网络优化和聚类分析等[2-8]领域。
文化作为存储知识的载体在生物群体中不断的传递和继承，对种群进化的加速作用比单纯依靠基因遗传快，可以很好地指导生物个体行为[9]。多数学者研究进化算法主要集中在生物进化选择机理方面，本文将文化算法思想[10]嵌入到ABC中，提出一种自适应混合文化蜂群算法 (AMC-ABC)。首先，整个蜜蜂种群个体采用佳点集理论产生；其次，将蜜蜂种群分为群体空间、信念空间和外部空间，并引入云模型理论、差分变异策略和反向混沌理论改进3个空间内个体的进化方式；最后，通过影响函数完成整个群体知识的存储和传播。
HTML
-
ABC算法将蜂群分为3类：引领蜂、跟随蜂和侦察蜂，本文以求解最小化问题为例简要阐述其具体寻优过程。
-
在解空间内按式 (1) 随机生成N个个体${x_i}$构成初始种群：
式中，${\rm{rand}}()$为[0, 1]区间上的随机数；${x_i}^{\min }$和${x_i}^{\max }$分别为解空间的上下限。
-
将种群中个体按照适应度值从小到大排序，取前$N/2$组成引领蜂种群，后$N/2$构成跟随蜂种群。对于当前第t代引领蜂种群中的个体$N/2$，随机选择个体$k \in [1, 2, \cdots, N/2], i \ne k$按式 (2) 进行交叉搜索生成新个体$k \in [1, 2, \cdots, N/2], i \ne k$：
式中，${\rm{rand}}()$为[-1, 1]区间上的随机数。按式 (3) 选择较优的个体更新引领蜂种群：
-
各跟随蜂按选择概率式 (4) 在引领蜂种群中选择引领蜂${x_k}(t), k \in [1, 2, \cdots, N/2]$，并在其邻域内按式 (2) 进行新位置的搜索，产生新个体${x_k}(t), $$k \in [N/2 + 1, N/2 + 2, \cdots, N]$，形成跟随蜂种群：
-
为了避免在迭代进化后期丧失种群的多样性，ABC将经过连续${\rm{limit}}$代进化适应度不变的个体转换成侦察蜂，并按式 (1) 重新产生新个体。通过引领蜂种群、跟随蜂种群及侦察蜂的进化搜索，经过反复循环寻优直到算法迭代到最大迭代次数或种群的最优解达到预定误差精度时算法结束。
1.1. 种群初始化
1.2. 引领蜂进化方式
1.3. 跟随蜂进化方式
1.4. 侦察蜂进化方式
-
从计算模型的角度出发，符合文化算法要求的进化算法都可以嵌入文化算法框架。本文将引领蜂、跟随蜂和侦察蜂划分为信念空间、群体空间和外部空间，3个空间通过自有的改进进化方式完成空间内个体的进化，利用影响函数实现空间之间各类知识的传播和继承，进而加速算法寻优速率，提升算法寻优性能及解决问题的适应性。
-
进化算法中种群初始化大多采用随机方式生成，若生成的个体分布在最优解周围，则算法快速收敛到最优解的概率将加大。在未知最优解所在位置的情况下，若要加速算法收敛、改善寻优性能，就需要让初始化的种群尽可能均匀分布在整个解空间。佳点集理论[11]表明：近似计算函数在s维欧氏空间单位立方体上的积分时，采用n个佳点得到的加权和比任何其他n个点获得的误差都小。文献[12-13]将其应用到种群的初始化，取得了很好的寻优效果，定义如下：
设${G_s}$是s维欧氏空间中的单位立方体，如果$r \in {G_s}$，形为${p_n}(k)=\{ (\{ {r_1}^{(n)}k\}, \{ {r_2}^{(n)}k\}, \cdots, $$\{ {r_s}^{(n)}k\})$，$1 \le k \le n\} $，其偏差$\varphi (n)$满足$\varphi (n)=C (r, \varepsilon){n^{-1 + \varepsilon }}$，其中, $C (r, \varepsilon)$是只与r和ε(ε > 0) 有关的常数，则称${p_n}(k)$为佳点集，r为佳点。一般情况下，取${p_n}(k)$，$1 \le k \le s\} $，p是满足$(p-s)/2 \ge s$的最小素数。
-
蜂群算法中的引领蜂是群体空间中最优子集，因此将其作为信念空间中的个体。经典ABC中引领蜂进化方式是任意选择一个个体与某个体进行交叉操作，这种方式可能存在两个个体互为选择进化的情况，也可能会出现同一个个体与多个个体交叉进化的情况。虽然存在一个随机因子会保证新生个体的多样性，但是这些个体的进化方向却相对稳定，对收敛速度会造成影响。同时每次迭代过程中最优个体都会找一个不如它的个体进行交叉，虽然存在能找到比其更优个体的可能性，但其操作的本质是进行局部寻优。所以有必要对引领蜂的进化方式进行两种改进。
-
社会学原理指出在优秀个体周围较易发现更优个体，即局部最优值周围往往存在更优值。云模型在知识表达时具有不确定中带有确定性、稳定之中又有变化的特点, 体现了自然界物种进化的基本原理[14-16]。本文采用正态云模型算法完成最优个体的进化行为。将最优个体作为期望 (Ex) 表示搜索中心；用当代适应度方差$(p-s)/2 \ge s$作为熵 (En) 来动态改变寻优搜索范围；用超熵 (He) 控制云滴的离散度，初期加大算法的随机性，后期加强算法的稳定性，设置$(p-s)/2 \ge s$，产生与空间内个体数量相同的一组云滴，如果新个体较优则替换。
-
差分进化算法是文献[17]为求解切比雪夫多项式拟合问题而提出的一种采用浮点矢量编码在连续空间中进行随机搜索的优化算法，具有原理简单、受控参数少的优势，采用最优排序差分变异策略[18-19]作为非最优个体的进化规则为：
式中，随机选择互不相同且不同于该更新个体的两个个体，然后对适应度进行排序，选择3个个体最优的个体作为${x_b}$，较优个体作为r1，最差个体作为r2；F为比例缩放因子。如果适应度相差很小，说明两个个体在空间中相隔很近，${F_i}$应取较大值，以防止扰动量过小；如果适应度相差很大，说明两个个体在空间相隔很远，${F_i}$应取较小值，以限制扰动量过大。下面给出一种确定方式：
式中，${F_u}{F_l}$分别为${F_i}$的上限和下限；${f_{r1}}{f_{r2}}{f_b}$分别为个体r1、r2和${x_b}$的适应度。
-
用跟随蜂组成群体空间，ABC的进化机理使其在求解高维连续优化问题时效果不够理想。主要是因为跟随蜂种群的搜索方式是择优选择个体进行贪婪搜索，虽然有利于加速收敛速度，却也增加了在解决高维优化问题时易陷入局部最优的概率。自然界中蜜蜂在采蜜过程中多数是以较少的移动来获取更多的蜜源，这也符合最优觅食理论：为获得较优的觅食效果，生物更趋向在觅食过程中以更低的能效耗费来获得更多的食物[20-21]。蜜蜂间的能效吸引力为：
设对蜜蜂个体${x_i}$产生最大${F_{ik}}$的蜜蜂个体为${x_{nx}}$，${x_k}$是在信念空间按原有选择方式选择的个体，为了丰富进化个体的参考信息，对于第t代个体进行更新：
式中，${\rm{rand}}()$是[0, 1]的随机数；w为吸引系数。
从式 (8) 可以看出吸引系数w的取值会影响寻优性能，在算法进化初期种群的多样性较多，这时适应度较差的个体可能离最优个体较远，其应该在向最优个体靠近时先获取足够的能量，故此时w的取值应该较大。而在进化后期多数个体已经趋于最优值的附近，此时w的取值应该较小，加快收敛速度。w的自适应取值为：
式中，$[a, b]$为w的取值范围。
-
外部空间由侦察蜂构成，反向学习理论可以使算法获取较好的收敛速率和优化性能[22]。混沌映射使生成的个体呈现遍历性、随机性和多样性，可有效地在收敛区域以外空间搜索全局最优位置[23-24]。采取k阶Chebyshev混沌映射完成个体变异，按式 (9) 计算适应度，取最优个体更新侦察蜂：
-
外部空间的个体主要是来自ABC进化过程中连续${\rm{limit}}$代进化适应度不变的个体，本文依旧沿用这种策略。利用影响函数将群体空间中的知识传递到信念空间，其目的是给信念空间分配若干个优秀个体参与信念空间的进化。通常采用预设的比例因子α，按照这个比例优选群体空间内的优秀个体与信念空间的个体采用锦标赛法替换信念空间内的个体。对于进化初期种群的多样性程度较高，此时α的选择比例应较大；进化后期种群的多样性程度降低，表明种群聚集在全局最优或局部最优，此时α应设置一个较小比例。方差是衡量随机变量或一组数据是离散程度的度量，方差越大离散程度越大。${E_t}(x)=({e_1}(x), {e_2}(x), \cdots, {e_t}(x))$为第1代到第t代适应度的方差。采用式 (10) 计算每次迭代后的选择比例，方差越大则公式计算值越大，说明当前进化周期的适应值离散程度大，应提供相对较多的个体经验。
式中，${\alpha _{\max }}$为比例因子的最大值；${\alpha _{\min }}$为比例因子的最小值。
-
1) 初始化算法的相关参数，并采用佳点集理论产生种群个体；2) 计算种群个体的适应度，将种群分为信念空间、群体空间和外部空间；3) 按照2.2节的进化方式进化信念空间中的个体，按照2.3节进化群体空间中的个体，按照2.4节进化外部空间中的个体；4) 计算个体适应度，满足结束条件则退出，否则执行流程5)；5) 利用影响函数完成3种空间知识的传递；6) 转到流程3)，直到满足终止条件。
2.1. 基于佳点集理论的个体初始化
2.2. 信念空间的进化方式
2.2.1. 信念空间内最优个体的进化方式
2.2.2. 信念空间内非最优个体的进化方式
2.3. 群体空间的进化方式
2.4. 外部空间的进化方式
2.5. 影响函数的设计
2.6. 算法流程
-
为验证本文算法性能，以8个函数极值优化为例，与标准粒子群算法 (PSO)、经典遗传算法 (GA)、蛙跳算法 (SFLA) 和经典蜂群算法 (ABC) 的寻优性能进行对比。5种算法的种群个体均设置为100，最大进化次数均设置为4 000，寻优精度均设置为10×10-10，各测试函数独立运行20次；PSO运行参数：惯性因子0.729 8，自身因子1.496 18，全局因子1.496 18；GA运行参数：交叉概率${P_c}=0.8$，变异概率${P_m}=0.01$；SFLA运行参数：分为10个子群，每个子群10个青蛙，子群内部迭代次数为20次；ABC算法的${\rm{limit}}={\rm{100}}$，比较5种算法的最优结果、最差结果、平均结果、平均运行时间和方差。其中，最优结果、最差结果反映解的质量，平均结果显示算法所能达到的精度，平均时间反映算法的收敛速度，方差反映算法的稳定性和鲁棒性。
该函数是二维的复杂函数，具有无数个极小值点，最小值0。
该函数存在许多局部极小点，全局最小值0。
该函数全局最小值0。
该函数有一个全局最小值0。
该函数存在许多局部极小点，全局最小值0。
该函数有一个全局最小值0。
该函数存在许多局部极小点，数目与问题的维数有关，全局最小值0。
该函数是个多峰值的函数，全局最小值0。
从表 1~表 8的运行结果可知，AMC-ABC的求解精度和速度都要优于其他4种算法。从以下两方面进行分析：
算法 f1 最优结果 最差结果 平均结果 平均时间/s 方差 PSO 1.410 6×10-12 0.009 7 9.72×10-4 22.957 3.53×10-1 GA 2.932×10-10 0.642 0. 261 25.687 1.62×103 SFLA 8.128×10-12 9.356×10-11 5.753×10-11 19.217 4.08×10-21 ABC 9. 153×10-12 8.197×10-6 2.173×10-8 15.361 7.19×10-10 AMC-ABC 8. 203×10-12 6.215×10-10 4.127×10-11 5.386 4.923×10-21 算法 f2 最优结果 最差结果 平均结果 平均时间/s 方差 PSO 33.907 148.942 104.779 23.618 3.28E×10-1 GA 40.918 369.462 267.396 26.397 1.03×102 SFLA 2.098×10-4 9.359×10-2 5.256×10-3 15.496 7.31×10-5 ABC 3. 852×10-3 7. 265 6. 527×10-2 16.038 5.25×10-1 AMC-ABC 6.025×10-10 8. 307×10-8 3.418×10-9 6. 014 5.43×10-17 算法 f3 最优结果 最差结果 平均结果 平均时间/s 方差 PSO 3.603×10-4 0.632 0.273 33.268 3.62×104 GA 5.038×10-2 7.62 4.826 36.623 5.43×105 SFLA -0.999 7.317 3.126 25.096 1.00 ABC 2. 295×10-2 8.015 4.095 17.629 6.21×102 AMC-ABC 2. 521×10-12 6.538×10-9 5.612×10-10 5.712 4.02×10-19 算法 f4 最优结果 最差结果 平均结果 平均时间/s 方差 PSO 2. 138×10-10 9. 402×10-8 5. 504×10-9 33.405 2.63×10-13 GA 2.459×10-8 7.713×10-7 6.748×10-8 36.526 6.25×10-11 SFLA 3.261×10-11 6.237×10-9 7.139×10-10 19.185 7.39×10-14 ABC 3.258×10-10 6.132×10-7 5.359×10-9 15.712 6.31×10-13 AMC-ABC 6.307×10-12 8.125×10-9 4.146×10-10 5.729 4.28×10-19 算法 f5 最优结果 最差结果 平均结果 平均时间/s 方差 PSO 9.667×10-5 0.019 9.81×10-4 132.875 1.25×10-5 GA 0.288 0. 716 0.392 148.28 5.38×101 SFLA 1.088×10-10 9.971×10-10 7.723×10-10 14.63 6.59×10-19 ABC 3. 127×10-6 5.157×10-2 8.302×10-4 18.03 5.34×10-4 AMC-ABC 2.719×10-12 7.627×10-10 5.841×10-10 6. 578 1.37×10-19 算法 f6 最优结果 最差结果 平均结果 平均时间/s 方差 PSO 8. 416×10-5 3. 583 1.586 144.748 4.96 GA 2.783 11.687 7.539 162.846 1.07×102 SFLA 1.840 1.840 1.840 16.981 3.39 ABC 5.016×10-4 2.018 2.129 18.163 5.08 AMC-ABC 4.126×10-10 8.702×10-8 6.108×10-9 6.852 5.12×10-17 算法 f7 最优结果 最差结果 平均结果 平均时间/s 方差 PSO 0.072 0.529 0.264 147.376 8.62×10-2 GA 1. 287 13.643 1.951 168.21 6.38×102 SFLA 0.029 0.121 0.067 15.284 5.21×10-3 ABC 0. 062 0. 561 0.301 18.581 4.28×10-2 AMC-ABC 6.267×10-11 8.137×10-8 6.01×10-9 6. 318 3.58×10-17 算法 f8 最优结果 最差结果 平均结果 平均时间/s 方差 PSO 5.952 40.732 17.725 139.393 4.31×102 GA 9.924 78.752 30.639 162.634 6.35×103 SFLA 4.767×10-11 1.989 0.597 13.671 9.91×10-1 ABC 5. 236×10-5 2.243 7.845 19.235 5.72×10-2 AMC-ABC 8.208×10-12 9.315×10-9 5.137×10-10 6.815 3.29×10-19 1) 对比最优结果、最差结果、平均结果可知，AMC-ABC的求解性能最好。①因为蜜蜂种群采用佳点集理论进行初始化，增加了蜜蜂个体快速定位到最优解的概率；②信念空间采用的云模型算法有益于最优个体向其附近更优值进行自适应定位，同时云模型的随机性又保持了蜜蜂个体的多样性，进而起到提高寻优性能和速率的作用；③由反向理论和混沌理论产生的个体变异，有利于算法在寻优后期增加个体多样性，可有效地在收敛区域以外空间搜索全局最优位置，进而改善算法在求解一些高维优化函数收敛速率慢、易早熟等问题。2) 对比运行时间和方差可知，AMC-ABC的性能要优于其他进化算法，分析其原因是：SFLA和ABC的进化方式较PSO和GA的简单，且调整参数少，同时它们利用小生镜的方式进行寻优，速度相对快一些。SFLA在分组内迭代一定次数后再重新分组，在一定程度上与ABC的经过${\rm{limit}}$次迭代后变成侦查蜂相似，所以二者的性能较相似。而AMC-ABC在进化过程中采用云模型和最优排序差分变异策略使得个体更新时既保持了随机性，又使得个体变化带有确定性，与经典算法的随机方式相比更易向最优解方向靠近。而基于最优觅食理论的群体空间更新机制有利于避免算法参数试算，虽然在每次迭代进化过程中增加了计算量，但通过迭代次数可以看出，其收敛的速度确实得到很大提高，使得运行时间较短。同时仿真结果表明AMC-ABC对高维多峰函数的求解具有很好的适应性。
-
本文将文化算法思想嵌入到人工蜂群算法中，将引领蜂、跟随蜂和侦察蜂划分为信念空间、群体空间和外部空间，利用佳点集、云模型和混沌算法等理论改进3种空间中个体的进化行为，既发挥了蜂群算法原有进化算子的优势，又改进了算法的不足。3个子群空间通过影响函数来完成个体间知识的交换，仿真实例结果表明所提算法具有很好的寻优速率和效率，同时对其他进化算法的改进具有一定的借鉴意义。
DownLoad: