陳嘉豪 童楠 符強(qiáng)

摘要： 在高維復(fù)雜問題上，蜉蝣優(yōu)化算法存在易陷入局部最優(yōu)區(qū)域且求解精度較差等問題，因而提出基于Logistic映射的蜉蝣優(yōu)化算法。引入依據(jù)Logistic映射的混沌機(jī)制，當(dāng)種群進(jìn)化停滯時，當(dāng)前最優(yōu)蜉蝣通過混沌機(jī)制尋找適應(yīng)度更好的蜉蝣，以激發(fā)種群進(jìn)化能力;建立較劣蜉蝣加速進(jìn)化機(jī)制，激勵蜉蝣個體以達(dá)到種群尋優(yōu)要求;采用動態(tài)慣性權(quán)重均衡算法全局和局部的搜索性能。抽取5個benchmark函數(shù)測試算法性能，實(shí)驗(yàn)結(jié)果驗(yàn)證了所提算法在尋優(yōu)性能上的有效性。

關(guān)鍵詞： 群智能算法; 蜉蝣優(yōu)化算法; Logistic映射; 擾動; 動態(tài)慣性權(quán)重

中圖分類號：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ?文章編號：1006-8228（2021）10-06-05

Mayfly optimization algorithm based on Logistic mapping

Chen Jiahao， Tong Nan， Fu Qiang

（College of Science and Technology， Ningbo University， Ningbo， Zhejiang 315300， China）

Abstract： For high-dimensional complex problems， mayfly optimization algorithm has problems such as easy to fall into local optimal area and poor solution accuracy. Therefore， a mayfly optimization algorithm based on Logistic mapping is proposed. Introducing the Logistic mapping based chaotic mechanism， when the evolution of the population stagnates， the current optimal mayfly uses the chaotic mechanism to find a mayfly with better adaptability to stimulate the evolutionary ability of the population; Establishing a accelerated evolution mechanism for inferior mayfly， the mayfly individual is motivated to meet the requirements of the population optimization; Using the dynamic inertial weight balance algorithm， the global and local search capabilities are balanced. Five benchmark functions are selected to test the performance of the algorithm， and the experimental results verify the effectiveness of the proposed algorithm in optimizing performance.

Key words： swarm intelligence algorithm; mayfly optimization algorithm; Logistic mapping; disturbance; dynamic inertia weight

0 引言

群智能優(yōu)化算法[1-2]易于編程，尋優(yōu)能力強(qiáng)，現(xiàn)已廣泛應(yīng)用于實(shí)際工程領(lǐng)域中，例如解決旅行商問題和0-1背包問題等[3-4]。

蜉蝣優(yōu)化算法[5]（A mayfly optimization algorithmMA）是一種2020年7月由Konstantinos Zervoudakis和 Stelios Tsafarakis 提出的新型群智能算法，此算法受蜉蝣飛行行為和交配過程的啟發(fā)，聯(lián)結(jié)粒子群算法[6]和遺傳算法[7]的優(yōu)點(diǎn)，在低維問題上，相比較其余群智能算法具備更好的收斂速度和收斂精度，且算法中的隨機(jī)飛行和婚禮舞蹈行為能有效平衡種群的全局探索及局部搜索要求。但當(dāng)遇到高維復(fù)雜問題時，蜉蝣算法單純依靠自身機(jī)制仍然較難跳出局部最優(yōu)區(qū)域，且由于蜉蝣在移動時步長太短，導(dǎo)致算法收斂精度不高。

針對上述問題，本文提出基于Logistic映射的蜉蝣優(yōu)化算法（mayfly optimization algorithm based on Logistic mapping LMA），采用動態(tài)慣性權(quán)重提高種群的搜索能力，增加算法收斂效率;引入基于Logistic映射的混沌機(jī)制，防止種群出現(xiàn)早熟收斂現(xiàn)象;建立較劣蜉蝣加速進(jìn)化機(jī)制，減少較劣蜉蝣在外徘徊的次數(shù)，提升種群整體進(jìn)化速度。通過對標(biāo)準(zhǔn)測試函數(shù)的仿真實(shí)驗(yàn)，并與其他幾種算法進(jìn)行比較，驗(yàn)證LMA算法對問題求解的有效性。

