一種多策略的變異果蠅優(yōu)化算法

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

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

1 引言

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

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

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

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

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

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

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

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

(1)

步驟3：估算果蠅與原點(diǎn)之間距離Di，再計(jì)算味道濃度判定值Si

(2)

Si=1/Di

(3)

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

Smelli=Function(Si)

(4)

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

[bestSmell，bestIndex]=min(Smell)

(5)

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

(6)

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

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

3.1 基于混沌的種群初始化

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

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

3.2 非線性控制策略

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

(7)

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

(8)

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

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

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

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

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

3.3 柯西變異

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

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

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

(9)

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

3.4 算法步驟

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

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

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

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

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

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

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

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

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

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

4 仿真分析

4.1 仿真場(chǎng)景設(shè)置

本文采用如表1所示的8個(gè)基準(zhǔn)測(cè)試函數(shù)來(lái)評(píng)估MFOA算法性能。

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

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

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

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

4.2 不同混沌映射的性能對(duì)比

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

表2 常用的一維混沌映射

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

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

函數(shù)指標(biāo)混沌映射名稱(chēng)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)解這三個(gè)評(píng)價(jià)指標(biāo)，與其它三種混沌映射相比，基于Cubic混沌映射的果蠅初始化種群的整體性能更好，更接近理論極值，具有更高的精度和穩(wěn)定性，也進(jìn)一步說(shuō)明混沌映射初始化種群的可行性和有效性。

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

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

表4 五種算法的性能比較

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

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

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

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

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

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

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

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

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

5 結(jié)論

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