一種改進(jìn)的量子粒子群算法*

彭　廣，方洋旺，張　磊，刁興華，徐　洋

（空軍工程大學(xué)航空航天工程學(xué)院，西安　710038）

一種改進(jìn)的量子粒子群算法*

彭廣，方洋旺，張磊，刁興華，徐洋

（空軍工程大學(xué)航空航天工程學(xué)院，西安710038）

量子粒子群算法是將量子計(jì)算與粒子群算法相結(jié)合的一種新的優(yōu)化方法。首先利用相位角進(jìn)行實(shí)數(shù)編碼，將動(dòng)態(tài)量子旋轉(zhuǎn)門引入到粒子群算法中，采用自適應(yīng)變異，提出了一種改進(jìn)的量子粒子群算法。然后運(yùn)用Penalized函數(shù)和Ackley函數(shù)測(cè)試了該算法的性能。最后將該算法應(yīng)用到武器目標(biāo)分配模型中，獲得了最優(yōu)的分配方案。仿真研究表明，該算法具有收斂速度快、搜索能力強(qiáng)和穩(wěn)定性高的特點(diǎn)。

量子粒子群算法，實(shí)數(shù)編碼，動(dòng)態(tài)量子旋轉(zhuǎn)門，自適應(yīng)變異，武器目標(biāo)分配

0　引言

為了使多種智能算法優(yōu)勢(shì)互補(bǔ)，遵循“組合優(yōu)化”的思路，對(duì)不同智能優(yōu)化算法進(jìn)行融合是一個(gè)重要的研究思路。量子進(jìn)化算法（QEA）就是量子計(jì)算與進(jìn)化計(jì)算相融合的產(chǎn)物［1］，它將量子比特的概率幅表示方式應(yīng)用于染色體的編碼，使得染色體能夠以概率表示所有狀態(tài)。同時(shí)，QEA利用染色體最優(yōu)個(gè)體的信息來更新量子旋轉(zhuǎn)門，使整個(gè)種群向當(dāng)前最優(yōu)解快速收斂。其中，Narayanan等［2］于1996年首次將量子理論與進(jìn)化算法相結(jié)合，提出了量子衍生遺傳算法（QIEA）的概念。Han等［3-5］將其擴(kuò)展為量子進(jìn)化算法，實(shí)現(xiàn)了組合優(yōu)化問題的求解。孫俊等［6］將量子算法引入到粒子群算法中，提出了一種量子粒子群算法（QPSO）。方偉等［7］討論了QPSO的收斂性，證明QPSO是一種全局收斂的算法。文獻(xiàn)［8］將協(xié)同搜索策略用于QPSO算法中，以解決進(jìn)化類算法的早熟問題，但通信頻率控制參數(shù)以及子種群大小不容易確定；文獻(xiàn)［9］分別基于勢(shì)阱、諧振子和方勢(shì)阱提出了改進(jìn)的量子勢(shì)阱粒子群優(yōu)化算法，通過對(duì)比發(fā)現(xiàn)勢(shì)阱的性能更優(yōu)；文獻(xiàn)［10］將遺傳算法中的交叉、變異操作引入到QPSO算法中，較好地解決了車輛路徑問題，但算法的運(yùn)行時(shí)間較長；文獻(xiàn)［11］提出了一種二進(jìn)制編碼的量子粒子群算法，用于解決離散空間優(yōu)化問題，但在解決高維復(fù)雜優(yōu)化問題時(shí)，算法會(huì)產(chǎn)生編碼“長度災(zāi)”和頻繁編、解碼問題。此外，通過對(duì)算法進(jìn)行改進(jìn)，QPSO算法已經(jīng)成功應(yīng)用于濾波器設(shè)計(jì)、系統(tǒng)辨識(shí)、航路規(guī)劃以及圖像處理等領(lǐng)域［12-15］。雖然量子粒子群算法與粒子群算法相比有更好的全局搜索能力，但仍然容易陷入局部最優(yōu)，出現(xiàn)早熟的問題，算法穩(wěn)定性需要進(jìn)一步提高。

