混沌果蠅優化算法研究

吳經緯，楊 靖，龍道銀，王 霄，覃 濤，余玲珍

（1.貴州大學 電氣工程學院，貴州 貴陽 550025；2.中國電建集團貴州工程有限公司，貴州貴陽 550001）

0 引言

果蠅優化算法（Fruit Fly Optimization Algorithm，FOA）由潘文超于2011 年提出，是一種模仿果蠅覓食行為而推演的智能群體算法［1］。與其它群體智能算法相比，FOA 具有尋優機制簡單、容易理解、程序代碼易于實現和所需調整的參數較少［2］等優點。當前，FOA 已成功應用于傳感器網絡節點定位［3］、股票價格預測模型［4］、光伏發電功率預測［5］和路徑覆蓋測試［6］等方面。

FOA 算法由于優化過程中的隨機性，在搜尋過程中存在盲目搜索，會導致算法早熟收斂、陷入局部最優等不足。與其它典型群智能算法類似，FOA 算法相關參數設置決定了該算法性能。在近幾年研究中，劉曉悅等［7］利用Logistic混沌搜索初始化果蠅群位置，提高了初始解的隨機性和遍歷性，從而提高FOA 初始種群的多樣性；戰非等［8］通過Lo?gistic 映射對算法初值進行優化，改進果蠅算法對初值的敏感性和不穩定性；時文峰等［9］引入混沌序列Logistic 映射以改進果蠅算法早熟收斂問題；張小平等［10］引入Logistic映射，解決果蠅算法早熟收斂問題。

上述基于混沌的改進算法盡管優化了FOA 算法性能，但是采用的是Logistic 映射，而該映射在［0，0.1］和［0.9，1］兩個區域內有較高的取值率，因此該映射遍歷不均勻性導致算法收斂速度較慢，造成算法執行效率降低。本文提出一種基于混沌映射Sinusoidal 的果蠅優化算法SFOA。①設計了一個與混沌相結合的參數α，通過提高種群位置的多樣性以改善算法全局搜索能力；②將引入混沌參數α的改進FOA 算法與其它4 種混沌映射相結合，通過仿真實驗，對比分析后得到最優算法，即SFOA 算法；③將混沌果蠅算法SFOA 與其它果蠅優化算法在7 種基本測試函數上相比較，仿真結果表明本文提出的改進果蠅優化算法具有更好的尋優精度和更快的收斂速度。

1 基本果蠅優化算法

果蠅優化算法（FOA）是一種源于果蠅覓食行為演化而來的新的全局優化進化算法。果蠅擁有在嗅覺和視覺上優于其它物種的特性，果蠅群體通過嗅覺有效地收集漂浮在空氣中的各種氣味，并往食物的方向靠近，然后利用敏銳的視覺辨別食物和同伴的位置，往食物味道濃度高的位置聚合，再利用嗅覺各自沿隨機方向飛出以尋找食物，如此循環直到找到食物為止［11］。

FOA 可以總結為7 個步驟：

步驟1：初始化種群規模數sizepop、最大迭代數Maxgen和隨機初始化果蠅群體位置X_axis、Y_axis。

步驟2：為果蠅方向和距離分配隨機參數，產生新位置。

步驟3：估算果蠅與原點之間的距離Disti，再計算味道濃度判定值Si。

步驟4：將Si分別代入味道濃度判定函數，求出果蠅位置味道濃度Smelli。

步驟5：尋找該果蠅群體中味道濃度（適應度）最佳的果蠅個體。

步驟6：根據最佳果蠅位置，此時所有果蠅利用視覺向最佳位置飛去。

步驟7：最后迭代運算，重復步驟2—步驟5，在尋優過程中判斷當前最佳味道濃度是否優于上一迭代結果，且判斷當前迭代次數是否小于最大迭代數；若是則執行步驟6，否則結束。

2 混沌果蠅優化算法

2.1 混沌優化

果蠅群體位置對收斂速度和尋優結果有重大影響，基本果蠅優化算法的初始果蠅種群是隨機的，在處理復雜非線性問題時，效果往往不太理想［12］。混沌是一種按照特定規律運行的非線性現象，具有較大的隨機性和遍歷性，利用混沌搜索的這些特性在生成果蠅種群位置時提高其多樣性。為了提高FOA 的收斂速度和尋優精度，引入了一個由混沌優化的新參數α用于更新果蠅種群，相較于原公式可有效降低其尋優過程中陷入局部最優的可能，將式（2）改為：

式中，Xi,j、Yi,j為當前果蠅個體位置，Xj、Yj為當前最佳果蠅位置，SP為種群數量，n為維度。

