基于欧氏距离的黑洞寻优算法*

王　通，刘文芳，刘春芳

(沈阳工业大学 电气工程学院，沈阳 110870)



基于欧氏距离的黑洞寻优算法*

王通，刘文芳，刘春芳

(沈阳工业大学 电气工程学院，沈阳 110870)

为了提高黑洞算法的寻优精度和算法的全局搜索能力，提出了一种基于欧氏距离的改进黑洞寻优算法.通过引入欧氏距离来初始化星体群位置，增强星体群的多样性，提高其全局搜索能力；设定黑洞半径最大值，避免由于黑洞面积过大跳过全局最优解，当有星体被黑洞吸收时，要求新的星体在距离黑洞一定欧氏距离以外的位置产生，提高星体的搜索区域；通过对3个基准测试函数进行寻优测试，并与PSO、ABC、DE、BH优化算法相比，验证了基于欧氏距离的黑洞寻优算法在寻优精度和全局寻优能力方面的优越性.结果表明，该算法不仅能够搜索到参数的全局最优解，而且与其他优化算法相比有一定优势.

黑洞算法；全局搜索；欧氏距离；优化；多模函数优化；群体智能；测试函数；改进算法

近年来，群体智能的研究正受到人们的广泛关注[1-2]，如遗传算法(GA)[3]、蚁群算法(ACA)[4]、模拟退火算法(SA)[5]、粒子群优化算法(PSO)[6]及人工蜂群算法(ABC)[7]等，它们通过模拟或解释某些自然现象或过程而得以发展，为解决寻优问题提供了新的思路和方法.这些优化算法与传统的算法相比具有能够从全局范围去寻找最佳结果的优点，而且参数在初始化时可以不在真值附近.然而，智能优化算法自身具有一定的局限性，文献[8]指出遗传算法存在早熟且易陷入局部极值的缺点，同时常规遗传算法使用赌轮选择方法来选择参与交叉的父体和母体，体现不出个体竞争力，无法实现遗传算法优胜劣汰的原则；文献[9]指出粒子群算法易陷入局部最优解，并对方法进行了改进；文献[10]指出蚁群算法在实际应用过程中，由于蚂蚁爬行缺乏有效信息素的引导，造成大量无效搜索，且蚁群算法在加速收敛过程中易出现停滞；文献[11]介绍了人工蜂群算法的优点，但也指出该算法在理论和实践上都还不够成熟，对于求解一些复杂问题，仍存在搜索速度慢、群体多样性差及易陷入局部最优等缺陷.

黑洞(black-hole，BH)算法是Zhang J和Tan Y等人受到黑洞物理现象的启发，于2008年在文献[12]首次提出的一种与粒子群优化算法相结合解决粒子陷入局部极值问题的算法；Hatamlou[13]改善了黑洞算法边界的确定和吸收星体处理问题，进一步接近黑洞的自然现状，并将该算法应用于解决数据聚类问题；文献[14]对随机黑洞粒子群算法方法进行了改进，提高了方法的收敛性能；文献[15]将随机黑洞粒子群算法成功应用到环境经济发电调度中；文献[16]将黑洞算法引入到数值寻优领域中，实现模型参数的寻优，完成大规模计算，防止早熟和欺骗现象的发生，并且具有寻优精度高、收敛速度快、不容易陷入局部极值的优点，但是该算法在寻优精度和全局的寻优能力方面研究有待进一步提高.

针对上述问题，本文提出一种改进的黑洞优化算法.首先，初始星体在搜索空间等欧氏距离产生，使其均匀遍历在整个搜索空间；其次，设定黑洞半径的最大值，提高最优星体附近寻优的概率，新的星体要求与黑洞的欧式距离超过一定的位置产生；最后，将算法与粒子群(PSO)、差分进化(DE)、人工蜂群(ABC)及黑洞(BH)优化算法用于3种典型的测试函数进行寻优比较，证明算法的全局搜索能力和寻优精度更有优势.

1　黑洞算法

BH算法主要是模拟实际黑洞现象，将有限的搜索空间假想成宇宙系统，在搜索空间内随机产生N个随机数充当星体，即

(1)

式中：xi(0)为第i个星体初始位置；xmin、xmax为第i个星体的下限和上限；rand为[0，1]之间的随机数；N为星体的个数.

星体的自适应值表示为

(2)

式中：fi(t)为t次寻优中第i个星体的目标函数值；Fi(t)为t次寻优中第i个星体自适应值.

BH算法中的黑洞具有与自然界黑洞同样的强吸引能力，其他所有星体在搜索域内不断向黑洞靠拢且无法逃逸.星体向黑洞靠近的更新公式为

(3)

式中：xi(t+1)、xi(t)为第i个星体在t+1和t次寻优中的位置；xBH为黑洞的位置；M为最大寻优次数.

利用式(2)计算新产生星体的自适应度值，与黑洞的自适应值比较，当星体的自适应值Fi(t)优于黑洞的自适应值FBH时，说明当前的黑洞不是最优的，将黑洞和星体互换位置，以新的最优适应值对应的星体为中心形成黑洞，其他星体继续向新形成的黑洞逼近.

黑洞的边界计算式为

(4)

当星体的自适应度值进入黑洞边界以内，即被黑洞吸收，将自动在搜索空间内随机产生新的星体，保证星体的数目不变.

2　改进的黑洞算法

2.1欧氏距离原理

欧氏距离(Euclisean distance)全名欧几里德距离，也含有普遍意义上距离的含义，表示的是两点之间存在的真实距离.欧氏距离常被用于度量分类对象之间的接近与相似程度，利用该性质将欧氏距离用于星体的初始化过程以及限定新产生星体的位置.