為了進(jìn)一步改善量子粒子群算法的性能，本文采用組合最優(yōu)方案，基于文獻(xiàn)［16］提出的具有量子行為的實(shí)數(shù)編碼進(jìn)化算法，擬采用相位角編碼的實(shí)數(shù)編碼方式，將動(dòng)態(tài)量子旋轉(zhuǎn)門引入到粒子群算法中，采用自適應(yīng)變異，提出一種改進(jìn)的量子粒子群算法。然后運(yùn)用Penalized函數(shù)和Ackley函數(shù)測(cè)試該算法的性能。最后將該算法應(yīng)用到武器目標(biāo)分配模型中，成功獲得了最優(yōu)的分配方案，驗(yàn)證了算法的合理性和有效性。

1　基于相位角編碼的量子粒子群算法

考慮n維連續(xù)空間目標(biāo)函數(shù)優(yōu)化問題

式中，F(xiàn)（x）為目標(biāo)函數(shù)；變量x=（x1，x2，…，xn）∈Rn；ai和bi為第i個(gè)變量的上下限。

1.1相位角編碼染色體

相位角編碼染色體是一種實(shí)數(shù)編碼方式，量子染色體chrom（t）的第i個(gè)量子位由變量xi對(duì)應(yīng)的相位角θi表示，長度解由空間的維數(shù)n決定，則相位角染色體編碼可以描述為：

其中，θi∈［-π/2，π/2］；通過相位角θi的更新，并按照一定的映射關(guān)系從相空間映射到解空間，實(shí)現(xiàn)染色體的進(jìn)化搜索。

變量xi和對(duì)應(yīng)相位角θi之間的映射關(guān)系可表示如下：

不同的映射關(guān)系對(duì)算法的性能有著較大的影響，本文選取有較好優(yōu)化性能的正弦函數(shù)作為變量與對(duì)應(yīng)相位角之間的映射關(guān)系［17］：

具體關(guān)系如圖1所示：

圖1　變量和相位角之間的映射關(guān)系

在相位角編碼染色體中，染色體chrom（t）中的第i個(gè)量子位的相位角θi的具體計(jì)算方法為：

其中，rand0是［0，1］間均勻分布的隨機(jī)數(shù)。從中可以看出，染色體量子位的相位角θi不再表示一個(gè)確定的角度值，而是可以表現(xiàn)為區(qū)間［-π/2，π/2］上的所有角度值，同時(shí)由于疊加態(tài)特性染色體chrom（t）映射到解空間后就能夠表達(dá)優(yōu)化問題的所有可行解，豐富了種群的多樣性。

1.2量子染色體的速度和位置更新

借鑒基本粒子群算法的基本思想，首先在可行解空間和速度空間初始化粒子群，即確定粒子群的初始位置和初始速度，其中初始位置代表問題的可行解。在本文中，粒子群的初始位置即為相位角編碼初始化的量子染色體，初始速度dangle=0。n維搜索空間中的第i個(gè)粒子的位置和速度可分別表示為：

通過評(píng)價(jià)各粒子的適應(yīng)度，確定t時(shí)刻每個(gè)粒子所經(jīng)過的最佳位置selfchromi=｛φi1，φi2，…，φin｝以及群體中所發(fā)現(xiàn)的最佳位置bestchrom，再按如下迭代公式分別更新各粒子的速度和位置

式中，w為慣性因子；c1和c2為正常數(shù)，稱為認(rèn)知因子和社會(huì)因子；r1和r2為［0，1］間均勻分布的隨機(jī)數(shù)。

1.3動(dòng)態(tài)量子旋轉(zhuǎn)門

