王　通，劉文芳，劉春芳

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

?

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

王通，劉文芳，劉春芳

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

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

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

近年來，群體智能的研究正受到人們的廣泛關(guān)注[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)點(diǎn)，而且參數(shù)在初始化時(shí)可以不在真值附近.然而，智能優(yōu)化算法自身具有一定的局限性，文獻(xiàn)[8]指出遺傳算法存在早熟且易陷入局部極值的缺點(diǎn)，同時(shí)常規(guī)遺傳算法使用賭輪選擇方法來選擇參與交叉的父體和母體，體現(xiàn)不出個(gè)體競爭力，無法實(shí)現(xiàn)遺傳算法優(yōu)勝劣汰的原則；文獻(xiàn)[9]指出粒子群算法易陷入局部最優(yōu)解，并對方法進(jìn)行了改進(jìn)；文獻(xiàn)[10]指出蟻群算法在實(shí)際應(yīng)用過程中，由于螞蟻爬行缺乏有效信息素的引導(dǎo)，造成大量無效搜索，且蟻群算法在加速收斂過程中易出現(xiàn)停滯；文獻(xiàn)[11]介紹了人工蜂群算法的優(yōu)點(diǎn)，但也指出該算法在理論和實(shí)踐上都還不夠成熟，對于求解一些復(fù)雜問題，仍存在搜索速度慢、群體多樣性差及易陷入局部最優(yōu)等缺陷.

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

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

1　黑洞算法

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

(1)

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

星體的自適應(yīng)值表示為

(2)

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

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

(3)

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

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

黑洞的邊界計(jì)算式為

(4)

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

2　改進(jìn)的黑洞算法

2.1歐氏距離原理

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

(5)

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

2.2改進(jìn)的黑洞算法原理

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

(6)

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

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

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

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

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

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

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

4) 更新星體的位置.

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

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

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

3　仿真實(shí)驗(yàn)與結(jié)果分析

3.1實(shí)驗(yàn)參數(shù)設(shè)置

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

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

表1　3個(gè)基準(zhǔn)測試函數(shù)

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

3.2實(shí)驗(yàn)結(jié)果分析

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

4　結(jié)　論

針對黑洞算法的特性，結(jié)合歐氏距離提出了一種改進(jìn)的黑洞算法，該算法利用等歐氏距離初始化星體，避免了初始星體距離近搜索范圍小的缺陷.設(shè)定黑洞的半徑，提高在黑洞附近搜索最優(yōu)解的概率，淘汰進(jìn)入黑洞的星體，生成與黑洞的歐氏距離大于J的新星體，提高算法的全局搜索能力.利用3個(gè)經(jīng)典基準(zhǔn)測試函數(shù)對改進(jìn)的黑洞尋優(yōu)算法的尋優(yōu)能力進(jìn)行測試，實(shí)驗(yàn)結(jié)果表明，該算法在保持黑洞算法優(yōu)點(diǎn)的同時(shí)，進(jìn)一步提高了算法的全局搜索能力和尋優(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ī)品位插值模型 [J].北京科技大學(xué)學(xué)報(bào)，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]龍文，梁昔明，龍祖強(qiáng)，等.基于蟻群算法和LSSVM的鍋爐燃燒優(yōu)化預(yù)測控制 [J].電力自動(dòng)化設(shè)備，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].中南大學(xué)學(xué)報(bào)(自然科學(xué)版)，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模型的城軌列車輪對尺寸預(yù)測 [J].沈陽工業(yè)大學(xué)學(xué)報(bào)，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]于明，艾月喬.基于人工蜂群算法的支持向量機(jī)參數(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]黃慧，顧波.改進(jìn)遺傳算法在電網(wǎng)規(guī)劃中的應(yīng)用 [J].電力系統(tǒng)保護(hù)與控制，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]白洋，段黎明，柳林，等.基于改進(jìn)的混合粒子群算法的變循環(huán)發(fā)動(dòng)機(jī)模型求解 [J].推進(jìn)技術(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]李冬，劉建昌，譚樹彬，等.改進(jìn)蟻群算法在熱精軋負(fù)荷分配優(yōu)化中的應(yīng)用 [J].控制理論與應(yīng)用，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ìn)的人工蜂群算法 [J].西安電子科技大學(xué)學(xué)報(bào)，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]陳民鈾，程杉.基于隨機(jī)黑洞和逐步淘汰策略的多目標(biāo)粒子群優(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]劉靜，羅先覺.采用多目標(biāo)隨機(jī)黑洞粒子群優(yōu)化算法的環(huán)境經(jīng)濟(jì)發(fā)電調(diào)查 [J].中國電機(jī)工程學(xué)報(bào)，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].東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，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.)

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

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.

國家自然科學(xué)基金資助項(xiàng)目(61102124).

王通(1976-)，男，遼寧沈陽人，講師，博士生，主要從事復(fù)雜工業(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)絡(luò)出版地址：http://www.cnki.net/kcms/detail/21.1189.T.20150915.0000.002.html