考慮距離因素與精英進(jìn)化策略的平衡優(yōu)化器

張偉康，劉升，黃倩，郭雨鑫

考慮距離因素與精英進(jìn)化策略的平衡優(yōu)化器

張偉康，劉升*，黃倩，郭雨鑫

（上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201620）（*通信作者電子郵箱 ls6601@163.com）

針對平衡優(yōu)化器（EO）存在尋優(yōu)精度低、收斂速度慢、容易陷入局部最優(yōu)的不足，提出一種考慮距離因素與精英進(jìn)化策略的平衡優(yōu)化器（E-SFDBEO）。該算法首先在平衡池候選解的選擇中引入距離因素，通過自適應(yīng)權(quán)重平衡適應(yīng)度值和距離，調(diào)節(jié)算法在不同迭代時(shí)期的探索和開發(fā)能力；其次引入精英進(jìn)化策略（EES），以精英自然進(jìn)化和精英隨機(jī)變異兩種方式提升算法的收斂速度和精度；最后使用自適應(yīng)t分布變異策略對部分個(gè)體施加擾動(dòng)，并以貪心策略對個(gè)體進(jìn)行保留，使算法能夠有效跳出局部最優(yōu)。在仿真實(shí)驗(yàn)中對所提算法與4種基本算法和2種改進(jìn)算法在10個(gè)基準(zhǔn)測試函數(shù)進(jìn)行比較，并對算法進(jìn)行Wilcoxon秩和檢驗(yàn)，結(jié)果表明所提算法具有更好的收斂性和更高的求解精度。

平衡優(yōu)化器；距離因素；精英進(jìn)化策略；自適應(yīng)權(quán)重；全局優(yōu)化

0 引言

全局優(yōu)化問題廣泛存在于經(jīng)濟(jì)、數(shù)學(xué)、醫(yī)學(xué)以及工程等領(lǐng)域，解決此類問題的方法一般可分為傳統(tǒng)數(shù)學(xué)優(yōu)化算法和元啟發(fā)式算法。傳統(tǒng)數(shù)學(xué)優(yōu)化算法（如牛頓法、共軛梯度法、二次規(guī)劃法等）具有完善的數(shù)學(xué)理論基礎(chǔ)，能夠快速準(zhǔn)確地求解單極值問題；而對于具有高維、非線性多極值等特點(diǎn)的復(fù)雜問題，元啟發(fā)式算法（如粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法、鯨魚優(yōu)化算法（Whale Optimization Algorithm， WOA）、麻雀搜索算法等）則具有更好的求解能力。元啟發(fā)式算法不涉及導(dǎo)數(shù)信息或其他數(shù)學(xué)特性（如連續(xù)性、凸性等），是一種模擬自然界生物行為和現(xiàn)象的算法，具有良好的適應(yīng)性和自主探索能力。然而，大多數(shù)元啟發(fā)式算法存在對控制參數(shù)敏感以及由于陷入局部最優(yōu)而無法保證收斂到最優(yōu)的狀況。

