基于歐氏距離的黑洞尋優(yōu)算法*

王　通，劉文芳，劉春芳

(沈陽工業(yè)大學 電氣工程學院，沈陽 110870)

?

基于歐氏距離的黑洞尋優(yōu)算法*

王通，劉文芳，劉春芳

(沈陽工業(yè)大學 電氣工程學院，沈陽 110870)

為了提高黑洞算法的尋優(yōu)精度和算法的全局搜索能力，提出了一種基于歐氏距離的改進黑洞尋優(yōu)算法.通過引入歐氏距離來初始化星體群位置，增強星體群的多樣性，提高其全局搜索能力；設定黑洞半徑最大值，避免由于黑洞面積過大跳過全局最優(yōu)解，當有星體被黑洞吸收時，要求新的星體在距離黑洞一定歐氏距離以外的位置產(chǎn)生，提高星體的搜索區(qū)域；通過對3個基準測試函數(shù)進行尋優(yōu)測試，并與PSO、ABC、DE、BH優(yōu)化算法相比，驗證了基于歐氏距離的黑洞尋優(yōu)算法在尋優(yōu)精度和全局尋優(yōu)能力方面的優(yōu)越性.結(jié)果表明，該算法不僅能夠搜索到參數(shù)的全局最優(yōu)解，而且與其他優(yōu)化算法相比有一定優(yōu)勢.

黑洞算法；全局搜索；歐氏距離；優(yōu)化；多模函數(shù)優(yōu)化；群體智能；測試函數(shù)；改進算法

近年來，群體智能的研究正受到人們的廣泛關注[1-2]，如遺傳算法(GA)[3]、蟻群算法(ACA)[4]、模擬退火算法(SA)[5]、粒子群優(yōu)化算法(PSO)[6]及人工蜂群算法(ABC)[7]等，它們通過模擬或解釋某些自然現(xiàn)象或過程而得以發(fā)展，為解決尋優(yōu)問題提供了新的思路和方法.這些優(yōu)化算法與傳統(tǒng)的算法相比具有能夠從全局范圍去尋找最佳結(jié)果的優(yōu)點，而且參數(shù)在初始化時可以不在真值附近.然而，智能優(yōu)化算法自身具有一定的局限性，文獻[8]指出遺傳算法存在早熟且易陷入局部極值的缺點，同時常規(guī)遺傳算法使用賭輪選擇方法來選擇參與交叉的父體和母體，體現(xiàn)不出個體競爭力，無法實現(xiàn)遺傳算法優(yōu)勝劣汰的原則；文獻[9]指出粒子群算法易陷入局部最優(yōu)解，并對方法進行了改進；文獻[10]指出蟻群算法在實際應用過程中，由于螞蟻爬行缺乏有效信息素的引導，造成大量無效搜索，且蟻群算法在加速收斂過程中易出現(xiàn)停滯；文獻[11]介紹了人工蜂群算法的優(yōu)點，但也指出該算法在理論和實踐上都還不夠成熟，對于求解一些復雜問題，仍存在搜索速度慢、群體多樣性差及易陷入局部最優(yōu)等缺陷.

黑洞(black-hole，BH)算法是Zhang J和Tan Y等人受到黑洞物理現(xiàn)象的啟發(fā)，于2008年在文獻[12]首次提出的一種與粒子群優(yōu)化算法相結(jié)合解決粒子陷入局部極值問題的算法；Hatamlou[13]改善了黑洞算法邊界的確定和吸收星體處理問題，進一步接近黑洞的自然現(xiàn)狀，并將該算法應用于解決數(shù)據(jù)聚類問題；文獻[14]對隨機黑洞粒子群算法方法進行了改進，提高了方法的收斂性能；文獻[15]將隨機黑洞粒子群算法成功應用到環(huán)境經(jīng)濟發(fā)電調(diào)度中；文獻[16]將黑洞算法引入到數(shù)值尋優(yōu)領域中，實現(xiàn)模型參數(shù)的尋優(yōu)，完成大規(guī)模計算，防止早熟和欺騙現(xiàn)象的發(fā)生，并且具有尋優(yōu)精度高、收斂速度快、不容易陷入局部極值的優(yōu)點，但是該算法在尋優(yōu)精度和全局的尋優(yōu)能力方面研究有待進一步提高.

