連續(xù)函數(shù)尋優(yōu)的改進(jìn)量子擴(kuò)展蟻群算法

李士勇，柏繼云，2

(1.哈爾濱工業(yè)大學(xué)控制科學(xué)與工程系，黑龍江 哈爾濱 150001;2.東北農(nóng)業(yè)大學(xué) 理學(xué)院，黑龍江 哈爾濱 150030)

蟻群算法(ant colony algorithm)是一種模擬螞蟻覓食行為的仿生優(yōu)化算法，該算法具有信息正反饋、分布式計(jì)算、易于與其他算法結(jié)合等優(yōu)點(diǎn)［1］，目前已成功應(yīng)用于離散空間優(yōu)化領(lǐng)域.但對(duì)于處理連續(xù)空間的優(yōu)化問(wèn)題，通常需要將問(wèn)題進(jìn)行離散化處理，求解精度不高，同時(shí)對(duì)于高維優(yōu)化問(wèn)題的求解存在很大困難［2］.

2008年，蟻群算法創(chuàng)始人Dorigo等提出了用于求解連續(xù)空間優(yōu)化問(wèn)題的最新蟻群優(yōu)化算法，該算法通過(guò)引入解存儲(chǔ)器作為信息素模型，并將基本蟻群算法的離散概率選擇方式連續(xù)化，從而將其擴(kuò)展到連續(xù)空間優(yōu)化問(wèn)題上，因而稱(chēng)之為擴(kuò)展蟻群算法(extension of ant colony optimization，ACOR)［3］.ACOR仍然按照ACO算法框架來(lái)設(shè)計(jì)，簡(jiǎn)單易行.Dorigo等將其應(yīng)用于經(jīng)典的連續(xù)函數(shù)求解并與現(xiàn)有的算法對(duì)比獲得了更高的精度.但是，ACOR由于其仍然采用隨機(jī)方式產(chǎn)生初始解，僅通過(guò)一次搜索中解存儲(chǔ)器中解的目標(biāo)函數(shù)值的大小來(lái)構(gòu)建信息素，解的方向不夠明確，收斂速度緩慢，且容易陷入局部最優(yōu).

量子優(yōu)化算法由于采用量子比特作為信息的最基本載體，比經(jīng)典比特的表示包含更多的信息.同時(shí)，量子比特狀態(tài)的的疊加性和相干性，以及量子比特之間的糾纏性，使量子算法具有量子并行計(jì)算的潛力［4-8］.因此，本文針對(duì)ACOR算法的不足提出量子擴(kuò)展蟻群算法(extended quantum ant colony algorithm，QACOR)，引入量子比特編碼螞蟻位置，在螞蟻數(shù)目不變的條件下，可以使搜索空間加倍;引入量子旋轉(zhuǎn)門(mén)和高斯核概率密度函數(shù)結(jié)合更新螞蟻攜帶的量子比特，利于在連續(xù)空間尋優(yōu);采用量子非門(mén)實(shí)現(xiàn)螞蟻位置的變異，增加解的多樣性;同時(shí)，根據(jù)ACOR解存儲(chǔ)器中解的重要性改進(jìn)每個(gè)解的權(quán)值以增加解的方向性，快速獲得最優(yōu)解.

1 擴(kuò)展蟻群算法

1.1 高斯核概率密度函數(shù)

基本蟻群算法(ACO)工作機(jī)制的核心為基于信息素的概率選擇規(guī)則來(lái)逐步地構(gòu)造可行解.ACOR與ACO最大的不同就是使用了連續(xù)概率分布而不是離散概率分布，也就是說(shuō)，ACOR的概率選擇規(guī)則為連續(xù)概率密度函數(shù)(probability density function，PDF)，如圖1所示.因此，在ACOR中，螞蟻是通過(guò)采樣PDF方式來(lái)選擇解成份.

圖1 連續(xù)概率密度函數(shù)Fig.1 Continuous probability density function