在量子理論中，各個(gè)量子狀態(tài)之間的轉(zhuǎn)換主要是通過量子門實(shí)現(xiàn)的。而量子染色體進(jìn)化是量子進(jìn)化算法的核心，是提高種群適應(yīng)度的關(guān)鍵手段。在量子粒子群算法中，量子旋轉(zhuǎn)門的實(shí)質(zhì)就是改變量子染色體的相位角。通過動(dòng)態(tài)量子旋轉(zhuǎn)門不斷地更新操作，可使種群更快地收斂到最優(yōu)解。

對(duì)于t代種群中的染色體chrom（t），經(jīng)過動(dòng)態(tài)旋轉(zhuǎn)門旋轉(zhuǎn)，其t+1代染色體chromi（t+1）的第j個(gè)量子位的相位角為

其中，Δθij（t）為量子旋轉(zhuǎn)門的旋轉(zhuǎn)角；Δθbj（t）為t代最優(yōu)解對(duì)應(yīng)的染色體θg（t）的第i個(gè)量子位的相位角。

量子門旋轉(zhuǎn)角極大地影響算法的搜索效率和精度，一般而言，初期算法需要較大的旋轉(zhuǎn)角以粗粒度探索未知空間；在后期，隨著解的質(zhì)量的提高，算法需要逐步減小旋轉(zhuǎn)角以細(xì)粒度搜索當(dāng)前空間。為此，本文采用動(dòng)態(tài)旋轉(zhuǎn)角來代替固定旋轉(zhuǎn)角，在算法迭代過程中動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角大小。對(duì)于染色體chrom（t），其動(dòng)態(tài)旋轉(zhuǎn)角為：

式中，Δθ0為初始旋轉(zhuǎn)角；λ為正常數(shù)，用于調(diào)整轉(zhuǎn)角的變化率；NCmax為最大迭代次數(shù)。

1.4自適應(yīng)變異

在量子染色體的速度和位置更新及動(dòng)態(tài)量子旋轉(zhuǎn)門的作用下，所有染色體向當(dāng)前最優(yōu)染色體快速演化，這樣在搜索過程中染色體可能無法覆蓋整個(gè)解空間。為保持種群多樣性，避免算法陷入局部最優(yōu)，引入了量子染色體自適應(yīng)變異的思想。染色體chrom（t）經(jīng)過自適應(yīng)變異操作后變?yōu)椋?/p>

式中，rand1是［0，1］間均勻分布的隨機(jī)數(shù)；P0為0～0.1之間的常數(shù)，稱為變異概率；O（chrom（t））為相位角重新編碼染色體，為新個(gè)體的產(chǎn)生提供機(jī)會(huì)。

2　量子粒子群算法流程

量子粒子群算法具體步驟如下：

Step1：參數(shù)初始化。t=0，種群初始化。

Step2：適應(yīng)度評(píng)價(jià)。將量子染色體映射到對(duì)應(yīng)解空間，進(jìn)行第一次適應(yīng)度評(píng)價(jià)，粒子歷史最優(yōu)值是粒子本身，種群歷史最優(yōu)值是適應(yīng)度最大的值。

Step3：速度和位置更新。根據(jù)式（7）和式（8）更新量子染色體的速度和位置。

Step4：保留最優(yōu)個(gè)體。將更新后的量子染色體再次映射到對(duì)應(yīng)解空間，分別計(jì)算其目標(biāo)函數(shù)值，更新個(gè)體極值和群體極值，確定群體最優(yōu)解并保留。判斷是否滿足約束條件：是，則程序結(jié)束運(yùn)行；否，轉(zhuǎn)到Step5。

Step5：用動(dòng)態(tài)量子旋轉(zhuǎn)門對(duì)染色體進(jìn)行更新。

圖2　量子粒子群算法流程圖

Step6：自適應(yīng)變異，變異概率設(shè)置為0.05。

Step7：迭代次數(shù)t=t+1，算法轉(zhuǎn)到Step3繼續(xù)執(zhí)行。

3　標(biāo)準(zhǔn)測(cè)試函數(shù)研究

