王继超等：一种改进的人工蜂群算法一粒子蜂群算法 ·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·