单纯形法的改进萤火虫算法及其在非线性方程组求解中的应用

莫愿斌，马彦追，郑巧燕，袁伟军（.广西民族大学信息科学与工程学院，广西南宁530006；.广西混杂计算与集成电路设计分析重点实验室，广西南宁530006）

单纯形法的改进萤火虫算法及其在非线性方程组求解中的应用

莫愿斌1，2，马彦追1，郑巧燕1，袁伟军2
（1.广西民族大学信息科学与工程学院，广西南宁530006；2.广西混杂计算与集成电路设计分析重点实验室，广西南宁530006）

萤火虫算法（FA）是一种基于群体搜索的启发式随机优化算法，其模拟自然界中萤火虫利用发光的生物学特性而表现出来的社会性行为。针对萤火虫算法存在着收敛速度慢、易陷入局部最优、求解精度低等不足，利用单纯形法局部搜索速度快和萤火虫算法全局寻优的特点，提出一种基于单纯形法的改进型萤火虫算法（SMFA）。通过对标准测试函数以及非线性方程组的实验仿真，并与其他算法进行的对比分析表明，改进后的算法在函数优化方面有较强的优势，在一定程度上有效地避免了陷入局部最优，提高了搜索的精度。

萤火虫算法；单纯形法；函数优化；非线性方程组

萤火虫算法（firefly algorithm，FA）是在2008年由英国剑桥学者Yang提出的一种启发式智能优化方法［1⁃2］，其基本思想来源于萤火虫成虫利用发光的生物学特性而表现出来的觅食、求偶、警戒等社会性行为。算法提出后，受到国内外许多学者的关注和研究，并且已经成功应用于组合优化［3］、路径规划［4］、图像处理［5］、经济调度［6］等领域。与其他优化算法类似，基本FA算法的随机性较大，且存在收敛速度慢、求解精度不高的问题。为此，国内外学者对该算法进行不少的研究，刘长平［7］通过逻辑自映射函数产生混沌序列，引入到萤火虫算法中对精英个体进行混沌优化，同时动态收缩搜索空间以加快收敛速度；S.M.Farahani［8］在每一次迭代中通过高斯分布使所有萤火虫向全局最优的萤火虫移动来增加算法的收敛速度；X.S.Yang［9］在基本萤火虫算法中加入Levy飞行移动策略，增强了算法的寻优性能；A.Gandomi［10］把12种混沌映射引入到萤火虫算法中，并分析了不同的混沌映射对于标准函数优化的影响；M.Subutic［11］提出了一种求解非约束优化问题的并行萤火虫算法；A.Abdullah［12］提出了一种混合进化萤火虫算法，它把差分进化算法的进化操作融入到萤火虫算法中，改善了算法的搜索精度和萤火虫之间的信息共享；S.Farahani［13］提出了3种改进基本萤火虫的方法：1）利用学习自动机影响吸收因子和随机化参数，2）将遗传算法和萤火虫算法混合，3）根据高斯分布随机移动以保证萤火虫遍布整个搜索空间；冯艳红［14］提出一种基于混沌理论的动态种群萤火虫算法，提高了算法的全局收敛能力。上述改进的算法虽然取得了一定的效果，但算法在收敛性、稳健性方面还有改进的空间。

本文从提高个体的多样性角度出发，通过在萤火虫算法中引入单纯形法的反射、扩张、压缩操作对较差位置的萤火虫作改进，提高个体的多样性，避免其陷入局部最优，以提高算法的求解精度。通过对标准测试函数以及非线性方程组的实验仿真，并与其他算法进行的对比分析表明了文中提出的基于单纯形法的萤火虫算法具有较强的跳出局部极值能力和较高的计算精度。

1 单纯形法的萤火虫算法

1.1 基本萤火虫算法

在自然界中，大约存在2 000多种萤火虫，大多数种类都会发出其独特的荧光，目前对萤火虫发光的真实目的还不清楚，一般认为萤火虫利用闪光信号来吸引异性或者是吸引潜在的猎物，实现求偶或觅食的目的。萤火虫算法就是模拟这种发光的生物学特性而表现出来的社会性行为而设计的随机优化算法。在萤火虫算法中存在2个关键的要素：自身亮度和吸引度。自身亮度反映了萤火虫位置的优劣，亮度小的萤火虫会被亮度大的吸引，并向亮度大的萤火虫方向移动，吸引度影响着萤火虫所要移动的距离，通过萤火虫的移动，每个个体自身亮度和吸引度得到不断更新，最终实现目标优化的目的［2］。

