求解離散優(yōu)化問題的元胞量子狼群演化算法

馬龍，盧才武，顧清華

（西安建筑科技大學(xué) 管理學(xué)院，陜西 西安 710055）

在人工智能計(jì)算和系統(tǒng)工程等領(lǐng)域中，許多離散空間優(yōu)化問題常具有解的多樣性、動(dòng)態(tài)性以及目標(biāo)函數(shù)收斂速度慢等特點(diǎn)。為了在有限的空間環(huán)境下快速搜尋到優(yōu)化問題的最優(yōu)解，學(xué)者們已對(duì)多種智能算法進(jìn)行融合并展開了廣泛的研究和應(yīng)用。

狼群演化算法(wolf pack evolutionary algorithm，WPEA)作為模擬自然界群狼分工協(xié)作捕獵的啟發(fā)式智能優(yōu)化算法，1970年美國著名專家Mech[1]在其著作中對(duì)狼群的行為特征進(jìn)行了詳細(xì)的描述；2014年Mirjalili等[2]將該算法與金字塔模型進(jìn)行結(jié)合，提出了一種具有等級(jí)森嚴(yán)的狼群捕獵層次模型，該算法在解決實(shí)數(shù)空間問題的應(yīng)用效果明顯。此后針對(duì)離散空間優(yōu)化問題，文獻(xiàn)[3]針對(duì)分類特征子集的優(yōu)化問題，提出了二進(jìn)制狼群演化算法；文獻(xiàn)[4-5]提出了一種改進(jìn)的二進(jìn)制狼群演化算法，擴(kuò)展了狼群演化算法的應(yīng)用范圍；Srikanth等[6]在深入分析狼群演化算法的基礎(chǔ)上，針對(duì)組合調(diào)度優(yōu)化問題，提出了二進(jìn)制量子狼群演化算法(quantum wolf pack evolutionary algorithm，QWPEA)。QWPEA算法相對(duì)于WPEA算法具有原理簡單、參數(shù)設(shè)置少、收斂速度快、較強(qiáng)的全局搜索能力等特點(diǎn)，在測(cè)試函數(shù)和實(shí)際工程應(yīng)用中取得了突出的效果[7-8]。但這些應(yīng)用都是以固定的搜索空間和種群個(gè)體位置的靜態(tài)更新為基礎(chǔ)進(jìn)行優(yōu)化求解，對(duì)于離散空間中局部和全局的并行演化以及狼群中的個(gè)體狼的量子位置旋轉(zhuǎn)角的動(dòng)態(tài)選取和調(diào)整問題，QWPEA算法并沒有一個(gè)有效的解決方法。

元胞自動(dòng)機(jī)(cellar automation，CA)最早由馮諾伊曼在1966年提出[9]，CA是一種根據(jù)簡單的并行演化規(guī)則和協(xié)同更新方法，采用元胞來模擬復(fù)雜的離散系統(tǒng)動(dòng)力學(xué)方法[10]，CA具有時(shí)空動(dòng)態(tài)性、狀態(tài)離散性和同步性等基本特征。

為了解決有限的離散空間內(nèi)狼群演化算法的收斂速度慢、搜索能力弱以及易于陷入局部最優(yōu)等問題，提出了一種求解離散優(yōu)化問題的元胞量子狼群演化算法(cellar quantum-behaved wolf pack evolutionary algorithm，CQWPEA)，該算法主要采用二進(jìn)制編碼方式和元胞自動(dòng)機(jī)中的演化規(guī)則，分別實(shí)現(xiàn)量子狼群中的個(gè)體狼位置與獵物之間的距離以及量子旋轉(zhuǎn)角的選取和調(diào)整，并給出了頭狼與獵物資源位置的編碼方式，同時(shí)給出了探狼和猛狼局部搜索算子的編碼方式，分析了編碼規(guī)則。另外，采用泛函分析方法對(duì)該算法的收斂性進(jìn)行了證明，最后通過6個(gè)測(cè)試函數(shù)驗(yàn)證了CQWPEA算法的有效性和合理性。

1 量子狼群演化算法

為了使量子狼群算法適應(yīng)離散搜索空間尋優(yōu)問題，受二進(jìn)制編碼量子粒子群演化算法[11]的啟示，在量子狼群演化算法中引入二進(jìn)制編碼，融合元胞自動(dòng)機(jī)演化規(guī)則，提出了求解離散優(yōu)化問題的元胞量子行為狼群演化算法。為分析方便，首先對(duì)元胞自動(dòng)機(jī)原理、二進(jìn)制量子狼群演化算法中的狼群行為規(guī)則、頭狼產(chǎn)生規(guī)則、狼群更新和變異等演化方程進(jìn)行描述。

1.1 元胞自動(dòng)機(jī)原理

