基于分區(qū)搜索和強化學習的多模態(tài)多目標頭腦風暴優(yōu)化算法

摘 要：維持種群多樣性和提高算法搜索效率是多模態(tài)多目標優(yōu)化亟需解決的兩大問題。為解決以上問題，提出了一種基于分區(qū)搜索和強化學習的多模態(tài)多目標頭腦風暴優(yōu)化算法（MMBSO-ZSRL）。在MMBSO-ZSRL中，首先將決策空間分解為多個子空間以降低搜索難度和維持種群多樣性；然后，使用SARSA（state-action-reward-state-action） 算法來平衡頭腦風暴算法的全局探索和局部開發(fā)能力；并使用特殊擁擠距離來挑選個體來指導種群進化。為了驗證所提算法的性能，選取六種先進的多模態(tài)多目標優(yōu)化算法來進行比較，并選取IEEE CEC2019多模態(tài)多目標問題基準測試集來對所有比較算法的性能進行測試。實驗結果表明，MMBSO-ZSRL的整體性能要顯著優(yōu)于其他六種比較算法。MMBSO-ZSRL不僅可以找到多樣性和逼近性更好的帕累托前沿，而且可以在決策空間找到更多的帕累托最優(yōu)解。

關鍵詞：多模態(tài)多目標優(yōu)化； 頭腦風暴優(yōu)化算法； 強化學習； SARSA算法； 分區(qū)搜索

中圖分類號：TP301.6 文獻標志碼：A

文章編號：1001-3695（2024）08-018-2374-10

doi：10.19734/j.issn.1001-3695.2023.12.0588

Multimodal multi-objective brain storm optimization algorithm based onzoning search and reinforcement learning

Li Xin1， Yu Moduo2， Jiang Qingchao3， Fan Qinqin1

（1.Logistics Research Center， Shanghai Maritime University， Shanghai 201306， China; 2.Key Laboratory of Control of Power Transmission & Conversion（Ministry of Education）， Shanghai Jiao Tong University， Shanghai 200240， China; 3.Key Laboratory of Smart Manufacturing in Energy Chemical Process of Ministry of Education， East China University of Science & Technology， Shanghai 200237， China）

Abstract：Maintaining population diversity and improving algorithm search efficiency are two major problems that need to be solved urgently in the multimodal multi-objective optimization. To address the above problems， this paper proposed a multimodal multi-objective brain storm optimization algorithm based on zoning search and reinforcement learning（MMBSO-ZSRL） . In the MMBSO-ZSRL， the decision space was first decomposed into multiple subspaces to reduce the search difficulty and maintain the population diversity. Subsequently， the proposed algorithm used SARSA algorithm to balance the global exploration and local exploitation capabilities of the brain storm optimization algorithm. Additionally， the MMBSO-ZSRL utilized the special crowding distance to select individuals for guiding the population evolution. To verify the performance of the proposed algorithm， this paper selected six advanced multimodal multi-objective optimization algorithms and the IEEE CEC2019 multimodal multi-objective problem benchmark test suite for experiments. Experimental results demonstrate that the overall perfor-mance of the MMBSO-ZSRL is significantly better than that of compared algorithms. The proposed MMBSO-ZSRL can not only find the Pareto front with better diversity and approximation， but also find more Pareto optimal solutions in the decision space.

Key words：multimodal multi-objective optimization（MMO）; brain storm optimization algorithm; reinforcement learning; SARSA algorithm; zoning search

0 引言

在現(xiàn)實世界中，諸多領域的優(yōu)化問題都屬于多目標優(yōu)化問題 （multi-objective optimization problems，MOPs）。對于部分MOPs，它們在解空間存在等效帕累托最優(yōu)解，因此被稱為多模態(tài)多目標優(yōu)化問題（multimodal MOPs，MMOPs）［1～3］ 。MMOPs廣泛存在于各個領域，比如調度優(yōu)化［4］、火箭發(fā)動機設計［5］、多機器人任務分配［6］、配電網(wǎng)故障恢復［7］等。一個典型的多模態(tài)多目標優(yōu)化問題如圖1所示。從圖1可以看出，決策空間中兩個不同點A和B對應相同的目標值P。因此，對于MMOPs而言，在目標空間找到好的帕累托前沿 （Pareto front，PF） 逼近和在決策空間找到足夠多的等效帕累托最優(yōu)解同等重要。此外，由于多模態(tài)多目標優(yōu)化（MMO） 可以提供等效方案，這有助于決策者在不確定/動態(tài)環(huán)境下找到替代方案，所以受到了廣泛關注［2， 3］。

為有效求解MMOPs，諸多學者從環(huán)境選擇的角度進行研究。比如，Deb等人［8］提出一種綜合性的優(yōu)化算法Omin-optimizer來求解多類優(yōu)化問題（即單目標、多目標、單模態(tài)、多模態(tài)優(yōu)化問題）。不同于之前的研究，該算法通過支配關系、決策空間和目標空間擁擠距離三個指標來對個體進行選擇，從而保證解集在決策空間和目標空間的多樣性。Yue等人［9］提出一種基于環(huán)形拓撲結構和特殊擁擠距離的MMO粒子群算法。該算法使用一種特殊擁擠距離 （special crowding distance，SCD） 來對個體進行選擇。此外，還使用一種基于索引的環(huán)形拓撲結構來形成穩(wěn)定的小生境以提高算法的搜索能力。結果表明，所提算法能夠有效地提高種群在決策空間的多樣性。李文樺等人［10］提出一種同時考慮全局和局部PF的MMO算法。結果表明，與其他算法相比，所提算法能有效兼顧全局和局部帕累托最優(yōu)解。