針對上述問題，本文提出一種改進的黑洞優(yōu)化算法.首先，初始星體在搜索空間等歐氏距離產(chǎn)生，使其均勻遍歷在整個搜索空間；其次，設定黑洞半徑的最大值，提高最優(yōu)星體附近尋優(yōu)的概率，新的星體要求與黑洞的歐式距離超過一定的位置產(chǎn)生；最后，將算法與粒子群(PSO)、差分進化(DE)、人工蜂群(ABC)及黑洞(BH)優(yōu)化算法用于3種典型的測試函數(shù)進行尋優(yōu)比較，證明算法的全局搜索能力和尋優(yōu)精度更有優(yōu)勢.

1　黑洞算法

BH算法主要是模擬實際黑洞現(xiàn)象，將有限的搜索空間假想成宇宙系統(tǒng)，在搜索空間內(nèi)隨機產(chǎn)生N個隨機數(shù)充當星體，即

(1)

式中：xi(0)為第i個星體初始位置；xmin、xmax為第i個星體的下限和上限；rand為[0，1]之間的隨機數(shù)；N為星體的個數(shù).

星體的自適應值表示為

(2)

式中：fi(t)為t次尋優(yōu)中第i個星體的目標函數(shù)值；Fi(t)為t次尋優(yōu)中第i個星體自適應值.

BH算法中的黑洞具有與自然界黑洞同樣的強吸引能力，其他所有星體在搜索域內(nèi)不斷向黑洞靠攏且無法逃逸.星體向黑洞靠近的更新公式為

(3)

式中：xi(t+1)、xi(t)為第i個星體在t+1和t次尋優(yōu)中的位置；xBH為黑洞的位置；M為最大尋優(yōu)次數(shù).

利用式(2)計算新產(chǎn)生星體的自適應度值，與黑洞的自適應值比較，當星體的自適應值Fi(t)優(yōu)于黑洞的自適應值FBH時，說明當前的黑洞不是最優(yōu)的，將黑洞和星體互換位置，以新的最優(yōu)適應值對應的星體為中心形成黑洞，其他星體繼續(xù)向新形成的黑洞逼近.

黑洞的邊界計算式為

(4)

當星體的自適應度值進入黑洞邊界以內(nèi)，即被黑洞吸收，將自動在搜索空間內(nèi)隨機產(chǎn)生新的星體，保證星體的數(shù)目不變.

2　改進的黑洞算法

2.1歐氏距離原理

歐氏距離(Euclisean distance)全名歐幾里德距離，也含有普遍意義上距離的含義，表示的是兩點之間存在的真實距離.歐氏距離常被用于度量分類對象之間的接近與相似程度，利用該性質(zhì)將歐氏距離用于星體的初始化過程以及限定新產(chǎn)生星體的位置.

(5)

式中，Xis和Xjs分別為Xi和Xj的第s個分量.兩個星體之間的歐氏距離越小，則兩個星體之間的相似度越大，其包含的冗余信息就越多，其接下來迭代可利用的有效信息就越少，導致算法陷入局部最優(yōu)的概率就增大，算法全局搜索的能力就越弱，因此本文引入歐氏距離的方法作為產(chǎn)生初始星體和更新星體的理論依據(jù)，增強星體的多樣性，提高算法的全局搜索能力.

2.2改進的黑洞算法原理

初始星體群中各星體位置為

(6)

采用式(2)計算初始星體的自適應值，選擇最優(yōu)的自適應值對應的星體作為黑洞.黑洞的半徑根據(jù)式(4)計算，若黑洞的半徑很大，就會增加星體進入黑洞的概率，經(jīng)過一次自適應度函數(shù)的比較，被黑洞吸收的星體停止繼續(xù)向最優(yōu)星體靠近，容易跳過全局最優(yōu)解.因此，有必要將黑洞的半徑設定一個閾值，當黑洞的半徑超過閾值時，將半徑賦值為閾值，否則按照計算的半徑尋優(yōu)，避免由于半徑過大跳過全局最優(yōu)星體.

