整數(shù)規(guī)劃的量子行為蝙蝠算法

李枝勇,馬 良,張惠珍

(上海理工大學(xué)管理學(xué)院,上海 200093)

1 引言

整數(shù)規(guī)劃問(wèn)題是運(yùn)籌學(xué)中的一門(mén)重要內(nèi)容,在工業(yè)、商業(yè)、運(yùn)輸、經(jīng)濟(jì)管理和軍事等諸多領(lǐng)域中都有廣泛的應(yīng)用,如決策變量為人數(shù)、機(jī)器臺(tái)數(shù)、商店個(gè)數(shù)等,要求其取值為整數(shù)[1]。對(duì)于規(guī)模較小的整數(shù)規(guī)劃問(wèn)題,常用的精確求解方法有分支界定法和割平面法,但隨著問(wèn)題規(guī)模的增大,精確算法變得不可取。為此,多年來(lái)人們?cè)O(shè)計(jì)了各種啟發(fā)式算法來(lái)應(yīng)對(duì)實(shí)際工作的需求。如蜂群算法[2]、粒子群算法[3]、量子行為粒子群算法[4]和蟻群算法[5]等。

蝙蝠算法BA(Bat Algorithm)是Yang Xin-she[6]受啟發(fā)于微型蝙蝠的回聲定位行為方式與優(yōu)化目標(biāo)功能的相關(guān)聯(lián)性,于2010年提出的一種新型啟發(fā)式算法。自該算法提出以來(lái),已有學(xué)者將該算法應(yīng)用于優(yōu)化問(wèn)題[7～9],他們的研究成果表明:相比于粒子群算法、遺傳算法和和聲算法,蝙蝠算法具有發(fā)揮更大作用的潛能。但是,通過(guò)大量的實(shí)驗(yàn)測(cè)試,發(fā)現(xiàn)傳統(tǒng)的蝙蝠算法的聚集性限制了蝙蝠的搜索范圍,因此它不允許蝙蝠出現(xiàn)在遠(yuǎn)離蝙蝠種群的位置,即使這個(gè)位置可能會(huì)好于當(dāng)前最好位置。

具有量子系統(tǒng)的QBA可以克服傳統(tǒng)蝙蝠算法的不足,這是由于:

(1)量子系統(tǒng)是態(tài)疊加原理作用的一個(gè)復(fù)雜的非線性系統(tǒng),所以一個(gè)量子系統(tǒng)比一個(gè)線性系統(tǒng)能描述的狀態(tài)更多。

(2)量子系統(tǒng)與經(jīng)典隨機(jī)系統(tǒng)不同,是一個(gè)不確定系統(tǒng)，即在測(cè)量之前沒(méi)有既定的軌道。

(3)概率密度函數(shù)描述的束縛狀態(tài)的蝙蝠可以以一定概率出現(xiàn)在整個(gè)可行搜索空間的任何區(qū)間。

本文在蝙蝠算法中引入量子理論,提出了基于勢(shì)阱的具有量子行為的蝙蝠算法。實(shí)驗(yàn)結(jié)果表明,量子行為蝙蝠算法QBA(Quantum-behaved Bat Algorithm)性能優(yōu)越,具有較好的收斂性。

2 蝙蝠算法

蝙蝠是一種神奇的動(dòng)物,它靠一種聲納(也稱回聲定位器)來(lái)探測(cè)獵物,避免障礙物,在黑暗中找到他們的棲息地，其探測(cè)獵物和避免障礙的原理都是基于回聲定位的聲學(xué)原理。雖然蝙蝠發(fā)射出的脈沖的持續(xù)時(shí)間很短,但是蝙蝠發(fā)出的脈沖的頻率通常為25 kHz 到150 kHz,波長(zhǎng)λ的范圍在2 mm到14 mm,波長(zhǎng)類同于蝙蝠搜尋獵物的大小。蝙蝠發(fā)出的聲波的響度能達(dá)到110 dB,且響度可以從搜索獵物時(shí)的最高變化到靠近獵物時(shí)的最小。

2.1 蝙蝠的速度更新和位置更新