為了有效提高決策空間的多樣性，研究人員還從搜索空間“隔離”的角度對MMO進行研究。比如，為了保留更多的等效帕累托最優(yōu)解，Liang等人［11］提出一種基于決策空間小生境方法的MMO算法。結果表明小生境方法可以保留幾乎所有的帕累托最優(yōu)解。隨后，Liang等人［12］提出一種基于自組織映射的多目標粒子群算法。該算法首先利用自組織映射策略來建立多個鄰域，然后使用精英學習策略提高算法的搜索效率。結果表明，所提算法能在決策空間定位到更多高質量的帕累托最優(yōu)解。Lin等人［13］提出一種決策和目標空間雙聚類的MMO算法。該算法首先在決策空間進行聚類，并選擇每個類中的非支配解和目標空間中的高質量解組成臨時種群。然后，在目標空間中對該臨時種群進行第二次聚類，并在目標空間擁擠的聚類中刪除決策空間擁擠的解。結果表明，該算法能有效維持全局和局部帕累托最優(yōu)解。Hu等人［14］提出一種基于自適應局部搜索的小生境回溯搜索MMO算法。該算法使用親和力傳播算法形成多個小生境，然后在每個小生境中使用所提算子進行搜索。此外，該算法還提出一種自適應局部搜索策略以平衡算法的探索和開發(fā)能力。結果表明，所提算法整體性能優(yōu)于所有對比算法。為解決決策空間種群多樣性差和個體空間分布不平衡的問題，Zhang等人［15］提出了一種基于兩階段雙小生境的進化策略。該算法分兩個階段解決MMOPs，第一階段使用決策空間小生境策略，其目標是在決策空間找到具有較好多樣性和收斂性的解集；為有效提高決策和目標空間中解集的質量，第二階段在兩個空間同時使用小生境策略。此外，為改善決策空間種群不平衡的問題，設計了一種決策空間密度自適應的策略。結果表明所提算法能夠有效求解MMOPs。上述研究大多采用小生境等“軟隔離”方法來提高決策空間的多樣性。不同于上述方法，F(xiàn)an等人［16］提出一種“硬隔離”的分區(qū)搜索 （zoning search，ZS） 方法以降低MMOPs的求解復雜度。隨后，F(xiàn)an等人［17］又提出一種自適應資源配置的ZS方法來進一步提高搜索效率。Ji等人［18］提出一種基于分區(qū)搜索和遷移學習的MMO算法。該算法引入遷移學習方法來實現(xiàn)子空間之間的知識共享。此外，F(xiàn)an等人［19］提出了一種基于分區(qū)搜索的多模態(tài)多目標頭腦風暴算法。該算法同時使用“軟隔離”和“硬隔離”的方法來提高決策空間多樣性。結果表明，所提算法在決策和目標空間上都極具競爭力。

在決策空間找到盡可能多的等效帕累托解和在目標空間找到一條高質量的帕累托前沿逼近是MMO的兩個重要目標。為進一步提高多模態(tài)多目標進化算法（multimodal multi-objective evolutionary algorithm，MMOEA） 的求解性能，本文提出一種基于分區(qū)搜索和強化學習的多模態(tài)多目標頭腦風暴優(yōu)化算法（multimodal multi-objective brain storm optimization algorithm based on zoning search and reinforcement learning，MMBSO-ZSRL）。在MMBSO-ZSRL中，首先使用分區(qū)搜索策略［16］將決策空間分為多個子空間以降低搜索難度，然后使用SARSA算法［20］來自動調整不同搜索算子的選擇概率，從而達到提高算法搜索性能的目的，此外，所提算法還利用特殊擁擠距離［9］來選擇個體，并將它們來引導種群進化。為了驗證MMBSO-ZSRL的性能，本文選取IEEE CEC2019 MMOPs基準測試集［21］與六種先進的MMOEAs［12，16，22～25］進行比較與測試。實驗結果顯示，MMBSO-ZSRL在PSP［9］和HV［26］兩個性能指標上均顯著優(yōu)于其他六種先進的MMOEAs。因此，MMBSO-ZSRL能夠搜索到更多的等效帕累托最優(yōu)解和獲得質量更高的PF逼近。

1 預備知識

1.1 多目標優(yōu)化問題

多目標優(yōu)化問題（以最小化問題為例）定義如下［27］：

min F（x）=（f1（x），f2（x），…，fM（x））s.t. x∈Ω（1）

其中：M表示目標的數(shù)量；x=（x1，x2，…，xD）為D維決策向量；Ω表示決策空間。其他一些相關概念描述如下［27］：

定理1 帕累托支配關系。向量q=（q1，q2，q3，…，qM）支配另一個向量q=（q1，q2，q3，…，qM）（記作pq）的條件是：i∈{1，2，3，…，M}，pi≤qi∧j∈{1，2，3，…，M}，pj<qj。

定理2 帕累托最優(yōu)解集（Pareto optimal set，PS）。一個向量x*∈Ω，若不存在其他向量x∈Ω，使得F（x）F（x*），就稱x*為帕累托最優(yōu)解。所有的帕累托最優(yōu)解構成的集合（記作X*），稱為PS。

定理3 帕累托前沿（Pareto front，PF）。在多目標優(yōu)化問題中，PF={F（x*）|x*∈X*}。

1.2 多模態(tài)多目標優(yōu)化問題及評價指標

相比于1.1節(jié)的多目標優(yōu)化問題，MMOPs是其一種特殊類型。若一個多目標優(yōu)化問題滿足以下任一條件［9，11］，則該問題屬于MMOPs：a）問題至少有一個局部帕累托最優(yōu)解集；b）問題存在至少兩個等效全局帕累托最優(yōu)解集對應于同一PF。MMO既要在目標空間找到高質量的PF逼近，又要保證找到?jīng)Q策空間足夠多的等效帕累托最優(yōu)解。因此，本文使用帕累托解集近似（Pareto set proximity，PSP）［9］和超體積值（hypervolume，HV）［26］這兩個性能指標來評價MMOEAs的性能。具體定義如下：

1）PSP

PSP用于評估所得解集PS*與真實帕累托最優(yōu)解集PS的相似性，其計算公式如式（2）所示。PSP值越大，表示算法在決策空間中的表現(xiàn)越好。

PSP=CRIGDx

IGDx（PS，PS*）=∑v∈PS*d（v，PS）|PS*|

