求解约束优化问题的萤火虫算法及其工程应用

龙文，蔡绍洪，焦建军，陈义雄，黄亚飞



求解约束优化问题的萤火虫算法及其工程应用

龙文1，蔡绍洪1，焦建军1，陈义雄2，黄亚飞2

(1. 贵州财经大学贵州省经济系统仿真重点实验室，贵州贵阳，550004；2. 中南大学信息科学与工程学院，湖南长沙，410083)

针对基本萤火虫算法存在收敛速度慢、易陷入局部最优等缺点，提出一种改进的萤火虫算法用于求解约束优化问题。该算法首先利用混沌序列初始化萤火虫的位置，引入动态随机局部搜索以加快算法的收敛速度；为了避免算法陷入局部最优，对当前全局最优解进行多样性变异操作。对几个数值优化和工程优化问题进行实验。研究结果表明：与其他启发计算法相比，该算法具有较强的寻优性能。

萤火虫算法；约束优化问题；动态随机局部搜索；工程优化

在工程实际应用中，许多问题可转化为求解含有约束条件的函数优化问题。不失一般性，1个含有不等式约束、等式约束和变量界约束的约束优化问题(最小化)可描述为

1 基本萤火虫算法

FA是模拟自然界中萤火虫的发光行为而衍生出的启发式全局优化方法，它利用萤火虫发光特性在搜索空间中寻找伙伴，并向位置较优的萤火虫移动，从而达到了进化的目的。

在描述具体的FA之前，需进行如下假设。

1) 萤火虫不分雌雄，发光较强的萤火虫可以吸引其他发光较弱的萤火虫。

2) 每个萤火虫的吸引度与其发光强度成正比。对于任意2只萤火虫，发光较弱的萤火虫会朝发光较强的萤火虫移动，且与随着2只萤火虫之间的距离的变大而变小。最亮的萤火虫(即最大的萤火虫)是随机飞行的。

3) 萤火虫的与目标函数值有关。

在满足上述3个假设的情况下，基本萤火虫算法的步骤如下。

Step 1 设置算法参数：种群规模，最大吸引度0，吸收系数，随机步长，最大迭代次数。在解空间中随机初始化萤火虫的位置，令=1。

Step 2 平均每只萤火虫的发光强度I(=1，2，…，)，将发光强度I作为适应度(x)(x表示问题的1个解)，即I=(x)，1≤≤。

其中：为决策变量的维数。

萤火虫的吸引度为

Step 4 移动更新萤火虫的位置。萤火虫被发光强度更亮的萤火虫吸引而发生位置移动。

Step 5 发光强度最亮的萤火虫随机飞行：

Step 6 判断算法是否满足终止条件，若满足，则算法结束，输出最优解；否则，令=+1，返回 Step 2。

2 改进萤火虫算法

2.1 种群初始化

目前，FA几乎全部采用随机方式对萤火虫的位置进行初始化，这有可能导致萤火虫分布位置的不均匀。另外，在求解优化问题前，由于对全局最优解没有任何先验知识，若随机初始化种群个体，则不利于搜索到全局最优解，可能导致增加迭代次数或种群规模，这势必会增加算法的计算量。因此，初始种群的优劣对FA的收敛性及搜索效率会产生较大的影响。

混沌是一种非线性现象，具有随机性、遍历性、有界性和规律性等特点，对初始值是极度敏感的，可在一定范围内按自身规律不重复地遍历所有状态，可将其应用到优化算法中来提高其全局搜索能力。因此，本文采用混沌序列初始化萤火虫的位置，以维持种群的多样性，为进一步有效地进行全局搜索建立基础。本文引入常用的Logistic映射[8]进行种群初始化，即

其中：为控制参数；x为变量；为迭代次数。当=4时，式(6)完全处于混沌状态，的取值不同，混沌序列的搜索范围也不同。

2.2 动态随机局部搜索

为了增强FA的局部搜索能力和加快其收敛速度，本文引入一种具有很强局部搜索能力的动态随机局部搜索技术[9]，其具体步骤如下。

Step 1 设定局部搜索代数，搜索步长上限0，对于每一个搜索步长的最大迭代次数为，，epoch= 0，=0。

Step 2 重置迭代计数器，=0。

Step 4 更新epoch，即epoch=epoch+1。

Step 7 若＜，则转Step 3；否则转Step 8。

Step 8=+1。

