趙鵬軍

(商洛學院 數(shù)學與計算機應用學院， 商洛 726000)

求解約束優(yōu)化問題的改進的礦井爆炸算法

趙鵬軍

(商洛學院 數(shù)學與計算機應用學院， 商洛 726000)

針對礦井爆炸算法在求解約束優(yōu)化問題時存在易陷入局部最優(yōu)的缺點，提出了一種改進的煤礦爆破算法。借鑒粒子群算法的思想對改進的引爆位置進行修正，若臨時解更優(yōu)時，對臨時解進行隨機一維變異。函數(shù)優(yōu)化問題的實驗結(jié)果表明了算法的可行性和有效性。

煤礦爆炸算法； 早熟收斂； 粒子群優(yōu)化算法

0 引言

基于對現(xiàn)實生活中礦井炸彈被引爆過程的研究，Ali Sadollaha等人[1]于2012年提出了一種新的主能算法--礦井爆炸算法(Mine Blast Algorithm , MBA)，目前該算法已成功應用于函數(shù)優(yōu)化、工程設計等方面[1-6]，在求解精確度和算法性能方面也取得了較好的結(jié)果[6]。然而，和其他智能算法一樣，MBA同樣存在早熟收斂現(xiàn)象。為提高算法的性能，本文借鑒粒子群優(yōu)化算法[7]及變異的思想，提出了改進的MBA(記為PMBA)，可在一定程度上避免算法陷入局部最優(yōu)，數(shù)值結(jié)果驗證了改進算法的可行性和有效性。

1 礦井爆炸算法

X0=Lb+r1·(Ub-Lb)

(1)

其中r1∈U(0,1)，Ub和Lb分別是變量的上界和下界，礦井爆炸的當前位置X如式(2)。

X={Xm},m=1,2,…,D

(2)

其中D是搜索空間維數(shù)，考慮當前礦井爆炸產(chǎn)生的Ns個彈片引起另一個礦井被引爆的位置Xn+1如式(3)。

(3)

(4)

(5)

(6)

其中F為X的函數(shù)值，在每個維度上彈片的初始距離如式(7)。

d0=Ub-Lb

(7)

此外，為了在解空間上進行充分的探索，算法在早期迭代中引入探測因子μ，將μ與迭代次數(shù)k進行比較，如果μ>k，則探索過程開始。這時解空間的探索方程可表示為式(8)。

(8)

(9)

其中r3∈N(0,1)，用式(8)修改每個彈片的距離，在早期迭代中，探索過程將促使彈片接近最優(yōu)點，大的μ值可以探索更遠的區(qū)域。因此，μ的值決定了探索的強度。

為了提高算法的全局搜索能力，d0自適應地表示為式(10)。

(10)

其中α是縮減常數(shù)，在迭代后期，彈片的距離將近似等于0。礦井爆炸算法的探索和開采過程，如圖1所示。

圖1 礦井爆破算法探索和開采過程示意圖

同心圓線表示探索過程，散狀線表示開采過程。

算法用式(4)-(6)分別計算爆破礦炸彈的位置、彈片的距離和方向。在開發(fā)過程中彈碎片的距離根據(jù)式(9)自適應減少，引導算法聚焦到全局最優(yōu)解。探索、開發(fā)過程如下：

如果μ>k

探測(方程(8)及((9))

否則

開發(fā)(方程(4)-(6)及(方程(10))

結(jié)束

2 改進的礦井爆炸算法

為提高算法的搜索效率，有效避免過早陷入局部最優(yōu)，受文獻 [7]中“慣性”部分和“社會”部分的啟發(fā)，將式(3)修改為式(11)。

(11)

(12)

這樣有助于避免陷入局部最優(yōu)。因而PMBA在繼承MBA優(yōu)點的同時，在一定程度上擴展了搜索范圍，促使算法朝最優(yōu)解方向移動，為跳出局部最優(yōu)提供了可能，更有可能求得優(yōu)化問題的全局最解。

綜上所述，PMBA的具體實現(xiàn)過程如下：

步驟1：初始化群體及參數(shù)：隨機解，Ns，α，β，μ，最大迭代次數(shù)Nmax。

步驟2：檢查探索條件。

步驟3：如果探索條件滿足，根據(jù)(8)及(9)計算彈片的位置和距離。否則，轉(zhuǎn)到步驟10。

步驟4：根據(jù)(6)計算彈片的方向。

步驟5：生成彈片并用式(11)計算改進位置。

步驟6：檢查彈片的約束。

步驟7：保存最好的彈片作為最好的臨時解。

步驟8：判斷彈片是否有比最好的臨時解更好的解。

步驟9：如果有，交換的彈片的位置和和臨時最優(yōu)解。否則，變異并轉(zhuǎn)到步驟10。

步驟10：用(4)及(5)計算彈片的距離和位置。返回第4步。

步驟11：用式(10)自適應減少彈片塊距離。

步驟12：檢查終止條件。如果滿足，算法停止。否則，返回步驟2。

3 數(shù)值實驗

為驗證PMBA的有效性性能，選取文獻[2]中的3個約束優(yōu)化問題進行仿真實驗，P1和P2是最小值問題，P4是最大值問題，將其轉(zhuǎn)化為最小值問題進行求解，3個約束優(yōu)化問題的具體表達式為式(13)、(14)、(15)。

3.2 約束處理

一方面將等式約束轉(zhuǎn)化為-h(x)-δ≤0，h(x)-δ≤0，是很小的正數(shù)；另一方面利用文獻[8]中提出的違反約束問題的4個規(guī)則：

1) 任何可行解優(yōu)于不可行解；

2) 當不可行解是極少違反約束條件的情況下被看作是可行解；

