整數規劃的量子行為蝙蝠算法

李枝勇,馬 良,張惠珍

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

1 引言

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

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

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

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

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

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

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

2 蝙蝠算法

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

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

Fi=Fmin+(Fmax-Fmin)ε

(1)

(2)

(3)

其中,Fi、Fmax、Fmin分別表示第i只蝙蝠在當前時刻發出的聲波的頻率、聲波頻率的最大值和最小值；ε∈[0,1]是隨機產生的數；x*表示當前全局最優解。

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

xnew(i)=xold+AVt

(4)

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

2.2 響度和脈沖速率

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

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

(5)

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

(6)

其中,0<θ<1,?>0,均為常量。不難發現，當t→∞時，At(i)→0,Rt(i)→R0(i)。

相比于現存的其他元啟發式算法,蝙蝠算法具有以下兩個優勢:頻率調諧;條件滿足時會自動從全局搜索轉換到局部搜索上來,從而實現了動態控制全局搜索和局部搜索的相互轉換。

3 量子行為蝙蝠算法

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

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

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

(7)

因此,根據一維定態Schr?dinger方程獲得歸一化的波函數:

(8)

概率密度函數:

(9)

分布函數:

(10)

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

(11)

參數L由下面的方程求得:

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

(12)

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

(13)

用平均最優位置mbest表示所有粒子當前的平均最優解,如下式所示:

(14)

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

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

(15)

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

(16)

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

(17)

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

(18)

P=Pbest

(19)

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

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

步驟2判斷是否滿足算法結束條件,如果滿足,則轉步驟8,否則轉步驟3。

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

步驟4產生一個[0 1]的隨機數rand,如果rand>R(i),則從當前最優解集中隨機選擇一個解xold,并利用式(18)和式(19)得到xnew。

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

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

步驟7更新當前最優解x*,轉步驟2。

步驟8算法結束,輸出、分析和處理實驗數據。

4 仿真實驗

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

Table1 Test functions表1 測試函數

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

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

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

算法的運行環境為Win7系統下的MATLAB7.8(R2009a),實驗結果見表3,比較結果見表4。

Table 3 Results of solving test functions with QBA表3 QBA算法求解測試函數的結果

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

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

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

5 結束語

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

[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] 馬良,朱剛,寧愛兵.蟻群優化算法[M].北京:科學出版社,2008.

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

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