吳經(jīng)緯，余玲珍，龍道銀，楊 靖*

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

1 引言

果蠅優(yōu)化算法(FOA)是一種通過模擬果蠅覓食行為來尋找全局最優(yōu)解的群體智能算法[1]。與其它群體智能算法比較，F(xiàn)OA具有機制結(jié)構(gòu)簡單、代碼易于實現(xiàn)、調(diào)節(jié)參數(shù)較少[2]的優(yōu)點。當前，F(xiàn)OA已被成功應(yīng)用于多核相關(guān)向量機預(yù)測模型[3]、模擬電路故障診斷[4]、傳感器網(wǎng)絡(luò)節(jié)點定位[5]、路徑覆蓋測試[6]等方面，具有很好的應(yīng)用前景。

FOA算法由于優(yōu)化過程中的隨機性，在搜尋過程中存在盲目搜索，會導(dǎo)致算法早熟收斂、陷入局部最優(yōu)。與其它典型群體智能算法類似，F(xiàn)OA算法相關(guān)參數(shù)的設(shè)置決定了該算法的性能。為了改善原算法的性能，文獻[7]利用混沌映射所產(chǎn)生的混沌現(xiàn)象具有良好的遍歷性、多樣性的特點來改進果蠅算法的固定步長，在一定程度上提高了果蠅優(yōu)化算法的優(yōu)化性能；文獻[8]從搜索方向的自適應(yīng)選擇機制、迭代步長值的自適應(yīng)調(diào)整機制、自適應(yīng)交叉變異機制和多子群機制四個方面對基本FOA算法進行改進，但該算法的復(fù)雜度較高；文獻[9]在尋優(yōu)過程中引入動態(tài)步長因子對基本果蠅優(yōu)化算法的步長實現(xiàn)持續(xù)動態(tài)更新；文獻[10]根據(jù)種群進化信息動態(tài)調(diào)整進化指導(dǎo)方向和搜索步長，但相對標準FOA算法需要較長的運行時間；文獻[11]對果蠅個體的尋優(yōu)步長進行了適應(yīng)性的改變，但在多峰函數(shù)的尋優(yōu)求解中得到的結(jié)果不太理想。

在上述研究基礎(chǔ)之上，本文提出一種多策略的變異果蠅優(yōu)化算法。首先，利用混沌映射的遍歷性和隨機性初始化果蠅種群，提高種群的多樣性；其次，對尋優(yōu)過程的隨機步長引入可調(diào)整的動態(tài)變化收斂因子，有效平衡局部和全局搜索能力；最后，對尋優(yōu)迭代中最優(yōu)果蠅個體位置引入柯西變異保證群體的多樣性，防止陷入局部最優(yōu)。這些改進能有效地均衡果蠅優(yōu)化算法的全局搜索與局部開發(fā)能力，提高了算法的收斂速度和尋優(yōu)精度。

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

果蠅在嗅覺和視覺上比其它物種有一定的優(yōu)勢。在尋找食物的過程中，首先，果蠅通過收集空氣中不同的氣味來尋找可能的食物來源；然后，果蠅群逐漸接近最佳氣味濃度的位置；最后，它們可以通過敏銳的視覺來確定食物來源的準確位置，如此循環(huán)直到找到食物為止[12]。

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

步驟1：初始化參數(shù)：種群規(guī)模數(shù)N、最大迭代次數(shù)Maxt和隨機初始化果蠅群體位置X＿axis、Y＿axis。

步驟2：給果蠅方向和距離分配隨機搜索的方向和距離

(1)

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

(2)

Si=1/Di

(3)

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

Smelli=Function(Si)

(4)

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

[bestSmell，bestIndex]=min(Smell)

(5)

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

(6)

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

3 改進的果蠅優(yōu)化算法(MFOA)

3.1 基于混沌的種群初始化

FOA算法在解決函數(shù)優(yōu)化問題中，一般利用隨機產(chǎn)生的數(shù)據(jù)作為初始種群信息，雖在一定程度上保證了初始位置的均勻分布，但難以保留種群的多樣性，導(dǎo)致算法的尋優(yōu)效果較差。混沌是一種復(fù)雜的非線性系統(tǒng)動態(tài)行為，具有遍歷性、隨機性和規(guī)律性的特點，這些特點能夠使算法容易逃離局部最優(yōu)解，維持果蠅種群的多樣性，同時提高全局搜索能力。

其思想即把果蠅種群的位置通過混沌映射線性地映射到混沌變量中，再根據(jù)混沌的特點優(yōu)化搜索，最后將得到的解線性地轉(zhuǎn)化到種群的變量空間中，從而使果蠅種群的初始位置分布更加均勻。