平衡優(yōu)化器（Equilibrium Optimizer， EO）［1］是一種基于物理的元啟發(fā)式算法，它受到控制容積的動(dòng)態(tài)質(zhì)量平衡啟發(fā)，模擬了控制容積中非活躍成分進(jìn)入、離開和生成的過程，以不同濃度的粒子作為搜索種群，其中每個(gè)粒子的濃度代表一種優(yōu)化問題的解決方案。EO具有結(jié)構(gòu)簡單、適應(yīng)性強(qiáng)以及靈活性高的優(yōu)點(diǎn)，目前已有學(xué)者將其應(yīng)用到電網(wǎng)優(yōu)化設(shè)計(jì)［2-3］等工程問題中，進(jìn)一步證實(shí)了算法的優(yōu)越性。然而算法中種群位置方式始終依賴于平衡狀態(tài)方程，使得算法容易陷入局部最優(yōu)，且缺乏跳出局部最優(yōu)的有效策略，限制了算法的尋優(yōu)能力［4］；同時(shí)，在構(gòu)建EO特有的平衡池階段時(shí)，候選者完全根據(jù)適應(yīng)度值大小進(jìn)行選取，這使得所選取的個(gè)體具有極大的相似性，增加了算法陷入局部最優(yōu)的風(fēng)險(xiǎn)。針對以上缺陷，國內(nèi)外學(xué)者相繼對EO進(jìn)行改進(jìn)。楊柳慶等［5］提出一種基于萊維飛行改進(jìn)的EO（Equilibrium Optimizer based on Lévy flight， LEO），為算法提供了一種跳出局部最優(yōu)的思路。Gupta等［6］利用高斯變異和基于種群劃分與重構(gòu)概念的探索機(jī)制改進(jìn)EO（modified EO， m-EO），豐富了EO的尋優(yōu)策略。Too等［4］針對EO平衡池階段的缺陷，引入一般學(xué)習(xí)思想，使得個(gè)體能夠從不同維度向平衡池中的候選者進(jìn)行學(xué)習(xí)，有助于算法避開局部最優(yōu)。Wunnava等［7］提出了一種基于當(dāng)前適應(yīng)度值的自適應(yīng)位置更新策略，用以改善EO過于依賴平衡狀態(tài)方程的問題。Sayed等［8］利用10種混沌映射對EO中平衡全局探索和局部開發(fā)能力的參數(shù)進(jìn)行自適應(yīng)更新，提高了算法的穩(wěn)健性。Abdel-Basset等［9］等通過線性化簡分集技術(shù)使較差的個(gè)體向最優(yōu)個(gè)體學(xué)習(xí)，以提高EO的收斂速度；同時(shí)為了防止個(gè)體多樣性降低，通過局部極小消去法隨機(jī)選擇的兩個(gè)個(gè)體邊界或問題本身的邊界作為當(dāng)前解，提高了算法的勘探能力。

以上對EO的改進(jìn)或是直接增加策略，或是集中于算法的某個(gè)缺陷，而本文針對EO的缺陷進(jìn)行了更加全面的分析和改進(jìn)，提出了一種基于精英進(jìn)化與自適應(yīng)平衡適應(yīng)度和距離改進(jìn)的平衡優(yōu)化器（Equilibrium Optimizer with Elite evolutionary and Self-adaption Fitness-Distance Balance， E-SFDBEO）。該算法引入了兩種較為新穎的改進(jìn)策略：在EO中平衡池候選者選取階段，考慮距離因素的影響，并引入自適應(yīng)權(quán)重平衡適應(yīng)度值和距離，調(diào)節(jié)算法在不同迭代時(shí)期的探索和開發(fā)能力；其次引入精英進(jìn)化策略（Elite Evolutionary Strategy， EES），以精英自然進(jìn)化和精英隨機(jī)變異兩種方式提升算法的收斂速度和精度。其中，距離因素是由Kahraman等［10］率先提出，以適應(yīng)度-距離平衡（Fitness-Distance Balance， FDB）方式選取候選者，并成功應(yīng)用于共生生物算法，能提高算法的尋優(yōu)性能；Duman等［11］進(jìn)一步提出了一種輪盤賭適應(yīng)度-距離平衡（Roulette Fitness-Distance Balance， RFDB）選擇方法，然而該方法采用的是固定比例平衡適應(yīng)度和距離，本文對其作了進(jìn)一步的改進(jìn)，通過一種自適應(yīng)余弦因子進(jìn)行調(diào)節(jié)，在迭代初期使距離因素占比更高，后期則使適應(yīng)度占比更高。EES則是由Li等［12］提出并成功應(yīng)用于哈里斯鷹算法，該策略以進(jìn)化方法的核心原理為基礎(chǔ)，通過精英個(gè)體的進(jìn)化和變異操作提高算法的尋優(yōu)能力。此外，為了增強(qiáng)算法跳出局部最優(yōu)的能力，本文使用自適應(yīng)t分布變異策略對部分個(gè)體施加擾動(dòng)，并以貪心策略對個(gè)體進(jìn)行保留。

1 平衡優(yōu)化器