元胞自動(dòng)機(jī)通過利用大量元胞的并行演化規(guī)則來模擬復(fù)雜結(jié)構(gòu)和過程，成為探索復(fù)雜系統(tǒng)的有效工具[12]。CA協(xié)同更新元胞空間中的所有元胞，協(xié)同更新的規(guī)則：下一個(gè)時(shí)刻元胞i的狀態(tài)是由自身和鄰居在前一時(shí)刻的狀態(tài)來決定的。元胞狀態(tài)集、鄰居、元胞空間以及局部演化規(guī)則作為CA的基本組成要素，其鄰接類型主要有兩種，即Von.Neumann 型和 Moore 型，如圖 1 所示。

元胞自動(dòng)機(jī)的動(dòng)態(tài)演化規(guī)則以元胞的動(dòng)態(tài)時(shí)間狀態(tài)變化集合為基礎(chǔ)，其可表示為

CA由一個(gè)標(biāo)準(zhǔn)的四元組構(gòu)成，其形式為

1.2 量子狼群算法

1.2.1 量子狼群編碼

在量子狼群演化算法中，人工狼編碼是以一組量子位和二進(jìn)制表示，每個(gè)量子位的狀態(tài)可用式表（6）示：

人工狼當(dāng)前位置的編碼可通過量子位的概率幅表示，考慮到狼群初始化時(shí)編碼的隨機(jī)性，假設(shè)采用量子方式編碼的個(gè)體為，則編碼方式為

式中： | α|2表示量子態(tài)被觀測(cè)為 |0 〉態(tài)概率， |β |2為量子 態(tài)被 觀測(cè) 為 |1 〉態(tài) 概 率 ， 滿足 |αi|2+|βi|2=1；i =1,2,d;d為編碼位數(shù)。

由此可知，量子狼群可表示為Q (q)=(qg1,qg2,···,qgn),其中， g 表示進(jìn)化代數(shù)，n表示個(gè)體狼數(shù)量；(i=1,2,···,n)表示第 g 代狼群中第 i只狼，即

1.2.2 雙策略的初始量子位生成過程

在初始化狼群演化過程中，狼群中每匹狼位置的所有量子位對(duì)應(yīng)態(tài)的概率幅可采用Logistic混沌映射產(chǎn)生，其產(chǎn)生的基本過程為：

1) 設(shè)狼群規(guī)模為 n，個(gè)體狼位置編碼的長度為 d；

式中：μ為混沌因子， 0 ≤μ≤4；k為迭代次數(shù)。當(dāng)μ=4， 0 ≤xkj≤1時(shí)，Logistic完全處于混沌狀態(tài)。

5) 計(jì)算全部 2n個(gè)個(gè)體的適應(yīng)度值并進(jìn)行排序，選取個(gè)適應(yīng)度值高的個(gè)體狼構(gòu)成初始狼群。

1.2.3 頭狼產(chǎn)生規(guī)則

在初始解空間中，將最接近獵物資源(或最優(yōu)目標(biāo)函數(shù))的個(gè)體狼視為頭狼，頭狼直接進(jìn)入迭代過程。算法運(yùn)行中，通過比較每匹人工狼的量子位狀態(tài)，獲得當(dāng)前狼群迭代過程中的最優(yōu)個(gè)體狼作為頭狼，最終求解得到頭狼的位置和最佳適應(yīng)度。第 j個(gè)位上的量子位狀態(tài)可表示為

式中： ( s1,s2,···,sj)表示量子狀態(tài)位對(duì)應(yīng)于人工狼的二進(jìn)制表示形式； r andom[0,1]表示在 [0 ,1]之間的隨機(jī)數(shù)， j =1,2,···,d。

在傳統(tǒng)的進(jìn)化算法中，與狼群算法的“優(yōu)勝劣汰生存”規(guī)則和遺傳算法的“輪盤賭”規(guī)則不同的是，本文設(shè)計(jì)了一種基于滑模原理的交叉量子位遺傳演化方法，用于將選擇之后產(chǎn)生的候選頭狼集合中的個(gè)體頭狼按優(yōu)秀程度降序排序，然后從染色體右端低量子位開始與頭狼染色體按照滑模方式交叉，式(11)和式(12)表示交叉參數(shù)呈高斯分布，隨著候選個(gè)體頭狼逐漸陷入局部解，如圖2所示，交叉點(diǎn)滑模按照式(13)向左移動(dòng)，用于分別與新一代頭狼迭代，產(chǎn)生更優(yōu)秀后代頭狼。

圖2 候選頭狼染色體量子位滑模交叉方法Fig. 2 The sliding mode crossover of quantum bits of candidate lead wolf

交叉權(quán)值分布函數(shù)為

式中： Ziod=(Zio,1d,Zio,2d,···,Zio,dj),j∈ L 表示第i匹候選頭狼染色體量子位 j 從最優(yōu)至次優(yōu)串排列；i=1,2,···,N;j=1,2,···,d。

交叉權(quán)值為

式中I表示當(dāng)前候選頭狼數(shù)量。

滑模位置為

1.2.4 狼群位置更新

在QWPEA中，當(dāng)滑模交叉結(jié)束后，采用上次迭代過程中的最優(yōu)解對(duì)狼群中的每一個(gè)量子位進(jìn)行量子旋轉(zhuǎn)門更新，更新過程如式(14)。