通常用高斯函數(shù)描述連續(xù)概率密度函數(shù)，它有采樣方便等優(yōu)點(diǎn).由于高斯函數(shù)僅有一個(gè)最大值，難以描述2個(gè)分離但可能包含潛在最優(yōu)解的區(qū)間情況.為此，使用高斯函數(shù)的線性組合—高斯核概率密度函數(shù)來(lái)描述，其形狀如圖2所示.

高斯核Gi(x)包含3個(gè)參數(shù)向量:ω是單個(gè)高斯函數(shù)權(quán)向量，μi是均值向量，σi是標(biāo)準(zhǔn)偏差向量.所有這些向量的維數(shù)等于組成高斯核的高斯函數(shù)個(gè)數(shù).

圖2 高斯概率密度函數(shù)分布以及高斯核函數(shù)表示Fig.2 Exam p le of four Gaussian functions and their Gaussian kernel functions

1.2 解存儲(chǔ)器

當(dāng)基本蟻群算法用于連續(xù)優(yōu)化時(shí)，每個(gè)螞蟻?zhàn)鞒龅倪x擇不再局限于有限集內(nèi)(如圖1所示).對(duì)于一個(gè)n維問(wèn)題的每個(gè)解向量Sl、目標(biāo)函數(shù)值f(Sl)和權(quán)值存放在一個(gè)解存儲(chǔ)器T中.因此，第l個(gè)解的第i個(gè)變量表示為，其解存儲(chǔ)器 T的結(jié)構(gòu)如圖3所示.

圖3 ACOR的解存儲(chǔ)器結(jié)構(gòu)Fig.3 The archive of solutions kept by ACOR

圖3中的可行解是根據(jù)它們函數(shù)值(或適應(yīng)度值)f(Sl)的大小排序的.例如，求極小值問(wèn)題時(shí)按f(S1)≤f(S2)≤…≤f(SK)來(lái)排序.每一個(gè)函數(shù)值都有一個(gè)相應(yīng)的權(quán)值ω，權(quán)值的排序?yàn)棣?≥ω2≥…≥ωK.構(gòu)造概率密度函數(shù)Gi僅需要所有k(k=K)個(gè)解的第i維坐標(biāo)，由該k個(gè)獨(dú)立的高斯函數(shù)組成高斯核函數(shù).對(duì)于每一個(gè)Gi，解存儲(chǔ)器中第i維變量所有解的值變成了向量μi的元素:μi=，…，}={，…，}.計(jì)算解向量Sl的權(quán)值ωl采用如下式:

式中:qk為標(biāo)準(zhǔn)偏差，q是本算法的一個(gè)參數(shù).

1.3 ACOR算法流程

ACOR算法主要包括初始化解存儲(chǔ)器、通過(guò)高斯核概率密度函數(shù)構(gòu)造可行解及信息素更新3個(gè)步驟:

1)解存儲(chǔ)器初始化.

設(shè)蟻群有m只螞蟻，解存儲(chǔ)器T的長(zhǎng)度為K，連續(xù)優(yōu)化問(wèn)題變量為n維，將解存儲(chǔ)器T隨機(jī)初始化為K維解向量，且每個(gè)解向量的長(zhǎng)度為n.由該K個(gè)解向量可計(jì)算出其對(duì)應(yīng)的目標(biāo)函數(shù)值，并根據(jù)式(2)計(jì)算出每個(gè)解向量的權(quán)值.

2)對(duì)高斯核概率密度函數(shù)采樣構(gòu)建可行解

采樣過(guò)程分兩步來(lái)實(shí)現(xiàn):

①選擇組成高斯核函數(shù)中的一個(gè)高斯函數(shù)，其選擇概率的計(jì)算公式為:

參數(shù)ξ對(duì)所有維變量均相同且ξ＞0.

3)信息素更新