為測(cè)試算法的性能，將量子粒子群算法（QEA-PSO）和基本粒子群算法（PSO）及量子進(jìn)化算法（QEA）分別對(duì)兩個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行求解。

1）Penalized函數(shù)

其中，yi=1+0.25（xi+1），xi∈［-50，50］，全局最小值點(diǎn)為（-1，-1，…，-1），全局最小值為0。

2）Ackley函數(shù)

其中，xi∈［-32，32］，全局最小點(diǎn)（0，0，…，0），全局最小值為0。

兩個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的維數(shù)均為n=30，3種算法的種群大小均為m=30，最大迭代次數(shù)NCmax=2 000，其他具體參數(shù)設(shè)置如下：

PSO：慣性因子w=0.729，記憶因子c1=c2=1.494；

QEA：初始旋轉(zhuǎn)角Δθ0=1.1°，調(diào)整轉(zhuǎn)角變化率的參數(shù)λ=6；

QEA-PSO：慣性因子w=0.729，記憶因子c1=c2= 1.494，初始旋轉(zhuǎn)角Δθ0=1.1°，調(diào)整轉(zhuǎn)角變化率的參數(shù)λ=6。

每次仿真實(shí)驗(yàn)均進(jìn)行50次仿真，并統(tǒng)計(jì)仿真結(jié)果的平均值、最優(yōu)值、最劣值和方差，得到的統(tǒng)計(jì)結(jié)果如表1和表2所示。

表1　Penalized函數(shù)優(yōu)化結(jié)果

表2　Ackley函數(shù)優(yōu)化結(jié)果

仿真結(jié)果表明，對(duì)于具有較多局部最小值的標(biāo)準(zhǔn)測(cè)試函數(shù)，PSO雖然有時(shí)能搜索到精度較高的最優(yōu)解，但算法的性能極不穩(wěn)定，每次尋優(yōu)結(jié)果相差較大；QEA對(duì)于具有較多局部最優(yōu)值的高維函數(shù)尋優(yōu)效果極差；而QEA-PSO無論是尋優(yōu)精度還是算法的穩(wěn)定性都優(yōu)于其他兩種算法。

圖3和圖4分別表示3種算法在50次獨(dú)立仿真中目標(biāo)函數(shù)值的平均的變化曲線。從對(duì)比的收斂曲線可以看出，對(duì)于求解復(fù)雜的高維函數(shù)，QEA-PSO尋優(yōu)速度快，搜素精度高，算法穩(wěn)定性好。

圖3　Penalized函數(shù)仿真結(jié)果

圖4　Ackley函數(shù)仿真結(jié)果

4　實(shí)例研究

本文采用文獻(xiàn)［18］的武器目標(biāo)分配模型進(jìn)行檢驗(yàn)，假設(shè)我方具有兩組不同類型的導(dǎo)彈，對(duì)3個(gè)目標(biāo)進(jìn)行打擊。第1組有6枚導(dǎo)彈，第2組由10枚導(dǎo)彈。求最優(yōu)分配方案，使導(dǎo)彈對(duì)目標(biāo)的毀傷指標(biāo)最大。

目標(biāo)函數(shù)為：

約束條件：

其中，目標(biāo)的危險(xiǎn)程度系數(shù)wn和目標(biāo)易損性pkn如表3所示。

表3　目標(biāo)重要程度和目標(biāo)易損性系數(shù)

為了驗(yàn)證算法的性能，將量子粒子群算法（QEA-PSO）和基本粒子群算法（PSO）及量子進(jìn)化算法（QEA）作仿真比較。其中，粒子群種群大小為10，最大迭代次數(shù)NCmax=100，其他具體參數(shù)設(shè)置如下：

PSO：慣性因子w在0.5～0之間線性取值，記憶因子c1=c2=2；

QEA：初始旋轉(zhuǎn)角Δθ0=10°，調(diào)整轉(zhuǎn)角變化率的參數(shù)λ=25；