由此可知，量子旋轉(zhuǎn)門是通過改變描述量子人工狼位置的相位角來實(shí)現(xiàn)人工狼在搜索空間位置的同步移動(dòng)。

1.2.5 量子狼群變異

為了避免算法陷入局部最優(yōu)解狀態(tài)，維持狼群的多樣性，以平衡維獵場(chǎng)空間內(nèi)隨機(jī)分布的人工狼和決策變量可行域?yàn)榛A(chǔ)，實(shí)施智能獵殺行為后，基于優(yōu)勝劣汰的生存法則，會(huì)有匹人工狼被淘汰，并會(huì)有新的R匹人工狼存活下來，但存活與淘汰的人工狼數(shù)量要相等，這樣既可維持狼群規(guī)模數(shù)量，也可避免算法的過早收斂和全局搜索能力差的問題。因此，狼群中個(gè)體狼的變異過程采用量子非門實(shí)現(xiàn)，其表達(dá)形式為

式中： θij表示量子旋轉(zhuǎn)角； i =1,2,···,N； j =1,2,···,d。

假設(shè)變異概率為 pm，每個(gè)人工狼在 (0 ,1)之間給定一個(gè)隨機(jī)數(shù)random，如果 ra ndom＜pm，則隨機(jī)選擇若干個(gè)量子比特，用量子非門交換兩個(gè)概率幅，而其旋轉(zhuǎn)角度向量保持不變。

1.2.6 量子人工狼群行為描述

1) 四處游走行為

假設(shè)量子人工探狼的當(dāng)前狀態(tài)為pi，在其感知的目標(biāo)獵物資源信息為 fi ti=f(xi)的范圍內(nèi)隨機(jī)選擇一個(gè)位置狀態(tài) pj，如果 fi ti＜fitj，這時(shí)探狼i代替頭狼發(fā)起召喚行為；如果 fi ti＞fitj， 則探狼i向P個(gè)方向按照游走步長前進(jìn)一步繼續(xù)偵察；如果此時(shí)探狼i 感知的獵物氣味濃度為，則自主決策后沿著獵物留下的氣味最濃且大于當(dāng)前位置 pi的方向 p?前移一步，同時(shí)對(duì)探狼i的位置pi進(jìn)行更新。反復(fù)執(zhí)行上述行為，直到 fi ti＞fitj，或者游走次數(shù) T 達(dá)到最大游走的次數(shù) Tmax。其中選擇的方向 p?應(yīng)滿足式（16）：

在人工狼群中存在的個(gè)體探狼有著不同差異，嗅探獵物資源的方式也不同，因此可取不同的 h 值，h 可取 [hmin,hmax]之間的隨機(jī)整數(shù)。而在 d維空間中，探狼 i 沿著 p (p=1,2,···,h)個(gè)游走方向前移一步后所處的空間位置為

式中：p 表示判斷游走的方向數(shù)；γ表示在 [? 1,1]間均勻分布的隨機(jī)數(shù)； s tepds為第 d維的游走步長；表示探狼的位置。

2) 嚎叫召喚行為

假設(shè)量子人工頭狼的當(dāng)前狀態(tài)為 pi，頭狼采用嚎叫召喚行為召集周圍的 Mnum匹猛狼向其位置集合，其中 Mnum=N?Snum?1；接到頭狼召喚的猛狼都以較大的奔襲步長 st epdb快速逼近頭狼所在的位置 pd，即在第 d 維空間，猛狼 j 經(jīng)歷第 k +1次迭代的位置為

猛狼在向頭狼聚攏的過程中，如果猛狼 j 感知的獵物氣味濃度 fi ti＞fitj，則令 fi ti=fitj，此時(shí)猛狼 j轉(zhuǎn)換為頭狼并發(fā)起召喚行為；如果 fi ti＜fitj， 則猛狼 j繼續(xù)快速奔襲，且與頭狼 fi tj間的距離dis＜dnear時(shí)，即轉(zhuǎn)入圍攻。則判定距離 dnear可表示為

式中：ω為距離判定因子； D 為空間維數(shù)；maxd、mind分別為待尋優(yōu)的第 d維空間變量的最大值和最小值。

3) 智能獵殺行為

假設(shè)量子人工頭狼的當(dāng)前狀態(tài)為 pi，將距離獵物資源最近的頭狼所在位置 pd看作獵物的位置。 fi tkid可視為在第 k 代狼群中在第 d維空間中獵物的位置信息，狼群的智能獵殺行為表達(dá)為

式中： γ ∈ [?1,1]為均勻分布的隨機(jī)數(shù)； s tepdi表示人工狼i (猛狼和探狼)在維空間中智能步長數(shù)。

式中：S 表示步長因子，S值越小人工探狼搜索越精細(xì)。

2 元胞量子狼群演化算法