1 蜉蝣優(yōu)化算法簡介

蜉蝣優(yōu)化算法抽象出蜉蝣的生命過程，將蜉蝣的位置映射為問題的潛在解決方案。算法最初隨機(jī)生成蜉蝣種群，將種群分為雄性蜉蝣群和雌性蜉蝣群。設(shè)一個[D]維問題，第[i]個蜉蝣的位置為[xi={x1，x2，x3，…，xD}][xi={x1，x2，x3，…，xD}][xi={x1，x2，x3，…，xD}]，對應(yīng)速度為[Vi={V1，V2，V3，…，VD}]。

1.1 雄雌蜉蝣的移動

MA算法中雄蜉蝣會朝更優(yōu)方向進(jìn)化，因此雄蜉蝣的速度將根據(jù)自身曾到過的最好位置與種群當(dāng)前最優(yōu)位置來調(diào)整，且當(dāng)蜉蝣適應(yīng)度優(yōu)于種群當(dāng)前最優(yōu)適應(yīng)度時，蜉蝣將根據(jù)婚禮舞蹈系數(shù)和慣性權(quán)重對速度進(jìn)行調(diào)整，速度更新公式為：

[vt+1ij=g*vtij+a1e-βr2ppbij-xtij+a2e-βr2ggbj-xtij，iffxi>fgbg*vtij+d*r1 ，iffgb≤fxi] ⑴

其中[vtij]為第[t]次迭代第[i]個蜉蝣在[j]維度上的速度，[xtij]為第[t]次迭代時第[i]個雄蜉蝣在[j]維度上的位置，[a1]為蜉蝣個體的認(rèn)知參數(shù)，[a2]為種群社會貢獻(xiàn)參數(shù)，[g]為慣性權(quán)重，[β]是一個固定的能見度因子，[d]為舞蹈因子，[r1]是[[-1，1]]內(nèi)的隨機(jī)因子，[pbij]為第[i]個蜉蝣在第[j]維曾經(jīng)到達(dá)過的最好的位置，[gbj]為第[j]維全局最好的位置，[rp]與[rg]分別為第[i]個蜉蝣與[pb]的笛卡爾距離和第[i]個蜉蝣與[gb]的笛卡爾距離。

個體適應(yīng)度排序等級相同的雄雌蜉蝣將會相互吸引，雌蜉蝣的移動依據(jù)為排序等級相同的雄蜉蝣位置。若雄蜉蝣優(yōu)于雌蜉蝣，則雌蜉蝣向雄蜉蝣靠近，否則受隨機(jī)飛行因子的影響隨機(jī)向周圍飛行。雌性蜉蝣的速度更新公式為：

[vt+1ij=g*vtij+a2e-βr2mfxtij-ytij ，iffyi>fxig*vtij+fl*r1? ?，iffyi≤fxi] ⑵

其中[ytij]為第[t]次迭代時第[i]個雌蜉蝣在[j]維度上的位置，[rmf]為雄雌蜉蝣之間的笛卡爾距離，[fl]是一個隨機(jī)飛行因子。

MA算法通過在當(dāng)前位置上添加速度[vt+1i]作為雄雌蜉蝣位置的移動。

[xt+1i=xti+vt+1i] ⑶

同時為防止蜉蝣速度無限增大導(dǎo)致蜉蝣飛出解空間范圍，MA算法對蜉蝣的速度進(jìn)行限定。在迭代的過程中，為滿足算法后期局部探索要求，蜉蝣的慣性權(quán)重、婚禮舞蹈因子與隨機(jī)飛行因子將逐漸減少。

1.2 雄雌蜉蝣的交配與變異

MA算法中個體適應(yīng)度排序等級相同的雄雌蜉蝣將會相互交配生成子代蜉蝣。交配的公式如下：

[offspring1=L*male+1-L*female]

[offspring2=L*female+1-L*male]? ⑷

其中[offspring]為子代蜉蝣，[male]為雄蜉蝣，[female]為雌蜉蝣，[L]為[[-1，1]]中的隨機(jī)因子。