2.2 SFOA 算法步驟

基于基本果蠅優化算法原理及上述改進方法，本文提出的混沌優化果蠅算法具體步驟如下：

步驟1：初始化種群規模sizepop、最大迭代次數Maxgen、維度n，根據式（1）確定隨機種群位置等。

步驟2：估算果蠅與原點之間的距離Disti，再計算味道濃度判定值Si。

步驟3：將Si分別代入味道濃度判定函數，求出果蠅位置味道濃度Smelli。

步驟4：尋找該果蠅群體中味道濃度（適應度）最佳的果蠅個體。

步驟5：根據最佳果蠅位置，此時所有果蠅利用視覺向最佳位置飛去。

步驟6：根據式（8）對果蠅種群位置進行更新后再進行迭代運算，重復步驟2—步驟5，在尋優過程中判斷當前最佳味道濃度是否優于上一迭代結果，且判斷當前迭代次數是否小于最大迭代數；若是則執行步驟5，否則結束。

SFOA 算法運行偽代碼如下：

3 仿真實驗與結果分析

3.1 實驗設計

為了驗證基于混沌映射的改進果蠅算法SFOA 的優化性能，4 種混沌映射名稱及表達式如表1 所示。本文對7個基準測試函數進行了求最小值問題的優化仿真實驗，測試函數如表2 所示。

Table 1 Four chaotic maps表1 4 種混沌映射

Table 2 Test functions and parameter setting表2 測試函數及參數設定

本文具體參數設置為：種群規模sizepop=30，最大迭代數Maxgen=1 000。所有算法采用Matlab R2016b 進行編程，計算機配置為：Intel Core（TM）i5-8250U、1.6GHz、4GB內存、Windows10 操作系統。

實驗內容如下：①將基于混沌映射的4 種改進果蠅算法 即Logistic-FOA、Tent-FOA、Circle-FOA 和Sinusoidal-FOA 進行對比實驗，以確定性能最佳的混沌果蠅算法SFOA；②將確定的混沌果蠅算法SFOA 與基本果蠅算法FOA 和其它參考文獻的改進果蠅算法進行對比實驗；③SFOA 算法與基本果蠅算法FOA 和其它參考文獻算法在高維、多峰函數上進行性能比較分析。

3.2 實驗評價標準

實驗中各算法獨立運行20 次，設置終止條件為迭代次數達到1 000 次。為評價算法優化效果，本文給出如下3 個判定標準：①優化均值（MEAN），算法運行20 次后得到的最優值的期望，用來衡量算法尋優平均質量；②標準差（STD），算法運行20 次后得到的最優值與平均最優值之間的標準差，評價算法尋優穩定性；③全局最優解（BEST），算法運行20 次得到的全局最優解。

3.3 實驗結果與分析

3.3.1 基于混沌映射的果蠅改進算法性能比較

7 個測試函數的進化迭代次數固定為1 000，分別采用4 種基于混沌映射的改進果蠅算法對其進行求解，各算法獨立運行20 次，其實驗結果如表3 所示。

Table 3 Performance comparison of four chaotic fruit-fly algorithms表3 4 種混沌果蠅算法性能比較

從表3 可以看出，4 種混沌果蠅算法相比，基于混沌映射為Sinusoidal 的改進果蠅算法比其它3 種混沌映射的整體性能更好，更接近理論最優值，其求解得到的平均最優值（MEAN）、標準差（STD）、全局最優值（BEST）均優于其它3 種混沌映射。

比其它混沌映射具有更高的精度以及更好的穩定性，也進一步說明該算法的可行性和有效性。

3.3.2 固定進化迭代次數收斂速度與精度

將7 個測試函數F1～F7 固定迭代次數為1 000 次，分別采用FOA、CDSFOA［13］、CSFOA［14］、VSFOA［15］和SFOA 算法經過20 次獨立運行，并分別將運行得到的優化均值（MEAN）、標準差（STD）和最優值（BEST）進行表征，維數均設置為30，得到的實驗結果如表4 所示，圖1 是算法尋優測試曲線。

Table 4 Comparison of the performance of the reference algorithms表4 與參考文獻算法性能比較

