單純形法的改進螢火蟲算法及其在非線性方程組求解中的應用

莫愿斌，馬彥追，鄭巧燕，袁偉軍（.廣西民族大學信息科學與工程學院，廣西南寧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.