在CQWPEA算法中，人工狼(頭狼、探狼和猛狼)的位置表示為一組0、1構(gòu)成的二進(jìn)制編碼向量，首先通過使用概率統(tǒng)計(jì)方法對(duì)個(gè)體狼與獵物之間的最優(yōu)平均位置值進(jìn)行編碼，并記錄編碼位中出現(xiàn)的0、1次數(shù)，實(shí)現(xiàn)局部搜索算子編碼位的計(jì)算；然后，采用元胞自動(dòng)機(jī)選取和調(diào)整人工狼群位置的量子位旋轉(zhuǎn)角，增強(qiáng)元胞量子狼群演化算法的搜索空間，加快算法的收斂速度。

CQWPEA的設(shè)計(jì)思路是，將散布在獵場(chǎng)空間中的量子狼群中的探狼朝著獵物遺留的氣味濃度強(qiáng)和環(huán)境信息方向進(jìn)行嗅探，一旦發(fā)現(xiàn)獵物，探狼需要判斷自身與頭狼距離獵物資源的位置，如果探狼與獵物的量子位置旋轉(zhuǎn)角比頭狼與獵物的量子位置旋轉(zhuǎn)角大，則探狼代替頭狼發(fā)起嚎叫召喚行為，否則向頭狼報(bào)告獵物的位置信息；猛狼收到嚎叫召喚信號(hào)后，猛狼迅速向頭狼所在位置或獵物所在位置靠攏，同時(shí)對(duì)獵場(chǎng)的周圍環(huán)境進(jìn)行探測(cè)，量子狼群進(jìn)化算法中的人工狼之間以嚎叫信息實(shí)現(xiàn)相互通信，并通過元胞機(jī)中的局部演化規(guī)則不斷調(diào)整人工狼的位置旋轉(zhuǎn)角度，更好地調(diào)節(jié)人工狼群的搜索范圍和定位獵物的位置，隨著局部搜索過程的不斷推進(jìn)，人工狼群向著全局最優(yōu)解逼近，最終通過計(jì)算頭狼與獵物的平均最優(yōu)位置來實(shí)現(xiàn)目標(biāo)函數(shù)的優(yōu)化求解。

2.1 個(gè)體狼位置的二進(jìn)制編碼

在二進(jìn)制編碼的元胞量子狼群演化算法中，為了精確描述狼群中頭狼與獵物資源之間的距離關(guān)系，將元胞空間作為量子狼群演化算法的搜索空間，將距離獵物資源最近的頭狼所在位置看作獵物資源(目標(biāo)函數(shù))的位置，使用量子狼群進(jìn)化算法中的探狼、猛狼搜索到的局部最優(yōu)解和獵殺攻擊后的全局最優(yōu)解分別作為元胞空間內(nèi)一個(gè)元胞，并采用擴(kuò)展Moore鄰居類型，采用數(shù)學(xué)語言對(duì)元胞量子狼群演化算法進(jìn)行形式化描述。

式中： N 表示人工狼總數(shù)，m表 示編碼長度； xij表示人工狼的第 Xi個(gè)位置的第 j個(gè)編碼位置，通過反置賦值操作且只能取0、1；頭狼 p 和獵物資源 q之間的曼哈頓距離可表示為

定義2 移動(dòng)算子[5]，設(shè)人工狼i 的位置為Xi={xi1,xi2,···,xij,···,xim}； M 表示非空的反置編碼位，即表達(dá)了人工狼的位置；r是非空的反置編碼位數(shù)，即游走步長；運(yùn)動(dòng)算子 θ (Xi,M,r)表示在人工狼i 的位置 Xi中，從 M 個(gè)編碼位中隨機(jī)選擇 r個(gè)編碼位并對(duì)其進(jìn)行反置操作。

定義3 設(shè)集合C =(c1,c2,···,ci,···,cn),ci∈ {0,1}，ci的排列組合構(gòu)成元胞空間，其具體形式為

式中CellX表示由 ci所組合的元胞。

定義4[7]擴(kuò)展Moore鄰居類型

式中：任意兩個(gè) ci、ci+1的排序組合的差異度為diあ(cellY?cellX)≤r ，r 為差異度，本文取 r = 2。

在二進(jìn)制編碼的元胞量子狼群演化算法中，為了精確表達(dá)頭狼和獵物資源之間的距離，根據(jù)定義1，假設(shè)頭狼和獵物的位置為 (X1,X2)，它們分別有兩個(gè)決策變量 (X11,X12)、 ( X21,X22)，采用6位二進(jìn)制編碼對(duì)每個(gè)決策變量進(jìn)行表示，如圖3所示。

圖3 頭狼與獵物位置的二進(jìn)制編碼Fig. 3 Location of the lead wolf and prey with binary encoding

在CQWPEA算法中，定義頭狼與獵物(目標(biāo)函數(shù))含有決策變量的個(gè)數(shù)即為元胞空間的維數(shù)；例如， Xid表示狼群中第i 匹頭狼的 d個(gè)決策變量， Xi、Xid的二進(jìn)制編碼長度分別用l 和 ld表示，則