將上面m只螞蟻采樣得到的m個(gè)解向量與原來(lái)解存儲(chǔ)器T中的解一起組成一個(gè)臨時(shí)解向量，并將這個(gè)臨時(shí)解向量按目標(biāo)函數(shù)排序，取前K個(gè)解向量加入解存儲(chǔ)器T里，以保持其長(zhǎng)度K不變.這就確保了只有最優(yōu)解能夠存儲(chǔ)在解存儲(chǔ)器里，于是在解存儲(chǔ)器里的解便能更好地引導(dǎo)螞蟻的搜索.

2 改進(jìn)量子擴(kuò)展蟻群算法

在連續(xù)空間尋優(yōu)，其可行解表現(xiàn)出稠密性，ACOR對(duì)初始解采用隨機(jī)確定的方式，信息累積的速度較慢，同時(shí)解的尋優(yōu)僅由一次搜索中解存儲(chǔ)器中目標(biāo)函數(shù)值的大小來(lái)構(gòu)建信息素，解的尋優(yōu)方向不明確，為此本文作如下改進(jìn).

2.1 螞蟻位置的雙鏈編碼和解空間變換

在QACOR算法中，直接利用概率幅對(duì)螞蟻位置進(jìn)行編碼，設(shè)蟻群中共有m只螞蟻，隨機(jī)分布在維單位空間=［－1 1］n中，則每只螞蟻的編碼為

其中，相位 tii=2π ×rand，rand是(0，1)之間的隨機(jī)數(shù).在QACOR中，把量子比特的2個(gè)概率幅都視為代表螞蟻當(dāng)前位置的信息，因此，每只螞蟻占據(jù)Ω中2個(gè)位置.這樣在蟻群規(guī)模不變時(shí)，可使搜索到的空間加倍，從而加快了收斂速度.

種群中每只螞蟻包含2n個(gè)量子比特的概率幅，利用線性變換，可將這2n個(gè)概率幅由n維單位空間映射到優(yōu)化問(wèn)題的解空間Ω.變換公式為

其中:aj≤Xj≤bj(j=1，2，…，n)，是優(yōu)化問(wèn)題解空間Ω.因此，每只螞蟻可以確定優(yōu)化問(wèn)題的2個(gè)解.

2.2 解存儲(chǔ)器的構(gòu)建和更新

在ACOR中，構(gòu)建和更新解存儲(chǔ)器只按目標(biāo)函數(shù)值的大小來(lái)取舍.每個(gè)解的權(quán)重僅由式(2)來(lái)確定，因此解的選擇概率僅與解的目標(biāo)函數(shù)值優(yōu)劣有關(guān)，沒(méi)有考慮當(dāng)前解在尋找最優(yōu)值時(shí)的貢獻(xiàn)程度.

本文引入解的變化率來(lái)反映當(dāng)前解在尋找最優(yōu)解的貢獻(xiàn)程度.令，解存儲(chǔ)器中解的權(quán)重計(jì)算如下:

比如海鮮，雖然菲律賓海島眾多，但出乎意料的是他們的海鮮生產(chǎn)鏈卻并不發(fā)達(dá)。例如他們習(xí)慣用剛撈上來(lái)的面包蟹做一罐香濃的蟹黃醬，或者直接用香茅加椰漿煮一鍋美味的淡青口——但這僅停留在最簡(jiǎn)單的海鮮做法之上。因?yàn)椋ｕr對(duì)于他們來(lái)講實(shí)際是一種吃不起的食物，急于果腹之余又不得不將捕撈上來(lái)的海鮮售賣(mài)給酒店，所以這導(dǎo)致他們很少去研究海鮮的更多做法。

式中:ωl由式(1)計(jì)算，▽fj()為評(píng)價(jià)函數(shù)f(x)在點(diǎn)處的梯度;▽flmax是評(píng)價(jià)函數(shù)f(x)對(duì)第j個(gè)變量的梯度的最大值.如果求目標(biāo)函數(shù)的最小值，當(dāng)▽flj是負(fù)值，說(shuō)明目標(biāo)函數(shù)在變優(yōu)，反之目標(biāo)函數(shù)值在變壞，且當(dāng)▽flj絕對(duì)值較小，則解的變化較慢，反之解的變化較快.