QEA-PSO：慣性因子w在0.5～0之間線性取值，記憶因子c1=c2=2，初始旋轉(zhuǎn)角Δθ0=10°，調(diào)整轉(zhuǎn)角變化率的參數(shù)λ=25。

用上述3種優(yōu)化算法分別進(jìn)行仿真實(shí)驗(yàn)，得到的染色體適應(yīng)度變化趨勢(shì)如圖5所示。

圖5　適應(yīng)度變化趨勢(shì)

目標(biāo)函數(shù)值記錄結(jié)果如下頁表4所示。

針對(duì)上述導(dǎo)彈武器火力分配模型，以往的文獻(xiàn)中也用不同的方法作出了不同的研究。例如文獻(xiàn)［19］用動(dòng)態(tài)規(guī)劃方法求解的結(jié)果為F=0.911 3，顯然不是最優(yōu)解。文獻(xiàn)［20］用遺傳算法求解，在必須使用先驗(yàn)知識(shí)的前提下，可以得到最優(yōu)解F=0.917 8，但這并不符合實(shí)際需要。文獻(xiàn)［18］采用改進(jìn)粒子群算法求解此問題，在迭代6次的時(shí)候可以得到最優(yōu)解F=0.917 8，而QEA-PSO只需要迭代4次，說明QEA-PSO的優(yōu)化效率更高。

表4　目標(biāo)函數(shù)值記錄結(jié)果

對(duì)比和分析上述仿真結(jié)果可以看出，在PSO、QEA、QEA-PSO 3種算法中，QEA的變換過程相對(duì)簡(jiǎn)單，尋優(yōu)過程容易陷入局部最優(yōu)從而出現(xiàn)早熟收斂；PSO和QEA相比，PSO全局搜索能力比QEA強(qiáng)，通過一定的迭代次數(shù)能找到全局最優(yōu)解；QEA-PSO結(jié)合了QEA和PSO兩種算法各自的優(yōu)點(diǎn)，具有收斂速度快、全局尋優(yōu)能力強(qiáng)、算法穩(wěn)定性高等特點(diǎn)。

5　結(jié)論

本文提出了一種改進(jìn)的量子粒子群算法。該算法利用相位角進(jìn)行實(shí)數(shù)編碼，保證了種群的多樣性和進(jìn)化的方向性，實(shí)現(xiàn)了算法局部搜索和全局搜索的平衡。為進(jìn)一步將該算法應(yīng)用到路徑規(guī)劃、運(yùn)籌調(diào)度、圖像處理以及控制器設(shè)計(jì)等領(lǐng)域奠定了堅(jiān)實(shí)的理論基礎(chǔ)。

［1］王凌.量子進(jìn)化算法研究現(xiàn)狀［J］.控制與決策，2008，23

（12）：1321-1326.

［2］NARAYANAN A，MOORE M.Quantum-inspired genetic algorithm［C］//IEEE Congress on Evolutionary Computation，1996：61-66.

［3］HAN K H，KIM J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization［J］.IEEE Trans on evolutionary computation，2002，6（6）：580-593.

［4］HAN K H，KIM J H.Quantum-inspired evolutionary algorithmwithanewterminationcriterion，Hεgateand two-phase scheme［J］.IEEE Trans on Evolutionary Computation，2004，8（2）：156-189.

［5］KIM Y，KIM J H，HAN K H.Quantum-inspired multi objective evolutionary algorithm for multi objective 0/1 knapsack problems［C］//IEEE Congress on Evolutionary Computation，2006：2601-2606.

［6］SUN J，F(xiàn)ENG B，XU W B.Particle swarm optimization with particles having quantum behavior［C］//Proceedings of IEEE Congress on Evolutionary Computation，2004：325-331.

［7］方偉，孫俊，謝振平，等.量子粒子群優(yōu)化算法的收斂性及控制參數(shù)研究［J］.物理學(xué)報(bào)，2010，59（6）：3686-3694.