根據(jù)量子狼群演化算法，通過修改算法中的頭狼和獵物之間的平均最優(yōu)位置的值，生成CQWPEA中的，并用二進(jìn)制位串表示種群中全部最優(yōu)個(gè)體狼位置，通過概率統(tǒng)計(jì)方法[6]，記錄二進(jìn)制編碼位中0、1出現(xiàn)的概率次數(shù)，如果0出現(xiàn)的次數(shù)多，則對(duì)應(yīng)的值為0，否則為1，如圖4所示。

圖4 人工狼與獵物之間的平均最優(yōu)位置值Fig. 4 The optimal average position between the artificial wolf and prey

從圖4中可知，狼群中有5個(gè)最優(yōu)位置值，每個(gè)個(gè)體狼當(dāng)前的最優(yōu)個(gè)體信息分別為、、、、，其第1列對(duì)應(yīng)的二進(jìn)制位值為1、 0、1、 0、 1，依據(jù)概率統(tǒng)計(jì)方法，則對(duì)應(yīng)的第1列二進(jìn)制值為1，以此類推。由此獲得的的值為1000011110001。特別地，如果對(duì)應(yīng)的每一列中的二進(jìn)制位數(shù)中出現(xiàn)相同的0或1，則隨機(jī)選擇0或1。由此可構(gòu)造出CQWPEA算法中的函數(shù)值。

在QWPEA算法中，式(17)、(18)是探狼和猛狼在整個(gè)搜索空間的局部位置信息，其值表示了局部搜索算子 pid， pid∈(pbesti,gbestd)，pid={pi1,pi2,···,piD}位于 ( pbesti、gbest)之間的對(duì)角線兩端的超矩形中，pid到 pbesti,gbest的距離需小于對(duì)角線的長度，即

通過對(duì) pid值的計(jì)算，可使種群產(chǎn)生多樣性，并可使算法跳出局部搜索空間。在QWPEA算法中，局部搜索算子 pid的產(chǎn)生主要取決于上一代種群的 pbesti和 gbest中的每一個(gè)量子位的隨機(jī)交叉，形成下一代的搜索算子 pid，顯然滿足定義1的曼哈頓距離，如圖5所示。

圖5 人工狼的多點(diǎn)交叉算子Fig. 5 Multi-point crossover operator of wolf

探狼和猛狼的局部搜索算子， pdi、pdj的每一位編碼可由式(29)與(30)計(jì)算獲得：

式中 γ ∈ [?1,1]內(nèi)的隨機(jī)數(shù)。由此可構(gòu)造出直接計(jì)算 pid與 pjd值的函數(shù)[6]。

2.2 基于CA的量子旋轉(zhuǎn)角選取策略

在QWPEA算法中，新一代個(gè)體狼的概率幅是由上一代個(gè)體的概率幅與量子旋轉(zhuǎn)門更新計(jì)算獲得，更新過程如式(31)：

設(shè)每匹狼i的 n ?1個(gè)鄰居構(gòu)成的集合為Si(t)={x1(t),x2(t),···,xn(t)}。在解算個(gè)體狼的鄰居集合最優(yōu)解時(shí)引入以下演化規(guī)則[13]：

式中： St與 St+1分別表示t 與 t+ 1時(shí)刻元胞狀態(tài)；s表示元胞鄰居集合中狀態(tài)為1的元胞個(gè)數(shù)。設(shè)第g代狼群當(dāng)前解集第 i匹狼的局部最優(yōu)解為1,2,···,n)，狼群的全局最優(yōu)解為則量子門旋轉(zhuǎn)角的更新策略如式(34)所示：

式中 T 與 Tmax分別表示當(dāng)前迭代次數(shù)和最大進(jìn)化迭代次數(shù)。

為了增強(qiáng)量子狼群演化算法搜索范圍，將量子旋轉(zhuǎn)角進(jìn)一步擴(kuò)展到，使狼群遍歷范圍呈現(xiàn)雙向性。另外，由于量子態(tài)經(jīng)測(cè)量后獲得二進(jìn)制編碼，因此按式(36)進(jìn)行取值：

由式(36)可知，本文算法中的量子旋轉(zhuǎn)角擴(kuò)大了3倍，呈現(xiàn)雙向性，避免了混沌序列的迭代計(jì)算和多次比較的查表操作，節(jié)省了運(yùn)算時(shí)間。

2.3 CQWPEA算法的步驟

1) 初始化參數(shù)，根據(jù)1.2.2節(jié)的雙策略對(duì)量子狼群的初始量子位進(jìn)行初始化，并采用二進(jìn)制序串的形式初始化狼群中的個(gè)體狼位置，使，計(jì)算初始狼群個(gè)體的適應(yīng)度值，同時(shí)對(duì)算法的基本參數(shù)進(jìn)行初始化操作。

4) 根據(jù)初始狼群的適應(yīng)度函數(shù)值計(jì)算種群中每個(gè)個(gè)體狼位置值，并與上一次迭代的局部最優(yōu)值進(jìn)行比較，如果適應(yīng)度值，則用更新局部最優(yōu)位置；反之，則不更新；轉(zhuǎn)入步驟5) 。