在萤火虫算法中［1］，萤火虫吸引度的大小和亮度的大小是成正比的，亮度由目标函数决定。一个萤火虫在坐标为X的位置，它的亮度I可以取I（X）＝f（X），X的位置越好，它的亮度就越大，它对其他个体的吸引度随着它们之间距离的增加而变小，另外在荧光传输的过程中，会被传播介质吸收一部分，所以吸引度的大小还和介质吸收因子有关。因此，一个萤火虫对距离其r处的亮度I称为相对亮度。

式中：I0是萤火虫对距离其r＝0处的荧光亮度，γ是介质吸收因子，rij是萤火虫i到萤火虫j的欧式距离。萤火虫的吸引度β被定义为

式中：β0为萤火虫对距离r＝0处的吸引度，βmin为最小吸引度，βmin＝0.2。萤火虫i被萤火虫j吸引的移动公式为

式中：xi、xj分别表示萤火虫i和j的位置，α为步长因子，rand表示［0，1］上服从均匀分布的随机因子。为使算法效果更好，在式中用αSk来代替α，其中Sk表示空间规模参数，并使α随着迭代次数的增加逐渐的减小，其更新公式为

α＝α（10＾（－4）／α0）＾（1／N Gen）

式中：α0选0.9，N Gen表示最大迭代次数。

1.2 单纯形法策略

为提高萤火虫算法的搜索性能，本文引入传统的单纯形法策略［15⁃16］，在一次迭代完成之后，利用单纯形法搜索策略，选择K个位置较差的萤火虫进行优化。单纯形法是指在一个空间中构造一个多面体，求出多面体各个顶点的适应值并作比较，找出最优点、次优点以及最差点，通过反射、压缩、扩张等操作更新最差点，形成一个新的多面体。它是一种局域的搜索方法，具有简单易用、适用范围广、收敛速度快的特点。假设较差萤火虫的位置为xs，xc为最优位置和次优位置的中心。

反射操作：xr＝xc＋δ（xc－xs），xr为反射点，反射系数δ通常取1。

扩张操作：xt＝xc＋φ（xs－xc），xe为扩张点，扩张系数φ通常取2。

压缩操作：xt＝xc＋φ（xs－xc），xt为压缩点，压缩系数φ通常取0.5。

收缩操作：xw＝xc－φ（xs－xc），xw为收缩点，收缩系数与压缩系数相同。

单纯形法的步骤如下：

1）计算所有搜索点的目标函数值，找到最优点xg，次优点xb，对应的目标函数分别记为f（xg）、f（xb），计算它们的中心位置：xc＝（xg＋xb）／2。

2）找出若干个较差萤火虫的位置，取其中一个记为xs，目标函数值记为f（xs）。将xs执行反射操作，得到反射点xr。

3）如果f（xr）＞f（xg），说明反射方向正确，执行扩张操作得到扩张点xe，如果f（xe）＞f（xg），则用xe取代xs，否则，用xr取代xs。

4）如果f（xr）＜f（xs），说明反射方向更差，执行压缩操作得到压缩点xt，如果f（xt）＞f（xs），则用xt取代xs。

5）如果f（xs）＜f（xr）＜f（xg），执行收缩操作得到收缩点xw，如果f（xw）＞f（xs），则用xw取代xs，否则，用xr取代xs。

图1 单纯形法搜索Fig.1 The searching of sim p lex method

1.3 基于单纯形法的萤火虫算法

从上面的分析可以看出，萤火虫算法和其他的算法一样存在步长因子α和吸引度β的确定不易性问题，定得小了，局部搜索的精度提高，但要实现整体区域的搜索所需的时间必定会长；而若定得大了，则搜索精度不高。因此，在萤火虫算法的搜索过程中，通过其他方式增加算法的局部的搜索机制是一个改进算法性能的思考方向。为此，拟结合以单纯形法的局部性能改进萤火虫算法性能。通过在算法过程中，以适当的方式增加单纯形法的局部搜素，提高萤火虫算法的局部性能。

1.4 基于单纯形法的萤火虫算法流程

1）初始化算法的参数，萤火虫数目m，步长因子α0，最大吸引度β0，最小吸引度βmin，介质吸收因子γ，最大迭代次数Tmax；