［8］周頔，孫俊，須文波.具有量子行為的協(xié)同粒子群優(yōu)化算法［J］.控制與決策，2011，26（4）：582-586.

［9］李盼池，王海英，宋考平，等.量子勢(shì)阱粒子群優(yōu)化算法的改進(jìn)研究［J］.物理學(xué)報(bào)，2012，61（6）：25-34.

［10］黃震.混合量子粒子群算法求解車輛路徑問題［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（24）：219-223.

［11］奚茂龍，孫俊，吳勇.一種二進(jìn)制編碼的量子粒子群優(yōu)化算法［J］.控制與決策，2010，25（1）：99-104.

［12］余靜，吳樂南，靳一.基于量子粒子群算法優(yōu)化的數(shù)字沖擊濾波器自動(dòng)設(shè)計(jì)［J］.東南大學(xué)學(xué)報(bào)，2012，42（2）：224-228.

［13］黃宇，韓璞，劉長良，等.改進(jìn)量子粒子群算法及其在系統(tǒng)辨識(shí)中的應(yīng)用［J］.中國電機(jī)工程學(xué)報(bào)，2011，31（20）：114-120.

［14］張航，劉梓溪.基于量子行為粒子群優(yōu)化算法的微型飛行器三維路徑規(guī)劃［J］.中南大學(xué)學(xué)報(bào)（自然科學(xué)版）. 2013，44（2），58-62.

［15］關(guān)澤群，周敏璐，王建梅.一種改進(jìn)的隱含相似性光學(xué)和SAR圖像配準(zhǔn)算法［J］.同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，41（4）：600-606.

［16］張磊.巡航導(dǎo)彈航路規(guī)劃與跟蹤關(guān)鍵技術(shù)研究［D］.西安：空軍工程大學(xué)，2014.

［17］傅陽光.粒子群優(yōu)化算法的改進(jìn)及其在航跡規(guī)劃中的應(yīng)用研究［D］.武漢：華中科技大學(xué)，2011.

［18］楊懿，武昌，劉涵.改進(jìn)粒子群算法在導(dǎo)彈火力分配中的應(yīng)用［J］.火力與指揮控制，2007，32（1）：60-63.

［19］解春明，李德勝.地地導(dǎo)彈突擊目標(biāo)火力分配模型分析［J］.軍事運(yùn)籌與系統(tǒng)工程，2004，18（1）：29-32.

［20］馮杰.遺傳算法及其在導(dǎo)彈火力分配上的應(yīng)用［J］.火力與指揮控制，2007，29（2）：43-45.

Research on an Improved Quantum Particle Swarm Optimization Algorithm

PENG Guang，F(xiàn)ANG Yang-wang，ZHANG Lei，DIAO Xing-hua，XU Yang
（School of Aeronautics and Astronautics Engineering，Air Force Engineering University，Xi'an 710038，China）

Quantum particle swarm optimization algorithm is a new algorithm based on the combination of quantum algorithm and particle swarm optimization algorithm.In this paper，an improved quantum particle swarm optimization algorithm is proposed：first，using the phase angle to encode quantum chromosome；second，the dynamic quantum rotation gate is introduced to particle swarm optimization；third，the adaptive mutation is applied.Furthermore，the performance of the algorithm is tested by Penalized function and Ackley function.Finally，the weapon target assignment model is solved by the improved quantum particle swarm optimization algorithm to obtain the optimal assignment.The simulative results show that the proposed algorithm has the characteristics of rapider convergence，powerful global search capability and better stability.

quantum particle swarm optimization algorithm，real-coded，dynamic quantum rotation gate，adaptivemutation，weapontargetassignment

E911

A

1002-0640（2016）07-0092-05

2015-06-09

2015-07-10
*

中國博士后科學(xué)基金資助項(xiàng)目（2014M562630）

彭廣（1992-），男，湖北廣水人，碩士。研究方向：智能計(jì)算，空天武器系統(tǒng)仿真。