求解约束优化问题的改进的矿井爆炸算法

赵鹏军

(商洛学院 数学与计算机应用学院， 商洛 726000)

求解约束优化问题的改进的矿井爆炸算法

赵鹏军

(商洛学院 数学与计算机应用学院， 商洛 726000)

针对矿井爆炸算法在求解约束优化问题时存在易陷入局部最优的缺点，提出了一种改进的煤矿爆破算法。借鉴粒子群算法的思想对改进的引爆位置进行修正，若临时解更优时，对临时解进行随机一维变异。函数优化问题的实验结果表明了算法的可行性和有效性。

煤矿爆炸算法； 早熟收敛； 粒子群优化算法

0 引言

基于对现实生活中矿井炸弹被引爆过程的研究，Ali Sadollaha等人[1]于2012年提出了一种新的主能算法--矿井爆炸算法(Mine Blast Algorithm , MBA)，目前该算法已成功应用于函数优化、工程设计等方面[1-6]，在求解精确度和算法性能方面也取得了较好的结果[6]。然而，和其他智能算法一样，MBA同样存在早熟收敛现象。为提高算法的性能，本文借鉴粒子群优化算法[7]及变异的思想，提出了改进的MBA(记为PMBA)，可在一定程度上避免算法陷入局部最优，数值结果验证了改进算法的可行性和有效性。

1 矿井爆炸算法

X0=Lb+r1·(Ub-Lb)

(1)

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

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

(2)

其中D是搜索空间维数，考虑当前矿井爆炸产生的Ns个弹片引起另一个矿井被引爆的位置Xn+1如式(3)。

(3)

(4)

(5)

(6)

其中F为X的函数值，在每个维度上弹片的初始距离如式(7)。

d0=Ub-Lb

(7)

此外，为了在解空间上进行充分的探索，算法在早期迭代中引入探测因子μ，将μ与迭代次数k进行比较，如果μ>k，则探索过程开始。这时解空间的探索方程可表示为式(8)。

(8)

(9)

其中r3∈N(0,1)，用式(8)修改每个弹片的距离，在早期迭代中，探索过程将促使弹片接近最优点，大的μ值可以探索更远的区域。因此，μ的值决定了探索的强度。

为了提高算法的全局搜索能力，d0自适应地表示为式(10)。

(10)

其中α是缩减常数，在迭代后期，弹片的距离将近似等于0。矿井爆炸算法的探索和开采过程，如图1所示。

图1 矿井爆破算法探索和开采过程示意图

同心圆线表示探索过程，散状线表示开采过程。

算法用式(4)-(6)分别计算爆破矿炸弹的位置、弹片的距离和方向。在开发过程中弹碎片的距离根据式(9)自适应减少，引导算法聚焦到全局最优解。探索、开发过程如下：

如果μ>k

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

否则

开发(方程(4)-(6)及(方程(10))

结束

2 改进的矿井爆炸算法

为提高算法的搜索效率，有效避免过早陷入局部最优，受文献 [7]中“惯性”部分和“社会”部分的启发，将式(3)修改为式(11)。

(11)

(12)

这样有助于避免陷入局部最优。因而PMBA在继承MBA优点的同时，在一定程度上扩展了搜索范围，促使算法朝最优解方向移动，为跳出局部最优提供了可能，更有可能求得优化问题的全局最解。

综上所述，PMBA的具体实现过程如下：

步骤1：初始化群体及参数：随机解，Ns，α，β，μ，最大迭代次数Nmax。

步骤2：检查探索条件。

步骤3：如果探索条件满足，根据(8)及(9)计算弹片的位置和距离。否则，转到步骤10。

步骤4：根据(6)计算弹片的方向。

步骤5：生成弹片并用式(11)计算改进位置。

步骤6：检查弹片的约束。

步骤7：保存最好的弹片作为最好的临时解。

步骤8：判断弹片是否有比最好的临时解更好的解。

步骤9：如果有，交换的弹片的位置和和临时最优解。否则，变异并转到步骤10。

步骤10：用(4)及(5)计算弹片的距离和位置。返回第4步。

步骤11：用式(10)自适应减少弹片块距离。

步骤12：检查终止条件。如果满足，算法停止。否则，返回步骤2。

3 数值实验

为验证PMBA的有效性性能，选取文献[2]中的3个约束优化问题进行仿真实验，P1和P2是最小值问题，P4是最大值问题，将其转化为最小值问题进行求解，3个约束优化问题的具体表达式为式(13)、(14)、(15)。

3.2 约束处理

一方面将等式约束转化为-h(x)-δ≤0，h(x)-δ≤0，是很小的正数；另一方面利用文献[8]中提出的违反约束问题的4个规则：

1) 任何可行解优于不可行解；

2) 当不可行解是极少违反约束条件的情况下被看作是可行解；

3) 两个可行解中，有较好目标函数值的解更优；

4) 两个不可行解中，违反约束较小的解更优。

若问题的最优解在可行域的边界上或靠近可行域的边界，规则2)能保证搜索到边界并且能够以较大的概率找到最优解[8]。这种约束处理技术在求解约束优化问题和工程设计问题方面已被学者们广泛使用。

3.3 参数设置

文中对MBA和PMBA分别进行了测试，为了增强可比性，采用文献[2]中给出的参数设置，如表1所示。

表1 参数设置

3.4 实验结果

每个测试函数在下述参数设置下独立运行30次以消除随机因素的影响，数值实验结果包括统计结果(最差结果、平均结果、最优结果、标准差)和最优结果比较。对3个测试函数的仿真结果，如表2-5所示。

表2 2种算法对P1的最优结果比较

表3 2种算法对P2的最优结果比较

表4 2种算法对P3的最优结果比较

从表2和5可知，对函数P1，两个算法获得了相似的最差结果和最好结果，而PMBA获得了较好的平均结果和标准差。

表5 2种算法对4个约束优化问题寻优统计结果比较

从表3和5可知，对函数P2，两个算法获得了相似的最好结果，PMBA获得了较好的最差结果、平均结果和标准差。

从表4和5可知，对函数P3，两个算法获得了相似的最差结果、平均结果和最好结果，PMBA获得了较好的标准差。

与文献[2]中提到的一些算法相比，PMBA也获得了较满意的结果。PBMA由于采用了随机变异以及粒子群优化算法的继承和引导策略，在一定程度上改善了对优化问题的寻优能力，其收敛精度高，稳定性好，提高了算法的搜索效率。

4 总结

矿井爆炸算法是一种新的智能算法，本文利用粒子群优化算法及变异的思想对矿井爆炸算法做了改进，使算法在保证良好收敛性的同时，有效地改善了算法的搜索效率。对约束优化问题的仿真结果表明PMBA提高了算法的搜索性能，能有效避免早熟收敛，而且算法的稳定性好。

[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] 王形. 云联网环境中服务路由机制的设计与仿真实现[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); 陕西省教育科学规划课题(SGH13405);商洛学院服务地方专项(13SKY-FWDF001)。

赵鹏军 (1979-)，男，副教授，硕士，研究方向：智能计算。

TP301.6

A

2017.04.08)