EO是一種基于控制容積內(nèi)質(zhì)量動(dòng)態(tài)平衡物理現(xiàn)象啟發(fā)的優(yōu)化算法，其具體尋優(yōu)流程如下：

1）隨機(jī)初始化。與大多數(shù)元啟發(fā)式算法相似，EO使用初始種群來啟動(dòng)優(yōu)化過程。初始狀態(tài)是根據(jù)粒子的數(shù)量和規(guī)模在搜索空間中隨機(jī)均勻構(gòu)造的，如下式所示：

2）平衡池和候選解。平衡池中匯集了當(dāng)前解中適應(yīng)度值排名前四位的粒子以及這四個(gè)粒子的平均值，作為更新公式的候選解，如下式所示：

5）更新公式。經(jīng)過對原物理理論的抽象和改進(jìn)后，EO的更新公式確立為：

2 平衡優(yōu)化器的改進(jìn)

2.1 精英進(jìn)化策略

為豐富EO的位置更新策略，本文首先采用一種多種群技術(shù)將種群劃分為兩個(gè)部分以便引入不同的策略，從而豐富解的多樣性，使種群盡可能地搜索更多的解空間［13-14］。將1/2的個(gè)體按照EES進(jìn)行尋優(yōu)，剩下的個(gè)體則仍然保持原始EO的策略。EES主要受到遺傳算法和差分進(jìn)化（Differential Evolution， DE）算法的啟發(fā)，包括了精英自然進(jìn)化和精英隨機(jī)突變兩個(gè)階段，能夠有效提高算法的收斂速度和跳出局部最優(yōu)的能力［12］。

2.1.1 精英自然進(jìn)化

精英自然進(jìn)化的核心原則是基因交叉和基因局部突變，主要包括以下三個(gè)步驟：

2.1.2 精英隨機(jī)突變

精英隨機(jī)突變是在搜索范圍內(nèi)對某些精英個(gè)體進(jìn)行變異，主要包括以下兩個(gè)步驟：

1）隨機(jī)突變：在搜索空間內(nèi)生成一個(gè)全新的個(gè)體，如式（14）。

2）基因交叉重組：將隨機(jī)突變產(chǎn)生的個(gè)體與精英個(gè)體進(jìn)行交叉重組，具體實(shí)現(xiàn)方式如式（15）。

2.2 考慮距離因素的平衡池構(gòu)建策略

啟發(fā)式算法一般可以分為兩部分：一是根據(jù)一定準(zhǔn)則在總體中選擇候選解（即搜索空間中的相關(guān)位置）；二是對選擇出來的候選解采用各種策略進(jìn)行搜索操作。因此，算法的收斂速度和收斂精度不僅取決于算法所采取的搜索策略，很大程度上也受到所采用的候選解選擇方法的影響。目前常用的選擇方法有隨機(jī)選擇法、基于適應(yīng)度值的順序選擇法、基于適應(yīng)度值的概率選擇法以及組合選擇法［10］。這些方法大多數(shù)都以適應(yīng)度值作為選擇依據(jù)，而僅考慮適應(yīng)度值會(huì)使得所選結(jié)果很大概率落在相似區(qū)域，這會(huì)使得算法容易陷入局部最優(yōu)。尤其對于結(jié)構(gòu)簡單、位置更新策略單一的算法而言，受到相似候選解的主導(dǎo)影響，算法快速向局部最優(yōu)值靠近，導(dǎo)致早熟早收斂。

EO在平衡池候選解選擇的過程中采用的是基于適應(yīng)度值的順序選擇法，這種方法使算法極易落入局部最優(yōu)，影響算法的尋優(yōu)效果。因此，本文提出一種自適應(yīng)權(quán)重平衡適應(yīng)度值和距離的選擇方法，將距離因素引入候選解的選擇中，并通過自適應(yīng)權(quán)重調(diào)節(jié)不同迭代時(shí)期適應(yīng)度值和距離的比重。具體實(shí)現(xiàn)步驟如下：

1）計(jì)算候選解與最佳解的距離：在這一步可以采取歐氏距離、曼哈頓距離以及閔可夫斯基距離等距離度量方式。本文采用歐氏距離，具體計(jì)算方式如下：