MA算法引入高斯變異[8]，對子代蜉蝣的單個維度進(jìn)行基因變異。子代蜉蝣的變異個數(shù)以種群數(shù)量[Pop]為基數(shù)，定義變異幾率為[mu]，[Pop*mu]為種群中子代的變異個數(shù)。變異公式如下：

[offspringn=offspringn+σ*Nn（0，1）]? ⑸

其中[Nn0，1]為平均值為0，方差為1的標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)，[σ]為正態(tài)分布的標(biāo)準(zhǔn)差，[offspringn]為變異蜉蝣的第[n]個維度。

2 改進(jìn)的蜉蝣優(yōu)化算法

2.1 根據(jù)Logistic映射的混沌機(jī)制

基于Logistic映射的混沌機(jī)制[9]中存在控制參數(shù)[μ∈[0，4]]，當(dāng)[μ]等于4時，混沌變量的取值將呈現(xiàn)混沌特征，因此本文取[μ]為4。該混沌機(jī)制將生成隨機(jī)分布在解空間中的混沌蜉蝣。LMA算法由當(dāng)前最優(yōu)蜉蝣隨機(jī)產(chǎn)生[10]個混沌蜉蝣，若最優(yōu)的混沌蜉蝣優(yōu)于當(dāng)前最優(yōu)蜉蝣，則替換之，否則隨機(jī)替換蜉蝣種群中除了最優(yōu)蜉蝣外的任一蜉蝣，增加種群多樣性，增大算法求得全局最優(yōu)解的可能性。

Logistic映射的混沌機(jī)制進(jìn)行擾動的公式如下：

[zt+1i=μzti（1-zti）] ⑹

其中[zti∈[0，1]]為第[i]個混沌蜉蝣的混沌位置。

將[xi∈[xmin，xmax]]映射到[zi∈[0，1]]的公式如下：

[zi=（xi-xmin）/（xmax-xmin）] ⑺

將[zi]映射回[xi]公式為：

[xi=xmin+zi（xmax-xmin）] ⑻

當(dāng)連續(xù)兩次迭代的種群蜉蝣的平均適應(yīng)度之差小于[10-3]，判定算法陷入局部最優(yōu)，將執(zhí)行混沌機(jī)制。

方差[10]計算公式如下：

[σ2=i=1N（（fi-favg）/f）2] ⑼

其中N為種群中蜉蝣的總數(shù)，[favg]為種群適應(yīng)度的平均值，[fi]為蜉蝣個體[i]的適應(yīng)度。[f]為用來限制[σ2]大小的因子，計算公式為：

[f=maxfi-favg，maxfi-favg>11? ? ? ? ? ? ? ? ? ? ? ? ? ? ?，max {|fi-favg|}≤1] ⑽

2.2 較劣蜉蝣加速進(jìn)化機(jī)制

種群中存在部分個體的進(jìn)化程度始終無法達(dá)到種群平均進(jìn)化程度，算法將判定這類個體為失效個體。對多次無法跟隨種群進(jìn)化腳步的蜉蝣進(jìn)行加速進(jìn)化操作，激發(fā)失效蜉蝣的潛能以增加算法收斂速度。當(dāng)蜉蝣無法跟隨種群進(jìn)化腳步的次數(shù)超過3次時，實(shí)施加速操作[11]，蜉蝣與當(dāng)前最優(yōu)解的適應(yīng)度差值與拉伸因子成正比，從而影響蜉蝣的速度。加入拉伸因子[SO]后的蜉蝣速度公式為：

[vtij=g*vtij+a1e-βr2ppbij-xtij][+a2e-βr2ggbj-xtij+SO] ⑾

其中[SO]為拉伸因子，其計算公式為：

[SO=c3*r2*（gbest-pbest）] ⑿

其中[c3]的計算公式為：

[c3=（xcost-gcost）/（avecost-gcost）] ⒀

其中[xcost]為蜉蝣的適應(yīng)度，[gcost]為全局最優(yōu)解的適應(yīng)度，[avecost]為種群平均適應(yīng)度。

2.3 動態(tài)慣性權(quán)重

為平衡算法全局搜索能力與局部探索性能，算法前期以較小的慣性權(quán)重減小蜉蝣步長，保持種群多樣性，中期增大慣性權(quán)重，加強(qiáng)全局搜索能力，后期減小慣性權(quán)重，增強(qiáng)局部探索性能，增加算法收斂精度，所以本文采用二次函數(shù)改變慣性權(quán)重，公式如下：