由式(7)可知，第1部分相當(dāng)于對(duì)已使用解的“利用”;第2部分相當(dāng)于對(duì)未使用解的“探索”部分，其大小決定了螞蟻發(fā)現(xiàn)新的較好解的能力.

2.3 螞蟻對(duì)新目標(biāo)的選擇和移動(dòng)

螞蟻k由位置xr利用式(3)、(7)選擇高斯核概率密度函數(shù)進(jìn)行采樣，構(gòu)建可行解xS.

在量子空間中，為使xr逼近xS，通常用量子旋轉(zhuǎn)門(mén)R=實(shí)現(xiàn)，式中轉(zhuǎn)角θ的選取至關(guān)重要.

關(guān)于量子旋轉(zhuǎn)門(mén)轉(zhuǎn)角的確定，很多文獻(xiàn)都給出了各自的方法，其中文獻(xiàn)［9］提出了一種自適應(yīng)調(diào)整轉(zhuǎn)角迭代步長(zhǎng)的方法，在此基礎(chǔ)上文獻(xiàn)［10］引入帶有目標(biāo)函數(shù)的梯度函數(shù)調(diào)整轉(zhuǎn)角，考慮了目標(biāo)函數(shù)的變化趨勢(shì)，當(dāng)函數(shù)在該點(diǎn)的梯度較大時(shí)，說(shuō)明在該點(diǎn)函數(shù)變化的速度快，變化的幅度大，此時(shí)盡量取較小的轉(zhuǎn)角，以防越過(guò)極大值點(diǎn);當(dāng)梯度較小時(shí)，說(shuō)明函數(shù)在該點(diǎn)變化較慢，此時(shí)應(yīng)取較大的轉(zhuǎn)角，大步越過(guò)平坦之處.本文利用類(lèi)似文獻(xiàn)［10］的方案設(shè)計(jì)轉(zhuǎn)角步長(zhǎng)，即令

表示第r個(gè)點(diǎn)第j個(gè)變量的轉(zhuǎn)角步長(zhǎng)，其中△θ0為迭代初值，轉(zhuǎn)角方向與 xr、xS有關(guān).若 xr、xS在第 j個(gè)變量上的概率幅分別為 [ α β]T及 [ α β]T，則

rjrjsjsj根據(jù)文獻(xiàn)［10］可以確定轉(zhuǎn)角步長(zhǎng)方向與矩陣A=的符號(hào)方向一致，若A=0，則轉(zhuǎn)角方向正負(fù)均可.因此，本文轉(zhuǎn)角步長(zhǎng)綜合如下:

2.4 用量子非門(mén)實(shí)現(xiàn)變異

變異的作用主要在于阻止未成熟收斂和提供算法局部搜索能力，本文通過(guò)量子非門(mén)設(shè)計(jì)量子變異操作.具體方法如下:

首先隨機(jī)選擇若干只螞蟻，然后隨機(jī)選擇其攜帶的若干個(gè)量子位，依變異概率對(duì)選中的量子位施加量子非門(mén)變換，使該量子位的2個(gè)概率幅互換.這樣可使螞蟻代表的2個(gè)空間位置同時(shí)得到變異.令[cosφkisinφki]T為螞蟻攜帶的第i個(gè)量子比特，變異操作如下:

變異后的相位正向旋轉(zhuǎn)了π/2－2φki.

2.5 量子擴(kuò)展蟻群算法(QACOR)流程

1)利用式(5)產(chǎn)生初始量子種群Q(t);

2)利用式(6)由Q(t)產(chǎn)生傳統(tǒng)種群P(t);

3)計(jì)算P(t)中每個(gè)個(gè)體的適應(yīng)度，構(gòu)造圖3中的解存儲(chǔ)器;

4)利用式(2)、(7)計(jì)算存儲(chǔ)器中各解的權(quán)重，利用式(3)選擇高斯核概率密度函數(shù)，確定新解;