星體不斷向黑洞靠近最終被吸收后，考慮到星體的個數(shù)和星體的多樣性，重新生成一個星體.因為星體與黑洞的相似度越小越好，要求星體在距離黑洞一定歐氏距離之外產(chǎn)生，從而增強星體與其他星體的差異性.

2.3改進黑洞算法的實現(xiàn)過程

根據(jù)上述的實現(xiàn)原理，具體實現(xiàn)步驟如下：

1) 初始化參數(shù)，包括星體范圍(xmin，xmax)，最大尋優(yōu)次數(shù)M，星體的個數(shù)N，新產(chǎn)生星體距離黑洞的最小距離J，星體的維數(shù)D.

2) 等歐氏距離產(chǎn)生N個初始星體.

3) 計算初始星體的自適應度值，選擇最優(yōu)的自適應度值確定初始黑洞.

4) 更新星體的位置.

5) 比較黑洞與星體的自適應值，若星體的自適應值優(yōu)于黑洞，交換星體和黑洞的位置；否則不更新黑洞.

6) 計算黑洞的半徑，如果一個星體與黑洞表面相交，那么這個星體將被吸收，同時，在搜索空間內(nèi)產(chǎn)生一個與黑洞歐式距離大于J的新星體.

7) 當系統(tǒng)達到最大迭代次數(shù)或者出現(xiàn)一個最優(yōu)尋優(yōu)結(jié)果時，尋優(yōu)結(jié)束，輸出最優(yōu)解；否則返回步驟4).

3　仿真實驗與結(jié)果分析

3.1實驗參數(shù)設置

為了驗證算法的尋優(yōu)能力，選取了3個經(jīng)典基準測試函數(shù)Griewank、Rastrgin、Ackle對尋優(yōu)算法的搜索能力進行測試.以上經(jīng)典測試函數(shù)的共同特點是均為復雜的非線性多峰函數(shù)，在定義域內(nèi)有多個局部最值，極難優(yōu)化，常用來測試算法的探索和開發(fā)能力.表1中給出了3個基準測試函數(shù)的表達式、搜索范圍以及理論全局最小值.

首先設置改進BH的實驗參數(shù)：最大迭代次數(shù)為100，星體數(shù)目為30，星體的維數(shù)為10，實驗次數(shù)為10次，星體的搜索范圍根據(jù)表1中不同的測試函數(shù)來設置，黑洞的最大半徑為0.09，最優(yōu)解精度e為10-20.為了突出算法的優(yōu)越性，將改進BH與PSO、DE、ABC、BH等典型的優(yōu)化算法對比，為便于比較算法的性能，參數(shù)設置同改進BH一致.記錄10次獨立實驗尋優(yōu)結(jié)果的最優(yōu)值(Best)、最差值(Worst)、平均值(Mean)、標準差(Std)以及算法的平均運行時間指標如表2所示.

表1　3個基準測試函數(shù)

表2　基準函數(shù)的優(yōu)化結(jié)果比較

3.2實驗結(jié)果分析

由表2可以看出，在對3個測試函數(shù)尋優(yōu)時，改進的黑洞算法得到的最優(yōu)值最接近理論最優(yōu)值且運行時間最短，在對Rastrgin和Ackle測試函數(shù)尋優(yōu)時，改進的黑洞相對其他優(yōu)化算法各項指標均具有一定的優(yōu)勢.分析原因：星體初始化采用了等歐氏距離的方法生成，避免了隨機生成的星體中存在相似的星體；限定新產(chǎn)生星體的位置，增強了星體的遍歷性.綜合來看，改進的黑洞算法與其他算法相比整體有一定優(yōu)勢.

4　結(jié)　論