2）随机初始化m个萤火虫的位置Xi（i＝1，2，..，m），计算各自的目标值作为自己的最大亮度I0；

3）根据式（1）、（2）计算各个萤火虫之间的相对亮度I和吸引度β，依照I的大小确定萤火虫的移动方向；

4）利用式（3）对萤火虫的位置进行更新，随机扰动处在最好位置的萤火虫；

5）根据上述单纯形法的步骤来更新较差萤火虫的位置，重新计算更新后萤火虫的亮度；

6）判断是否满足结束条件，若是，转到7），否则转3），进入下一次搜索；

7）输出最优位置和最优解。

2 仿真实验

本文对14个标准测试函数和2个非线性方程组进行仿真测试来证明SMFA算法的性能。实验仿真在MATLAB 2012a上实现。参数设置：SMFA中，种群规模为N＝20，每次用单纯形策略优化的萤火虫个数取K＝10，步长因子α0＝0.9，最大吸引度β0＝1，最小吸引度βmin＝0.2，介质吸收因子γ＝1，最大迭代次数为200。PSO算法中设置的种群大小为400，GA算法利用的是GATOOL工具箱，设置的交概率为0.95，变异概率为0.05，种群规模为1 000。

2.1 标准函数测试

对每个函数独立运行20次，表1列出了标准测试函数的搜索空间、维数以及最优值等参数；表2列出了20次实验得到的最好值、最差值、平均值以及标准差，并与GA、FA、PSO进行比较。为了直观地反映出算法的寻优效果，给出了函数的收敛曲线图，如图2～15。

表1 测试函数及参数取值Table 1 The test function and its parameter value

表2 不同算法的测试结果对比Table 2 Com parison of experiments results of different algorithm s

续表1

图2 函数f1（x）的收敛曲线图Fig.2 Convergence curve of function 1

图3 函数f2（x）的收敛曲线图Fig.3 Convergence curve of function 2

图4 函数f3（x）的收敛曲线图Fig.4 Convergence curve of function 3

图5 函数f4（x）的收敛曲线图Fig.5 Convergence curve of function 4

图6 函数f5（x）的收敛曲线图Fig.6 Convergence curve of function 5

图7 函数f6（x）的收敛曲线图Fig.7 Convergence curve of function 6

图8 函数f7（x）的收敛曲线图Fig.8 Convergence curve of function 7

图9 函数f8（x）的收敛曲线图Fig.9 Convergence curve of function 8

图10 函数f9（x）的收敛曲线图Fig.10 Convergence curve of function 9

图11 函数f10（x）的收敛曲线图Fig.11 Convergence curve of function 10

图12 函数f11（x）的收敛曲线图Fig.12 Convergence curve of function 11

图13 函数f12（x）的收敛曲线图Fig.13 Convergence curve of function 12

图14 函数f13（x）的收敛曲线图Fig.14 Convergence curve of function 13

图15 函数f14（x）的收敛曲线图Fig.15 Convergence curve of function 14

从表2中的结果可以看出，SMFA与GA、PSO、FA相比，SMFA有更好的搜索最优值能力，所得到的结果更加接近标准值。对于单峰函数f1，SMFA的求解精度比FA提高2个数量级。对于函数f2，SMFA的求解精度最高，比GA、PSO高了3个数量级，比FA提高了2个数量级。对于单峰函数f3，SMFA的求解精度最高，平均求解精度比GA、PSO、FA都提高了2个数量级。对于函数f4，GA没能找到理想值，SMFA的求解精度最高，比FA提高了5个数量级，比PSO提高了4个数量级。对于多峰函数f5，SMFA的最优值求解精度达到e－5，平均的求解精度比GA、PSO、FA都提高了一个数量级。对于函数f6，SMFA的最优值求解精度达到e－7，平均求解精度比FA提高了5个数量级，GA和PSO在最大迭代次数内没有找到最优解。对于多峰函数f7，GA的求解效果最好，FA、SMFA、PSO都不能得到理想最优解，相比较而言，SMFA比FA、PSO求解效果要好。对于多峰函数f8，SMFA的求解精度最高，平均求解精度比FA提高一个数量级，比GA提高2个数量级，比PSO提高3个数量级。对于多峰函数f9，它是一个二维函数，PSO求解的最优值为0，其求解精度明显高于SMFA、FA和GA，SMFA、FA和GA的求解精度相同。对于函数f10，SMFA的标准差比FA的标准差提高了5个数量级，说明了SMFA有着更强的鲁棒性和稳定性。对于函数f11，GA和FA无法在迭代次数内找出最优解，SMFA的求解精度达到e－6，比PSO提高4个数量级。对于函数f12，SMFA的求解精度最高，最优值求解精度达到e－19，平均求解精度比FA提高5个数量级，比GA、PSO提高4个数量级。对于函数f13，SMFA的性能明显优于FA，标准差远远高于FA，说明SMFA更稳定。对于函数f14，PSO没有找到理想值，SMFA的最优值求解精度比FA高出2个数量级。从上面的数据也可以看出，SMFA在高维空间的搜索能力比PSO更强。从图2～15可以直观地看出，SMFA能够跳出局部最优，使得求解的精度更高，它的搜索性能要强于其他算法。

