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

李枝勇,馬 良,張惠珍

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

1 引言

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

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

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

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

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

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

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

2 蝙蝠算法

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

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

Fi=Fmin+(Fmax-Fmin)ε

(1)

(2)

(3)

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

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

xnew(i)=xold+AVt

(4)

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

2.2 響度和脈沖速率

脈沖的響度A(i)和發(fā)射速率R(i)要隨著迭代過程的進行來更新。通常,在接近獵物的過程中,響度會逐漸降低,脈沖發(fā)射的速率會逐漸提高。更新方程如式(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→∞時，At(i)→0,Rt(i)→R0(i)。

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

3 量子行為蝙蝠算法

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

簡單地說,首先考慮粒子在一維空間時的情形。在一維空間中,點作為勢的中點,粒子的勢能δ勢阱可表示為:

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

(7)

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

(8)

概率密度函數(shù):

(9)

分布函數(shù):

(10)

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

(11)

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

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

(12)

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

(13)

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

(14)

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

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

(15)

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

(16)

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

(17)

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

(18)

P=Pbest

(19)

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

步驟1初始化蝙蝠種群大小為n,初始種群中第i只蝙蝠位置為x(i,:),脈沖發(fā)射速率為R(i),脈沖響度為A(i),脈沖頻率為F(i),計算個體適應(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)生一個[0 1]的隨機數(shù)rand,如果rand>R(i),則從當(dāng)前最優(yōu)解集中隨機選擇一個解xold,并利用式(18)和式(19)得到xnew。

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

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

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

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

4 仿真實驗

利用表1中的七個整數(shù)規(guī)劃問題的測試函數(shù)來檢驗QBA算法的性能。

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

[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.

附中文參考文獻:

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

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

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