針對黑洞算法的特性，結(jié)合歐氏距離提出了一種改進的黑洞算法，該算法利用等歐氏距離初始化星體，避免了初始星體距離近搜索范圍小的缺陷.設定黑洞的半徑，提高在黑洞附近搜索最優(yōu)解的概率，淘汰進入黑洞的星體，生成與黑洞的歐氏距離大于J的新星體，提高算法的全局搜索能力.利用3個經(jīng)典基準測試函數(shù)對改進的黑洞尋優(yōu)算法的尋優(yōu)能力進行測試，實驗結(jié)果表明，該算法在保持黑洞算法優(yōu)點的同時，進一步提高了算法的全局搜索能力和尋優(yōu)精度.

[1]Blum C，Merkle D.Swarm intelligence：introduction and applications [M].Berlin：Springer-Verlag，2008.

[2]Peng F，Tang K，Chen G，et al.Population-based algorithm portfolios for numerical optimization [J].IEEE Transaction on Evolutionary Computation，2010，14(5)：782-800.

[3]李翠平，鄭瑤瑕，張佳，等.基于遺傳算法優(yōu)化的支持向量機品位插值模型 [J].北京科技大學學報，2013，35(7)：837-843.

(LI Cui-ping，ZHENG Yao-xia，ZHANG Jia，et al.Ore grade interpolation model based on support vector machines optimized by genetic algorithms [J].Journal of University of Science and Technology Beijing，2013，35(7)：837-843.)

[4]龍文，梁昔明，龍祖強，等.基于蟻群算法和LSSVM的鍋爐燃燒優(yōu)化預測控制 [J].電力自動化設備，2011，31(11)：89-93.

(LONG Wen，LIANG Xi-ming，LONG Zu-qiang，et al.Predictive control based on LSSVM and ACO for boiler combustion optimization [J].Electric Power Automation Equipment，2011，31(11)：89-93.)

[5]王志奇，周乃君，郭靜，等.基于模擬退火算法的低溫余熱發(fā)電系統(tǒng)參數(shù)優(yōu)化 [J].中南大學學報(自然科學版)，2012，43(1)：366-371.

(WANG Zhi-qi，ZHOU Nai-jun，GUO Jing，et al.Pa-rametric optimization of low-temperature waste heat power generation system by simulated annealing algorithm [J].Journal of Central South University(Science and Technology)，2012，43(1)：366-371.)

[6]邢宗義，冒玲麗，廖貴玲，等.基于PSO-SVM模型的城軌列車輪對尺寸預測 [J].沈陽工業(yè)大學學報，2014，36(4)：411-415.

(XING Zong-yi，MAO Ling-li，LIAO Gui-ling，et al.Forecasting of wheelset size of urban rail train based on PSO-SVM model [J].Journal of Shenyang University of Technology，2014，36(4)：411-415.)

[7]于明，艾月喬.基于人工蜂群算法的支持向量機參數(shù) [J].光電子激光，2012，23(2)：374-378.

(YU Ming，AI Yue-qiao.SVM parameter optimization and application based on artificial bee colony algorithm [J].Journal of Optoelectronics Laser，2012，23(2)：374-378.)

[8]黃慧，顧波.改進遺傳算法在電網(wǎng)規(guī)劃中的應用 [J].電力系統(tǒng)保護與控制，2012，40(22)：64-67.

(HUANG Hui，GU Bo.Application of improved genetic algorith in the network planning [J].Power System Protection and Control，2012，40(22)：64-67.)

[9]白洋，段黎明，柳林，等.基于改進的混合粒子群算法的變循環(huán)發(fā)動機模型求解 [J].推進技術(shù)，2014，35(12)：1694-1700.

(BAI Yang，DUAN Li-ming，LIU Lin，et al.Solving variable cycle engine model based on improved hybrid particle swarm optimezation [J].Journal of Propulsion Technology，2014，35(12)：1694-1700.)