3.2 非線性控制策略

如式(1)所示，F(xiàn)OA在進行尋優(yōu)時，果蠅的飛行方向和飛行距離都是隨機的，導(dǎo)致FOA的尋優(yōu)結(jié)果不穩(wěn)定且易陷入局部最優(yōu)。本文的改進思想是在算法執(zhí)行的初期著重于全局搜索，以保證廣泛的搜索范圍，在算法執(zhí)行的后期著重于精細的局部搜索，即針對最佳果蠅個體周圍鄰域進行搜索，以提高算法的尋優(yōu)精度，從而實現(xiàn)全局搜索能力和局部尋優(yōu)的動態(tài)平衡。因此本文在迭代過程中采用非線性調(diào)整策略更新果蠅個體位置：

(7)

式中，new＿X和new＿Y為上一代最佳果蠅個體位置；ω為非線性動態(tài)變化收斂因子，公式如下

(8)

式中，ω1和ω2分別是ω的初始值和終值，經(jīng)大量實驗，ω∈[1，100]；μ是收斂調(diào)整因子，0<μ<1稱為對數(shù)壓縮因子，μ>1稱為對數(shù)膨脹因子。圖1是μ=1、Maxt=1000時的迭代次數(shù)與收斂因子的關(guān)系曲線圖。

圖1 收斂因子遞減規(guī)律曲線

從圖1可知，當μ=1，ω1=10，ω2=1時，在前期對數(shù)遞減策略ω減小的趨勢很快，如果找到適當?shù)墓壸罴盐恢镁涂梢栽诰植窟M行精細搜索。本文μ=1，在實際工程應(yīng)用中，對不同的優(yōu)化問題可以適當?shù)恼{(diào)整μ的值。

式(7)中將上一代最佳果蠅位置作為迭代尋優(yōu)的起始位置，此策略既保持了圍繞果蠅種群最優(yōu)值分布的特點，又可通過動態(tài)變化收斂因子控制種群的全局搜索和局部開發(fā)。

式(8)功能如下：在算法的迭代前期果蠅具有較強的全局搜索能力，ω1取一個較大值來保證果蠅廣泛的搜索范圍，ω2取一個適當小的值，使得算法的迭代后期著重于精細的局部搜索。

3.3 柯西變異

種群中所有果蠅個體在進入迭代尋優(yōu)時均向最優(yōu)個體靠近，從而導(dǎo)致群體多樣性的缺失，容易陷入局部最優(yōu)，為了避免這種情況的出現(xiàn)，對其中最優(yōu)果蠅個體進行柯西變異，增加種群的多樣性?？挛鞣植己驼龖B(tài)分布的概率密度函數(shù)曲線如圖2所示，柯西分布在0處的峰值比正態(tài)分布小，果蠅個體會使用相對較少的時間來搜索相鄰區(qū)間，從峰值到0值下降趨勢比起正態(tài)分布更平緩，趨向于零的速度更慢，因此柯西變異的擾動能力更強，更容易產(chǎn)生遠離原點的隨機數(shù)，變異后的個體較容易跳出局部極值[13]。

圖2 概率密度函數(shù)曲線

基本果蠅優(yōu)化算法根據(jù)最優(yōu)個體來更新下一代自身的位置，對最優(yōu)個體提出的柯西變異策略表達式為

(9)

式中，new＿X和new＿Y為當前最優(yōu)個體位置，new＿X′和new＿Y′為變異后的最佳果蠅個體位置；ω為2.2節(jié)的非線性動態(tài)變化收斂因子，利用ω的自適應(yīng)能力來達到增強及減小變異擾動的作用；C(0，1)為以0為中心，尺度參數(shù)為1的柯西分布的隨機數(shù)。

3.4 算法步驟

本文將混沌映射和非線性調(diào)整策略以及柯西變異的果蠅算法定義為MFOA，改進后的MFOA算法的具體步驟如下：

步驟1：初始化參數(shù)：種群規(guī)模數(shù)N，最大迭代數(shù)Maxt，收斂因子初終值ω1和ω2，維度d。

步驟2：利用混沌映射初始化果蠅種群位置。

步驟3：根據(jù)式(2)估算果蠅與原點之間距離Di，再根據(jù)式(3)計算味道濃度判定值Si。

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

步驟5：根據(jù)式(8)生成動態(tài)變化收斂因子，按式(9)對當前最佳果蠅個體位置進行柯西變異。

步驟6：進入迭代運算后，按式(7)對果蠅種群位置進行更新，重復(fù)步驟3～步驟5，在尋優(yōu)過程中判斷當前最佳味道濃度是否優(yōu)于上一迭代結(jié)果，且判斷當前迭代次數(shù)是否小于最大迭代數(shù)；若是則執(zhí)行步驟5，否則結(jié)束。

3.5 算法復(fù)雜度分析

時間復(fù)雜度是衡量尋優(yōu)算法性能優(yōu)劣的重要指標之一，主要取決于問題重復(fù)執(zhí)行的次數(shù)。果蠅優(yōu)化算法FOA的計算復(fù)雜度主要包括個體位置更新 、濃度值計算和適應(yīng)度評估，假設(shè)種群規(guī)模為N，最大迭代次數(shù)M，維數(shù)d，個體濃度更新計算量為O(1)，所以FOA的時間復(fù)雜度為O(N ×M)。

本文改進的算法中，在FOA的基礎(chǔ)上增加了混沌初始化種群位置，生成果蠅初始位置階段的時間復(fù)雜度為O(N×d)；生成動態(tài)變化收斂因子ω的時間復(fù)雜度為O(M)，對最佳果蠅個體進行柯西變異的時間復(fù)雜度為O(M)，更新果蠅位置階段的時間復(fù)雜度為O(M×(N+2))。

4 仿真分析

4.1 仿真場景設(shè)置

本文采用如表1所示的8個基準測試函數(shù)來評估MFOA算法性能。

表1 測試函數(shù)及參數(shù)設(shè)定

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

實驗內(nèi)容：①將4種混沌映射初始化果蠅種群的優(yōu)化結(jié)果進行對比實驗，以確定性能最佳的混沌映射；②固定進化迭代次數(shù)，評估算法的收斂速度和尋優(yōu)精度，并與FOA、ABC算法和其它參考文獻的改進果蠅算法進行性能對比；③評估算法在高維、多峰函數(shù)上的性能，并與FOA算法和其它參考文獻算法進行比較分析。

實驗評價標準：實驗中各算法獨立運行20次，設(shè)置終止條件為迭代次數(shù)達到1000次。為評價算法的優(yōu)化效果，本文給出如下三個判定標準：1)優(yōu)化均值(MEAN)，用來衡量算法尋優(yōu)的平均質(zhì)量；2)標準差(STD)，評價算法尋優(yōu)的穩(wěn)定性；3)全局最優(yōu)解(BEST)；4)達到最優(yōu)適應(yīng)度值所需平均迭代次數(shù)(以下簡述為迭代次數(shù))。

