工程科学学报，第40卷，第7期：871-881,2018年7月 Chinese Journal of Engineering,Vol.40,No.7:871-881,July 2018 DOI:10.13374/j.issn2095-9389.2018.07.014;http://journals.ustb.edu.cn 一种改进的人工蜂群算法—粒子蜂群算法 王继超)，李擎)回，崔家瑞，左文香)，赵越飞 1)北京科技大学自动化学院，北京1000832)河北水利电力学院，沧州061001 ☒通信作者，E-mail:liqing@(ics.usth.cdu.cm 摘要针对经典人工蜂群算法收敛速率较慢，后期易陷入局部最优解的不足，本文将粒子群算法中“全局最优”的思想引入 到人工蜂群算法的改进过程，从而形成了一种新的人工蜂群改进算法一粒子蜂群算法.首先，提出了趋优度的概念，用来衡 量引领蜂在有限次迭代过程中向全局最优解靠近或远离的程度，趋优度值可以评价个体的“发展潜力”，趋优度值越低的个 体，越需要增大变异的程度，以便找到质量更优的解.其次，专门设计了一种新的蜜蜂群体一粒子蜂，在引领蜂变异阶段根 据趋优度的大小将引领蜂变异为侦查蜂和粒子蜂，粒子蜂的出现在很大程度上增加了种群的多样性，拓展了算法的搜索范 围.然后，通过粒子蜂群算法种群序列是一个有限齐次马尔科夫链和种群进化单调性的分析，验证了本文所提算法的种群序 列依概率1收敛于全局最优解集.最后，将本文所提算法应用于多个常见测试函数，并与经典蜂群算法、近年其他文献改进蜂 群算法进行了仿真对比研究，仿真结果表明本文所提算法确实加大了种群的分散度、扩宽了搜索范围，从而具有更快的收敛 速度和更高的寻优精度 关键词人工蜂群算法：趋优度：粒子蜂；马尔科夫链；种群分散度 分类号TP18 An improved artificial bee colony algorithm:particle bee colony WANG Ji-chao,LI Qing,CUI Jia-rui),ZUO Wen-xiang),ZHAO Yue-fei) 1)School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Hebei University of Water Resources and Electric Engineering,Cangzhou 061001.China Corresponding author,E-mail:liqing@ies.ustb.edu.en ABSTRACT With an aim to address the disadvantages of the artificial bee colony algorithm of slow convergence speed and ease of falling into the local optimum in the later period of the evolution process as well as to improve the traditional artificial bee colony algo- rithm,the concept of the "global optimum"in particle swarm optimization is introduced.Therefore,an improved artificial bee colony algorithm,called particle bee colony (PBC),is proposed herein.First,the concept of degree toward optimum is proposed for measur- ing the degree to which the leader approaches or is removed from the "global optimum"in a limited iteration process.The individuals' values of degree toward optimum denote their"development potentials."The individuals that have a low degree toward optimum require a great mutation extent to find a good solution.Second,a new colony of bees,initiated by the particle bee,is uniquely developed.In mutation period,the leader will be changed into the scout or the particle bee according to the value of the degree toward optimum.The appearance of particle bees can increase the population diversity and expand the search area to a large extent.Next,analysis reveals that the sequence of population of the PBC is a finite homogeneous Markov chain and the population evolution process is monotonous. On the basis of the above observations,it can be proved that the population sequence of the proposed algorithm converges to the global optimum solution set with probability 1.Last,the algorithm proposed in this study is applied to numerical simulations of several classi- cal test functions.Furthermore,the proposed algorithm is compared with the traditional artificial bee colony algorithm and other im- proved bee colony algorithms.The simulation results show that PBC increases the population dispersion and broadens the search area, 收稿日期：2017-05-14 基金项目：国家自然科学基金资助项目(61673098)
工程科学学报,第 40 卷,第 7 期:871鄄鄄881,2018 年 7 月 Chinese Journal of Engineering, Vol. 40, No. 7: 871鄄鄄881, July 2018 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2018. 07. 014; http: / / journals. ustb. edu. cn 一种改进的人工蜂群算法———粒子蜂群算法 王继超1) , 李 擎1) 苣 , 崔家瑞1) , 左文香2) , 赵越飞1) 1) 北京科技大学自动化学院, 北京 100083 2) 河北水利电力学院, 沧州 061001 苣通信作者, E鄄mail: liqing@ ies. ustb. edu. cn 摘 要 针对经典人工蜂群算法收敛速率较慢,后期易陷入局部最优解的不足,本文将粒子群算法中“全局最优冶的思想引入 到人工蜂群算法的改进过程,从而形成了一种新的人工蜂群改进算法———粒子蜂群算法. 首先,提出了趋优度的概念,用来衡 量引领蜂在有限次迭代过程中向全局最优解靠近或远离的程度,趋优度值可以评价个体的“发展潜力冶,趋优度值越低的个 体,越需要增大变异的程度,以便找到质量更优的解. 其次,专门设计了一种新的蜜蜂群体———粒子蜂,在引领蜂变异阶段根 据趋优度的大小将引领蜂变异为侦查蜂和粒子蜂,粒子蜂的出现在很大程度上增加了种群的多样性,拓展了算法的搜索范 围. 然后,通过粒子蜂群算法种群序列是一个有限齐次马尔科夫链和种群进化单调性的分析,验证了本文所提算法的种群序 列依概率 1 收敛于全局最优解集. 最后,将本文所提算法应用于多个常见测试函数,并与经典蜂群算法、近年其他文献改进蜂 群算法进行了仿真对比研究,仿真结果表明本文所提算法确实加大了种群的分散度、扩宽了搜索范围,从而具有更快的收敛 速度和更高的寻优精度. 关键词 人工蜂群算法; 趋优度; 粒子蜂; 马尔科夫链; 种群分散度 分类号 TP18 收稿日期: 2017鄄鄄05鄄鄄14 基金项目: 国家自然科学基金资助项目(61673098) An improved artificial bee colony algorithm: particle bee colony WANG Ji鄄chao 1) , LI Qing 1) 苣 , CUI Jia鄄rui 1) , ZUO Wen鄄xiang 2) , ZHAO Yue鄄fei 1) 1) School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China 2) Hebei University of Water Resources and Electric Engineering,Cangzhou 061001, China 苣Corresponding author, E鄄mail: liqing@ ies. ustb. edu. cn ABSTRACT With an aim to address the disadvantages of the artificial bee colony algorithm of slow convergence speed and ease of falling into the local optimum in the later period of the evolution process as well as to improve the traditional artificial bee colony algo鄄 rithm, the concept of the “global optimum冶 in particle swarm optimization is introduced. Therefore, an improved artificial bee colony algorithm, called particle bee colony (PBC), is proposed herein. First, the concept of degree toward optimum is proposed for measur鄄 ing the degree to which the leader approaches or is removed from the “global optimum冶 in a limited iteration process. The individuals爷 values of degree toward optimum denote their “development potentials. 冶 The individuals that have a low degree toward optimum require a great mutation extent to find a good solution. Second, a new colony of bees, initiated by the particle bee, is uniquely developed. In mutation period, the leader will be changed into the scout or the particle bee according to the value of the degree toward optimum. The appearance of particle bees can increase the population diversity and expand the search area to a large extent. Next, analysis reveals that the sequence of population of the PBC is a finite homogeneous Markov chain and the population evolution process is monotonous. On the basis of the above observations, it can be proved that the population sequence of the proposed algorithm converges to the global optimum solution set with probability 1. Last, the algorithm proposed in this study is applied to numerical simulations of several classi鄄 cal test functions. Furthermore, the proposed algorithm is compared with the traditional artificial bee colony algorithm and other im鄄 proved bee colony algorithms. The simulation results show that PBC increases the population dispersion and broadens the search area
·872· 工程科学学报，第40卷，第7期 thereby allowing the proposed algorithm to achieve fast convergence rate and high optimization accuracy. KEY WORDS artificial bee colony;degree toward optimum;particle bee;Markov chain;population dispersion 人工蜂群算法(artificial bee colony,ABC)由 f0) Karaboga提出)，该算法在海内外优化领域引起很 P:= 团 (1) fa) 大的关注.目前人工蜂群算法在蛋白质的检测和预 测问题、动态路径选择问题、可靠性冗余分配等领域 其中，P,表示选择概率，0：表示第i个蜜蜂，f(0)表 应用中取得良好效果).经典人工蜂群算法原理简 示第i个蜜蜂的适应度值，m表示种群规模.引领蜂 单、参数少且容易实现，但同时也存在进化后期寻优 与跟随蜂对蜜源进行搜索是按公式(2)进行，公式 速度慢、易出现“早熟”现象等不足[).为提高人工 (2)是蜜源搜索公式，同时也被称为引领蜂与跟随 蜂群算法性能，产生了大量改进方案.Bao与 蜂位置更新公式 Zeng[4)系统地分析研究了人工蜂群算法的参数调用 ya=xd+Ra（xa-xd）,ie（1,2,…,m)(2) 机制，提出了三种新的调用方式，改变了原有的参数 其中，ya是新蜜源位置，xa是当前蜜源位置，Ra是区 调用范围：Alatas)应用混沌映射调整了参数，使其 间[-1,1]之间的随机数，xa是当前蜜源邻域中的 一个随机蜜源位置，d是优化问题的参数维度 自适应变化，提高了人工蜂群算法的全局搜索能力； 当某个引领蜂开采蜜源连续limit代不变，则该 Chen等)把模拟退火算子添加到引领蜂的寻优过 引领蜂自动转换成侦察蜂，按新的搜索公式(3)产 程，提高了人工蜂群算法的初步探索能力 生新蜜源，计算其适应度值，同样保留适应度值高的 近年来，由于粒子群算法(particle swarm optimi- 蜜源 zation,PS0)和人工蜂群算法在算法原理和解决实 际问题中有许多相通之处，国内外许多学者对其进 =mi+rand(0,1)(%jm-%min), i∈(1,2，…，m),je(1,2,…,d) (3) 行研究.KRan与GuNduZ☑将粒子群算法和人工 其中，rand(0,1)是[0,1]间的随机数，ma和xmn是 蜂群算法进行混合，该算法将粒子群算法的全局最 参数变量的最大值与最小值. 优作为跟随蜂的位置，又把人工蜂群算法找到的最 优解当作粒子群算法的局部最优：El-Ad8]设计了 2粒子蜂群算法 一种运用人工蜂群算法改善粒子群算法中的参数从 2.1粒子群算法和人工蜂群算法融合的必要性以 而实现两者融合：Si等)提出两种信息交换机制， 及粒子群蜂群算法思想 分别设置了“基站”，实现了粒子群算法和人工蜂群 通过分析人工蜂群算法原理可知，人工蜂群算 算法的信息交互，提高了二者性能 法的全局搜索能力很强，是因为其将种群一半的蜜 本文借鉴了粒子群算法利用全局最优位置的优 蜂作为引领蜂产生初始解并通过保留适应度高的蜜 点，改变了引领蜂的变异方式，在算法后期扩大了解 蜂来进行迭代，这样既保证了解空间的多样性，又增 的搜索范围，更加有效地解决了后期易陷入局部最 强了其全局搜索能力.但现有的侦查蜂机制导致了 优的问题，在很大程度上提高了算法的收敛速度. 当引领蜂找到一个不错的解并且连续几代蜜源适应 多个函数不同维数下的仿真研究说明了本文所提算 度不变时，只能在当前蜜源位置的邻域内搜索一个 法的有效性 新蜜源，这样会大幅度降低搜索效率，从而导致算法 1人工蜂群算法 的收敛速度慢以及过早收敛，出现“早熟”现象 粒子群算法可以较好地利用全局最优解来适时 人工蜂群算法是一种较为新型的群智能优化算 地更新粒子位置，避免提前陷入局部最优.并且粒 法，其原理是通过模仿生物界蜜蜂采蜜来实现寻优. 子群算法和人工蜂群算法都是通过迭代来更新个体 蜂群算法的四个基本组成要素是：蜜源、引领蜂、跟 位置，融合方便.虽然粒子群算法自身在处理复杂 随蜂和侦察蜂：两种最基本的行为模型：招募蜜源和 的多峰问题时效果不是很好，但是人工蜂群算法的 放弃蜜源 引领蜂策略很好地弥补了粒子群算法搜索空间多样 人工蜂群算法是通过蜜蜂不断地局部寻优最终 性差的问题，因此二者融合很有必要 突显出全局最优值.跟随蜂根据引领蜂分享的信 所以，受粒子群算法的启发，在引领蜂变异为侦 息，按下式所描述的概率公式选择蜜源： 查蜂阶段，可以改变其位置更新策略，不单单在现有
工程科学学报,第 40 卷,第 7 期 thereby allowing the proposed algorithm to achieve fast convergence rate and high optimization accuracy. KEY WORDS artificial bee colony; degree toward optimum; particle bee; Markov chain; population dispersion 人工蜂群算法( artificial bee colony,ABC) 由 Karaboga 提出[1] ,该算法在海内外优化领域引起很 大的关注. 目前人工蜂群算法在蛋白质的检测和预 测问题、动态路径选择问题、可靠性冗余分配等领域 应用中取得良好效果[2] . 经典人工蜂群算法原理简 单、参数少且容易实现,但同时也存在进化后期寻优 速度慢、易出现“早熟冶现象等不足[3] . 为提高人工 蜂群 算 法 性 能, 产 生 了 大 量 改 进 方 案. Bao 与 Zeng [4]系统地分析研究了人工蜂群算法的参数调用 机制,提出了三种新的调用方式,改变了原有的参数 调用范围;Alatas [5] 应用混沌映射调整了参数,使其 自适应变化,提高了人工蜂群算法的全局搜索能力; Chen 等[6]把模拟退火算子添加到引领蜂的寻优过 程,提高了人工蜂群算法的初步探索能力. 近年来,由于粒子群算法(particle swarm optimi鄄 zation,PSO)和人工蜂群算法在算法原理和解决实 际问题中有许多相通之处,国内外许多学者对其进 行研究. K覦Ran 与 G俟Nd俟Z [7]将粒子群算法和人工 蜂群算法进行混合,该算法将粒子群算法的全局最 优作为跟随蜂的位置,又把人工蜂群算法找到的最 优解当作粒子群算法的局部最优;El鄄Abd [8] 设计了 一种运用人工蜂群算法改善粒子群算法中的参数从 而实现两者融合;Shi 等[9] 提出两种信息交换机制, 分别设置了“基站冶,实现了粒子群算法和人工蜂群 算法的信息交互,提高了二者性能. 本文借鉴了粒子群算法利用全局最优位置的优 点,改变了引领蜂的变异方式,在算法后期扩大了解 的搜索范围,更加有效地解决了后期易陷入局部最 优的问题,在很大程度上提高了算法的收敛速度. 多个函数不同维数下的仿真研究说明了本文所提算 法的有效性. 1 人工蜂群算法 人工蜂群算法是一种较为新型的群智能优化算 法,其原理是通过模仿生物界蜜蜂采蜜来实现寻优. 蜂群算法的四个基本组成要素是:蜜源、引领蜂、跟 随蜂和侦察蜂;两种最基本的行为模型:招募蜜源和 放弃蜜源. 人工蜂群算法是通过蜜蜂不断地局部寻优最终 突显出全局最优值. 跟随蜂根据引领蜂分享的信 息,按下式所描述的概率公式选择蜜源: pi = f(兹i) 移 m n = 1 f(兹n ) (1) 其中,pi 表示选择概率,兹i 表示第 i 个蜜蜂,f( 兹i)表 示第 i 个蜜蜂的适应度值,m 表示种群规模. 引领蜂 与跟随蜂对蜜源进行搜索是按公式(2) 进行,公式 (2)是蜜源搜索公式,同时也被称为引领蜂与跟随 蜂位置更新公式. yid = xid + Rid (xid - xqid ), i沂(1,2,…,m) (2) 其中,yid是新蜜源位置,xid是当前蜜源位置,Rid是区 间[ - 1,1]之间的随机数,xqid是当前蜜源邻域中的 一个随机蜜源位置,d 是优化问题的参数维度. 当某个引领蜂开采蜜源连续 limit 代不变,则该 引领蜂自动转换成侦察蜂,按新的搜索公式(3) 产 生新蜜源,计算其适应度值,同样保留适应度值高的 蜜源. xij = xjmin + rand(0,1)(xjmax - xjmin ), i沂(1,2,…,m),j沂(1,2,…,d) (3) 其中,rand(0,1)是[0,1]间的随机数,xjmax和 xjmin是 参数变量的最大值与最小值. 2 粒子蜂群算法 2郾 1 粒子群算法和人工蜂群算法融合的必要性以 及粒子群蜂群算法思想 通过分析人工蜂群算法原理可知,人工蜂群算 法的全局搜索能力很强,是因为其将种群一半的蜜 蜂作为引领蜂产生初始解并通过保留适应度高的蜜 蜂来进行迭代,这样既保证了解空间的多样性,又增 强了其全局搜索能力. 但现有的侦查蜂机制导致了 当引领蜂找到一个不错的解并且连续几代蜜源适应 度不变时,只能在当前蜜源位置的邻域内搜索一个 新蜜源,这样会大幅度降低搜索效率,从而导致算法 的收敛速度慢以及过早收敛,出现“早熟冶现象. 粒子群算法可以较好地利用全局最优解来适时 地更新粒子位置,避免提前陷入局部最优. 并且粒 子群算法和人工蜂群算法都是通过迭代来更新个体 位置,融合方便. 虽然粒子群算法自身在处理复杂 的多峰问题时效果不是很好,但是人工蜂群算法的 引领蜂策略很好地弥补了粒子群算法搜索空间多样 性差的问题,因此二者融合很有必要. 所以,受粒子群算法的启发,在引领蜂变异为侦 查蜂阶段,可以改变其位置更新策略,不单单在现有 ·872·
王继超等：一种改进的人工蜂群算法一粒子蜂群算法 ·873· 个体最优蜜源位置附近进行搜索，而是根据全局最 模拟退火算法、蚁群算法等各类寻优算法的收敛性 优解的位置和个体最优解的位置来搜索蜜源，这样 验证0).宁爱平与张雪英]、王艳娇4)和邱剑 有利于跳出局部最优. 锋研究了经典人工蜂群算法的收敛性，因此，本 2.2粒子蜂和趋优度的提出 文受人工蜂群算法收敛性分析的启发，运用马尔科 针对上述问题，本文提出了趋优度的概念，通过 夫链理论，构造马尔科夫链对粒子蜂群算法的收敛 测试每一个引领蜂在迭代过程中向着全局最优解位 性进行分析 置靠近或远离的程度，来将引领蜂分为两类，一类是 3.1粒子蜂群算法的马尔科夫性 趋向程度较高的蜜蜂依然变异为侦查蜂，在当前蜜 由文献[13]可知，人工蜂状态由X,一步转移 源附近搜索：另一类趋向程度较低变异为粒子蜂，迭 到X,的转移概率表达式 代按照粒子群算法的公式进行迭代，通过全局最优 p(T(X)=X)= 解和个体最优解来更新位置，这样把趋优度较弱的 P(T.(X)=),引领蜂的一步转移概率； 个体搜索范围扩大，有利于其跳出局部最优，进而发 P(T.(X:）=X),跟随蜂的一步转移概率； 现质量更好的解.形成新的蜜蜂命名为粒子蜂，按 照粒子群算法公式更新位置： P(T.(X)=X),侦查蜂的一步转移概率： x+1=x++ (4) Pem pon 引领蜂和跟随蜂共同作用的转移概率 =w+c;rand (x)+czrand.( (7) (5) 其中，T(X)=X表示在空间S中X转移到X 其中，为第i个粒子蜂迭代到k代时的速度，0为 Pm(T.(X:)=X)= 惯性权值，c1和c2都为正常数，rand,和rand2是两 X X∈[X:-(X-X),X:+(X-X.)]; 个在[0,1]范围内变化的随机数，x,为粒子蜂自己 找到的历史最优解，x为所有粒子蜂中的全局最 otherwise. 优解. (8) 如果所有在经过limit代后最优解不发生变化 其中，X为引领峰搜索阶段解空间内随机的一个 的引领蜂都变为粒子蜂的话，有一些较好的蜜源会 点，P1表达式如下. 丢失，以提出趋优度的概念来将引领蜂分类 1, fit(X)>fit(X 趋优度： P1= (9) (0,fit(X)≤fit(X:) 其中，ft表示个体的适应度值. Q:= 觉--k-1 川x。-1-x。-x1‖ (6) pn (T.(X)=X;)= 其中，x表示第i个粒子蜂迭代到k代时的位置，x。 表示全局最优解的位置. X,∈[X-(X,-X)X+(X-X]: 测试每个个体在迭代过程中位置的变化是否趋 0 otherwise. 向于当前的全局最优解的位置，个体每迭代一代，其 (10) 位置比上一代离全局最优解位置近，趋优度加一，反 其中，X为跟随蜂搜索阶段解空间内随机的一 之减一，若无变化则加零.趋优度可以评价每个个 个点 体趋向全局最优解的程度，从而可以将蜜蜂分类 X,∈[Xa,Xs] 为了更好地将蜜蜂分类，需要设定一个临界值 p.(T.(X:)=X Q。,若Q高于Q。,引领蜂转变为侦查蜂，按照(3)更 otherwise 新位置；若Q低于Q。,引领蜂转变为粒子蜂，按照公 (11) 式(4)和(5)更新位置，通过大量实验测试，发现Q。 所以得出本文提出的粒子蜂由X,一步转移到 取为limit/2比较合理 X,的转移概率表达式为： 3粒子蜂群算法的依概率收敛性 P=(T(X)=X)= X;E[X;-(X;-X),X;+(X;-X)]; Markov过程是一类有着重要地位的随机过程， 在随机分析学中应用普遍，国内外许多学者将其拓 0, otherwise. 展并运用在各个领域，目前已成功用于对免疫算法、 (12)
王继超等: 一种改进的人工蜂群算法———粒子蜂群算法 个体最优蜜源位置附近进行搜索,而是根据全局最 优解的位置和个体最优解的位置来搜索蜜源,这样 有利于跳出局部最优. 2郾 2 粒子蜂和趋优度的提出 针对上述问题,本文提出了趋优度的概念,通过 测试每一个引领蜂在迭代过程中向着全局最优解位 置靠近或远离的程度,来将引领蜂分为两类,一类是 趋向程度较高的蜜蜂依然变异为侦查蜂,在当前蜜 源附近搜索;另一类趋向程度较低变异为粒子蜂,迭 代按照粒子群算法的公式进行迭代,通过全局最优 解和个体最优解来更新位置,这样把趋优度较弱的 个体搜索范围扩大,有利于其跳出局部最优,进而发 现质量更好的解. 形成新的蜜蜂命名为粒子蜂,按 照粒子群算法公式更新位置: x k + 1 i = x k i + v k + 1 i (4) v k + 1 i = wv k i + c1 rand1 (xp - x k i ) + c2 rand2 (xg - x k i ) (5) 其中,v k i 为第 i 个粒子蜂迭代到 k 代时的速度,w 为 惯性权值,c1 和 c2 都为正常数,rand1 和 rand2 是两 个在[0, 1]范围内变化的随机数,xp为粒子蜂自己 找到的历史最优解, xg 为所有粒子蜂中的全局最 优解. 如果所有在经过 limit 代后最优解不发生变化 的引领蜂都变为粒子蜂的话,有一些较好的蜜源会 丢失,所以提出趋优度的概念来将引领蜂分类. 趋优度: Qi = 移 limit k = 0 | xg - x k i | - | xg - x k + 1 i | 椰xg - x k i | - | xg - x k + 1 i 椰 (6) 其中,x k i 表示第 i 个粒子蜂迭代到 k 代时的位置,xg 表示全局最优解的位置. 测试每个个体在迭代过程中位置的变化是否趋 向于当前的全局最优解的位置,个体每迭代一代,其 位置比上一代离全局最优解位置近,趋优度加一,反 之减一,若无变化则加零. 趋优度可以评价每个个 体趋向全局最优解的程度,从而可以将蜜蜂分类. 为了更好地将蜜蜂分类,需要设定一个临界值 Q0 ,若 Qi高于 Q0 ,引领蜂转变为侦查蜂,按照(3)更 新位置;若 Qi低于 Q0 ,引领蜂转变为粒子蜂,按照公 式(4)和(5)更新位置,通过大量实验测试,发现 Q0 取为 limit / 2 比较合理. 3 粒子蜂群算法的依概率收敛性 Markov 过程是一类有着重要地位的随机过程, 在随机分析学中应用普遍,国内外许多学者将其拓 展并运用在各个领域,目前已成功用于对免疫算法、 模拟退火算法、蚁群算法等各类寻优算法的收敛性 验证[10鄄鄄12] . 宁爱平与张雪英[13] 、王艳娇[14] 和邱剑 锋[15]研究了经典人工蜂群算法的收敛性,因此,本 文受人工蜂群算法收敛性分析的启发,运用马尔科 夫链理论,构造马尔科夫链对粒子蜂群算法的收敛 性进行分析. 3郾 1 粒子蜂群算法的马尔科夫性 由文献[13] 可知,人工蜂状态由 Xi 一步转移 到 Xj 的转移概率表达式 p(Ts(Xi) = Xj) = pem(Ts(Xi) = Xj), 引领蜂的一步转移概率; pon (Ts(Xi) = Xj), 跟随蜂的一步转移概率; psc(Ts(Xi) = Xj), 侦查蜂的一步转移概率; pem*pon , ì î í ï ïï ï ïï 引领蜂和跟随蜂共同作用的转移概率 (7) 其中,Ts(Xi) = Xj表示在空间 S 中 Xi转移到 Xj . pem(Ts(Xi) = Xj) = 1 |Xi - Xer | p1 , Xj沂[Xi - (Xi - Xer),Xi + (Xi - Xer)]; 0, otherwise { . (8) 其中,Xer为引领峰搜索阶段解空间内随机的一个 点,p1 表达式如下. p1 = 1, fit(Xj) > fit(Xi) 0, fit(Xj)臆fit(Xi { ) (9) 其中,fit 表示个体的适应度值. pon (Ts(Xi) = Xj) = 1 |Xi - Xor | p1 , Xj沂[Xi - (Xi - Xor),Xi + (Xi - Xor)]; 0, otherwise { . (10) 其中,Xor 为跟随蜂搜索阶段解空间内随机的一 个点. psc(Ts(Xi) = Xj) = 1 |Xmax - Xmin | , Xj沂[Xmin ,Xmax] 0, { otherwise (11) 所以得出本文提出的粒子蜂由 Xi 一步转移到 Xj 的转移概率表达式为: ppa(Ts(Xi) = Xj) = 1 |Xi - Xpr | p1 , Xj沂[Xi - (Xi - Xpr),Xi + (Xi - Xpr)]; 0, otherwise { . (12) ·873·
.874. 工程科学学报，第40卷，第7期 其中，X为粒子蜂搜索阶段解空间内随机的一个点. 蜂、跟随蜂还是侦查蜂，它们的选择蜜源方式都遵循 定义1]：设{X(t),t∈T}是一个随机过程，当 “贪婪”选择，即比较新蜜源和旧蜜源两者适应度 {X(t),t∈T}在t。时刻所处的状态为已知时，它在 值，如果新的适应度值高于旧的，便选择新的蜜源； t>to所处状态的条件分布与其在to之前所处的状 反之，则维持原来蜜源不变.而粒子蜂群算法的不 态无关，则称{X(t),t∈T}具有马尔科夫性 同之处是将一部分即将变为侦查蜂的蜜蜂按照新的 定义2[)：设{X(k),k∈N*}具有马尔科夫性， 位置更新公式更新位置，目的是增加解的多样性，但 如果其一步转移概率P,(k)一直和起始时刻k无 并没有改变其选择方式，依然是选择适应度高的蜜 关，则称为齐次马尔科夫链。反之，则称为非齐次马 源位置，即 尔科夫链 Y:, fit(Y)>fit(X;); 引理11]：人工蜂群算法的种群序列B(k)= (14) x,fit(Y)≤ft(X) {X,i=1,2,…,m;k∈N*}是一有限齐次马尔科 其中Y,为新蜜源位置，所以，整个种群的进化方向 夫链 是单调的 定理1：在粒子蜂群算法中，种群状态序列 引理2[]：进化方向具有单调性且为有限齐次 C(k)={X,i=1,2,…,m;k∈N*}是一有限齐次马 马尔科夫链的种群序列以概率1收敛于全局最优解 尔科夫链 集M,即 证明：根据引理1得知，人工蜂群算法中每个蜜 limP{B(k)∈M}=1 (15) 蜂的状态与k-1时刻无关，所有蜜蜂的转移概率 定理3：在基于趋优度的粒子蜂群算法中的马 P(T(X-)=X)决定了蜂群状态序列{B(k),k∈ 尔科夫链种群序列依概率1收敛于全局最优解集 N}中的转移概率P(T.(B(k-1))=B(k),其种 M,即 群序列B(k)是一有限齐次马尔科夫链 limP{C(k)∈M}=1 (16) 在粒子蜂群算法中，蜜蜂种群的维数以及个体 证明：由定理1可得粒子蜂群种群序列为有限 数均没有变化.假设粒子蜂群算法的搜索空间为 齐次马尔科夫链，由定理2可得粒子蜂群进化方向 2,则对于空间中的随机解X,都有X∈2.因此，对 具有单调性，根据引理2可得定理3成立 于蜜蜂群体中个体状态X均为有限维数的，并且有 限个体构成的状态空间同样是有限的，且改进算法 4仿真实验 没有改变原有的三种蜜蜂的位置更新公式，添加的 为了更加合理地说明问题，本文在仿真试验中 粒子蜂位置更新公式只是与k-1时刻蜂群个体所 选取了4个不同类型的常见函数进行测试，分别是 处状态、连续没有更新位置的代数、全局最优蜜源位 Sphere、Rosenbrock、Griewank和Rastrigin..其中， 置和引领蜂领域内的局部最优位置有关，与k-1时 Sphere函数是一个简单的单峰函数：Rosenbrock函 刻无关，又因为其状态空间有限，所以粒子蜂群状态 数是一个常见的复杂单峰函数，在其空间内走势平 序列C(k)是一有限齐次马尔科夫链 缓，全局最优点却处于抛物线的顶点，所以很难收敛 3.2粒子蜂群算法的依概率收敛性 到全局最优.Griewank函数是一个非线性的函数， 定理2：粒子蜂群算法的种群进化方向都是单 具有多峰多谷特性；Rastrigin函数同样是一个多峰 调性的，即 多谷函数，与Griewank函数不同的是局部极小值比 fit(X)fit() (13) 较集中，常用来测试算法的“脱困”能力：各测试函 证明：由经典人工蜂群算法得知，无论是引领 数的具体函数表达式和取值范围如表1所示 表1测试函数 Table 1 Test function 测试函数 函数公式 取值范围 Sphere 6国=2对 [-100,100] Rosenbrock f5(x)= ,[100(41-x)2+(x-1)2] [-5.12.5.12] Griewank 1 -m-(=(）小 [-600.600] Rastrigin f4(x)= 3(号-10es(2m,)+10) [-10,10]
工程科学学报,第 40 卷,第 7 期 其中,Xpr为粒子蜂搜索阶段解空间内随机的一个点. 定义 1 [13] :设{X(t),t沂T}是一个随机过程,当 {X(t),t沂T}在 t 0 时刻所处的状态为已知时,它在 t > t 0 所处状态的条件分布与其在 t 0 之前所处的状 态无关,则称{X(t),t沂T}具有马尔科夫性. 定义 2 [13] :设{X(k),k沂N + }具有马尔科夫性, 如果其一步转移概率 pij ( k) 一直和起始时刻 k 无 关,则称为齐次马尔科夫链. 反之,则称为非齐次马 尔科夫链. 引理 1 [15] :人工蜂群算法的种群序列 B( k) = {X k i ,i = 1,2,…,m;k沂N + } 是一有限齐次马尔科 夫链. 定理 1: 在粒子蜂群算法中, 种群 状 态 序 列 C(k) = {X k i ,i = 1,2,…,m;k沂N + }是一有限齐次马 尔科夫链. 证明:根据引理 1 得知,人工蜂群算法中每个蜜 蜂的状态与 k - 1 时刻无关,所有蜜蜂的转移概率 P(Ts(X k - 1 i ) = X k i )决定了蜂群状态序列{B( k),k沂 N + }中的转移概率 P(TB (B(k - 1)) = B(k)),其种 群序列 B(k)是一有限齐次马尔科夫链. 在粒子蜂群算法中,蜜蜂种群的维数以及个体 数均没有变化. 假设粒子蜂群算法的搜索空间为 赘,则对于空间中的随机解 Xi,都有 Xi沂赘. 因此,对 于蜜蜂群体中个体状态 Xi 均为有限维数的,并且有 限个体构成的状态空间同样是有限的,且改进算法 没有改变原有的三种蜜蜂的位置更新公式,添加的 粒子蜂位置更新公式只是与 k - 1 时刻蜂群个体所 处状态、连续没有更新位置的代数、全局最优蜜源位 置和引领蜂领域内的局部最优位置有关,与 k - 1 时 刻无关,又因为其状态空间有限,所以粒子蜂群状态 序列 C(k)是一有限齐次马尔科夫链. 3郾 2 粒子蜂群算法的依概率收敛性 定理 2:粒子蜂群算法的种群进化方向都是单 调性的,即 fit(X k i ) > fit(X k - 1 i ) (13) 证明:由经典人工蜂群算法得知,无论是引领 蜂、跟随蜂还是侦查蜂,它们的选择蜜源方式都遵循 “贪婪冶 选择,即比较新蜜源和旧蜜源两者适应度 值,如果新的适应度值高于旧的,便选择新的蜜源; 反之,则维持原来蜜源不变. 而粒子蜂群算法的不 同之处是将一部分即将变为侦查蜂的蜜蜂按照新的 位置更新公式更新位置,目的是增加解的多样性,但 并没有改变其选择方式,依然是选择适应度高的蜜 源位置,即 Yi = Yi, fit(Yi) > fit(Xi); Xi, fit(Yi)臆fit(Xi { ) (14) 其中 Yi 为新蜜源位置,所以,整个种群的进化方向 是单调的. 引理 2 [15] :进化方向具有单调性且为有限齐次 马尔科夫链的种群序列以概率 1 收敛于全局最优解 集 M,即 lim k寅肄 P{B(k)沂M} = 1 (15) 定理 3:在基于趋优度的粒子蜂群算法中的马 尔科夫链种群序列依概率 1 收敛于全局最优解集 M,即 lim k寅肄 P{C(k)沂M} = 1 (16) 证明:由定理 1 可得粒子蜂群种群序列为有限 齐次马尔科夫链,由定理 2 可得粒子蜂群进化方向 具有单调性,根据引理 2 可得定理 3 成立. 4 仿真实验 为了更加合理地说明问题,本文在仿真试验中 选取了 4 个不同类型的常见函数进行测试,分别是 Sphere、 Rosenbrock、 Griewank 和 Rastrigin. 其 中, Sphere 函数是一个简单的单峰函数;Rosenbrock 函 数是一个常见的复杂单峰函数,在其空间内走势平 缓,全局最优点却处于抛物线的顶点,所以很难收敛 到全局最优. Griewank 函数是一个非线性的函数, 具有多峰多谷特性;Rastrigin 函数同样是一个多峰 多谷函数,与 Griewank 函数不同的是局部极小值比 较集中,常用来测试算法的“脱困冶 能力;各测试函 数的具体函数表达式和取值范围如表 1 所示. 表 1 测试函数 Table 1 Test function 测试函数 函数公式 取值范围 Sphere f1 (x) = 移 n i = 1 x 2 i [ - 100,100] Rosenbrock f2 (x) = 移 n-1 i = 1 [100(xi + 1 - x 2 i ) 2 + (xi - 1) 2 ] [ - 5郾 12,5郾 12] Griewank f3 (x) = 1 ( 4000 移 n i = 1 (xi - 100) 2 - ( 仪 n i = 1 cos ( xi - 100 ) ) i + 1 [ - 600,600] Rastrigin f4 (x) = 移 n i = 1 (x 2 i - 10cos (2仔xi) + 10) [ - 10,10] ·874·
王继超等：一种改进的人工蜂群算法一粒子蜂群算法 ·875· 仿真实验在matlab2014平台下进行，运行环境为 群算法（文献[9]的信息交互算法）和粒子蜂群算法进 winl0系统下ntel(R)Core(TM)i5-4200M处理器，4G 行对比，不同函数的具体情况分析如下 的内存，2.5G主频.在不同参数值的情况下分别对测 4.1 Sphere函数 试函数进行优化，目的是求取目标函数的最小值，并将 仿真实验分别测试了五种算法在不同维数下的 仿真程序运行30次后统计平均结果.本文分别将经典 最优解、最优解平均值、最优解方差、平均耗时和耗 人工蜂群算法、P人工蜂群算法（文献[7]的混合算 时方差，测试结果如表2所示，加粗表示五种对比算 法)、I人工蜂群算法（文献[8]的改进算法）、S人工蜂 法在每项指标中的最优值. 表2 Sphere函数的测试结果 Table 2 Test results of the Sphere function 维数 优化算法 最优解 最优解平均值 最优解方差 平均耗时/s 耗时方差/s2 人工蜂群算法 2.78×10-16 5.91×10-16 3.03×10-2 2.75 1.72×10-3 P人工蜂群算法 4.84×10-n 1.98×10-6 5.86×10-2 2.90 1.14×10-3 I人工蜂群算法 3.18×10-17 6.04×10-17 3.36×10-2 2.53 1.07×10-3 S人工蜂群算法 7.00×10-7 9.85×10-17 7.83×10-12 2.69 2.05×10-3 粒子蜂群算法 2.46×10-7 3.47×10-n 1.89×10-2 2.23 2.31×10-3 人工蜂群算法 1.67×10-1 7.20×10-0 4.14×10-10 3.10 1.94×10-3 P人工蜂群算法 1.26×10-16 7.36×10-5 2.59×10-1 3.34 1.62×10-3 I人工蜂群算法 7.69×10-7 5.44×10-6 1.83×10-1 3.79 2.07×10-3 S人工蜂群算法 1.62×10-4 7.15×10-18 9.19×10-2 3.15 3.72×10-3 粒子蜂群算法 4.01×10-n 1.53×10-16 7.08×10-1 2.82 1.47×10-3 人工蜂群算法 2.22×10-3 4.02×10-3 1.20×10-5 3.92 1.92×10-3 P人工蜂群算法 8.17×10-3 9.87×10-3 3.44×10-5 3.69 1.94×10-3 I人工蜂群算法 1.33×10-5 6.99×10-5 5.63×10-5 3.89 1.48×10-3 S人工蜂群算法 4.22×10-7 5.49×10-7 1.96×10-5 3.41 1.82×10-3 粒子蜂群算法 2.80×10-0 6.49×10-10 1.15×10-5 2.91 2.11×10-3 由表2可以看出：(1)五种算法最优解方差和 由表3可以看出，5维和30维情况下，粒子蜂 耗时方差基本上在同一个数量级且较小，说明这五 群算法解的方差的平均值为五种算法中最高，说明 种算法均比较稳定：(2)在收敛精度（最优解平均 其种群分散度最大，解的搜索范围最广，达到了趋优 值)方面，粒子蜂群算法优于其他算法，5维和10维 度概念提出的预期目的：10维情况下粒子蜂群算法 时有一定的优势，30维时表现突出，比人工蜂群算 解的方差的平均值同样高于P人工蜂群算法、I人 法高了5个数量级，比P人工蜂群算法、I人工蜂群 工蜂群算法和S人工蜂群算法，虽低于人工蜂群算 算法和S人工蜂群算法高了3个数量级：(3)在耗 法，但从表1中可以看出人工蜂群算法的收敛精度 时方面，粒子蜂群算法为五种算法中最低 与其余四种算法相比差了5个数量级，因此不具可 为了更加直观地说明五种算法的收敛趋势，图 比性 1列出了30次仿真实验中五种算法最优解随迭代 4.2 Rosenbrock函数 代数变化的收敛曲线.其中，D表示维数：ABC表示 五种算法在不同维数下的最优解、最优解平均 人工蜂群算法；PABC表示P人工蜂群算法；IABC 值、最优解方差、平均耗时和耗时方差，测试结果如 表示I人工蜂群算法：SABC表示S人工蜂群算法； 表4所示. PBC表示粒子蜂群算法. 由表4可以看出：(1)五种算法最优解方差和 由图1可以看出，无论在低维还是高维情况下， 耗时方差均处在同一数量级且较小，粒子蜂群算法 粒子蜂群算法的最优值下降速度都是最快的 又是五种算法中最高的，说明PBC在测试Rosenbro- 为了进一步说明粒子蜂群算法对种群分散度的 ck函数时具有良好的稳定性：(2)在收敛精度方面， 影响，表3列出了五种算法在不同维数下30次仿真 粒子蜂群算法优于人工蜂群算法、P人工蜂群算法 实验解的方差的平均值 和S人工蜂群算法，仅次于I人工蜂群算法，分析其
王继超等: 一种改进的人工蜂群算法———粒子蜂群算法 仿真实验在 matlab2014 平台下进行,运行环境为 win10 系统下 Intel(R)Core(TM)i5鄄鄄4200M 处理器,4 G 的内存,2郾 5 G 主频. 在不同参数值的情况下分别对测 试函数进行优化,目的是求取目标函数的最小值,并将 仿真程序运行30 次后统计平均结果. 本文分别将经典 人工蜂群算法、P 人工蜂群算法(文献[7]的混合算 法)、I 人工蜂群算法(文献[8]的改进算法)、S 人工蜂 群算法(文献[9]的信息交互算法)和粒子蜂群算法进 行对比,不同函数的具体情况分析如下. 4郾 1 Sphere 函数 仿真实验分别测试了五种算法在不同维数下的 最优解、最优解平均值、最优解方差、平均耗时和耗 时方差,测试结果如表 2 所示,加粗表示五种对比算 法在每项指标中的最优值. 表 2 Sphere 函数的测试结果 Table 2 Test results of the Sphere function 维数 优化算法 最优解 最优解平均值 最优解方差 平均耗时/ s 耗时方差/ s 2 人工蜂群算法 2郾 78 伊 10 - 16 5郾 91 伊 10 - 16 3郾 03 伊 10 - 12 2郾 75 1郾 72 伊 10 - 3 P 人工蜂群算法 4郾 84 伊 10 - 17 1郾 98 伊 10 - 16 5郾 86 伊 10 - 12 2郾 90 1郾 14 伊 10 - 3 5 I 人工蜂群算法 3郾 18 伊 10 - 17 6郾 04 伊 10 - 17 3郾 36 伊 10 - 12 2郾 53 1郾 07 伊 10 - 3 S 人工蜂群算法 7郾 00 伊 10 - 17 9郾 85 伊 10 - 17 7郾 83 伊 10 - 12 2郾 69 2郾 05 伊 10 - 3 粒子蜂群算法 2郾 46 伊 10 - 17 3郾 47 伊 10 - 17 1郾 89 伊 10 - 12 2郾 23 2郾 31 伊 10 - 3 人工蜂群算法 1郾 67 伊 10 - 11 7郾 20 伊 10 - 10 4郾 14 伊 10 - 10 3郾 10 1郾 94 伊 10 - 3 P 人工蜂群算法 1郾 26 伊 10 - 16 7郾 36 伊 10 - 15 2郾 59 伊 10 - 11 3郾 34 1郾 62 伊 10 - 3 10 I 人工蜂群算法 7郾 69 伊 10 - 17 5郾 44 伊 10 - 16 1郾 83 伊 10 - 11 3郾 79 2郾 07 伊 10 - 3 S 人工蜂群算法 1郾 62 伊 10 - 14 7郾 15 伊 10 - 13 9郾 19 伊 10 - 12 3郾 15 3郾 72 伊 10 - 3 粒子蜂群算法 4郾 01 伊 10 - 17 1郾 53 伊 10 - 16 7郾 08 伊 10 - 11 2郾 82 1郾 47 伊 10 - 3 人工蜂群算法 2郾 22 伊 10 - 3 4郾 02 伊 10 - 3 1郾 20 伊 10 - 5 3郾 92 1郾 92 伊 10 - 3 P 人工蜂群算法 8郾 17 伊 10 - 3 9郾 87 伊 10 - 3 3郾 44 伊 10 - 5 3郾 69 1郾 94 伊 10 - 3 30 I 人工蜂群算法 1郾 33 伊 10 - 5 6郾 99 伊 10 - 5 5郾 63 伊 10 - 5 3郾 89 1郾 48 伊 10 - 3 S 人工蜂群算法 4郾 22 伊 10 - 7 5郾 49 伊 10 - 7 1郾 96 伊 10 - 5 3郾 41 1郾 82 伊 10 - 3 粒子蜂群算法 2郾 80 伊 10 - 10 6郾 49 伊 10 - 10 1郾 15 伊 10 - 5 2郾 91 2郾 11 伊 10 - 3 由表 2 可以看出:(1)五种算法最优解方差和 耗时方差基本上在同一个数量级且较小,说明这五 种算法均比较稳定;(2) 在收敛精度(最优解平均 值)方面,粒子蜂群算法优于其他算法,5 维和 10 维 时有一定的优势,30 维时表现突出,比人工蜂群算 法高了 5 个数量级,比 P 人工蜂群算法、I 人工蜂群 算法和 S 人工蜂群算法高了 3 个数量级;(3) 在耗 时方面,粒子蜂群算法为五种算法中最低. 为了更加直观地说明五种算法的收敛趋势,图 1 列出了 30 次仿真实验中五种算法最优解随迭代 代数变化的收敛曲线. 其中,D 表示维数;ABC 表示 人工蜂群算法;PABC 表示 P 人工蜂群算法;IABC 表示 I 人工蜂群算法;SABC 表示 S 人工蜂群算法; PBC 表示粒子蜂群算法. 由图 1 可以看出,无论在低维还是高维情况下, 粒子蜂群算法的最优值下降速度都是最快的. 为了进一步说明粒子蜂群算法对种群分散度的 影响,表 3 列出了五种算法在不同维数下 30 次仿真 实验解的方差的平均值. 由表 3 可以看出,5 维和 30 维情况下,粒子蜂 群算法解的方差的平均值为五种算法中最高,说明 其种群分散度最大,解的搜索范围最广,达到了趋优 度概念提出的预期目的;10 维情况下粒子蜂群算法 解的方差的平均值同样高于 P 人工蜂群算法、I 人 工蜂群算法和 S 人工蜂群算法,虽低于人工蜂群算 法,但从表 1 中可以看出人工蜂群算法的收敛精度 与其余四种算法相比差了 5 个数量级,因此不具可 比性. 4郾 2 Rosenbrock 函数 五种算法在不同维数下的最优解、最优解平均 值、最优解方差、平均耗时和耗时方差,测试结果如 表 4 所示. 由表 4 可以看出:(1) 五种算法最优解方差和 耗时方差均处在同一数量级且较小, 粒子蜂群算法 又是五种算法中最高的,说明 PBC 在测试 Rosenbro鄄 ck 函数时具有良好的稳定性;(2)在收敛精度方面, 粒子蜂群算法优于人工蜂群算法、P 人工蜂群算法 和 S 人工蜂群算法,仅次于 I 人工蜂群算法,分析其 ·875·