CR=（∏Dj=1δj）12D

δj=1 Vmaxj=Vminj

0vminj≥Vmaxj‖vmaxj≤Vminj

min（vmaxj，Vminj）-max（vminj，Vmaxj）Vmaxj-Vminjotherwise（2）

其中：CR為覆蓋率；IGDx是決策空間反世代距離［28］；d（v，PS）指v與PS中最近點的歐氏距離；|PS*|表示PS*中解的數(shù)量；vmaxj和vminj分別表示PS中第j個維度的最大值和最小值；Vmaxj和Vminj分別表示PS*中第j個維度的最大值和最小值；max和min分別表示最大值函數(shù)和最小值函數(shù)。

2）HV

HV反映所獲得PF逼近的收斂性和多樣性，其計算公式如式（3）所示。HV值越大，代表算法所獲得PF逼近越接近真實PF，算法在目標空間中的表現(xiàn)越好。

HV（PS）=VOL（∪x∈PS*［f1（x），r1］×…×［fM（x），rM］）（3）

其中：VOL為勒貝格測度；r* = （r*1，r*2，…，r*M）是選擇的參考點。

1.3 頭腦風暴優(yōu)化算法

受人類頭腦風暴過程的啟發(fā)，Shi等人［29］于2011年提出一種模擬人類集體行為的頭腦風暴優(yōu)化（brain storm optimization，BSO）算法。BSO算法的步驟［29～31］如下：

a）隨機生成一個初始種群。

b）使用K-means聚類方法將種群分為K個聚類，對每個聚類中的個體進行排序，并將好的個體作為該類的聚類中心。

c）以一定概率Pre產(chǎn)生隨機個體替代某一類的聚類中心。

d）在任意一個聚類中，選擇一個隨機個體或者聚類中心來產(chǎn)生候選個體xtselect；或者在任意兩個聚類中，分別選擇它們的隨機個體或者聚類中心來生成xtselect。產(chǎn)生xtselect的具體方式如下［29］：

if p1<0.8

xtselect=xc if p2<0.4xrotherwise（4）

else

xtselect=w1×xc1+（1-w1）×xc2 if p3<0.5w1×xr1+（1-w1）×xr2otherwise（5）

end

其中：xc和xr分別為任意一個聚類的聚類中心和隨機個體；xc1和xc2為任意兩個聚類的聚類中心；xr1和xr2為任意兩個聚類的隨機個體；p1、p2、p3和w1都為［0，1］的隨機數(shù)。

然后，通過高斯變異來產(chǎn)生新個體xtnew，公式如下：

xtnew=xtselect+ξ（t）×N（μ，σ）

ξ（t）=log sig0.5×T-tz×rand（6）

其中：ξ為變異系數(shù)；N（μ，σ）是均值為μ，方差為σ的高斯隨機數(shù)；logsig為對數(shù)S型傳遞函數(shù)；T表示最大迭代次數(shù)；z是改變logsig函數(shù)的斜率；rand為［0，1］的隨機數(shù)。

e）選擇較好的個體進入下一次的迭代。

f）如果生成的新個體數(shù)沒有達到N，則返回步驟d）。

g）若達到最大迭代次數(shù)，則輸出最終解；否則返回步驟b）。

2 基于分區(qū)搜索和強化學習的多模態(tài)多目標頭腦風暴優(yōu)化算法

如何得到更多高質量的等效帕累托最優(yōu)解一直是求解MMO的難點。BSO算法在求解多模態(tài)優(yōu)化問題方面有較好表現(xiàn)［30］。基于此，為有效解決MMOPs，本文提出一種MMBSO-ZSRL算法。

2.1 分區(qū)搜索

由于MMOPs的解集在決策空間有多模態(tài)特性，所以大的搜索空間會對算法搜索帶來極大困難。根據(jù)文獻［16，32］，使用分區(qū)策略不僅可以縮小算法的搜索空間，而且能以“物理隔離”的方式提高/維持種群的多樣性；從而輔助MMOEAs找到更多等效Pareto解。為此，本文同樣使用分區(qū)搜索策略來對整個搜索空間進行劃分，以此來降低各個子區(qū)域的搜索難度。具體步驟如下，隨機選擇h（1≤h≤D）個決策變量，然后將每個決策變量等分成e段。因此，搜索空間被劃分為w=eh個子空間。

2.2 基于特殊擁擠距離的個體選擇方法

文獻［9］提出一種特殊擁擠距離（special crowding distance，SCD） 來對種群個體進行評價，其計算公式如下［9］：

SCDi=max（CDi，x，CDi，f） if CDi，x>CDavg，x or

CDi，f>CDavg，f

min（CDi，x，CDi，f）otherwise（7）

其中：CDi，x和CDi，f分別表示第i個個體在決策和目標空間中的擁擠距離；CDavg，x和CDavg，f分別表示決策和目標空間中所有個體擁擠距離的平均值。由于利用SCD能夠挑選出高質量的個體，所以使用它來引導種群進化。根據(jù)文獻［9］，使用式（7） 得到每個個體的SCD值，然后使用概率公式來計算子種群中各個個體被選中的概率。概率公式計算如下：

pri=SCDi∑ni=1SCDi（8）

其中：n為該子種群的種群規(guī)模。所提個體選擇方法分為三個步驟：a） 根據(jù)式（8）計算出子種群中所有個體所對應的概率值；b） 根據(jù)概率值計算子種群中各個個體被選中的概率區(qū)間；c） 產(chǎn)生一個隨機數(shù)rand，當rand落在某區(qū)間內，則該區(qū)間的個體被選中。

2.3 改進的BSO算法生成策略

2.3.1 個體生成公式的改進

盡管BSO算法在多模態(tài)優(yōu)化中具有良好的性能，但固定的搜索模式可能難以適應不同的進化階段。因此，本文提出了一種改進的個體生成策略。

if p1<P1

xtnew=xcpr+F×（xnbest-xcpr）+F×（xr1-xr2） p2<P2

xrpr+ξ（t）×N（μ，σ1）otherwise（9）