3）確定候選解：根據(jù)個(gè)體得分大小確定最終的候選者。

2.3 自適應(yīng)t分布變異策略

2.4 E-SFDBEO的流程

E-SFDBEO的具體執(zhí)行流程如圖1所示。

圖1 E-SFDBEO流程

2.5 計(jì)算復(fù)雜度分析

因此，EO總體時(shí)間復(fù)雜度可以表示為：

故改進(jìn)算法的計(jì)算復(fù)雜度與原算法保持一致，并沒有增加計(jì)算負(fù)擔(dān)。

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

3.1 仿真實(shí)驗(yàn)環(huán)境

本文的仿真實(shí)驗(yàn)基于Intel Core i7-7500U CPU @ 2.70 GHz 2.90 GHz，12 GB內(nèi)存，以及Windows 10操作系統(tǒng)，仿真軟件為Matlab R2018b。

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

本文選取的對比算法包括：基本EO、PSO算法［16］、DE算法［17］、灰狼優(yōu)化（Grey Wolf Optimization， GWO）算法［18］、WOA［19］、LEO［5］以及m-EO［6］。為保證實(shí)驗(yàn)的公平性，所有算法的種群規(guī)模為30，迭代次數(shù)為200，其他參數(shù)設(shè)置見表1。

表1 各算法的實(shí)驗(yàn)參數(shù)

3.3 測試函數(shù)

表2 基準(zhǔn)測試函數(shù)

3.4 與其他智能算法對比分析

將所有算法分別在13個(gè)基本測試函數(shù)上獨(dú)立運(yùn)行30次，其中非固定維度函數(shù)的維度定為30（即=30），用于分析本文算法相較于其他群智能算法在尋優(yōu)性能以及穩(wěn)定性方面的優(yōu)勢，結(jié)果如表3所示。

表3 測試函數(shù)實(shí)驗(yàn)結(jié)果

以上分析表明E-SFDBEO通過對兩個(gè)種群執(zhí)行不同的搜索策略，提供了多樣的尋優(yōu)思路和解決方案，并以自適應(yīng)t分布變異策略對最優(yōu)個(gè)體進(jìn)行擾動(dòng)，使得算法具備快速跳出局部最優(yōu)的能力，提高了算法的尋優(yōu)能力和魯棒性。

圖2 測試函數(shù)收斂曲線

Fig 2 Convergence curves of test functions

3.5 Wilcoxon秩和檢驗(yàn)

3.6 所提改進(jìn)策略有效性分析

表4 Wilcoxon秩和檢驗(yàn)結(jié)果

表5 不同策略改進(jìn)的EO對測試函數(shù)實(shí)驗(yàn)結(jié)果

3.7 E-SFDBEO求解大規(guī)模問題可行性分析

在實(shí)際應(yīng)用中大規(guī)模問題普遍存在，為了檢驗(yàn)本文E-SFDBEO算法在求解大規(guī)模問題中的可行性，將其在3.3節(jié)中非固定維數(shù)的測試函數(shù)上進(jìn)行測試，函數(shù)維度分別設(shè)為500和1 000，相關(guān)參數(shù)同3.2節(jié)，共運(yùn)行30次取平均值，結(jié)果如表6所示。

表6 大規(guī)模測試函數(shù)實(shí)驗(yàn)結(jié)果

4 結(jié)語

本文提出一種考慮距離因素與精英進(jìn)化的平衡優(yōu)化器，通過精英進(jìn)化策略，改善了EO在位置更新過程中過于依賴平衡狀態(tài)方程的問題；針對EO中平衡池構(gòu)建過程中僅考慮適應(yīng)度值，導(dǎo)致候選解過于集中的缺陷，提出一種自適應(yīng)平衡適應(yīng)度值和距離的選擇方法，將距離因素考慮到候選解的選擇中，提高了候選解的多樣性和質(zhì)量；另外，通過自適應(yīng)t分布變異，使算法有機(jī)會(huì)跳出局部最優(yōu)?；鶞?zhǔn)測試函數(shù)實(shí)驗(yàn)及Wilcoxon秩和檢驗(yàn)顯示，改進(jìn)算法具有較強(qiáng)的跳出局部最優(yōu)的能力、更快的收斂速度和更高的收斂精度。下一步考慮將E-SFDBEO應(yīng)用到實(shí)際問題中，如機(jī)器學(xué)習(xí)中超參數(shù)的優(yōu)化等，以擴(kuò)展本文算法的應(yīng)用范圍。