5)在量子空間中利用量子旋轉(zhuǎn)門(mén)實(shí)現(xiàn)螞蟻移動(dòng);

6)隨機(jī)選擇若干只螞蟻，利用量子非門(mén)實(shí)現(xiàn)變異;

7)t← t+1，轉(zhuǎn)至步驟 2)，繼續(xù)迭代;若t=max(t)，輸出全局最優(yōu)解.

3 QACOR算法求解多維連續(xù)函數(shù)

為了便于比較，本文利用文獻(xiàn)［3］實(shí)例應(yīng)用改進(jìn)量子擴(kuò)展蟻群算法(QACOR)和擴(kuò)展蟻群算法(ACOR)以及標(biāo)準(zhǔn)遺傳算法(SGA)進(jìn)行仿真實(shí)驗(yàn).

3.1 參數(shù)選擇

對(duì)照文獻(xiàn)［3］，QACOR、ACOR算法初始參數(shù)選擇:螞蟻數(shù)目m=70，解存儲(chǔ)器容量K=45，參數(shù)ξ=1，q=0.000 1.QACOR其他參數(shù):轉(zhuǎn)角步長(zhǎng)初值θ0=0.05π，變異概率Pm=0.05.SGA 參數(shù):種群規(guī)模為M=50，交叉概率 pc=0.90 和變異概率pm=0.10－［1∶1∶M］·(0.01)/M.

3.2 二維函數(shù)舉例

Shaffer’s F6 函數(shù):

此函數(shù)有無(wú)限個(gè)局部極大點(diǎn)，其中只有(0，0)為全局最大，最大值為1，如圖4.當(dāng)優(yōu)化結(jié)果為1時(shí)認(rèn)為算法收斂.

分別用QACOR、ACOR、SGA進(jìn)行10次仿真，其中，“BV”、“AV”分別為10次獨(dú)立運(yùn)行結(jié)果中的最好最優(yōu)值、平均最優(yōu)值;“AG”為發(fā)現(xiàn)全局最優(yōu)值的平均代數(shù);“NS”為10次獨(dú)立運(yùn)行中找出全局最優(yōu)值的成功次數(shù).仿真結(jié)果對(duì)比見(jiàn)表1.

圖4 Shaffer’s F6 函數(shù)Fig.4 The Shaffer’s F6 function

表1 極值問(wèn)題優(yōu)化結(jié)果對(duì)比(10次實(shí)驗(yàn))Table 1 The comparison of optimization results on extremum(10 experiments)

圖5 f1(x，y)平均適應(yīng)度曲線Fig.5 The average fitness curves of f1(x，y)

Shaffer’s F6函數(shù)有無(wú)限個(gè)局部極大值點(diǎn)，比較接近于1的極大值約為0.990 284，從表1和圖5可以看出，在10次尋優(yōu)過(guò)程中 QACOR算法僅在0.990 284處做短暫停留，就很快到達(dá)最優(yōu)解1，SGA算法一旦進(jìn)入0.990 284，就很難跳出該局部極大值，ACOR也有2次沒(méi)有跳出該局部極大，但是ACOR算法在跳出該局部極大值后，又停留在0.997附近，達(dá)到1的次數(shù)不是非常理想.

3.3 多維連續(xù)函數(shù)的優(yōu)化

為了更全面地測(cè)試本文改進(jìn)算法的性能，再選用多個(gè)多維測(cè)試函數(shù)［3］進(jìn)行優(yōu)化仿真對(duì)比.

3.3.1 Rosenbrock 函數(shù)

自變量取值范圍1≤xi≤10，當(dāng)xi=1時(shí)取得全局最大值10，當(dāng)函數(shù)值為9.8時(shí)尋優(yōu)成功.

3.3.2 Sinc 函數(shù)

自變量取值范圍1≤xi≤10，當(dāng)xi=5時(shí)取得全局最大值1，當(dāng)函數(shù)值為0.999時(shí)尋優(yōu)成功.