2.2 非线性方程组测试

方程组1［15］

测试结果［16－17］：

表3 不同算法求解方程组1的统计结果Table 3 Statistical results of each algorithm for equations 1

方程组2［47］

测试结果［16－17］：

表4 不同算法求解方程组2的统计结果Table 4 Statistical results of each algorithm for equations 2

从表格3和表格4的结果可以看出，FA和SMFA相比较牛顿法、Effati算法、进化算法来说，求出的结果更接近理论最优值。SMFA比FA有更高的求解精度。

3 结束语

本文针对基本萤火虫算法存在易陷入局部最优、求解精度低的不足，提出了一种基于单纯形法的萤火虫算法（SMFA）。算法中通过单纯形搜索策略对较差位置的萤火虫作改进，有效地避免了算法陷入局部最优。通过对标准函数和非线性方程组的仿真实验，证明了SMFA算法的有效性和可行性，在跳出局部最优能力、求解精度以及鲁棒性方面都要优于基本的FA算法。关于算法的收敛性证明以及算法的应用是进一步要做的工作。

［1］YANG X S.Nature⁃inspired metaheuristic algorithms［M］.［S.l.］：Luniver Press，2008：1⁃30.

［2］YANG X S.Firefly algorithms for multimodal optimization［C］／／Stochastic Algorithms：Foundations and Applications.Sapporo，Japan，2009，5792：169⁃178.

［3］SAYADIM K，RAMEZANIAN R，GHAFFARI⁃NASAB N.A discrete firefly meta⁃heuristic with local search for make span minimization in permutation flow shop scheduling prob⁃ lems［J］.International Journal of Industrial Engineering Computations，2010，1（1）：1⁃10.

［4］BANDA M，SRIVASTAVA P R，YANG X S，et al.Opti⁃mal test sequence generation using firefly algorithm［J］.Swarm and Evolutionary Computation，2013，8：44⁃53.

［5］HORNG M H，LIOU R J.Multilevelminimum cross entropy threshold selection based on the firefly algorithm［J］.Expert Systems with Applications，2011，38：14805⁃14811.

［6］郭丽萍，李向涛，谷文祥.改进的萤火虫算法求解阻塞流水线调度问题［J］.智能系统学报，2013，8（1）：33⁃38.GUO Liping，LIXiangtao，GUWenxiang.An improved fire⁃fly algorithm for the blocking flow shop scheduling problem［J］.CAAI Transactions on Intelligent Systems，2013，8（1）：33⁃38.

［7］刘长平，叶春明.具有混沌搜索策略的萤火虫优化算法［J］.系统管理学报，2013，4：538⁃543.LIU Changping，YE Chunming.Firefle algorithm with chaot⁃ic search strategy［J］.Journal of Systems＆Management，2013，22（4）：538⁃543.

［8］FARAHAN S M，ABSHOURI A，NASIRI B，et al.A Gaussian firefly algorithm［J］.International Journal of Ma⁃chine Learning and Computing，2011，1（5）：448⁃454.

［9］YANG X S.Firefly algorithm，levy flights and global optimi⁃zation［C］／／Research and Development in Intelligent Syste⁃msXXVI.Berlin，Germany，2010：209⁃218.

［10］GANDOMIA，YANG X S，TALATAHARIS，etal.Firefly algorithm with chaos［J］.Communications in Nonlinear Sci⁃ence and Numerical Simulation，2013，18（1）：89⁃98.

［11］SUBUTIC M，TUBA M，STANAREVIC N.Parallelization of the firefly algorithm for unconstrained optim ization prob⁃lems［J］.Latest Advances in Information Science and Ap⁃plications，2012，22（3）：264⁃269.