3) 兩個可行解中，有較好目標函數(shù)值的解更優(yōu)；

4) 兩個不可行解中，違反約束較小的解更優(yōu)。

若問題的最優(yōu)解在可行域的邊界上或靠近可行域的邊界，規(guī)則2)能保證搜索到邊界并且能夠以較大的概率找到最優(yōu)解[8]。這種約束處理技術(shù)在求解約束優(yōu)化問題和工程設計問題方面已被學者們廣泛使用。

3.3 參數(shù)設置

文中對MBA和PMBA分別進行了測試，為了增強可比性，采用文獻[2]中給出的參數(shù)設置，如表1所示。

表1 參數(shù)設置

3.4 實驗結(jié)果

每個測試函數(shù)在下述參數(shù)設置下獨立運行30次以消除隨機因素的影響，數(shù)值實驗結(jié)果包括統(tǒng)計結(jié)果(最差結(jié)果、平均結(jié)果、最優(yōu)結(jié)果、標準差)和最優(yōu)結(jié)果比較。對3個測試函數(shù)的仿真結(jié)果，如表2-5所示。

表2 2種算法對P1的最優(yōu)結(jié)果比較

表3 2種算法對P2的最優(yōu)結(jié)果比較

表4 2種算法對P3的最優(yōu)結(jié)果比較

從表2和5可知，對函數(shù)P1，兩個算法獲得了相似的最差結(jié)果和最好結(jié)果，而PMBA獲得了較好的平均結(jié)果和標準差。

表5 2種算法對4個約束優(yōu)化問題尋優(yōu)統(tǒng)計結(jié)果比較

從表3和5可知，對函數(shù)P2，兩個算法獲得了相似的最好結(jié)果，PMBA獲得了較好的最差結(jié)果、平均結(jié)果和標準差。

從表4和5可知，對函數(shù)P3，兩個算法獲得了相似的最差結(jié)果、平均結(jié)果和最好結(jié)果，PMBA獲得了較好的標準差。

與文獻[2]中提到的一些算法相比，PMBA也獲得了較滿意的結(jié)果。PBMA由于采用了隨機變異以及粒子群優(yōu)化算法的繼承和引導策略，在一定程度上改善了對優(yōu)化問題的尋優(yōu)能力，其收斂精度高，穩(wěn)定性好，提高了算法的搜索效率。

4 總結(jié)

礦井爆炸算法是一種新的智能算法，本文利用粒子群優(yōu)化算法及變異的思想對礦井爆炸算法做了改進，使算法在保證良好收斂性的同時，有效地改善了算法的搜索效率。對約束優(yōu)化問題的仿真結(jié)果表明PMBA提高了算法的搜索性能，能有效避免早熟收斂，而且算法的穩(wěn)定性好。

[1] Sadollah A, Bahreininejad A, Eskandar H, et al. Mine blast algorithm for optimization of truss structures with discrete variables[J]. Computers & Structures, 2012, 102-103(1):49-63.

[2] Sadollah A, Bahreininejad A, Eskandar H, et al. Mine blast algorithm: A new population based algorithm for solving constrained engineering optimization problems[J]. Applied Soft Computing, 2013, 13(5):2592-2612.

[3] Yoo D G. Improved mine blast algorithm for optimal cost design of water distribution systems[J]. Engineering Optimization, 2014, 47(12):1602-1618.

[4] Sadollah A, Eskandar H, Bahreininejad A, et al. Water cycle, mine blast and improved mine blast algorithms for discrete sizing optimization of truss structures[J]. Computers & Structures, 2015, 149(49):1-16.

[5] Elazim S M A, Ali E S. Optimal locations and sizing of capacitors in radial distribution systems using mine blast algorithm[J]. Electrical Engineering, 2016:1-9.

[6] 王形. 云聯(lián)網(wǎng)環(huán)境中服務路由機制的設計與仿真實現(xiàn)[D].沈陽:東北大學,2014.

[7] Shi Y, Eberhart R C. Empirical study of particle swarm optimization[C]∥Proceeding of Congress on Evolutionary Computation. Piscataway , NJ :IEEE Service Center , 1999 .1945-1949.

[8] Efrén Mezura-Montes, Carlos A. Coello Coello. An empirical study about the usefulness of evolution strategies to solve constrained optimization problems[J]. International Journal of General Systems, 2008, 37(4):443-473.

ModifiedMineBlastAlgorithmforSolvingConstrainedOptimizationProblems

Zhao Pengjun

(School of Mathematics and Computer Application, Shangluo University, Shangluo 726000, China)

Mine blast algorithm (MBA) trapped easily into local optima when it is used to solve constrained optimization problems, an improved MBA is proposed. In order to improve the search ability of the algorithm, the proposed algorithm uses the ideas in the particle swarm optimization to modify new detonated position. If temporary solution has a better solution, one dimensional mutation is randomly performed. The proposed algorithm is applied to solve function optimization problems. The result shows the effectiveness and robustness of the PMBA when it compares with other existing optimization algorithms.

Mine blast algorithm; Premature convergence; Particle swarm optimization

1007-757X(2017)12-0033-03

陜西省自然科學基礎研究計劃項目(2014JM1019); 陜西省教育科學規(guī)劃課題(SGH13405);商洛學院服務地方專項(13SKY-FWDF001)。

趙鵬軍 (1979-)，男，副教授，碩士，研究方向：智能計算。

TP301.6

A

2017.04.08)