[10]李冬，劉建昌，譚樹彬，等.改進蟻群算法在熱精軋負荷分配優(yōu)化中的應用 [J].控制理論與應用，2014，31(8)：1077-1086.

(LI Dong，LIU Jian-chang，TAN Shu-bin，et al.Application of improved ant colony algorithm in load distribution optimization of hot finishing mills [J].Control Theory & Applications，2014，31(8)：1077-1086.)

[11]臧明相，馬軒，段奕明.一種改進的人工蜂群算法 [J].西安電子科技大學學報，2015，42(2)：73-79.

(ZANG Ming-xiang，MA Xuan，DUAN Yi-ming.Improved artificial bee colony algorithm [J].Journal of Xidian University，2015，42(2)：73-79.)

[12]Zhang J，Liu K，Tan Y，et al.Random black hole particle swarm optimization and its application [C]//IEEE International Conference on Neural Networks and Signal Processing.Zhenjiang，China，2008：359-365.

[13]Hatamlou A.Black hole：a new heuristic optimization approach for data clustering [J].Information Sciences，2013，222：175-184.

[14]陳民鈾，程杉.基于隨機黑洞和逐步淘汰策略的多目標粒子群優(yōu)化算法 [J].控制與決策，2013，28(11)：1129-1134.

(CHEN Min-xiu，CHENG Shan.Multi objective partocle swarm optimization algorithm based on random black hole mechanism and step-by-step elimination strategy [J].Control and Decision，2013，28(11)：1129-1134.)

[15]劉靜，羅先覺.采用多目標隨機黑洞粒子群優(yōu)化算法的環(huán)境經(jīng)濟發(fā)電調(diào)查 [J].中國電機工程學報，2010，30(34)：105-111.)

(LIU Jing，LUO Xian-jue.Environmental economic dispatching adopting multiobjective random black-hole particle swarm optimization algorithm [J].Proceedings of the CSEE，2010，30(34)：105-111.)

[16]王通，高憲文，蔣子健.基于黑洞算法的 LSSVM 的參數(shù)優(yōu)化 [J].東北大學學報(自然科學版)，2014，35(2)：170-174.

(WANG Tong，GAO Xian-wen，JIANG Zi-jian.Parameters optimizing of LSSVM based on black hole algorithm [J].Journal of Northeastern University(Natural Science Edition)，2014，35(2)：170-174.)

(責任編輯：景勇英文審校：尹淑英)

Optimization algorithm of black-hole based on Euclidean distance

WANG Tong,LIU Wen-fang,LIU Chun-fang

(School of Electrical Engineering,Shenyang University of Technology,Shenyang 110870,China)

To improve the optimization precision and global search capability of black-hole algorithm,an improved optimization algorithm of black-hole based on Euclidean distance was proposed.The Euclidean distance was applied to initialize the star swarm locations,increase the diversity of star swarm and improve the global searching capability.The maximum radius of black-hole was set to avoid the escape of global optimization solutions due to too large black-hole area.When a star was swallowed by the black-hole,it was required that a new star generated at a position with a certain Euclidean distance from the black-hole in order to enhance the star searching areas.Through the optimization tests for three benchmark functions and the comparison with PSO,ABC,DE,BH optimization algorithms,the superiority of optimization precision and global search capability for the optimization algorithm of black-hole based on Euclidean distance was verified.The results show that the present algorithm can not only search the global optimal solution to the parameters,but also exhibit a certain advantage compared with other optimization algorithms.

black-hole algorithm; global searching; Euclidean distance; optimization; multi-model function optimization; swarm intelligence; test function; improved algorithm

2015-05-14.

國家自然科學基金資助項目(61102124).

王通(1976-)，男，遼寧沈陽人，講師，博士生，主要從事復雜工業(yè)過程的控制及故障監(jiān)測等方面的研究.

10.7688/j.issn.1000-1646.2016.02.15

TP 18

A

1000-1646(2016)02-0201-05

*本文已于2015-09-15 00∶00在中國知網(wǎng)優(yōu)先數(shù)字出版.網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/21.1189.T.20150915.0000.002.html