else

xtnew=w1×xc1+（1-w1）×xc2+ξ（t）×N（μ，σ） p3<P3

w1×xr1+（1-w1）×xr2+ξ（t）×N（μ，σ）otherwise（10）

end

其中：F是縮放因子；xcpr是使用2.2節(jié)所提方法得到的聚類中心；xnbest是該聚類中不同于xcpr的非支配個體；xrpr是使用2.2節(jié)所提方法得到的普通個體；σ1為小于方差σ的參數(shù)值；P1、P2、P3為概率參數(shù)，取值為［0，1］。

2.3.2 生成策略自適應

在BSO算法搜索過程中，不同的搜索算子對其性能有顯著影響。為使BSO算法能夠根據(jù)進化過程實現(xiàn)自主調整，本文利用SARSA（state-action-reward-state-action）算法［20］來達到以上目的。為了評價不同搜索算子的性能，首先根據(jù)不同的個體生成策略將種群劃分為四個子種群，然后使用式（2）計算四個子種群的PSP值。動作空間定義為AC=［+δ，-δ］；狀態(tài)空間定義為SV=［優(yōu)，差］；獎勵設置為RC=［1，-1］。針對P1、P2、P3三個參數(shù)，分別建立Q-1表、Q-2表、Q-3表。Q-表的形式，見表1。

在MMBSO-ZSRL算法中，更新動作鏈AC的步驟如下：

a）由策略xcpr+F×（xnbest-xcpr）+F×（xr1-xr2）和xrpr+ξ（t）×N（μ，σ1）生成個體的子種群分別表示為OP1和OP2；由策略w1×xc1+（1-w1）×xc2+ξ（t）×N（μ，σ）和w1×xr1+（1-w1）×xr2+ξ（t）×N（μ，σ）生成個體的子種群分別表示為OP3和OP4。

b）性能評估。使用式（2）分別計算OP1、OP2、OP3和OP4的PSP值，表示為PSP1、PSP2、PSP3和PSP4。對于P1值，若 （PSP1+PSP2）>（PSP3+PSP4），那么P1的獎勵值為1；反之，P1的獎勵值為-1。對于P2，若PSP1>PSP2，那么P2的獎勵值為1；反之，P2的獎勵值為-1。對于P3，若PSP3>PSP4，那么P3的獎勵值為1；反之，P3的獎勵值為-1。

c）根據(jù)步驟b）判斷P1、P2、P3所對應的狀態(tài)s′和獎勵值r，更新對應的狀態(tài)向量SV和獎賞鏈RC。

d）在對應的狀態(tài)s′下，使用貪心策略［20］預測相應的動作a′。

e）根據(jù)式（11）［20］更新對應P1、P2、P3的Q-表。

Q（s，a）=Q（s，a）+α（r+γQ（s′，a′）-Q（s，a））（11）

f）更新對應的動作鏈AC。

2.4 MMBSO-ZSRL算法框架

所提算法MMBSO-ZSRL的偽代碼見算法1。第1行，首先使用分區(qū)搜索策略將整個決策空間分為w個子空間。第3行，初始化當前迭代次數(shù)、P1、P2、P3及它們的Q-表、狀態(tài)向量、動作鏈、獎賞鏈。第4行，在第i個子空間中，隨機初始化種群POPi（0）、初始化聚類中心存檔CAi。第6行，在決策空間使用K-means算法將種群POPi（t）分成K個聚類。第7～10行，對K個聚類分別使用non-dominated_scd_sort方法［9］進行排序。此外，在每個聚類中隨機選擇一個非支配個體保存至CAi。第12～14行，以一定的概率產(chǎn)生隨機個體取代某一類的聚類中心，以避免算法陷入局部最優(yōu)［29］。第16～20行，使用2.3.1節(jié)改進的BSO個體生成策略產(chǎn)生N個新個體并保存。第21行，通過2.3.2節(jié)所提的生成策略自適應方法更新概率參數(shù)。第22行，種群POPi（t+1）與POPi（t）合并，并使用non-dominated_scd_sort方法［9］進行排序，取其前N個個體存入POPi（t+1）進行下一次的迭代。第25行，達到第i個子空間的最大迭代次數(shù)后，保存該子空間內最后一次迭代種群POPi（T/w）中的非支配個體。第27、28行，將所有子空間中的非支配個體合并，使用多目標處理技術［27］ （記為selection） 得到最終的PS和PF。

算法1 MMBSO-ZSRL算法

輸入：子空間數(shù)w;最大迭代次數(shù)T;種群規(guī)模N;聚類數(shù)K。

輸出：PS和PF。

1 根據(jù)2.1節(jié)對搜索空間分區(qū)得到w個子空間，記作S1，S2，…，Sw；

2 for i=1：w do

3 初始化當前迭代次數(shù)t=0、概率參數(shù)P1、P2、P3及它們的Q-表、狀態(tài)向量SV、動作鏈AC、獎賞鏈RC；

4 初始化種群POPi（0）和聚類中心存檔CAi；

5 while t<T/w do

6 在搜索空間使用K-means算法將種群POPi（t）分成K個聚類，分別記作C1，C2，…，CK；

7 for k=1：K do

8 使用non-dominated_scd_sort方法對聚類Ck進行排序；

9 在Ck中，隨機選擇一個非支配個體，存檔在CAi中；

10 end for

11 //以一定概率產(chǎn)生隨機個體取代某一類的聚類中心

12 if rand<0.2 then

13 在CAi中，用一個隨機個體替換掉隨機選中的一個聚類中心；

14 end if

15 //產(chǎn)生N個新個體

16 for k=1：K do

17 for l=1：|Ck| do

18 使用2.3.1節(jié)所提策略產(chǎn)生新個體并保存至POPi（t+1）；

19 end for

20 end for

21 通過2.3.2節(jié)所提的生成策略自適應方法更新概率參數(shù)；

22 通過non-dominated_scd_sort方法對POPi（t+1）和POPi（t）排序，取其前N個個體存入POPi（t+1）； //環(huán)境選擇