4.2 不同混沌映射的性能對比

為了驗證不同混沌映射初始化果蠅種群的優(yōu)化性能，使用了4種常見的一維混沌映射函數(shù)，如表2所示。

表2 常用的一維混沌映射

8個測試函數(shù)的進化迭代次數(shù)固定為1000，分別采用表2的常用一維混沌映射對果蠅種群進行初始化，各算法獨立運行20次，其實驗結(jié)果如表3所示。

表3 混沌映射優(yōu)化的性能比較

函數(shù)指標混沌映射名稱LogisticCubicKentTentF2MEAN2.54E-1211.99E-1225.43E-1222.02E-117STD8.02E-1201.99E-1228.45E-1146.39E-116BEST0000F3MEAN9.47E-1161.48E-1204.26E-1171.81E-113STD2.99E-1144.67E-1191.35E-1155.73E-112BEST0000F4MEAN-1-1-1-1STD0000BEST-1-1-1-1F5MEAN1.89E-1129.77E-1235.25E-1183.69E-111STD5.99E-1113.09E-1211.66E-1161.17E-109BEST0000F6MEAN0000STD0000BEST0000F7MEAN8.88E-168.88E-168.88E-168.88E-16STD0000BEST8.88E-168.88E-168.88E-168.88E-16F8MEAN0000STD0000BEST0000

由表3可知，綜合優(yōu)化均值、平均值和全局最優(yōu)解這三個評價指標，與其它三種混沌映射相比，基于Cubic混沌映射的果蠅初始化種群的整體性能更好，更接近理論極值，具有更高的精度和穩(wěn)定性，也進一步說明混沌映射初始化種群的可行性和有效性。

4.3 收斂速度和尋優(yōu)精度分析

將8個測試函數(shù)F1～F8固定迭代次數(shù)為1000次，分別采用FOA、ABC、文獻[14]中的WFOA算法、文獻[15]中的CSFOA算法和本文算法MFOA經(jīng)過20次獨立運行，其中人工蜂群算法ABC算法參數(shù)設(shè)置為：試驗極限次數(shù)limit=60；其它參考文獻算法按照原文獻進行設(shè)置。分別將運行得到的優(yōu)化均值(MEAN)、標準差(STD)、最優(yōu)值(BEST)和迭代次數(shù)來表征，維數(shù)均設(shè)置為30，得到的實驗結(jié)果如表4所示。