[1] FARAMARZI A， HEIDARINEJAD M， STEPHENS B， et al. Equilibrium optimizer： a novel optimization algorithm［J］. Knowledge-Based Systems， 2020， 191： No.105190.

[2] 楊蕾，李勝男，黃偉，等. 基于平衡優(yōu)化器的含高比例風(fēng)光新能源電網(wǎng)無功優(yōu)化［J］. 電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)， 2021， 33（4）：32-39.（YANG L， LI S N， HUANG W， et al. Reactive Power optimization of power grid with high-penetration wind and solar renewable energies based on equilibrium optimizer［J］. Proceedings of the CSU-EPSA， 2021， 33（4）：32-39.）

[3] KHARRICH M， KAMEL S， ABDEEN M， et al. Developed approach based on equilibrium optimizer for optimal design of hybrid PV/wind/diesel/battery microgrid in Dakhla， Morocco［J］. IEEE Access， 2021， 9：13655-13670.

[4] TOO J， MIRJALILI S. General learning equilibrium optimizer： a new feature selection method for biological data classification［J］. Applied Artificial Intelligence， 2021， 35（3）： 247-263.

[5] 楊柳慶，楊婷婷，王鵬飛，等. 一種基于萊維飛行的新型改進(jìn)平衡全局優(yōu)化算法［J］. 宇航計(jì)測技術(shù)， 2020， 40（5）： 62-69.（YANG L Q， YANG T T， WANG P F， et al. A new improved equilibrium global optimization algorithm based on Lévy flight［J］. Journal of Astronautic Metrology and Measurement， 2020， 40（5）：62-69.）

[6] GUPTA S， DEEP K， MIRJALILI S. An efficient equilibrium optimizer with mutation strategy for numerical optimization［J］. Applied Soft Computing， 2020， 96： No.106542.

[7] WUNNAVA A， NAIK M K， PANDA R， et al. A novel interdependence based multilevel thresholding technique using adaptive equilibrium optimizer［J］. Engineering Applications of Artificial Intelligence， 2020， 94： No.103836.

[8] SAYED G I， KHORIBA G， HAGGAG M H. A novel chaotic equilibrium optimizer algorithm with S-shaped and V-shaped transfer functions for feature selection［J］. Journal of Ambient Intelligence and Humanized Computing， 2022， 13： 3137-3162.

[9] ABDEL-BASSET M， MOHAMED R， MIRJALILI S， et al. Solar photovoltaic parameter estimation using an improved equilibrium optimizer［J］. Solar Energy， 2020， 209：694-708.

[10] KAHRAMAN H T， ARAS S， GEDIKLI E. Fitness-Distance Balance （FDB）： a new selection method for meta-heuristic search algorithms［J］. Knowledge-Based Systems， 2020， 190： No.105169.

[11] DUMAN S， KAHRAMAN H T， GUVENC U， et al. Development of a Lévy flight and FDB-based coyote optimization algorithm for global optimization and real-world ACOPF problems［J］. Soft Computing， 2021， 25（8）：6577-6617.

[12] LI C Y， LI J， CHEN H L， et al. Memetic Harris hawks optimization： developments and perspectives on project scheduling and QoS-aware web service composition［J］. Expert Systems with Applications， 2021， 171： No.114529.

[13] BARSHANDEH S， PIRI F， SANGANI S R. HMPA： an innovative hybrid multi-population algorithm based on artificial ecosystem-based and Harris hawks optimization algorithms for engineering problems ［J/OL］. Engineering with Computers， 2020（35）［2021-04-13］. https：//doi.org/10.1007/s00366-020-01120-w.