Fi=Fmin+(Fmax-Fmin)ε

(1)

(2)

(3)

其中,Fi、Fmax、Fmin分別表示第i只蝙蝠在當(dāng)前時(shí)刻發(fā)出的聲波的頻率、聲波頻率的最大值和最小值；ε∈[0,1]是隨機(jī)產(chǎn)生的數(shù)；x*表示當(dāng)前全局最優(yōu)解。

一旦從現(xiàn)有最優(yōu)解集中選擇一個(gè)解(蝙蝠),該蝙蝠所處的新位置可通過(guò)公式(4)產(chǎn)生:

xnew(i)=xold+AVt

(4)

其中,xold表示從當(dāng)前最優(yōu)解集中隨機(jī)選擇的一個(gè)解,AVt表示當(dāng)前蝙蝠種群響度的平均值,為每個(gè)分量屬于[-1,1]的d維隨機(jī)向量。

2.2 響度和脈沖速率

脈沖的響度A(i)和發(fā)射速率R(i)要隨著迭代過(guò)程的進(jìn)行來(lái)更新。通常,在接近獵物的過(guò)程中,響度會(huì)逐漸降低,脈沖發(fā)射的速率會(huì)逐漸提高。更新方程如式(5)和式(6):

At+1(i)=θAt(i)

(5)

Rt+1(i)=R0(i)×[1-exp(-?t)]

(6)

其中,0<θ<1,?>0,均為常量。不難發(fā)現(xiàn)，當(dāng)t→∞時(shí)，At(i)→0,Rt(i)→R0(i)。

相比于現(xiàn)存的其他元啟發(fā)式算法,蝙蝠算法具有以下兩個(gè)優(yōu)勢(shì):頻率調(diào)諧;條件滿足時(shí)會(huì)自動(dòng)從全局搜索轉(zhuǎn)換到局部搜索上來(lái),從而實(shí)現(xiàn)了動(dòng)態(tài)控制全局搜索和局部搜索的相互轉(zhuǎn)換。

3 量子行為蝙蝠算法

QBA是一種具有量子行為的蝙蝠算法。QBA中的每只蝙蝠都是量子中的一個(gè)粒子。量子空間中,依據(jù)粒子的勢(shì)場(chǎng),通過(guò)概率密度函數(shù)|Ψ(X)|2來(lái)獲得粒子在某一點(diǎn)出現(xiàn)的概率。為使粒子不發(fā)散,能夠匯聚到它們的局部點(diǎn)P,在點(diǎn)P(p2,p2,…,pd)使用可變的勢(shì)阱,從而使粒子具有聚集態(tài)[10]。

簡(jiǎn)單地說(shuō),首先考慮粒子在一維空間時(shí)的情形。在一維空間中,點(diǎn)作為勢(shì)的中點(diǎn),粒子的勢(shì)能δ勢(shì)阱可表示為:

V(X)=-γδ(X-P)

(7)

因此,根據(jù)一維定態(tài)Schr?dinger方程獲得歸一化的波函數(shù):

(8)

概率密度函數(shù):

(9)

分布函數(shù):

(10)

參數(shù)L是δ勢(shì)阱的特征長(zhǎng)度,是進(jìn)化方程中最重要的參量。使用蒙特卡羅方法,可以得到粒子的位置:

(11)

參數(shù)L由下面的方程求得:

L(t)=2α|P-X(t)|

(12)

從而,粒子的迭代方程可由下式表示:

(13)

用平均最優(yōu)位置mbest表示所有粒子當(dāng)前的平均最優(yōu)解,如下式所示:

(14)

其中，N表示蝙蝠的個(gè)數(shù);Pi是蝙蝠i所經(jīng)歷的位置;L的值由下式給出:

L(t)=2α|mbest-X(t)|

(15)

α稱為收縮-擴(kuò)張系數(shù)。從而蝙蝠位置的迭代方程可以寫(xiě)為:

(16)

為了保證算法的收斂性,每個(gè)粒子必須收斂于各自的局部點(diǎn)P點(diǎn),它是每個(gè)粒子唯一的局部吸引子,可表示為:

(17)

需要指出的是:應(yīng)用到下文所提的量子蝙蝠算法,當(dāng)進(jìn)行局部搜索時(shí),

(18)

P=Pbest

(19)

綜上所述,方程(16)～(19)即為QBA的量子搜索優(yōu)化的核心迭代方程。綜合基本蝙蝠算法的步驟,則QBA步驟如下:

步驟1初始化蝙蝠種群大小為n,初始種群中第i只蝙蝠位置為x(i,:),脈沖發(fā)射速率為R(i),脈沖響度為A(i),脈沖頻率為F(i),計(jì)算個(gè)體適應(yīng)值fitness(i,:)=f(x(i)),i=1,2,…,n。

步驟2判斷是否滿足算法結(jié)束條件,如果滿足,則轉(zhuǎn)步驟8,否則轉(zhuǎn)步驟3。

步驟3利用式(16)和式(17)產(chǎn)生xnew。

步驟4產(chǎn)生一個(gè)[0 1]的隨機(jī)數(shù)rand,如果rand>R(i),則從當(dāng)前最優(yōu)解集中隨機(jī)選擇一個(gè)解xold,并利用式(18)和式(19)得到xnew。

步驟5計(jì)算fnew=f(xnew)。

步驟6產(chǎn)生一個(gè)[0 1]的隨機(jī)數(shù)rand,如果rand<(A(i)+0.93)且fnew

步驟7更新當(dāng)前最優(yōu)解x*,轉(zhuǎn)步驟2。

步驟8算法結(jié)束,輸出、分析和處理實(shí)驗(yàn)數(shù)據(jù)。

4 仿真實(shí)驗(yàn)

利用表1中的七個(gè)整數(shù)規(guī)劃問(wèn)題的測(cè)試函數(shù)來(lái)檢驗(yàn)QBA算法的性能。

Table1 Test functions表1 測(cè)試函數(shù)

本文選取文獻(xiàn)[4]中的粒子群(PSO)算法和量子行為粒子群(QPSO)算法與QBA算法進(jìn)行比較。其中PSO算法和QPSO算法針對(duì)上述函數(shù)的實(shí)驗(yàn)結(jié)果,直接引用其最好的實(shí)驗(yàn)結(jié)果。

Table 2 Some parameters of test functions表2 測(cè)試函數(shù)的部分參數(shù)

算法初始化參數(shù)如下:初始群體均勻分布在d維空間中，每個(gè)個(gè)體在每一維的取值區(qū)間為[-100,100]。每個(gè)測(cè)試函數(shù)將用QBA算法各獨(dú)立求解50次,記錄每次的求解結(jié)果和達(dá)到最優(yōu)解需要的迭代次數(shù),在迭代過(guò)程中,保留算法尋優(yōu)過(guò)程產(chǎn)生的一切值；另外，單獨(dú)對(duì)實(shí)數(shù)領(lǐng)域的蝙蝠位置進(jìn)行取整并求整數(shù)空間領(lǐng)域的函數(shù)值,同時(shí)進(jìn)行相應(yīng)的整數(shù)最優(yōu)解和函數(shù)最優(yōu)值的更新操作。算法的收縮-擴(kuò)張系數(shù)也在三個(gè)不同區(qū)間[1.4,0.4]、[1.4,0.6]、[1.4,0.8]內(nèi)隨迭代次數(shù)的增加而線性減少。測(cè)試函數(shù)的維數(shù)、對(duì)應(yīng)的群體規(guī)模和最大迭代次數(shù)設(shè)置情況完全與文獻(xiàn)[4]中一致,詳見(jiàn)表2。另外,Qmax=0.05,Qmin=0,θ=0.9,?=0.9初始響度均為7,初始發(fā)射速率均為0.5,初始頻率均為0。

算法的運(yùn)行環(huán)境為Win7系統(tǒng)下的MATLAB7.8(R2009a),實(shí)驗(yàn)結(jié)果見(jiàn)表3,比較結(jié)果見(jiàn)表4。

Table 3 Results of solving test functions with QBA表3 QBA算法求解測(cè)試函數(shù)的結(jié)果