Step 10 若epoch=，则算法结束；否则返回 Step 2。

其中：epoch为局部搜索迭代计数器；best为当前最优解；(∙)为计算适应值的函数。

2.3 多样性变异策略

变异算子可避免算法陷入局部最优，同时也可保持种群的多样性。本文对当前全局最优解进行多样性变异操作，其具体实现如下[10]：

2.4 约束处理技术

FA是一种基于无约束的全局优化方法，因此利用它求解约束优化问题时一定要结合一种合适的约束处理技术。Deb[11]提出了一种不需要任何参数的联赛选择算子，比较和选择个体时采用如下3个比较准则：

1) 若选择进行比较的2个个体均为可行个体，则目标函数值小的个体要优。

2) 若选择进行比较的2个个体中，一个为可行个体，另一个为不可行个体，则可行个体要优。

3) 若选择进行比较的2个个体均为不可行个体，则约束违反度小的个体要优。约束违反度计算公式为

由于这种约束处理技术原理简单、参数设置少，容易实现。因此，本文采用基于可行性规则的联赛选择算子来处理约束条件。

2.5 算法步骤

综上所述，本文提出的改进FA算法步骤如下。

Step 1 设置算法参数：种群规模，最大吸引度0，吸收系数，随机步长，动态随机局部搜索代数，对于每一个搜索步长的最大迭代次数，变异概率p，最大迭代次数。

Step 2 在解空间中利用混沌序列初始化萤火虫的位置，令=1。

Step 3 计算每只萤火虫的发光强度I(=1，2，…，)，将发光强度I作为适应度值(x)(x表示问题的一个解)，即，找出当前最优位置及其对应的最优适应度。

Step 4 根据2.4节中的方法比较和选择萤火虫进入下一代群体。

Step 5 判断算法是否满足结束条件，若满足，则算法结束，输出全局最优解；否则，转Step 6。

Step 6 计算各萤火虫的吸引度。先按式(2)确定2只萤火虫之间的距离r，然后根据式(3)计算萤火虫的吸引度。

Step 7 移动更新萤火虫的位置。根据式(4)更新萤火虫的位置。

Step 8 发光强度最亮的萤火虫按式(5)进行随机飞行。

Step 9 对当前最优萤火虫的位置(当前全局最优解)进行动态随机局部搜索。

Step 10 以一定的概率p对每一代全局最优解进行多样性变异操作，令=+1，返回Step 3。

3 数值实验与比较分析

为了验证所提出的改进萤火虫算法(记为IFA)的有效性，本文首先从文献[12]选取4个标准约束优化问题进行测试实验，然后将IFA应用到2个工程优化应用问题中。

4个约束优化测试问题的具体表达式为：

；

G2:

G4:

在4个约束优化函数中，G1，G3和G4是最小值问题，G2是最大值问题，在一般情况下，通过将最大值问题转化为最小值问题。

利用IFA求解上述4个约束优化问题，其参数设置如下：种群规模=50，最大吸引度0=0.20，吸收系数=1，随机步长=0.25，动态随机局部搜索迭代次数=100，对于每一个搜索步长α的最大迭代次数=10，变异概率p=0.1，最大迭代次数为3 000。每个测试函数在上述参数设置下独立运行30次，记录其最好结果、平均结果、最差结果和标准差，并与文献[13]中的genetic algorithm (GA)，evolution strategy (ES)，particle swarm optimization (PSO)，simulating annealing (SA)，bat algorithm (BA)和firefly algorithm (FA)[14]得到的结果进行比较，结果如表1所示。

表1 IFA和其他6种算法对4个约束优化问题的寻优结果比较

从表1可知：对于4个标准约束优化测试问题，IFA求得的解精度高、且30次实验的标准差较小，从而说明IFA具有较强的全局寻优能力和稳定性。与GA相比，IFA对4个函数均得到了较好的结果。与ES相比，对于函数G1和G2，IFA获得了相似的最优结果和较好的平均结果、最差结果和标准差；对于函数G3和G4，IFA得到的结果比ES要优。与PSO算法相比，对于函数G2，IFA获得了相似的结果；对于函数G1，G3和G4，IFA得到了较好的结果。与SA相比，对于函数G1和G2，IFA获得了相似的结果；对于函数G3和G4，IFA则得到了较好的结果。与BA相比，对于函数G1，G2和G4，IFA获得了相似的结果；而对于函数G3，IFA求得的结果要优。与FA相比，对于函数G1和G4，IFA得到的结果要优。对于函数G2和G3，IFA得到了相似的最优结果和较好的平均结果、最差结果和标准差。图1~4所示为IFA对4个函数的寻优收敛曲线。