(5)

式中，Xis和Xjs分别为Xi和Xj的第s个分量.两个星体之间的欧氏距离越小，则两个星体之间的相似度越大，其包含的冗余信息就越多，其接下来迭代可利用的有效信息就越少，导致算法陷入局部最优的概率就增大，算法全局搜索的能力就越弱，因此本文引入欧氏距离的方法作为产生初始星体和更新星体的理论依据，增强星体的多样性，提高算法的全局搜索能力.

2.2改进的黑洞算法原理

初始星体群中各星体位置为

(6)

采用式(2)计算初始星体的自适应值，选择最优的自适应值对应的星体作为黑洞.黑洞的半径根据式(4)计算，若黑洞的半径很大，就会增加星体进入黑洞的概率，经过一次自适应度函数的比较，被黑洞吸收的星体停止继续向最优星体靠近，容易跳过全局最优解.因此，有必要将黑洞的半径设定一个阈值，当黑洞的半径超过阈值时，将半径赋值为阈值，否则按照计算的半径寻优，避免由于半径过大跳过全局最优星体.

星体不断向黑洞靠近最终被吸收后，考虑到星体的个数和星体的多样性，重新生成一个星体.因为星体与黑洞的相似度越小越好，要求星体在距离黑洞一定欧氏距离之外产生，从而增强星体与其他星体的差异性.

2.3改进黑洞算法的实现过程

根据上述的实现原理，具体实现步骤如下：

1) 初始化参数，包括星体范围(xmin，xmax)，最大寻优次数M，星体的个数N，新产生星体距离黑洞的最小距离J，星体的维数D.

2) 等欧氏距离产生N个初始星体.

3) 计算初始星体的自适应度值，选择最优的自适应度值确定初始黑洞.

4) 更新星体的位置.

5) 比较黑洞与星体的自适应值，若星体的自适应值优于黑洞，交换星体和黑洞的位置；否则不更新黑洞.

6) 计算黑洞的半径，如果一个星体与黑洞表面相交，那么这个星体将被吸收，同时，在搜索空间内产生一个与黑洞欧式距离大于J的新星体.

7) 当系统达到最大迭代次数或者出现一个最优寻优结果时，寻优结束，输出最优解；否则返回步骤4).

3　仿真实验与结果分析

3.1实验参数设置

为了验证算法的寻优能力，选取了3个经典基准测试函数Griewank、Rastrgin、Ackle对寻优算法的搜索能力进行测试.以上经典测试函数的共同特点是均为复杂的非线性多峰函数，在定义域内有多个局部最值，极难优化，常用来测试算法的探索和开发能力.表1中给出了3个基准测试函数的表达式、搜索范围以及理论全局最小值.

首先设置改进BH的实验参数：最大迭代次数为100，星体数目为30，星体的维数为10，实验次数为10次，星体的搜索范围根据表1中不同的测试函数来设置，黑洞的最大半径为0.09，最优解精度e为10-20.为了突出算法的优越性，将改进BH与PSO、DE、ABC、BH等典型的优化算法对比，为便于比较算法的性能，参数设置同改进BH一致.记录10次独立实验寻优结果的最优值(Best)、最差值(Worst)、平均值(Mean)、标准差(Std)以及算法的平均运行时间指标如表2所示.

表1　3个基准测试函数

表2　基准函数的优化结果比较

3.2实验结果分析

由表2可以看出，在对3个测试函数寻优时，改进的黑洞算法得到的最优值最接近理论最优值且运行时间最短，在对Rastrgin和Ackle测试函数寻优时，改进的黑洞相对其他优化算法各项指标均具有一定的优势.分析原因：星体初始化采用了等欧氏距离的方法生成，避免了随机生成的星体中存在相似的星体；限定新产生星体的位置，增强了星体的遍历性.综合来看，改进的黑洞算法与其他算法相比整体有一定优势.

4　结　论

针对黑洞算法的特性，结合欧氏距离提出了一种改进的黑洞算法，该算法利用等欧氏距离初始化星体，避免了初始星体距离近搜索范围小的缺陷.设定黑洞的半径，提高在黑洞附近搜索最优解的概率，淘汰进入黑洞的星体，生成与黑洞的欧氏距离大于J的新星体，提高算法的全局搜索能力.利用3个经典基准测试函数对改进的黑洞寻优算法的寻优能力进行测试，实验结果表明，该算法在保持黑洞算法优点的同时，进一步提高了算法的全局搜索能力和寻优精度.

[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]李翠平，郑瑶瑕，张佳，等.基于遗传算法优化的支持向量机品位插值模型 [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的锅炉燃烧优化预测控制 [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]王志奇，周乃君，郭静，等.基于模拟退火算法的低温余热发电系统参数优化 [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].沈阳工业大学学报，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].光电子激光，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].电力系统保护与控制，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].推进技术，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].控制理论与应用，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]陈民铀，程杉.基于随机黑洞和逐步淘汰策略的多目标粒子群优化算法 [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]刘静，罗先觉.采用多目标随机黑洞粒子群优化算法的环境经济发电调查 [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 的参数优化 [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-)，男，辽宁沈阳人，讲师，博士生，主要从事复杂工业过程的控制及故障监测等方面的研究.

10.7688/j.issn.1000-1646.2016.02.15

TP 18

A

1000-1646(2016)02-0201-05

*本文已于2015-09-15 00∶00在中国知网优先数字出版.网络出版地址：http://www.cnki.net/kcms/detail/21.1189.T.20150915.0000.002.html