由表3可看出:QBA對(duì)不同區(qū)間的收縮-擴(kuò)張系數(shù)均能以100%的成功率找到每個(gè)函數(shù)的最優(yōu)解,而文獻(xiàn)[4]中的PSO和QPSO卻無(wú)法保證,PSO的慣性系數(shù)w和QPSO的收縮-擴(kuò)張系數(shù)α需要在合適的區(qū)間才能保證,PSO中慣性系數(shù)的區(qū)間為[1.0,0.4],QPSO中收縮-擴(kuò)張系數(shù)的區(qū)間為[1.2,0.4],這說(shuō)明QBA對(duì)收縮-擴(kuò)張系數(shù)的區(qū)間的設(shè)置的敏感度更小,故而比PSO和QPSO具有更好的性能。

由表4可看出，QBA相比較于PSO和QPSO的另外一個(gè)性能優(yōu)勢(shì)在于QBA能夠以更快的速度收斂到最優(yōu)解。

Table 4 Comparison of the results with PSO、QPSO and QBA表4 PSO、QPSO和QBA求解結(jié)果比較

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

本文所提出的基于Delta勢(shì)阱的具有量子行為的蝙蝠算法,雖然比粒子群算法和量子行為粒子群算法具有更好的性能,但在實(shí)驗(yàn)的過(guò)程中發(fā)現(xiàn),該算法對(duì)控制全局搜索和局部搜索動(dòng)態(tài)轉(zhuǎn)換進(jìn)程的脈沖響度和脈沖發(fā)射速率的初始設(shè)置具有較強(qiáng)的敏感度,至于其原因,是接下來(lái)要研究的課題。

[1] Ma Liang, Zhu Gang, Ning Ai-bing. Ant optimization algorithm[M].Beijing:Science Press, 2008.(in Chinese)

[2] Liu Yong, Ma Liang. Bee colony foraging algorithm for integer programming[C]∥Proc of IEEE Business Management and Electronic Information (BMEI), 2011:199-201.

[3] Omran M G H, Engelbrecht A, Salman A. Barebones particle swarm for integer programming problems[C]∥Proc of IEEE Swarm Intelligence Symposium, 2007:170-175.

[4] Sun Jun, Fang Wei, Wu Xiao-jun, et al. Quantum-behaved particle swarm optimization:Theory and application[M]. Beijing:Tsinghua University Press, 2011.(in Chinese)

[5] Gao Shang,Yang Jing-yu.Ant colony optimization algorithm for nonlinear integer programming[J]. Journal of Nanjing University of Science and Technology, 2005, 29(suppl):120-123.(in Chinese)

[6] Yang X S. A new metaheuristic bat-inspired algorithm[C]∥Proc of Nature Inspired Cooperative Strategies for Optimization(NICSO 2010), 2010:65-74.

[7] Yang X S. Bat algorithm for multi-objective optimization[J]. International Journal of Bio-Inspired Computation, 2011, 3(5):267-274.

[8] Yang X S, Gandomi A H. Bat algorithm:A novel approach for global engineering optimization[J]. Engineering Computation, 2012, 29(5):267-289.

[9] Gandomi A H, Yang X S, Alavi A H, et al. Bat algorithm for constrained optimization tasks [J]. Neural Computing &Applications,2013,22(6):1239-1255.

[10] Sun Jun, Feng Bin, Xu Wen-bo. Particle swarm optimization with particles having quantum behavior [C]∥ Proc of 2004 Congress on Evolutionary Computation, 2004:325-331.

附中文參考文獻(xiàn):

[1] 馬良,朱剛,寧愛(ài)兵.蟻群優(yōu)化算法[M].北京:科學(xué)出版社,2008.

[4] 孫俊,方偉,吳小俊,等.量子行為粒子群優(yōu)化:原理及其應(yīng)用[M].北京:清華大學(xué)出版社,2011.

[5] 高尚,楊靜宇.非線性整數(shù)規(guī)劃的蟻群算法[J].南京理工大學(xué)學(xué)報(bào), 2005, 29(增刊):120-123.