5) 量子人工狼按照式(31)～(36)進(jìn)行元胞鄰域搜索，并計(jì)算狼群體中新的適應(yīng)度值。將狼群的全局最優(yōu)位置值與上一次的全局最優(yōu)位置值進(jìn)行比較，如果，則替換原最優(yōu)位置值，反之，不更新。另外在量子旋轉(zhuǎn)角中，如果，對(duì)狼群的量子編碼位進(jìn)行交叉，交換量子位概率幅與。

6) 按頭狼產(chǎn)生規(guī)則和獵物氣息元胞鄰居空間的演化規(guī)則對(duì)頭狼位置進(jìn)行更新，鄰域搜索同4)。

9) 輸出目前的最優(yōu)解集和最優(yōu)值。

3 CQWPEA算法的收斂性分析

本節(jié)將用泛函分析方法[13-14]對(duì)CQWPEA算法的收斂性進(jìn)行分析證明。令二進(jìn)制編碼字符集，采用長度為的二進(jìn)制位串表示頭狼位置編碼，編碼空間。假設(shè)狼群規(guī)模為，狼群單錢位置集合為，頭狼最佳位置集合為，則狼群的當(dāng)前位置空間可表示為

狼群中人工狼的最佳位置空間為

全局最優(yōu)解的位置空間為

根據(jù)QWPEA算法的流程圖[6]可知，QWPEA算法的解算過程遵循著反復(fù)迭代，逐漸求精的過程，該過程中包括目標(biāo)函數(shù)適應(yīng)度值的評(píng)價(jià)、位置和位置的選擇，以及人工狼的位置更新，從而使狼群達(dá)到更優(yōu)狀態(tài)。因此，可用隨機(jī)映射運(yùn)算過程來抽象表示QWPEA算法的流程。

定義5 CQWPEA算法的搜索算子T是通過逐步迭代方式對(duì)個(gè)體狼的當(dāng)前位置進(jìn)行迭代搜索，以獲得個(gè)體狼的最好位置的過程，該過程是從人工狼當(dāng)前位置的元胞狀態(tài)空間以及全局位置的元胞狀態(tài)空間隨機(jī)映射到個(gè)體狼最好位置狀態(tài)空間，其映射形式為

實(shí)驗(yàn)表明，CQWPEA算法中每一代全局最好解位置的適應(yīng)度值序列是一個(gè)遞增序列，即

在CQWPEA算法中，解算優(yōu)化問題時(shí)，通常只需關(guān)注搜索過程中狼群攻擊獲得的最好解，不妨將迭代狼群體用全局最好位置來代替。由此對(duì)CQWPEA算法的映射過程進(jìn)行重新定義，其形式為

在CQWPEA算法中，解算優(yōu)化問題的過程可視為元胞演化空間之間的映射。以下采用隨機(jī)映射的方法證明和分析CQWPEA算法的收斂性。

證明 首先證明 (S ,d)是度量空間。設(shè) S ≠?，d∈S×S的實(shí)值函數(shù)。對(duì)于 Pg,i、Pg,j、Pg,k∈ S，對(duì)應(yīng)一個(gè)實(shí)數(shù) d Pg,i,Pg,j∈S滿足：

其次證明 (S ,d)為完備度量空間。設(shè) S是有限的二進(jìn)制編碼位串{數(shù)，對(duì)當(dāng)}前狼群中最好個(gè)體狼位置的柯西序列( Pg,i,Pg,i∈S，以及 ? ε＞0， ? N，當(dāng)自然數(shù) n ＞N 時(shí)， d Pg,n,Pg,m＜ε，當(dāng) n → ∞時(shí)， Pg,n→Pg。因此 (S ,d)是完備的度量空間。

最后證明 (S ,d)是可分的。設(shè) G ?S ，因 S為有限元集合，所以 G 為可數(shù)子集。又因?yàn)?G 閉包于 S，所以 G 在 S 中稠密，由此得到 (S ,d)是可分的論證。故 (S ,d)是完備可分的度量空間，證畢。

定義7 隨機(jī)搜索算子 T :?×S→S稱為隨機(jī)壓縮算子，如果 ? K(ω)＜ 1的非負(fù)實(shí)值隨機(jī)變量，則

證明 依據(jù)CQWPEA原理，每迭代一次均可產(chǎn)生比上一次更優(yōu)的個(gè)體狼和目標(biāo)獵物資源，所以存在一個(gè)非負(fù)實(shí)值隨機(jī)變量 K (ω)∈ [0,1)，使得

定理2 (隨機(jī)壓縮映射定理)設(shè)隨機(jī)搜索算子 T :?×S→S 滿足所有的 ω ∈S ， T (ω)均為壓縮算子，即 ? ?0∈ ?,p(?0)=1，對(duì) ? ω ∈ ?0，則d Tω,Pg,i,則Pg,i,Pg,i?1,Pg,i+1∈ S,0≤ K(ω)＜1，則 T (ω)有唯一隨機(jī)不動(dòng) 點(diǎn) r (ω)，即T(ω,r(ω))=r(ω)。