23 t=t+1； //更新迭代次數(shù)

24 end while

25 保存POPi（T/w）中的非支配個體，得到PSi和PFi；

26 end for

27 PS=selection（PS1∪PS2∪…∪PSw）；

28 PF=selection（PF1∪PF2∪…∪PFw）.

2.5 所提算法復雜度分析

本節(jié)討論所提MMBSO-ZSRL在最壞情況下的運行時間復雜度。各個子空間內主要執(zhí)行以下步驟：聚類、選擇聚類中心、新個體生成、環(huán)境選擇。在本文中，種群規(guī)模、問題的目標數(shù)量、決策變量維度分別為N、M、D。對每一代使用K-means算法聚類的時間復雜度為O（t1KND），其中，t1為K-means算法的迭代次數(shù)。選擇聚類中心的時間復雜度為O（KM|Ck|2）。對于新個體的生成，時間復雜度為O（K|Ck|2）。此外，對于環(huán)境選擇，其計算復雜度為max{O（M（2N）2，O（M（2N） log（2N）），O（D（2N） log（2N））}。MMBSO-ZSRL的最終時間復雜度為max{O（t1TKND），O（TKM|Ck|2），O（TM（2N）2），O（TD（2N） log （2N） }，T為迭代次數(shù)。在本文中，t1≈5;K=15;M=D=2 or 3;|Ck|≈N/K。因此，N>|Ck|>K>t1>M=D。故可以確定MMBSO-ZSRL的運行時間復雜度為O（TM（2N）2）。

3 實驗結果

為驗證所提算法的性能，將MMBSO-ZSRL與其他六種知名的多模態(tài)多目標優(yōu)化算法進行比較。它們分別是SMPSO_MM［12］、SS_MOPSO［24］、MMODE_CSCD［23］、MMODE_ICD［22］、MMOHEA［25］和ZS-MO_Ring_PSO_SCD［16］等。同時，IEEE CEC2019 MMOPs測試函數(shù)集［21］被用來測試它們的性能；并利用PSP和HV來評估所有比較算法的性能。另外，為保證實驗結果分析的可靠性，采用Wilcoxon［33］秩和檢驗和Friedman［34］檢驗來對實驗結果進行統(tǒng)計分析，顯著性水平設置為5%，其中“+”和“-”分別表示MMBSO-ZSRL優(yōu)于和劣于相比較算法，“=”表示MMBSO-ZSRL與相比較的算法性能接近。

3.1 實驗設置

對于所有比較算法，它們的種群規(guī)模和最大適應度函數(shù)評估次數(shù)分別設置為800和80 000。另外，在MMBSO-ZSRL中，K設為15，δ設為2.5%，σ1設為0.2，w設為4。對于其他對比算法，它們的參數(shù)設置與原始文獻［12，16，22～25］的設置一致。此外，所有比較算法都使用MATLAB R2021a實現(xiàn)，并在每個測試函數(shù)上獨立運行21次。

3.2 實驗結果

所有比較算法的PSP和HV的平均值和標準方差如表2、3所示。為有效區(qū)分各個比較算法與所提算法的性能，本文采用Wilcoxon秩和檢驗來對它們的結果進行統(tǒng)計分析。統(tǒng)計分析結果也顯示在表2、3。此外，表中最好的結果用粗體表示。從表2可以看出，對于PSP性能指標，MMBSO-ZSRL在22個測試函數(shù)上的表現(xiàn)要顯著好于其他六種多模態(tài)多目標進化算法。這表明所提算法能夠在決策空間中找到更多的等效帕累托最優(yōu)解。主要原因是所提算法使用分區(qū)搜索策略來降低各個子區(qū)域的搜索難度和有效維持種群多樣性。同時，MMBSO-ZSRL分別使用改進的BSO生成策略來提高算法的搜索能力和利用SCD來挑選高質量的個體來引導種群進化。因此，相比于其他比較算法，所提算法不僅具有較強的全局探索能力，而且還擁有很好的局部開發(fā)能力；這有助于它在決策空間找到更多的帕累托最優(yōu)解。除了以上結果，本文還使用Friedman檢驗來對所有比較算法的性能進行排序，其排序結果如圖2所示。從圖2可以看出，MMBSO-ZSRL在PSP性能指標上的綜合表現(xiàn)是最好的。因此，所提算法是一種求解MMOPs的有效方法。從表3可以觀察到，對于HV性能指標，MMBSO-ZSRL在IEEE CEC 2019 MMOPs測試函數(shù)集上總體表現(xiàn)出比其他算法更好的性能。具體來說，22個測試問題中，MMBSO-ZSRL在18個問題上表現(xiàn)出了最佳性能。主要原因可能是：MMBSO-ZSRL綜合了“軟隔離”（K-means聚類）和“硬隔離”（分區(qū)搜索）的優(yōu)勢，找到了更多的帕累托最優(yōu)解，從而提高解集在目標空間中的多樣性。此外，MMODE_CSCD、MMODE_ICD、ZS-MO_Ring_PSO_SCD分別在1個、4個、1個測試問題上獲得了相似性能的HV值。主要原因可能是：對于MMOPs來講，只要得到部分PS，也能獲得收斂性和多樣性好的PF逼近。這也是其他六種比較算法與所提算法在PSP指標上差距很大，卻在HV指標上差距并不大的原因。此外，從圖3還可以看出，MMBSO-ZSRL在HV指標上的Friedman性能排序是最好的。因此，所提算法能夠在目標空間中得到好的PF逼近。

綜上所述，MMBSO-ZSRL在決策空間和目標空間中的表現(xiàn)是所有比較算法中最好的。所提算法不僅可以在目標空間中找到逼近性和多樣性好的PF逼近，而且能夠定位到更多的等效帕累托最優(yōu)解。

4 實驗分析

4.1 分區(qū)搜索策略對MMBSO-ZSRL算法的影響

