DOI: 10.11817/j.issn.1672-7207.2015.04.013

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

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

(1. 贵州财经大学 贵州省经济系统仿真重点实验室，贵州 贵阳，550004；

2. 中南大学 信息科学与工程学院，湖南 长沙，410083)

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

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

中图分类号：TP273             文献标志码：A         文章编号：1672-7207(2015)04-1260-08

Firefly algorithm for solving constrained optimization problems and engineering applications

LONG Wen¹, CAI Shaohong¹, JIAO Jianjun¹, CHEN Yixiong², HUANG Yafei²

(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)

Abstract: 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.

Key words: firefly algorithm; constrained optimization problem; dynamic random local search; engineering optimization

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

          (1)

式中：为目标函数；为n维决策变量；为不等式约束；p为不等式约束的

个数；为等式约束；m-p为等式约束的个数；l_i和u_i分别为决策变量x_i的上界和下界。等式约束通常可以转化为和这2个不等式约束来处理，δ是1个很小的正数。由于问题(1)目标函数和约束条件通常具有高度非线性或具有离散的搜索区域，传统的基于梯度信息的优化方法难以对其进行有效求解。与传统的优化方法相比，以遗传算法等为代表的进化算法是一类基于种群迭代的启发式搜索方法，具有原理简单、容易实现、能以较大概率收敛到问题的全局最优解等特点，因此，在函数优化、组合优化、机器学习等诸多领域中有着广泛的应用^[1]。鉴于进化算法是一类基于无约束优化的搜索技术，利用其求解问题(1)时一定要结合一种合适的约束处理技术。常用的基于进化算法的约束处理技术有惩罚函数法、分离可行解与不可行解法、多目标法等。在过去的10多年中，出现许多约束优化进化算法^[2]。萤火虫算法(firefly algorithm, FA)是Yang^[3]于2009年提出的一种新型进化算法，其思想是模拟自然界中萤火虫的发光行为，即通过萤火虫总是朝向更亮的区域飞去实现进化。FA已被证明在求解精度和稳定性方面都超过了其他进化算法如粒子群优化算法^[4]。由于FA具有容易实现、稳定性强和全局寻优能力较强等优点，因此，在许多领域中有着广泛的应用。Yang等^[5]将FA应用于求解经济调度问题。Gandomi等^[6]利用FA求解具有混合变量的结构优化设计问题。Kumbharana等^[7]将FA用于求解旅行商问题，得到了较好的结果。尽管FA在许多领域中得到了成功的应用，但其存在对初始解分布的依赖性、后期收敛速度慢、求解精度低和易陷入局部最优等缺点，因此，本文作者提出一种改进的FA用于求解约束优化问题。该算法首先利用混沌序列构造初始种群以维持其多样性。其次，引入动态随机局部搜索算法对当前最优解进行局部搜索，以加快算法的收敛速度。以一定概率对当前全局最优解进行多样性变异以避免算法陷入局部最优。几个标准约束优化测试函数的实验结果表明该算法的有效性。最后将该算法应用到2个实际工程应用问题中。

1  基本萤火虫算法

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

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

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

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

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

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

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

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

Step 3  计算萤火虫的吸引度。先确定萤火虫与萤火虫j之间的距离r_ij：

        (2)

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

萤火虫的吸引度β为

                 (3)

式中：为r_ij=0时的吸引度；为荧光吸收系数。

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

    (4)

其中：表示第i只萤火虫在第t代的位置；α为随机步长，且满足；表示随机数。

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

          (5)

其中：为第t代群体中的全局最优位置。

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

2  改进萤火虫算法

2.1  种群初始化

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

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

           (6)

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

将决策变量按下式映射为[0,1]之间的混沌变量：

          (7)

其中：和分别为第j维变量的搜索上、下界。

将混沌变量利用下式计算得到下步迭代的混沌变量：

        (8)

最后将混沌变量按下式转化为决策变量：

       (9)

2.2  动态随机局部搜索

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

Step 1  设定局部搜索代数E，搜索步长上限α₀，对于每一个搜索步长α_t的最大迭代次数为M，，A_epoch = 0，k=0。

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

Step 3  产生随机向量dx，且；

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

Step 5  。

若，则， ，m=m+1，转Step 7；

若，则，，m=m+1，转Step 7。

Step 6  。

若，则， ，m=m+1，转Step 7；

若，则， ，m=m+1，转Step 7。

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

Step 8  k=k+1。

Step 9  。

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

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

2.3  多样性变异策略

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

假设某个体为，以概率1/n随机从个体x中选择一个元素，然后在范围内随机产生1个实数替代个体中的元素x_k，从而产生一个新的个体。多样性变异算子如下：

           (10)

其中：。

2.4  约束处理技术

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

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

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

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

 (11)

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

2.5  算法步骤

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

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

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

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

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

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

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

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

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

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

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

3  数值实验与比较分析

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

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

；

。

其中：；。

G2:

其中：。

其中：；(i=10，11，12)和。

G4:

其中：。

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

利用IFA求解上述4个约束优化问题，其参数设置如下：种群规模N=50，最大吸引度β₀=0.20，吸收系数γ=1，随机步长α=0.25，动态随机局部搜索迭代次数E=100，对于每一个搜索步长α_t的最大迭代次数M=10，变异概率p_m=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可知：对于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  IFA和其他6种算法对4个约束优化问题的寻优结果比较

Table 1  Comparison of statistical results of IFA with respect to six other algorithms for 4 functions

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

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

Fig. 1  Convergence graph for function G1

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

Fig. 2  Convergence curve for function G2

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

Fig. 3  Convergence curve for function G3

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

Fig. 4  Convergence curve for function G4

4  IFA在工程优化中的应用

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

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

焊接梁结构设计优化的目标是在一定约束条件下使其总成本最小。焊接梁的结构如图5所示，它有4个设计变量，分别为h(x₁)，l(x₂)，t(x₃)和b(x₄)，约束变量为梁上的弯曲应力σ、剪应力τ、压曲临界载荷P_c和梁的尾端误差δ。

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

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

Fig. 5  Schematic view of welded beam design problem

其中：

；

；；；

；；。

；；；；

；；。

4个变量的取值范围为0.1≤x₁≤2.0，0.1≤x₄≤2.0，0.1≤x₂≤10.0，0.1≤x₃≤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和表3可知：对于焊接梁结构设计优化问题，IFA求得的最优解为1.724 894，仅略差于MBA的最优解。与CDE算法和CPSO算法相比，IFA获得了较好的最优结果、平均结果、最差结果和标准差。

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

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

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

Table 2  Comparison of the best solution for welded beam design problem found by different algorithms

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

Table 3  Statistical results of different approaches for welded beam design problem

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

Fig. 6  Schematic view of spring design problem

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

其中：；；。

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

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

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

Table 4  Comparison of the best solution for spring design problem found by different algorithms

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

Table 5  Statistical results of different approaches for spring design problem

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.

(编辑  杨幼平)

收稿日期：2014-04-22；修回日期：2014-06-22

基金项目(Foundation item)：国家自然科学基金资助项目(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