然后證明r ( ω)的可測(cè)性。對(duì) ? 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(ω)連續(xù)。依據(jù)符合定理，Pg,i為一個(gè)隨機(jī)變量序列，再根據(jù)巴拿赫壓不動(dòng)點(diǎn)定理可知， Pg,i(ω)→ r(ω)，根據(jù)極限隨機(jī)變量定理的定義，r (ω)作為一個(gè)隨機(jī)變量，因此 r (ω)作為TCQWPEA(ω)的隨機(jī)不動(dòng)點(diǎn)，證畢。

4 實(shí)驗(yàn)仿真與結(jié)果分析

4.1 測(cè)試函數(shù)

為了檢驗(yàn)CQWPEA算法的尋優(yōu)性能，選取6個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，6個(gè)測(cè)試函數(shù)的表達(dá)式如下：

1) Sphere函數(shù)

2) Schwefel函數(shù)

3) Rosenbrock函數(shù)

4) Rastrigrin函數(shù)

5) Ackley函數(shù)

6)Griewangk函數(shù)

在上述6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)中， f1(x)、 f2(x)和f3(x)為單峰函數(shù)， f4(x)、 f5(x)和 f6(x)為多峰函數(shù)，函數(shù)的維數(shù)均設(shè)置為30，6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的全局最優(yōu)解均為0。

4.2 仿真結(jié)果分析

采用CQWPEA算法對(duì)6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行解算，并將其結(jié)果與WPEA、QWPEA算法的結(jié)果進(jìn)行比較。其中相同的參數(shù)設(shè)置為：狼群規(guī)模均為500，最大迭代次數(shù)為500次，收斂精度設(shè)置為0.000 01。具體到每個(gè)不同算法的參數(shù)，在WPEA算法和QWPEA算法中，判定因子，步長因子，更新因子，最大游走次數(shù)，探狼比例因子，滑模交叉，，,。在CQWPEA算法的控制參數(shù)，量子旋轉(zhuǎn)角，實(shí)驗(yàn)仿真環(huán)境：Windows7系統(tǒng)，3 GB內(nèi)存，4 GHz CPU，算法基于MATLAB2015a。每種算法的終止條件均為滿足算法的尋優(yōu)目標(biāo)或達(dá)到最大迭代次數(shù)，計(jì)算結(jié)果見表1所示。各取每個(gè)算例20次的實(shí)驗(yàn)數(shù)據(jù)，記錄其最優(yōu)值、平均值、最差值；并將CQWPEA算法的結(jié)果與WPEA和QWPEA算法進(jìn)行比較，分別記錄其平均迭代次數(shù)、最大迭代次數(shù)、收斂率以及20次獨(dú)立運(yùn)行消耗的總時(shí)間。為了增加算法的可信度，WPEA和QWPEA算法的參數(shù)直接來源于參考文獻(xiàn)，優(yōu)化比較結(jié)果如表2所示。表2中的“—”表示對(duì)應(yīng)的尋優(yōu)成功次數(shù)指標(biāo)無法獲得統(tǒng)計(jì)結(jié)果。

表1 6個(gè)測(cè)試函數(shù)的結(jié)果比較Table 1 Experimental results of six test functions

從表1的結(jié)果可知，在滿足固定收斂精度下，本文提出的CQWPEA算法分別在維度為10、20和30的基礎(chǔ)上進(jìn)行測(cè)試，發(fā)現(xiàn)除了Schwefel函數(shù)、Rosenbrock函數(shù)和Ackley函數(shù)外，其他3種函數(shù)經(jīng)過20次實(shí)驗(yàn)均能一致性收斂到問題的全局最優(yōu)解0。針對(duì)函數(shù)，CQWPEA算法和QWPEA算法均可獲得最優(yōu)解，而WPEA算法的尋優(yōu)能力較差；針對(duì)函數(shù)，3種算法均無法獲得最優(yōu)解，但幾乎可達(dá)到近似最優(yōu)解；針對(duì)函數(shù)，3種算法雖然無法獲得最優(yōu)解，但CQWPEA算法要比其他2種算法獲得的近似最優(yōu)解更為接近最優(yōu)解值0；針對(duì)函數(shù)，CQWPEA算法的尋優(yōu)能力最強(qiáng)，WPEA算法的尋優(yōu)能力要比QWPEA算法強(qiáng)，這主要是因?yàn)樵O(shè)置算法參數(shù)的不同而造成的；針對(duì)函數(shù)，雖然3種算法均沒有獲得最優(yōu)解值，但從總體上來看，CQWPEA算法獲得的最優(yōu)解幾乎接近全局最優(yōu)解，其尋優(yōu)能力較強(qiáng)，而QWPEA算法和WPEA算法獲得的最優(yōu)解距離全局最優(yōu)解相差甚遠(yuǎn)；針對(duì)函數(shù)，CQWPEA算法可獲得全局最優(yōu)解，WPEA算法的尋優(yōu)能力要比QWPEA算法強(qiáng)。