[14] CHEN H， HEIDARI A A， CHEN H L， et al. Multi-population differential evolution-assisted Harris hawks optimization： framework and case studies［J］. Future Generation Computer Systems， 2020， 111：175-198.

[15] 周方俊，王向軍，張民. 基于分布變異的進(jìn)化規(guī)劃［J］. 電子學(xué)報(bào)， 2008， 36（4）：667-671.（ZHOU F J， WANG X J， ZHANG M. Evolutionary programming using mutations based on theprobability distribution［J］. Acta Electronica Sinica， 2008， 36（4）：667-671.）

[16] KENNEDY J， EBERHART R. Particle swarm optimization［C］// Proceedings of the 1995 International Conference on Neural Networks. Piscataway： IEEE， 1995： 1942-1948.

[17] STORN R， PRICE K. Differential evolution — a simple and efficient heuristic for global optimization over continuous spaces［J］. Journal of Global Optimization， 1997， 11（4）：341-359.

[18] MIRJALILI S， MIRJALILI S M， LEWIS A. Grey wolf optimizer［J］. Advances in Engineering Software， 2014， 69：46-61.

[19] MIRJALILI S， LEWIS A. The whale optimization algorithm［J］. Advances in Engineering Software， 2016， 95： 51-67．

Equilibrium optimizer considering distance factor and elite evolutionary strategy

ZHANG Weikang， LIU Sheng*， HUANG Qian， GUO Yuxin

（，，201620，）

Aiming at the shortcomings of Equilibrium Optimizer （EO） such as low optimization accuracy， slow convergence and being easy to fall into local optimum， a new EO in consideration with distance factor andElite Evolutionary Strategy （EES） named E-SFDBEO was proposed. Firstly， the distance factor was introduced to select the candidate solutions of the equilibrium pool， and the adaptive weight was used to balance the fitness value and distance， thereby adjusting the exploration and development capabilities of the algorithm in different iterations. Secondly， the EES was introduced to improve the convergence speed and accuracy of the algorithm by both elite natural evolution and elite random mutation. Finally， the adaptive t-distribution mutation strategy was used to perturb some individuals， and the individuals were retained with greedy strategy， so that the algorithm was able to jump out of the local optimum effectively. In the simulation experiment， the proposed algorithm was compared with 4 basic algorithms and 2 improved algorithms based on 10 benchmark test functions and Wilcoxon rank sum test was performed to the algorithms. The results show that the proposed algorithm has better convergence and higher solution accuracy.

Equilibrium Optimizer (EO); distance factor; Elite Evolutionary Strategy (EES); adaptive weight; global optimization

This work is partially supported by National Natural Science Foundation of China （61075115，61673258）， Shanghai Municipal Natural Science Foundation （19ZR1421600）.

ZHANG Weikang， born in 1996， M. S. candidate. His research interests include business statistics， intelligent computing.

LIU Sheng， born in 1966， Ph. D.， professor. His research interests include artificial intelligence， machine learning.

HUANG Qian， born in 1995， M. S. candidate. Her research interests include intelligent computing， business statistics.

GUO Yuxin， born in 1996， M. S. candidate. Her research interests include intelligent computing， technical economic management.

TP301.6

A

1001-9081（2022）06-1844-08

10.11772/j.issn.1001-9081.2021040574

2021?04?13；

2021?06?28；

2021?06?29。

國家自然科學(xué)基金資助項(xiàng)目（61075115，61673258）；上海市自然科學(xué)基金資助項(xiàng)目（19ZR1421600）。

張偉康（1996—），男，山東臨沂人，碩士研究生，主要研究方向：商務(wù)統(tǒng)計(jì)、智能計(jì)算；劉升（1966—），男，湖北黃石人，教授，博士，主要研究方向：人工智能、機(jī)器學(xué)習(xí)；黃倩（1995—），女，江蘇常州人，碩士研究生，主要研究方向：智能計(jì)算、商務(wù)統(tǒng)計(jì)；郭雨鑫（1996—），女，山東濰坊人，碩士研究生，主要研究方向：智能計(jì)算、技術(shù)經(jīng)濟(jì)管理。