从图1~4可以清晰地看出：对于4个测试函数，IFA迭代较少次数时就达到全局最优解或近似最 优解。

图1 IFA对函数G1的寻优收敛曲线

图2 IFA对函数G2的寻优收敛曲线

图3 IFA对函数G3的寻优收敛曲线

图4 IFA对函数G4的寻优收敛曲线

4 IFA在工程优化中的应用

为了进一步验证IFA的有效性，本文将其求解2个工程优化问题，即焊接梁结构设计优化问题和拉力/压力弹簧结构设计优化问题。

4.1 焊接梁结构设计优化问题

焊接梁结构设计优化的目标是在一定约束条件下使其总成本最小。焊接梁的结构如图5所示，它有4个设计变量，分别为(1)，(2)，(3)和(4)，约束变量为梁上的弯曲应力、剪应力、压曲临界载荷P和梁的尾端误差。

图5 焊接梁结构设计优化问题

焊接梁结构设计优化问题的目标函数和约束条件如下。

其中：

；；；

；；；；

4个变量的取值范围为0.1≤1≤2.0，0.1≤4≤2.0，0.1≤2≤10.0，0.1≤3≤10.0。

利用IFA对焊接梁结构设计优化问题进行求解，并与co-evolutionary differential evolution (CDE)[15]，co-evolutionary particle swarm optimi- zation (CPSO)[16]和mine blast algorithm (MBA)[17]进行比较，结果如表2和表3所示。

表2 4种算法对焊接梁设计问题的最优结果比较

表3 不同算法对焊接梁设计问题的寻优统计结果比较

从表2和表3可知：对于焊接梁结构设计优化问题，IFA求得的最优解为1.724 894，仅略差于MBA的最优解。与CDE算法和CPSO算法相比，IFA获得了较好的最优结果、平均结果、最差结果和标准差。

4.2 拉力/压力弹簧结构设计优化问题

拉力/压力弹簧结果设计优化问题如图6所示，其设计目标是在满足最小挠度、剪应力和振动频率等约束条件下最小化其质量，它有3个设计变量，分别是弹簧线圈直径(1)、弹簧圈平均直径(2)和有效绕圈数(3)。

图6 拉力/压力弹簧结构设计优化问题

拉力/压力弹簧结构设计优化问题的目标函数和约束条件如下：

利用IFA对拉力/压力弹簧结构设计优化问题进行求解，并与CDE、CPSO和accelerating adaptive trade-off model (AATM)[18]进行比较，结果如表4和表5所示。

表4 4种算法对拉压弹簧设计问题的最优结果比较

表5 不同算法对拉压弹簧设计问题的寻优统计结果比较

从表4和表5可以看出：对于拉力/压力弹簧结构设计优化问题，与其他3种算法相比，IFA求得了最优的结果。与CDE算法相比，IFA获得了较好的最优结果，而CDE算法则得到了较好的平均结果、最差结果和相似的标准差。与CPSO算法和AATM算法相比，IFA获得了较好的最优结果、平均结果、最差结果和标准差。

5 结论

1) 提出一种基于动态随机局部搜索和多样性变异的改进萤火虫算法。该算法利用动态随机局部搜索以加快算法的收敛速度，引入多样性变异操作以避免算法陷入局部最优。

2) 该算法比同类算法在搜索能力和搜索效率两方面均有较大的提高。最后将该算法应用于求解2个实际工程设计优化问题，获得了较满意的结果。

[1] Pan Q, Suganthan P, Wang L, et al. A differential evolution algorithm with self-adapting strategy and control parameters[J]. Computers & Operations Research, 2011, 38(1): 394−408.

[2] Long W, Liang X, Huang Y, et al. A hybrid differential evolution augmented Lagrangian method for constrained numerical and engineering optimization[J]. Computer-Aided Design, 2013, 45(12): 1562−1574.

[3] Yang X. Firefly algorithms for multimodal optimization[C]// Proceedings of the International Conference on Stochastic Algorithms: Foundations and Applications. Beilin: Springer-Verlag, 2009: 169−178.