由上述分析結(jié)果可以得出，從總體上來看，本文提出的求解離散優(yōu)化問題的元胞量子狼群演化算法在尋優(yōu)能力均要優(yōu)于其他狼群演化算法和量子狼群演化算法，但從部分函數(shù)測(cè)試的結(jié)果可知，本文算法對(duì)于部分函數(shù)也會(huì)存在無法獲得全局最優(yōu)解問題，這主要是因?yàn)樗惴ǖ某跏紖?shù)設(shè)置的隨機(jī)性、局部尋優(yōu)結(jié)果差、元胞演化規(guī)則對(duì)量子旋轉(zhuǎn)角的調(diào)整速度慢、量子相位角的選擇不精確等原因造成的。

表2 迭代次數(shù)比較Table 2 Comparison of iterations

由表2的結(jié)果可知，在不同的維數(shù)和相同的優(yōu)化步數(shù)下，從收斂率和消耗時(shí)間上來看，對(duì)于6種不同的標(biāo)準(zhǔn)測(cè)試函數(shù)，CQWPEA算法收斂率均可到達(dá)100%，且消耗時(shí)間明顯比WPEA算法和QWPEA算法少；但對(duì)于不同的函數(shù)，3個(gè)算法的性能還存在一定的差異。對(duì)于f1(x)函數(shù)、f4(x)函數(shù)、f5(x)函數(shù)和f6(x)函數(shù)，WPEA算法的尋優(yōu)結(jié)果不理想，主要是因?yàn)楫?dāng)維數(shù)大于3時(shí)，這4個(gè)典型的凹函數(shù)呈現(xiàn)多峰特征，具有大量的局部極值點(diǎn)，因此找到全局最優(yōu)解較為困難。對(duì)于f3(x)函數(shù)、f4(x)函數(shù)和f6(x)函數(shù)，QWPEA算法的尋優(yōu)結(jié)果的收斂率為0，其搜索到的最優(yōu)解與目標(biāo)函數(shù)的最優(yōu)解的偏差較大，這是因?yàn)檫@3個(gè)函數(shù)是復(fù)雜的非線性多峰函數(shù)，尋優(yōu)過程中會(huì)使算法陷入局部收斂；對(duì)于f2(x)函數(shù)和f3(x)函數(shù)，QWPEA算法的收斂率也幾乎為0，其搜索到的最優(yōu)解偏差也較大。

由上述的比較結(jié)果知，與WPEA算法和QWPEA算法相比，無論從收斂精度還是收斂穩(wěn)定性方面，CQWPEA算法的尋優(yōu)性能明顯優(yōu)于其他2種算法。

另外，從算法收斂(達(dá)到收斂精度)時(shí)間方面，WPEA算法對(duì)6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)20次實(shí)驗(yàn)的收斂消耗總時(shí)間分別為31.55、91.34、77.39、33.74和31.59 s，而QWPEA算法對(duì)6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)20次實(shí)驗(yàn)的收斂消耗總時(shí)間分別為3.69、3.24、2.62、3.20、3.10和3.25 s，CQWPEA算法對(duì) 6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)20次實(shí)驗(yàn)的收斂消耗總時(shí)間分別為0.46、0.82、0.52、0.72、0.84和 0.55 s。從收斂消耗總時(shí)間來看，與WPEA算法和QWPEA算法相比，CQWPEA算法的收斂速度明顯加快。從圖6中可清晰地看出，CQWPEA算法要比WPEA算法和QWPEA算法具有較快的收斂速度。

圖6 6個(gè)測(cè)試函數(shù)的進(jìn)化曲線Fig. 6 Evolutionary curves for six test functions

5 結(jié)束語

1) 基于元胞自動(dòng)機(jī)和量子狼群演化算法的原理，提出一種求解離散優(yōu)化問題的元胞量子狼群演化算法，該算法采用雙策略方法，實(shí)現(xiàn)量子人工狼群初始位置的生成。

2) 針對(duì)狼群中個(gè)體狼的位置與獵物資源的關(guān)系問題，采用二進(jìn)制編碼方式和元胞自動(dòng)機(jī)中的演化規(guī)則，分別對(duì)狼群中個(gè)體狼與獵物間的距離進(jìn)行精確描述和量子旋轉(zhuǎn)角的選取、調(diào)整，實(shí)現(xiàn)狼群個(gè)體與獵物資源位置的精確定位和增強(qiáng)狼群的全局搜索空間能力。

3) 元胞量子狼群演化算法是對(duì)解決離散空間優(yōu)化問題的初步探索，該算法具有尋優(yōu)精度高、收斂速度快以及較強(qiáng)的魯棒性，將CQWPEA算法進(jìn)行改進(jìn)以加強(qiáng)算法的尋優(yōu)能力，并用于處理復(fù)雜約束優(yōu)化問題是進(jìn)一步研究的方向。