為驗證分區(qū)搜索策略的有效性，本文選用沒有使用分區(qū)搜索策略（即w=1）的MMBSO-ZSRL（命名為MMBSO-v1）作為對照組，將子空間數(shù)量w分別設為1，2，4，6，8進行實驗。對算法在22個測試函數(shù)上運行21次所得到的PSP平均值進行Fridman性能排序，所得結果見圖4。從圖4可以看出，隨著子空間數(shù)量的增加，算法性能呈現(xiàn)先上升后下降的趨勢。這主要是當總的計算資源固定時，各個分區(qū)的計算資源會隨著分區(qū)數(shù)量的增加而減少。當分區(qū)數(shù)量和各個分區(qū)的資源達到平衡狀態(tài)時，這個時候分區(qū)數(shù)量可以使得算法性能達到最佳。但當分區(qū)數(shù)量繼續(xù)增加，每個搜索子空間的計算資源會變少，因此整體性能會下降。此外，從圖4可以看出，當w=4時，所提算法獲得最佳性能。因此，在所提算法中，分區(qū)數(shù)量設定為4。

4.2 基于SCD的個體選擇方法對算法的影響

為驗證基于SCD的個體選擇方法的有效性，本文選擇沒有采用該方法的MMBSO-ZSRL（命名為MMBSO-v2）和MMBSO-ZSRL進行性能比較。兩個算法的所得結果如表4所示。最佳結果用粗體表示。

為確保結論的可靠性，本文使用Wilcoxon［33］秩和檢驗來對結果進行統(tǒng)計分析，相應的統(tǒng)計結果見表4。從表4可以看出，MMBSO-ZSRL在15個測試函數(shù)上得到的PSP值明顯優(yōu)于MMBSO-v2，且在其余7個測試問題上與MMBSO-v2取得了相似的結果。相比于MMBSO-v2，MMBSO-ZSRL算法在在求解復雜優(yōu)化問題（例如SYM_PART rotated、Omni_test等）時，具有更好表現(xiàn)。因此，在大多數(shù)測試問題上，基于SCD的個體選擇方法可以依據(jù)決策空間和目標空間的擁擠信息挑選高質量個體引導種群進化，從而輔助MMBSO-ZSRL找到更多的等效帕累托最優(yōu)解。

4.3 改進的BSO算法生成策略的效果

本文采用未應用改進BSO算法生成策略的MMBSO-ZSRL（命名為MMBSO-v3）和MMBSO-ZSRL進行性能比較，以驗證所改進BSO算法生成策略的有效性。MMBSO-v3和MMBSO-ZSRL在22個測試函數(shù)上各運行21次，所得PSP值的平均值和標準方差顯示在表4中。為確保結論的可靠性，本文還使用Wilcoxon［33］秩和檢驗來統(tǒng)計分析結果，相應的統(tǒng)計結果也列于表4中。此外，最佳結果用粗體表示。從表4可以看出，MMBSO-ZSRL在21個測試函數(shù)上所得到的PSP值都明顯優(yōu)于MMBSO-v3；僅在測試函數(shù)MMF14_a上，兩個算法取得了相似的結果。這表明所改進的BSO生成策略可以在絕大多數(shù)測試問題上有效提高MMBSO-ZSRL的搜索效率，從而找到更多的等效帕累托最優(yōu)解。

為進一步驗證所提生成策略自適應方法的有效性，使用MMF3測試函數(shù)來對P1、P2、P3進行分析。它們在各個分區(qū)的變化趨勢見圖5。較小的P1值有助于全局搜索；而較大的P1值會偏向算法進行局部搜索。從圖5可以發(fā)現(xiàn)，P1值在4個子空間都呈上升趨勢。因此，在進化后期，所提算法能以較高的概率選擇式（9） 來對各個子空間進行局部精細搜索，這有助于得到更高質量的解集。同時，從圖5可以看出，P2值在整個搜索過程中呈變大趨勢，這表明xcpr+F×（xnbest-xcpr）+F×（xr1-xr2）能夠為所提算法找到更好的Pareto解。另外，從圖5（a）（c）來看，P3值隨進化過程而變大，這說明在子空間1和3中，全局搜索能力較強的搜索策略占據(jù)主導地位。這可以有效幫助所提算法提高搜索性能。而從圖5（b）（d）可以看出，兩種搜索策略在其子空間中的作用幾乎相當。因此，本文可以看出，所提自適應方法可以根據(jù)實際情況來自動調整算法的搜索性能以找到更多和更高質量的Pareto解。

4.4 視覺效果

為更直觀體現(xiàn)所用方法的效果，使用MMBSO-v1、MMBSO-v2、MMBSO-v3和MMBSO-ZSRL來對MMF3問題進行測試。所有算法的PSs如圖6所示。

從圖6 （a）可以看出，由于未使用分區(qū)策略，所以MMBSO-v1算法得到解集在均勻性方面要遜于MMBSO-ZSRL。同樣，SCD的個體選擇方法和BSO生成策略同樣對所提算法的性能產(chǎn)生影響。因此，改進方法對所提算法的性能提升都起到了很大幫助。

4.5 參數(shù)K的敏感性分析

聚類數(shù)K對MMBSO-ZSRL的性能可能有較大影響，故本實驗對參數(shù)K進行敏感性分析。一般來說，雖然大的K值能提高種群的多樣性，但是會影響種群的收斂速度。相反，如果K值太小，種群的多樣性可能無法得到有效維持。為了驗證MMBSO-ZSRL在不同K值下的性能，使用控制變量法進行實驗分析。當參數(shù)δ設為1.0%，參數(shù)σ1設為0.2，將K值分別設置為10、15、20、25、30進行實驗。結果如表5所示，最佳結果用粗體標出。從表5可以看出，沒有任何一個K值使得MMBSO-ZSRL在所有問題上都能取得最好結果。因此，使用Friedman檢驗［34］對實驗結果進行分析，得到的性能排序結果見圖7。如圖7所示，隨著聚類數(shù)K值的增加，算法的整體性能先上升，后下降。其中，當K值取15時，MMBSO-ZSRL獲得最佳整體表現(xiàn)。因此，在MMBSO-ZSRL中，將K值設為15。

