.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·