[4] Pal S, Rai C, Singh A. Comparative study of firefly algorithm and particle swarm optimization for noisy non-linear optimization problems[J]. International Journal of Intelligent Systems and Applications, 2012, 4(10): 50−57.

[5] Yang X, Hosseini S, Gandomi A. Firefly algorithm for solving non-convex economic dispatch problems with value loading effect[J]. Applied Soft Computing, 2012, 12(3): 1180−1186.

[6] Gandomi A, Yang X, Alavi A. Mixed variable structural optimization using firefly algorithm[J]. Computers and Structures, 2011, 89: 2325−2336.

[7] Kumbharana S, Pandey M. Solving traveling salesman problem using firefly algorithm[J]. International Journal for Research in Science & Advanced Technologies, 2013, 2(2): 53−57.

[8] Liu B, Wang L, Jin Y, et al. Improved particle swarm optimization combined with chaos[J]. Chaos, Solis & Fractals, 2005, 25(5): 1261−1271.

[9] Hamzacebi C. Improving genetic algorithms’ performance by local search for continuous function optimization[J]. Applied Mathematics and Computation, 2008, 196(1): 309−317.

[10] Wang Y, Cai Z, Zhou Y, et al. Constrained optimization based on hybrid evolutionary algorithm and adaptive constraint−handling technique[J]. Structural Multidiscipline Optimization, 2009, 37(4): 395−413.

[11] Deb K. An efficient constraint handling method for evolutionary optimization[J]. Computers Methods in Applied Mechanics and Engineering, 2000, 186(2/3/4): 311−338.

[12] Runarsson T, Yao X. Stochastic ranking for constrained evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2000, 4(3): 284−294.

[13] Gandomi A, Yang X, Talatahari S, et al. Coupled eagle strategy and differential evolution for unconstrained and constrained global optimization[J]. Computers and Mathematics with Applications, 2012, 63(1): 191−200.

[14] Deshpande A, Phatnani G, Kulkarni A. Constraint handling in firefly algorithm[C]//Proceedings of IEEE International Conference on Cybernetics. Lausame, Switzerland: IEEE Press, 2013: 186−190.

[15] Huang F, Wang L, He Q. An effective co-evolutionary differential evolution for constrained optimization[J]. Applied Mathematics and Computation, 2007, 186(1): 340−356.

[16] He Q, Wang L. An effective co-evolutionary particle swarm optimization for constrained engineering design problems[J]. Engineering Applications of Artificial Intelligence, 2007, 20(1): 89−99.

[17] 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.

[18] Wang Y, Cai Z, Zhou Y. Accelerating adaptive trade-off model using shrinking space technique for constrained evolutionary optimization[J]. International Journal for Numerical Methods in Engineering, 2009, 77(11): 1501−1534.

(编辑 杨幼平)

Firefly algorithm for solving constrained optimization problems and engineering applications

LONG Wen1, CAI Shaohong1, JIAO Jianjun1, CHEN Yixiong2, HUANG Yafei2

(1. Guizhou Key Laboratory of Economics System Simulation, Guizhou University of Finance and Economics, Guiyang 550004, China; 2. School of Information Science and Engineering, Central South University, Changsha 410083, China)

Firefly algorithm (FA) has a few disadvantages in the global searching, including slow convergence speed and high possibility of being trapped in local optimum. An improved FA was proposed to solve constrained optimization problems. Firstly, chaotic sequence was used to initiate firefly position. Secondly, dynamic random local search technique was introduced to improve speed of convergence; thirdly, a diversity mutation operator was given on the global optimum of each generation, thus the algorithm could effectively jump out of local minima. The experimental results and comparisons with other meta-heuristic methods using a set of numerical and engineering optimization problems show that the proposed algorithm is an effective method.

firefly algorithm; constrained optimization problem; dynamic random local search; engineering optimization

10.11817/j.issn.1672-7207.2015.04.013

TP273

A

1672−7207(2015)04−1260−08

2014−04−22；

2014−06−22

国家自然科学基金资助项目(61463009)；贵州省科学技术基金资助项目(黔科合J字[2013]2082号)(Project (61463009) supported by the National Natural Science Foundation of China; Project ([2013]2082) supported by the Science Technology Foundation of Guizhou Province, China)

龙文，博士，教授，从事进化计算、系统建模与优化控制研究；E-mail：lw084601012@163.com