由表4 可知，對7 個基準測試函數的實驗結果中，SFOA 的3 項評價指標均優于FOA 算法、CDSFOA 算法、CSFOA 算法和VSFOA 算法。具有較好的優化均值和較小的測試標準差，尤其對于單峰函數F1、多峰函數F4、F5、F6和F7 而言，SFOA 算法的優化均值和測試標準差的數量級都遠高于其它4 種算法，在單峰函數F2 的優化上，SFOA算法的均值優化與其它算法均在一個數量級，但測試標準差比其它算法更優，單峰函數F3 的優化均值和測試標準差與CSFOA 算法和VSFOA 算法的數量級一樣，但SFOA算法仍更接近理論值，說明SFOA 算法在整體上具有較好的優化精度和較強的魯棒性；并且具有最優的BEST 指標，尤其對于測試函數F1、F4、F6 和F7 而言，SFOA 算法的全局最優值均優于其它算法，在單峰函數F2 和F3 優化上，SFOA 算法的全局最優雖與其它算法在同一數量級，但仍更接近理論值，對于多峰函數F5 而言，SFOA 算法的全局最優與CSFOA 算法和VSFOA 算法相比均在同一數量級，但仍優于FOA 算法和CDSFOA 算法，表明本文改進算法保證了較好的最優預測性能。

為了對比5 種算法對各測試函數的迭代尋優性能，繪制了5 種算法的迭代尋優對比曲線，如圖1 所示。

Fig.1 Optimization test curves of five algorithms圖1 5 種算法的尋優測試曲線

由圖1 可以看出，在對各測試函數的迭代尋優過程中，SFOA 算法與其它算法相比不僅保證了算法前期較好的全局尋優性能和較快的收斂速度，而且在算法后期也有效實現了進一步局部搜索。因此，在一定程度上說明改進算法SFOA 具有較好的迭代尋優性能。其中，雖然對于單峰測試函數F3 和多峰測試函數F5 而言，SFOA 算法略遜于CSFOA 算法和VSFOA 算法，但SFOA 算法的收斂速度仍遠遠高于其它算法。而且對于單峰測試函數F1、多峰測試函數F4、F6 和F7 的優化，SFOA 算法的收斂速度和尋優效果都遠高于其它4 種算法。因此，SFOA 算法不僅對單峰測試函數具有較好的尋優性能，而且對Ackly、Griewank、Rastrigin 和Solomon Problem 多峰測試函數也表現出較好的尋優性能和收斂精度，進一步驗證了SFOA 算法的優良尋優性能。

3.3.3 算法在高維、多峰函數上的性能對比

全局優化算法普遍存在易陷入局部最優，導致后期收斂速度變慢、收斂精度變低的問題，尤其上對于高維、多峰復雜優化問題。將FOA、CDSFOA［13］、CSFOA［14］、VSFOA［15］和SFOA 在不同測試函數上，對維數依次遞增的情況下各算法的優化均值（MEAN）進行實驗比較。在不同測試函數條件下，對各算法獨立運行20 次，結果如表5 所示。

Table 5 Comparison of optimization mean values on multi-dimensional and peak functions表5 在多維、高峰函數上的優化均值比較

由表5 可知，對于多峰測試函數Griewank 和Rastri?gin，SFOA 算法的優化均值顯著優于FOA、CDSFOA［13］、CS?FOA［14］和VSFOA［15］，并且隨著測試函數維數的增加，SFOA算法的優化均值基本在同一數量級內變化，比較接近理論最優值，而且對于多峰函數F5 而言，SFOA 算法隨著維數的增加，其優化均值不僅沒有遠離理論最優值，而且隨著維數的增加而減少，但FOA 算法和其它改進果蠅算法則隨著維數的增加，其優化均值逐漸遠離理論最優均值。這表明隨著維數的增加，SFOA 算法對高維的復雜函數仍保持平穩且較高精度的尋優性能。

3.3.4 算法時間復雜度分析

時間復雜度是指算法執行所需要的計算工作量，主要取決于問題重復執行次數，在SFOA 算法中，時間復雜度主要受到種群規模sizepop、迭代次數Maxgen和維度n的影響，在計算時間復雜度時，種群規模為N，迭代次數為M，維度為n，因此SFOA 算法的時間復雜度為O（M×N×n）。

4 結語

本文針對FOA 尋優精度低和易陷入局部最優等缺陷，引入與混沌相結合的新參數，提出一種混沌果蠅優化算法——SFOA 算法，利用混沌搜索的隨機性和遍歷性這些特性，在更新果蠅種群的初始位置時提高其多樣性，達到優化全局搜索能力的目的。通過7 個基本測試函數測試，基于Sinusoidal 映射的改進果蠅算法具有更好的優化性能，仿真結果表明，本文提出的算法SFOA 相比基本果蠅算法和參考文獻的改進果蠅算法，測試指標至少高出3 個數量級，尤其針對高維、多峰函數，SFOA 算法的測試指標至少高出了2 個數量級，說明該算法比其它算法的性能更佳。下一步研究的重點是將SFOA 算法應用于實際工程領域中的約束優化問題和多目標問題等。