[g=-4gmax-gminMaxIt2*it2+][4gmax-gminMaxIt*it+gmin] ⒁

其中[gmax]為最大慣性因子;[gmin]為最小慣性因子，[MaxIt]為最大迭代次數(shù)，[it]為當(dāng)前迭代次數(shù)。

2.4 LMA算法流程

Step1 初始化參數(shù)，初始化雄雌蜉蝣位置與速度，并計算適應(yīng)度，尋找當(dāng)前最佳適應(yīng)度。

Step2 更新蜉蝣速度與位置，判斷蜉蝣無法跟隨進(jìn)化的次數(shù)，若超過3次，則按式⑿更新速度，否則按式⑴和式⑵更新速度，并計算適應(yīng)度。

Step3 根據(jù)式⑷生成后代數(shù)量為nm，根據(jù)變異可能性mu和式⑸產(chǎn)生變異后代，并將各個后代隨機(jī)插入雄蜉蝣或雌蜉蝣隊列。

Step4 根據(jù)種群的適應(yīng)度實(shí)行精英保留策略。

Step5 按式⑼計算本次種群解的方差值，并與上一代種群的方差作比較，若差值小于[10-3]，則按式⑹～式⑻執(zhí)行混沌機(jī)制。

Step6 更新舞蹈因子，隨機(jī)飛行因子，更新慣性因子。

Step7 迭代次數(shù)加一，判斷是否到達(dá)迭代上限，若是則轉(zhuǎn)Step8，若否則轉(zhuǎn)Step2。

Step8 輸出種群歷史最優(yōu)解。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 測試函數(shù)

為驗(yàn)證LMA的算法性能，隨機(jī)抽取5個benchmark標(biāo)準(zhǔn)測試函數(shù)。其中F1、F2為單峰函數(shù)，用來測試算法的全局尋優(yōu)能力，F(xiàn)3、F4為高維多峰函數(shù)，用來檢測算法對復(fù)雜問題的處理能力。F5函數(shù)在最優(yōu)點(diǎn)附近較為狹窄，用于測試算法的局部搜索能力。測試函數(shù)相關(guān)參數(shù)設(shè)置見表1。

3.2 算法參數(shù)設(shè)置

在解決高維問題時，群智能算法常常較難獲得很好的結(jié)果，為驗(yàn)證LMA算法在處理高維問題上的尋優(yōu)能力，設(shè)計在50維問題上的對比實(shí)驗(yàn)。設(shè)置迭代次數(shù)為2000次，種群數(shù)量為40。實(shí)驗(yàn)對比蜉蝣算法（MA），本文所提算法（LMA），經(jīng)典蜂群算法（ABC）[12]和基于混沌序列的蜂群優(yōu)化算法（CABC）[13]四種算法，LMA算法的參數(shù)設(shè)置可參照表2，其他算法參數(shù)設(shè)置參考文獻(xiàn)。

3.3 實(shí)驗(yàn)數(shù)據(jù)及分析

實(shí)驗(yàn)將每個算法對每個問題獨(dú)立測試100次記錄算法結(jié)果的平均值，最優(yōu)解，最劣解和方差。

表3中記錄四種算法對每個測試函數(shù)進(jìn)行測試后的數(shù)據(jù)。在F1、F2測試函數(shù)上，LMA算法對比其他算法的平均值、最優(yōu)值、最劣值和方差都有較為明顯的優(yōu)勢，說明LMA算法的尋優(yōu)能力更強(qiáng)、魯棒性更好。對比MA算法與ABC算法，LMA算法與CABC算法都采用混沌機(jī)制，在處理F3、F4函數(shù)時，最優(yōu)值上有較大的優(yōu)勢，說明采用該機(jī)制使算法處理多峰復(fù)雜問題的能力有所提升。綜上所述，LMA算法的改進(jìn)策略有效地提升算法對處理高維問題的能力，提高了算法尋優(yōu)性能。

為更加直觀地體現(xiàn)LMA算法的優(yōu)越性能，繪制出圖1～圖5仿真四種算法的收斂曲線。