4.6 參數(shù)δ的敏感性分析

控制參數(shù)δ可能會對MMBSO-ZSRL的性能產(chǎn)生一定影響。為驗證MMBSO-ZSRL在不同δ值下的表現(xiàn)，對其實驗分析。本文使用控制變量法，當參數(shù)K設為15、參數(shù)σ1設為0.2，將δ值分別設置為0.5%、1.0%、1.5%、2.0%、2.5%、3.0%、3.5%、4.0%、4.5%、5.0%進行實驗。實驗結果見表6，最佳結果用粗體標出。

從表6可以看出，不同δ值都只能在少數(shù)測試問題上取得最好結果。即，在一定范圍內，不同δ值對MMBSO-ZSRL的性能影響是有限的。為使MMBSO-ZSRL獲得最佳性能，本文使用Friedman檢驗［34］對實驗結果進行進一步性能排序；排序結果如圖8所示。可以看出，在δ值取2.5%的時候，MMBSO ZSRL獲得最佳性能。因此，在MMBSO-ZSRL中，將δ值設為2.5%。

4.7 參數(shù)σ1的敏感性分析

為驗證MMBSO-ZSRL在不同σ1值下的性能，當參數(shù)K設為15、δ設為2.5%時，將參數(shù)σ1分別設為0.2、0.4、0.6、0.8、1.0進行實驗。實驗結果如表7所示，最好結果用粗體標出。從表7可以看出，所有σ1值均未能使MMBSO-ZSRL在全部測試問題上取得最好結果。因此，對實驗結果使用Friedman檢驗［34］進一步分析，所得性能排序結果見圖9。如圖9所示，隨著σ1值取的增加，MMBSO-ZSRL的性能呈下降趨勢，且取0.2的時候獲得最佳性能。因此，在MMBSO-ZSRL中，將σ1值設為0.2。

5 結束語

為維持種群多樣性和提高算法搜索效率以及獲得盡可能多的等效帕累托最優(yōu)解，本文提出了一種基于分區(qū)搜索和強化學習的多模態(tài)多目標頭腦風暴優(yōu)化算法。在該算法中，首先將決策空間分解為多個子空間以降低搜索難度并提高種群多樣性；然后，使用SARSA來平衡頭腦風暴優(yōu)化算法的全局探索和局部開發(fā)能力；并使用特殊擁擠距離來挑選個體指導種群進化。為測試所提算法性能，本文選取六種先進的MMOEAs進行對比，并選用IEEE CEC 2019 MMOPs 基準測試集來對所有算法的性能進行測試。此外，在實驗分析中設計三組對照實驗來驗證所提方法的有效性。結果表明，分區(qū)搜索可以有效提高種群多樣性且降低MMOPs的求解難度；改進BSO生成策略可以有效提高算法的搜索效率；基于特殊擁擠距離的個體選擇方法可以有效輔助MMBSO-ZSRL找到更多的帕累托最優(yōu)解。此外，為檢驗參數(shù)對MMBSO-ZSRL性能的影響，本文設計了三組對照實驗來進行參數(shù)敏感性分析，實驗結果表明，在K取值為15，δ取值為2.5%，σ1取值為0.2時，算法整體性能最佳。綜上所述，相比于其他算法，MMBSO-ZSRL能夠在決策空間找到更多帕累托最優(yōu)解，且獲得質量更高的PF逼近。未來將對MMBSO-ZSRL做進一步研究，使其能夠解決約束多模態(tài)多目標優(yōu)化問題，并探究其在實際工程應用中的性能表現(xiàn)。

參考文獻：

［1］Li Wenhua， Zhang Tao， Wang Rui， et al. Multimodal multi-objective optimization： comparative study of the state-of-the-art［J］. Swarm and Evolutionary Computation， 2023， 77： article ID 101253.

［2］Tanabe R， Ishibuchi H. A review of evolutionary multimodal multi-objective optimization［J］. IEEE Trans on Evolutionary Computation， 2020，24（1）： 193-200.

［3］岳彩通， 梁靜， 瞿博陽， 等. 多模態(tài)多目標優(yōu)化綜述［J］. 控制與決策， 2021，36（11）： 2577-2588. （Yue Caitong， Liang Jing， Qu Boyang， et al. A review of multimodal multiobjective optimization［J］. Journal of Control and Decision， 2021， 36（11）： 2577-2588.）

［4］Pérez E， Posada M， Herrera F. Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling［J］. Journal of Intelligent Manufacturing， 2012， 23（3）： 341-356.

［5］Kudo F， Yoshikawa T， Furuhashi T. A study on analysis of design variables in pareto solutions for conceptual design optimization problem of hybrid rocket engine［C］//Proc of IEEE Congress of Evolutionary Computation. Piscataway， NJ： IEEE Press， 2011： 2558-2562.

［6］Miao Zhenhua， Huang Wentao， Jiang Qingchao， et al. A novel multimodal multi-objective optimization algorithm for multi-robot task allocation［J/OL］. Trans of the Institute of Measurement and Control.（2023-06-25）.https：//doi.org/10.1177/01423312231183588.

［7］Li Xin， Li Mingyang， Yu Moduo， et al. Fault reconfiguration in distribution networks based on improved discrete multimodal multi-objective particle swarm optimization algorithm［J］. Biomimetics， 2023， 8（5）： article ID 431.

［8］Deb K， Tiwari S. Omni-optimizer： a generic evolutionary algorithm for single and multi-objective optimization［J］. European Journal of Operational Research， 2008， 185（3）： 1062-1087.

［9］Yue Caitong， Qu Boyang， Liang Jing. A multiobjective particle swarm optimizer using ring topology for solving multimodal multiobjective problems［J］. IEEE Trans on Evolutionary Computation， 2017， 22（5）： 805-817.

