混沌果蠅優(yōu)化算法研究

吳經(jīng)緯，楊 靖，龍道銀，王 霄，覃 濤，余玲珍

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

0 引言

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

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

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

1 基本果蠅優(yōu)化算法

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

FOA 可以總結(jié)為7 個步驟：

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

步驟2：為果蠅方向和距離分配隨機參數(shù)，產(chǎn)生新位置。

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

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

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

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

步驟7：最后迭代運算，重復(fù)步驟2—步驟5，在尋優(yōu)過程中判斷當(dāng)前最佳味道濃度是否優(yōu)于上一迭代結(jié)果，且判斷當(dāng)前迭代次數(shù)是否小于最大迭代數(shù)；若是則執(zhí)行步驟6，否則結(jié)束。

2 混沌果蠅優(yōu)化算法

2.1 混沌優(yōu)化

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

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

2.2 SFOA 算法步驟

基于基本果蠅優(yōu)化算法原理及上述改進(jìn)方法，本文提出的混沌優(yōu)化果蠅算法具體步驟如下：

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

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

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

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

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

步驟6：根據(jù)式（8）對果蠅種群位置進(jìn)行更新后再進(jìn)行迭代運算，重復(fù)步驟2—步驟5，在尋優(yōu)過程中判斷當(dāng)前最佳味道濃度是否優(yōu)于上一迭代結(jié)果，且判斷當(dāng)前迭代次數(shù)是否小于最大迭代數(shù)；若是則執(zhí)行步驟5，否則結(jié)束。

SFOA 算法運行偽代碼如下：

3 仿真實驗與結(jié)果分析

3.1 實驗設(shè)計

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

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

Table 2 Test functions and parameter setting表2 測試函數(shù)及參數(shù)設(shè)定

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

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

3.2 實驗評價標(biāo)準(zhǔn)

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

3.3 實驗結(jié)果與分析

3.3.1 基于混沌映射的果蠅改進(jìn)算法性能比較

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

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

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

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

3.3.2 固定進(jìn)化迭代次數(shù)收斂速度與精度

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

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

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

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

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

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

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

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

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

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

3.3.4 算法時間復(fù)雜度分析

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

4 結(jié)語

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