在局部搜索能力方面，參照F5函數(shù)，觀察函數(shù)收斂曲線，ABC算法較難向下收斂，CABC算法依靠混沌策略可以向下尋優(yōu)，但尋優(yōu)過程不穩(wěn)定，魯棒性較差。MA算法較為有效地向下尋優(yōu)，但對比LMA算法的收斂曲線，LMA算法的求解精度更為準(zhǔn)確，收斂效率更高。因此相比較其他算法，LMA算法在局部搜索能力上更強(qiáng);在算法全局搜索能力方面，對比F2函數(shù)曲線可以看到LMA算法在算法中后期的收斂效率明顯優(yōu)于其他三種算法;在改進(jìn)策略的有效性方面，全面對比函數(shù)曲線，LMA算法在迭代前期收斂效率高于MA算法，在迭代后期，LMA算法對于部分容易陷入局部最優(yōu)的函數(shù)仍然可以向下尋優(yōu)，這說明改進(jìn)策略有效地提升算法的尋優(yōu)能力，增強(qiáng)算法對求解陷入困境的處理能力。

4 結(jié)束語

MA算法本身在收斂效率、全局搜索能力和局部搜索能力上，比一般群智能算法更好，本文針對MA算法在高維度復(fù)雜問題上易陷入局部最優(yōu)區(qū)域和求解精度較低等問題，提出改進(jìn)算法，實(shí)驗(yàn)證明在種群進(jìn)化停止時，LMA算法的處理能力比MA算法更好，在尋優(yōu)能力方面，LMA算法也展現(xiàn)出更好的性能，下一步研究方向?yàn)榧涌焖惴ǖ氖諗克俣取?/p>

參考文獻(xiàn)（References）：

[1] Guo X D， Zhang X L， Wang L F， et al. Fruit Fly

Optimization Algorithm Based on Single-Gene Mutation for High-Dimensional Unconstrained Optimization Problems[J].Mathematical Problems in Engineering，2020.

[2] 王習(xí)濤.一種優(yōu)化局部搜索能力的灰狼算法[J].計算機(jī)時代，2020.342（12）：57-59

[3] 何錦福，符強(qiáng)，王豪東.求解TSP問題的改進(jìn)模擬退火算法[J].計算機(jī)時代，2019.7：47-50

[4] 劉生建，楊艷，周永權(quán).求解0-1背包問題的二進(jìn)制獅群算法[J].計算機(jī)工程與科學(xué)，2019.41（11）：179-187

[5] Zervoudakis K， Tsafarakis S. A mayfly optimizationalgorithm[J].Computers & Industrial Engineering，2020.145：106559

[6] Liu Z， Qin Z， Zhu P， et al. An adaptive switchover hybrid particle swarm optimization algorithm with local search strategy for constrained optimization problems[J].Engineering Applications of Artificial Intelligence，2020.95：103771

[7] Hou L， Zou J， Du C， et al. A fault diagnosis model of? marine diesel engine cylinder based on modified genetic algorithm and multilayer perceptron[J]. Soft Computing，2020.24（2）.

[8] 李永恒，趙志剛.基于越界重置和高斯變異的蝙蝠優(yōu)化算法[J].計算機(jī)工程與科學(xué)，2019.41（1）：144-152

[9] 韓雪娟，李國東，王思秀 基于Logistic和超混沌結(jié)合的加密算法[J].計算機(jī)科學(xué)，2019.46（0z2）：477-482

[10] 王亞，熊焰，龔旭東，陸琦瑋.基于混沌PSO算法優(yōu)化RBF網(wǎng)絡(luò)入侵檢測模型[J].計算機(jī)工程與應(yīng)用，2013.49（10）：84-87

[11] 李榮龍，羅杰.一種改進(jìn)的粒子群優(yōu)化算法[J].計算機(jī)技術(shù)與發(fā)展，2015.25（7）：67-71

[12] 何堯，劉建華，楊榮華.人工蜂群算法研究綜述[J]. 計算機(jī)應(yīng)用研究，2018.319（5）：7-12

[13] 羅鈞，李研.具有混沌搜索策略的蜂群優(yōu)化算法[J].控制與決策，2010.25（12）：1913-1916