［10］李文樺， 明夢君， 張濤， 等. 考慮全局和局部帕累托前沿的多模態(tài)多目標優(yōu)化算法［J］. 自動化學報， 2023， 49（1）： 148-160. （Li Wenhua， Ming Mengjun， Zhang Tao， et al. Multimodal multi-objective evolutionary algorithm considering global and local Pareto fronts［J］. Acta Automatica Sinica， 2023， 49（1）： 148-160.）

［11］Liang Jing， Yue Caitong， Qu Boyang. Multimodal multi-objective optimization： a preliminary study［C］//Proc of IEEE Congress on Evolutionary Computation. Piscataway， NJ： IEEE Press， 2016： 2454-2461.

［12］Liang Jing， Guo Qianqian， Yue Caitong， et al. A self-organizing multi-objective particle swarm optimization algorithm for multimodal multi-objective problems［C］//Advances in Swarm Intelligence： Proc of the 9th International Conference. Berlin： Springer， 2018： 550-560.

［13］Lin Qiuzhen， Lin Wu， Zhu Zexuan， et al. Multimodal multiobjective evolutionary optimization with dual clustering in decision and objective spaces［J］. IEEE Trans on Evolutionary Computation， 2021， 25（1）： 130-144.

［14］Hu Zhongbo， Zhou Ting， Su Qinghua， et al. A niching backtracking search algorithm with adaptive local search for multimodal multiobjective optimization［J］. Swarm and Evolutionary Computation， 2022， 69： article ID 101031.

［15］Zhang Kai， Shen Chaonan， Yen G G， et al. Two-stage double niched evolution strategy for multimodal multiobjective optimization［J］. IEEE Trans on Evolutionary Computation， 2021， 25（4）： 754-768.

［16］Fan Qinqin， Yan Xuefeng. Solving multimodal multiobjective problems through zoning search［J］. IEEE Trans on Systems， Man， and Cybernetics： Systems， 2021， 51（8）： 4836-4847.

［17］Fan Qinqin， Ersoy O K. Zoning search with adaptive resource allocating method for balanced and imbalanced multimodal multi-objective optimization［J］. IEEE/CAA Journal of Automatica Sinica， 2021， 8（6）： 1163-1176.

［18］Ji Hebing， Chen Shaojie， Fan Qinqin. Zoning search and transfer learning-based multimodal multi-objective evolutionary algorithm［C］//Proc of IEEE Congress on Evolutionary Computation. Pisca-taway， NJ： IEEE Press， 2022： 1-8.

［19］Fan Jiajia， Huang Wentao， Jiang Qingchao， et al. A zoning search based multimodal multi-objective brain storm optimization algorithm for multimodal multi-objective optimization［J］. Algorithms， 2023， 16（7）： article ID 350.

［20］Liu Qingqing， Cui Caixia， Fan Qinqin. Self-adaptive constrained multi-objective differential evolution algorithm based on the state-action-reward-state-action method［J］. Mathematics， 2022， 10（5）： article ID 813.

［21］Yue Caitong， Qu Boyang， Yu Kunjie， et al. A novel scalable test problem suite for multimodal multiobjective optimization［J］. Swarm and Evolutionary Computation， 2019， 48： 62-71.

［22］Yue Caitong， Suganthan P N， Liang Jing， et al. Differential evolution using improved crowding distance for multimodal multiobjective optimization［J］. Swarm and Evolutionary Computation， 2021， 62： article ID 100849.

［23］Liang Jing， Qiao Kangjia， Yue Caitong， et al. A clustering-based differential evolution algorithm for solving multimodal multi-objective optimization problems［J］. Swarm and Evolutionary Computation， 2021， 60： article ID 100788.

［24］Qu Boyang， Li Chao， Liang Jing， et al. A self-organized speciation based multi-objective particle swarm optimizer for multimodal multi-objective problems［J］. Applied Soft Computing， 2020， 86： article ID 105886.

［25］Hu Yi， Wang Jie， Liang Jing， et al. A two-archive model based evolutionary algorithm for multimodal multi-objective optimization problems［J］. Applied Soft Computing， 2022，119： article ID 108606.

［26］Zitzler E， Thiele L. Multiobjective optimization using evolutionary algorithms—a comparative case study［J］. IEEE Trans on Evolutio-nary Computation， 1999， 3（4）： 257-271.

［27］Deb K， Pratap A， Agarwal S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II［J］. IEEE Trans on Evolutionary Computation， 2002， 6（2）： 182-197.

［28］Zhou Aimin， Zhang Qingfu， Jin Yaochu. Approximating the set of Pareto-optimal solutions in both the decision and objective spaces by an estimation of distribution algorithm［J］. IEEE Trans on Evolutionary Computation， 2009， 13（5）： 1167-1189.

［29］Shi Yuhui. Brain storm optimization algorithm［C］//Advances in Swarm Intelligence： Proc of the 2nd International Conference. Berlin： Springer， 2011： 303-309.

［30］Cheng Shi， Qin Quande， Chen Junfeng， et al. Brain storm optimization algorithm： a review［J］. Artificial Intelligence Review， 2016， 46（4）： 445-458.

［31］魏詩雨， 劉勇. 機器人路徑規(guī)劃的新型頭腦風暴優(yōu)化算法［J］. 計算機應用研究， 2022，39（2）： 402-406. （Wei Shiyu， Liu Yong. Robot path planning with novel brain storm optimization algorithm［J］. Application Research of Computers， 2022， 39（2）： 402-406.）

［32］胡潔， 范勤勤， 王直歡. 融合分區(qū)和局部搜索的多模態(tài)多目標優(yōu)化［J］. 智能系統(tǒng)學報， 2021，16（4）： 774-784. （Hu Jie， Fan Qinqin， Wang Zhihuan. Multimodal multi-objective optimization combining zoning and local search［J］. CAAI Trans on Intelligent Systems， 2021， 16（4）： 774-784.）

［33］Wilcoxon F. Individual comparisons by ranking methods［J］. Biometrics Bulletin， 1945， 1（6）： 80-83.

［34］Friedman M. The use of ranks to avoid the assumption of normality implicit in the analysis of variance［J］. Journal of the American Statistical Association， 1937， 32（200）： 675-701.