［12］ABDULLAH A，DERIS S，MOHAMAD M，et al.A new hybrid firefly algorithm for complex and nonlinear problem［J］.Distributed Computing and Artificial Intelligence，2012，14（4）：673⁃680.

［13］FARAHANIS，ABSHOURIA，NASIRIB，et al.Some hy⁃brid models to improve firefly algorithm performance［J］.International Journal of Artificial Intelligence，2012，8（12）：97⁃117.

［14］冯艳红，刘建芹，贺毅朝.基于混沌理论的动态种群萤火虫算法［J］.计算机应用，2013，33（3）：796⁃805.FENG Yanhong，LIU Janqin，HE Yichao.Chaos⁃based dy⁃namic population firefly algorithm［J］.Journal of Computer Applications，2013，33（3）：796⁃805.

［15］张红霞，罗毅，师瑞峰.基于单纯形法的改进型人工鱼群算法［J］.计算机应用，2011，31（5）：1321⁃1327.ZHANG Hongxia，LUO Yi，SHI Ruifeng.Artificial fish swarm algorithm based on simplex method［J］.Journal of Computer Applications，2011，31（5）：1321⁃1327.

［16］曲良东，何登旭，黄勇.自适应改进和声—单纯形进化算法研究［J］.计算机应用研究，2013，30（3）：676⁃678. QU Liangdong，HE Dengxu，HUANG Yong.Research on adaptive improved harmony—simplex evolutionary algorithm［J］.Application Research of Computers，2013，30（3）：676⁃678.

［17］GROSAN C，ABRAHAM A.A new approach for solving nonlinear equations systems［J］.IEEE Trans Systems and Humans，2008，38（3）：698⁃714.

莫愿斌，男，1969年生，副教授，博士，主要研究方向为智能信息处理与应用。

补充一些学术成就及论文发表情况

马彦追，男，1987年生，硕士研究生，主要研究方向为计算智能。

郑巧燕，女，1989年生，硕士研究生，主要研究方向为计算智能。

Improved firefly algorithm based on simp lex method and its app lication in solving non⁃linear equation groups

MO Yuanbin1，2，MA Yanzhui1，ZHENG Qiaoyan1，YUANWeijun2
（1.College of Information Science and Engineering，GuangxiUniversity for Nationalities，Nanning 530006，China；2.Guangxi Key La⁃boratory of Mixed Computing Integrated Circuit Design and Analysis，Nanning 530006，China）

The firefly algorithm（FA）is a heuristic random optimization algorithm based on groupization.It simu⁃lates the social behavior of firefly in the natural environment represented in its biological characteristics of shining.FA has disadvantages in global searching，such as slow convergence speed，high possibility of being trapped in lo⁃cal optimum and low solving precision.An improved FA based on the simplex method is proposed.The proposed method combines the characteristics of speedy local search of simplexmethod with the global optimization of firefly algorithm.The simplexmethod modifies the firefly，which is located at poor positions through its reflection，expan⁃sion and compression operation.However，it improves the diversity of individuals and avoids falling into local opti⁃mum and improves the precision of the algorithm.The results showed that through simulations of standard bench⁃mark functions and nonlinear functions and contrasted with other algorithms，the improved algorithm has a strong advantage in function optimization.It also avoids trapping in local optimum and improves the calculation accuracy to a certain extent.

firefly algorithm；simplexmethod；function optimization；non⁃linear equation groups

TP18

A

1673⁃4785（2014）06⁃0747⁃09

莫愿斌，马彦追，郑巧燕，等.单纯形法的改进萤火虫算法及其在非线性方程组求解中的应用［J］.智能系统学报，2014，9（6）：747⁃755.

英文引用格式：MO Yuanbin，MA Yanzhui，ZHENG Qiaoyan，et al.Improved firefly algorithm based on sim plexmethod and its ap⁃plication in solving non⁃linear equation groups［J］.CAAITransactions on Intelligent Systems，2014，9（6）：747⁃755.

10.3969／j.issn.1673⁃4785.201309075

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1673⁃4785.201309075.htm l

2013⁃09⁃25.

日期：2014⁃09⁃30.

国家自然科学基金资助项目（21466008）；广西民族大学科研资助项目（2014MDYB030）.

莫愿斌.E⁃mail：674148582＠qq.com.