表2 極值問(wèn)題優(yōu)化結(jié)果對(duì)比(10次實(shí)驗(yàn))Tab le 2 The comparison of optimization results on functions extremum(10 experiments)

表2是分別利用3種方法對(duì)2個(gè)函數(shù)的10次優(yōu)化結(jié)果.從表2可以看出，QACOR算法在處理多維函數(shù)的優(yōu)化上明顯優(yōu)于其他2種算法.

4 結(jié)束語(yǔ)

本文結(jié)合了量子計(jì)算和擴(kuò)展蟻群算法的優(yōu)點(diǎn)，提出一種新型的改進(jìn)量子擴(kuò)展蟻群算法(QACOR).該算法使用量子比特的概率幅編碼種群個(gè)體，將個(gè)體中的2條概率幅都看作代優(yōu)化問(wèn)題的近似解，這種基于概率幅的雙鏈編碼方案可以產(chǎn)生豐富的種群，克服了擴(kuò)展蟻群算法中初始解的單一和信息素累計(jì)的緩慢;同時(shí)本文還對(duì)擴(kuò)展蟻群算法中解存儲(chǔ)器中解的權(quán)重進(jìn)行了改進(jìn)，引入了當(dāng)前解的變化率來(lái)反映當(dāng)前解在尋找最優(yōu)解的貢獻(xiàn)度，提高了解的方向性.通過(guò)對(duì)多個(gè)多維連續(xù)函數(shù)尋優(yōu)表明，QACOR算法在收斂速度和收斂精度上均優(yōu)于ACOR、SGA算法.

［1］李士勇.蟻群算法及其應(yīng)用［M］.哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2004:63-121.

［2］李盼池，李士勇.求解連續(xù)空間優(yōu)化問(wèn)題的量子蟻群算法［J］.控制理論與應(yīng)用，2008，25(2):237-241.LI Panchi，LI Shiyong.Quantum ant colony algorithm for continuous space optimization ［J］.Control Theory and Applications，2008，25(2):237-241.

［3］SOCHA K，DORIGO M.Ant colony optimization for continuous domains［J］.European Journal of Operational Research，2008，185(3):1155-1173.

［4］GRIGORENKO I，GARCIA M E.Calculation of the partition function using quantum genetic algorithms［J］.Physica A，2002，313:463-470.

［5］RAMOSR V.Numerical algorithms for use in quantum information［J］.Journal of Computational Physics，2003，192(1):95-104.

［6］YANG JA，LI B，ZHUANG Z Q.Multi-universe parallel quantum genetic algorithm and its application to blindsource separation［C］//Proc of IEEE Int Conf on Neural Networks＆ Signal Processing.New York，USA，2003:393-398.

［7］BENENTIG，CASATIG，STRINIG.Principles of quantum computation and information［M］.Singapore:World Scientific，2004:144-150.

［8］覃朝勇，鄭建國(guó).一種新量子進(jìn)化算法及其在函數(shù)優(yōu)化中的應(yīng)用［J］.系統(tǒng)仿真學(xué)報(bào)，2009，21(10):2862-2871.TAN Chaoyong，ZHENG Jianguo.Novel quantum-inspired evolutionary algorithm and its application to numerical optimization problems［J］.Journal of System Simulation，2009，21(10):2862-2871.

［9］張葛祥，李娜，金煒東，等.一種新量子遺傳算法及其應(yīng)用［J］.電子學(xué)報(bào)，2004，32(3):476-479.ZHANG Gexiang，LINa，JIN Weidong，et al.A novel quantum genetic algorithm and its application［J］.Acta Electronica Sinica，2004，32(3):476-479.

［10］李士勇，李盼池.基于實(shí)數(shù)編碼和目標(biāo)函數(shù)梯度的量子遺傳算法［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2006，38(8):1216-1223.LI Shiyong，LIPanchi.Genetic algorithm based on realencoding and gradient information of object function ［J］.Journal of Harbin Institute of Technology，2006，38(8):1216-1223.