第5期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·723· 证明首先证明(S,d)是度量空间。设S≠O, P∈S,令r(o)= h(w),w∈2o Pg,ωe2-2o 为T(w)的唯一不 dES×S的实值函数。对于Pi、P、Pk∈S,对应 动点。 一个实数d(P,P)∈S满足： 然后证明r()的可测性。对HPo∈S,令P:(o)= 1)d(PsP)≥0，当且仅当Pu=P时，dPi, TCowPEA (@Pso),Paiti (@)TCOwPEA (@P).i=1,2.. P）=0,满足非负性； 因为P1(d)→Pg0,TCOWPEA(d,Pgu(w)→TCQWPEA(u, 2)d(Pxi.Psj)=c-f(Ps)-(c-f(Ps))=c-f(P:j)- Po),P∈S,即TCOWPEA(ω)连续。依据符合定理，{P (c-f(P)冰满足对称性； 为一个随机变量序列，再根据巴拿赫压不动点定 3)(PrP)=(c-f(P:)-(c-f(P=c-f(P)- 理可知，P(ω)→r(ω)，根据极限随机变量定理的 (c-f(Ps)+(c-f(Pg》-(c-f(Px》≤c-f(Pg)- 定义，r(U)作为一个随机变量，因此r(w)作为TCOWPEA(d) (c-f(P)川+(c-f(P)-(c-f(P)川，满足三角 的随机不动点，证毕。 不等式，因此(S,d)为度量空间。 其次证明(S,d为完备度量空间。设S是有限 4实验仿真与结果分析 的二进制编码位串数，对当前狼群中最好个体狼 4.1测试函数 位置的柯西序列P,P∈S,以及Ve>0,3N,当自 为了检验CQWPEA算法的寻优性能，选取 然数n>N时，d(Pa,Pgm)<E,当n→o时，Pn→Pgo 6个标准的测试函数进行仿真实验，6个测试函数 因此(S,d)是完备的度量空间。 的表达式如下： 最后证明(S,d)是可分的。设GSS,因S为有 l)Sphere函数 限元集合，所以G为可数子集。又因为G闭包于S, -100≤x:≤100 所以G在S中稠密，由此得到(S,d)是可分的论证。 故(S,d)是完备可分的度量空间，证毕。 o 2)Schwefel函数 定义7随机搜索算子T:2×S→S称为随机 压缩算子，如果K()<1的非负实值随机变量，则 E=418929xd-2-smu. -500≤x≤500 d(to,d(T(w,P,T(w,Pg+i)》K(ω)dPg,Pg+i)D=1 3)Rosenbrock函数 P,Pg41∈S 定理1 CQWPEA算法的迭代过程形成的映 -2oa-f+c-y -30≤：≤30 射TCOWPEA是随机压缩算子。 证明依据CQWPEA原理，每迭代一次均可 4)Rastrigrin函数 产生比上一次更优的个体狼和目标猎物资源，所 i)-∑(G-10cos2)+10 ，-5.12≤x≤5.12 以存在一个非负实值随机变量K()∈0,1)，使得 d(TCQWPEA(@,Psi-1).TcQWPEA(@,P))=d(Pi,P3.it)= 5)Ackley函数 (c-f(P》-(c-f(Ps*i)≤K(o)I(c-f(P-i)》- (c-f(Px)川=K(ω)d(Pg-1,P) =-20e52 2o=:d(TcQWPEA (@Pi-1),TCQWPEA(@,Pi-1)) K(w)d(P-,Pg}≤2 an传2me小w622 p(2o)=1 6)Griewangk函数 由此可知，CQWPEA算法迭代过程中形成的 映射TCQWPEA:2×SX×SP×S8→SP是一个随机压缩 f()= 2-im+1-1mxe1m 算子。 在上述6个标准测试函数中，无(x)、(,)和 定理2（随机压缩映射定理）设随机搜索算 6(x)为单峰函数，(x、5(x)和f6(x)为多峰函数，函 子T:2×S→S满足所有的w∈S,T(w)均为压缩算 数的维数均设置为30,6个标准测试函数的全局 子，即32∈2，p(2o)=1,对w∈2o,则d(T(w,P), 最优解均为0。 T(,P-i》≤K(o)d(P,P+),则P,P-l,Pg41∈S, 4.2仿真结果分析 0≤K()<1,则T(w)有唯一随机不动点r(),即 采用CQWPEA算法对6个标准测试函数进 T(w,r(w)=r(w)。 行解算，并将其结果与WPEA、QWPEA算法的结 证明首先利用巴拿赫压不动点定理，对 果进行比较。其中相同的参数设置为：狼群规模 u∈2o,h(o)∈S作为T(o)的唯一不动点，对 均为500，最大迭代次数为500次，收敛精度设置(S,d) S , Ø d ∈ S ×S Pg,i、Pg, j、Pg,k ∈ S d ( Pg,i ,Pg, j ) ∈ S 证明 首先证明 是度量空间。设 ， 的实值函数。对于 ，对应 一个实数 满足： d ( Pg,i ,Pg, j ) ⩾0 Pg,i =Pg, j d(Pg,i Pg, j) = 0 1 ) ，当且仅当 时 ， ， ，满足非负性； d ( Pg,i ,Pg, j ) =   c− f ( Pg,i ) − ( c− f ( Pg, j ))  =   c− f ( Pg, j ) − ( c− f ( Pg,i ))   2) ，满足对称性； ( Pg,i ,Pg, j ) =   (c− f ( Pg,i ) − ( c− f ( Pg, j ))  =   c− f ( Pg,i ) − ( c− f ( Pg,k ) ) + ( c− f ( Pg,k )) − ( c− f ( Pg, j )) ⩽ c− f ( Pg,i ) − ( c− f ( Pg,k ))  +    ( c− f ( Pg,k ))− ( c− f ( Pg, j ))   (S,d) 3 ) ，满足三角 不等式，因此 为度量空间。 (S,d) S { Pg,i ,Pg,i ∈ S } ∀ε>0 ∃N n>N d ( Pg,n,Pg,m ) <ε n → ∞ Pg,n → Pg (S,d) 其次证明 为完备度量空间。设 是有限 的二进制编码位串数，对当前狼群中最好个体狼 位置的柯西序列 ，以及 ， ，当自 然数 时 ， ，当 时 ， 。 因此 是完备的度量空间。 (S,d) G ⊆ S S G G S G S (S,d) (S,d) 最后证明 是可分的。设 ，因 为有 限元集合，所以 为可数子集。又因为 闭包于 ， 所以 在 中稠密，由此得到 是可分的论证。 故 是完备可分的度量空间，证毕。 T : Ω×S → S ∃K(ω) < 1 定义 7 随机搜索算子 称为随机 压缩算子，如果 的非负实值随机变量，则 d({ω,d(T(ω,Pg,i),T(ω,Pg,i+1))K(ω)d(Pg,i ,Pg,i+1)}) = 1 Pg,i , Pg,i+1 ∈ S TCQWPEA 定理 1 CQWPEA 算法的迭代过程形成的映 射 是随机压缩算子。 K(ω) ∈ [0,1) 证明 依据 CQWPEA 原理，每迭代一次均可 产生比上一次更优的个体狼和目标猎物资源，所 以存在一个非负实值随机变量 ，使得 d ( TCQWPEA ( ω,Pg,i−1 ) ,TCQWPEA ( ω,Pg,i )) =d ( Pg,i ,Pg,i+1 ) =    ( c− f ( Pg,i ))− ( c− f ( Pg,i+1 ))   ⩽ K(ω)| ( c− f ( Pg,i−1 ))− ( c− f ( Pg,i ))   = K(ω)d ( Pg,i−1 ,Pg,i ) Ω0 = { ω : d ( TCQWPEA ( ω,Pg,i−1 ) ,TCQWPEA ( ω,Pg,i−1 )) ⩽ K(ω)d ( Pg,i−1 ,Pg,i )} ⩽ Ω p(Ω0) = 1 TCQWPEA : Ω×S X ×S P ×S g → S P 由此可知，CQWPEA 算法迭代过程中形成的 映射 是一个随机压缩 算子。 T : Ω×S → S ω ∈ S T (ω) ∃Ω0 ∈ Ω, p(Ω0) = 1 ∀ω ∈ Ω0 d ( T ( ω,Pg,i ) , T ( ω,Pg,i−1 )) ⩽ K(ω)d ( Pg,i ,Pg,i+1 ) Pg,i ,Pg,i−1,Pg,i+1 ∈ S, 0 ⩽ K(ω)<1 T (ω) r(ω) T (ω,r(ω)) = r(ω) 定理 2 (随机压缩映射定理) 设随机搜索算 子 满足所有的 ， 均为压缩算 子，即 ， 对 ， 则 ， 则 ， 则 有唯一随机不动点 ， 即 。 ∀ω ∈ Ω0 ∃h(ω) ∈ S T (ω) 证明 首先利用巴拿赫压不动点定理，对 ， 作 为 的唯一不动点，对 Pg,i ∈ S r(ω) = { h(ω), ω ∈ Ω0 Pg,i , ω ∈ Ω−Ω0 ， 令 为 T (ω) 的唯一不 动点。 r(ω) ∀Pg,0 ∈ S Pg,1 (ω) = TCQWPEA ( ω,Pg,0 ) Pg,i+1 (ω) = TCQWPEA ( ω,Pg,i ) ,i = 1,2,··· , Pg,1 (ω)→Pg,0 TCQWPEA ( ω,Pg,i(ω) )→TCQWPEA (ω, Pg,0 ) ,Pg,i ∈ S TCQWPEA (ω) { Pg,i } Pg,i(ω) → r(ω) r(ω) r(ω) TCQWPEA (ω) 然后证明 的可测性。对 ，令 ， 因 为 ， ，即 连续。依据符合定理， 为一个随机变量序列，再根据巴拿赫压不动点定 理可知， ，根据极限随机变量定理的 定义， 作为一个随机变量，因此 作为 的随机不动点，证毕。 4 实验仿真与结果分析 4.1 测试函数 为了检验 CQWPEA 算法的寻优性能，选取 6 个标准的测试函数进行仿真实验，6 个测试函数 的表达式如下： 1) Sphere 函数 f1 (x) = ∑d i=1 x 2 i , −100 ⩽ xi ⩽ 100 2) Schwefel 函数 f2 (x) = 418.982 9×d− ∑d i=1 xi ·sin( |xi | 1 2 ) , −500 ⩽ xi ⩽ 500 3) Rosenbrock 函数 f3 (x) = ∑d i=1 [ 100( xi+1 − x 2 i )2 +(xi −1) 2 ] , −30 ⩽ xi ⩽ 30 4) Rastrigrin 函数 f4 (x) = ∑d i=1 ( x 2 i −10 cos(2πxi)+10) , −5.12 ⩽ xi ⩽ 5.12 5) Ackley 函数 f5 (x) = −20 exp  − 1 5 √ 1 d ∑d i=1 x 2 i  − exp   1 d ∑d i=1 cos(2πxi)   +20+e, −32 ⩽ xi ⩽ 32 6)Griewangk 函数 f6 (x) = 1 4 000 ∑d i=1 x 2 i − ∏d i=1 cos( xi √ i ) +1,−100 ⩽ xi ⩽ 100 f1 (x) f2 (x) f3 (x) f4 (x) f5 (x) f6 (x) 在上述 6 个标准测试函数中， 、 和 为单峰函数， 、 和 为多峰函数，函 数的维数均设置为 30，6 个标准测试函数的全局 最优解均为 0。 4.2 仿真结果分析 采用 CQWPEA 算法对 6 个标准测试函数进 行解算，并将其结果与 WPEA、QWPEA 算法的结 果进行比较。其中相同的参数设置为：狼群规模 均为 500，最大迭代次数为 500 次，收敛精度设置 第 5 期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·723·