表4 五種算法的性能比較

由表4可知，當維數(shù)為30時，MFOA算法在F1～F3和F5測試函數(shù)上所得的優(yōu)化均值(MEAN)更加理想，至少提高了118個數(shù)量級，雖然對于復(fù)雜的多峰函數(shù)F7來說，只是提高了14個數(shù)量級，但對于F4、F6和F8測試函數(shù)來說，MFOA算法均達到了理論極值，說明MFOA算法具有較好的優(yōu)化精度；在F1～F3和F5測試函數(shù)上所得的測試標準差(STD)，MFOA算法相比其它四種算法更加理想，至少提高了102個數(shù)量級，對于多峰測試函數(shù)F6～F8和單峰函數(shù)F4來說，MFOA算法的STD達到了最優(yōu)，說明MFOA算法具有較強的魯棒性；并且在8個測試函數(shù)中，MFOA算法相比其它四種算法具有最優(yōu)的BEST指標，迭代次數(shù)也最少，表明改進算法保證了較好的最優(yōu)預(yù)測性能和較快的收斂速度。

總而言之，在測試函數(shù)F1～F8中，MFOA獲得的MEAN、STD、BEST和迭代次數(shù)這四個測試指標均優(yōu)于其它四種算法，這充分驗證了相比這四種算法，MFOA在收斂速度、尋優(yōu)精度以及算法的穩(wěn)定性上都有很大的提升，說明改進算法不僅對單峰測試函數(shù)具有較好的尋優(yōu)精度，而且對多峰函數(shù)也表現(xiàn)出較好的尋優(yōu)性能和收斂速度，進一步驗證了MFOA算法的優(yōu)良尋優(yōu)性能。

五種算法的迭代尋優(yōu)對比曲線如圖3所示。

圖3 五種算法的尋優(yōu)測試曲線

由圖3可知：在對各測試函數(shù)的迭代尋優(yōu)過程中，MFOA算法與其它算法相比不僅獲得較快的收斂速度且易跳出局部最優(yōu)值。這些結(jié)果表明，MFOA算法因為初始種群的多樣性和非線性動態(tài)變化收斂因子以及柯西變異對最佳果蠅個體位置的優(yōu)化，能有效地均衡全局尋優(yōu)和局部尋優(yōu)性能，增加種群的多樣性，具有較強的迭代尋優(yōu)性能。

4.4 高維多峰函數(shù)上的對比分析

全局優(yōu)化算法普遍存在易陷入局部最優(yōu)，后期收斂速度變慢、收斂精度低的問題，尤其對于高維、多峰復(fù)雜優(yōu)化問題。將WFOA算法、CSFOA算法和本文算法MFOA在不同多峰測試函數(shù)上，對維數(shù)依次遞增的情況下各算法的優(yōu)化均值(MEAN)進行實驗比較。在不同多峰測試函數(shù)條件下，對各算法獨立運行20次，結(jié)果如表5所示。

表5 在高維、多峰函數(shù)上的優(yōu)化均值比較

由表5可知，無論維數(shù)100還是200，對于多峰測試函數(shù)F5和F7，MFOA算法的優(yōu)化均值顯著優(yōu)于FOA、WFOA和CSFOA算法，并且隨著函數(shù)維數(shù)的增加，MFOA算法的優(yōu)化均值基本在同一數(shù)量級內(nèi)變化，比較接近最優(yōu)值，而且對于多峰測試函數(shù)F6和F8，隨著維數(shù)的增加，仍達到理論最優(yōu)值。這表明MFOA算法對高維的復(fù)雜函數(shù)仍保持平穩(wěn)且較高精度的尋優(yōu)性能。

5 結(jié)論

針對FOA收斂速度慢和尋優(yōu)精度低等不足，提出一種改進算法MFOA，采用Cubic混沌映射初始化果蠅種群以增加種群的多樣性；引入非線性動態(tài)收斂因子來均衡算法的局部及全局搜索能力；對果蠅最優(yōu)個體進行柯西變異，增加種群的多樣性，以跳出局部最優(yōu)，提高種群的收斂速度和尋優(yōu)精度。對8個典型基準測試函數(shù)進行仿真，由仿真結(jié)果可知，MFOA的測試指標均優(yōu)于對比算法，這表明該算法在總體性能上具有優(yōu)勢。下一步研究的重點是將MFOA算法應(yīng)用于實際工程領(lǐng)域中的約束優(yōu)化問題和多目標優(yōu)化問題等。