融合聚類和小生境搜索的多模態多目標優化算法

顧清華，唐慧，李學現，江松

（1.西安建筑科技大學 資源工程學院, 陜西 西安 710055; 2.西安市智慧工業感知計算與決策重點實驗室, 陜西西安 710055; 3.西安優邁智慧礦山研究院有限公司, 陜西 西安 710055; 4.西安建筑科技大學 管理學院, 陜西 西安 710055）

多模態多目標優化問題（multimodal multi-objective optimization problem, MMOP）[1]是一類特殊的多目標優化問題（mmulti-objective optimization problem, MOP）[2]，它著重于獲取具有相同目標值的帕累托最優解集（Pareto-optimal sets, PSs）。如何獲取并保持決策空間更多的PSs，提高決策空間的多樣性以及算法的搜索能力一直是多模態多目標優化問題存在的難點。

目前，多模態多目標問題主要從兩個方面來優化：一是提高算法的搜索能力。最早有學者提出通過改進粒子群算法來提高搜索能力，如CLPSO（comprehensive learning particle swarm optimization）[3]和AMPSO（modified particle swarm optimization）[4]通過優化粒子的學習方式以提高算法的搜索能力；STMOPSO（star-structured multi-objective particle swarm optimization）[5]基于星型拓撲結構提出一種非支配解集分布均勻程度的評價方法，提高了算法的收斂速度。小生境策略可以提高算法的搜索能力，如Qu 等[6]提出的LIPS（distance-based locally informed particle swarm）利用鄰域信息在小生境空間內粒子根據局部最優粒子進行搜索，提高了算法的精細搜索能力；SS-MOPSO（self-organized speciation based multi-objective particle swarm optimizer）[7]基于物種形成策略形成多個穩定的物種，物種與物種之間互不重疊，分別搜索并保持Pareto 最優解；Liang 等[8]在NSGAII 的基礎上提出DN-NSGAII（decision space based niching NSGAII），在決策空間小生境內分別搜索不同的Pareto 最優解，有效防止了過早收斂，但該算法僅考慮決策空間的擁擠程度；DN-MMOES（two-stage double niched evolution strategy）[9]采用兩階段策略，分別在決策和目標空間中都采用小生境。此外，還設計了決策密度自適應策略來改善不平衡的決策空間密度，該算法提高了搜索能力，但該算法的某些局部最優解可能被全局最優解支配；

MO-Ring-PSO-SCD（multi-objective particle swarm optimization algorithm with ring topology）[10]和MORing-CSO-SCD（multi-objective competitive swarm optimization algorithm with ring topology）[11]采用環形拓撲結構形成穩定的小生境，且不需要定義小生境參數，算法能夠搜索到更多的Pareto 最優解，能在決策空間和目標空間中獲得良好的分布；

SMPSO-MM（multi-objective particle swarm optimizer with a self-organizing mechanism）[12]和MMOPIO（multimodal multi-objective pigeon-inspired optimization）[13]都引入自組織映射機制（self-organizing map, SOM），將決策空間轉化到目標空間，使粒子在映射空間進行鄰域搜索，有效提高了算法的搜索能力，但算法引入的SOM 機制，映射機理較復雜；MOMMOP（transformation technique based on multi-objective optimization）[14]將MMOP 轉化為具有兩個沖突目標的MOP，因此MMOP 的所有最優解都轉化成優化問題的Pareto 最優解；Luo 等[15]提出的MMOEA-CAS（evolutionary algorithm with clustering-based assisted selection strategy）在決策空間采用添加算子增加多樣性，在目標空間采用刪除算子刪除最差解，提高了算法的搜索能力；近來，有學者為了保留更多的全局和局部Pareto最優解，提出MMOMA-DM&CS（multimodal multiobjective memetic algorithm based on a local detection mechanism and a clustering-based selection strategy）[16]

算法在局部檢測機制中采用了基于密度的聚類方法，幫助收集局部聚類中的解；MMOHEA（efficient two-archive model based multimodal evolutionary algorithm）[17]結合競爭粒子群和差分進化算法的策略并行生成子代解，擴展了具有不同進化需求的決策空間和目標空間，有效改善了算法搜索能力。

上述提高算法搜索能力的策略可以搜索到更多的Pareto 最優解，此外通過提高決策空間的多樣性也能解決多模態多目標優化問題。如TriMOEATA&R（multi-modal multi-objective evolutionary algorithm using two-archive and recombination strategies）[18]引入新的環境選擇機制即特殊擁擠距離非支配排序法（special crowding distance, SCD）計算決策空間和目標空間的擁擠距離，建立收斂性和多樣性兩個檔案分別處理空間的變量關系，最后還對檔案中的解進行重組，實驗證明該算法同時保證了決策空間和目標空間的多樣性，DN_NSGAII[8]、MO_Ring_PSO_SCD[10]和MO_Ring_CSO_SCD[11]算法也同樣引入了SCD 方法；Yang 等[19]提出EMO-DD（evolutionary multi-objective optimization algorithm with a decomposition strategy in the decision space）將整個種群分解為若干子種群對收斂程度和分布密度協同優化，從而篩選出決策空間收斂性和多樣性好的解；ZLS-SMPSO-MM（multimodal multi-objective particle swarm optimization combing zoning search and local search）[20]在SOM 機制前對決策空間進行處理，將決策空間分為多個子種群并用協方差矩陣自適應算法，縮短了算法的計算時間；MMODE（multimodal multi-objective Differential Evolution optimization algorithm）[21]

制定決策變量預選檔案，對邊界解引入一個邊界突變機制，提高了決策空間的多樣性；此外，基于聚類的方法也可以改善多樣性，如MMO-CLRPSO（cluster based PSO with leader updating mechanism and ring-topology）[22]引用一種決策變量聚類方法在決策空間形成多個子種群，子種群同時考慮到全局最優粒子和局部最優粒子進行信息交流，在探索與開發階段實現了較好的平衡；Lin 等[23]提出MMOEA/DC（novel MMOEA with dual clustering in decision and objective spaces）首先在決策空間和目標空間分別采用NCM（neighborhood-based clustering method）聚類和HCM（hierarchical clustering method）聚類方法，再選擇收斂性好的解進行二次聚類，該算法同時在兩空間實現了較好的性能；MMODE-CSCD（differential evolution algorithm based on the clustering technique and an elite selection mechanism）[24]將差分進化算法與聚類策略結合，采用基于聚類的特殊擁擠距離計算決策空間與目標空間的綜合擁擠程度，從而提高種群分布的均勻性；MOEA-GA（multimodal multi-objective evolutionary algorithm using a density-based one-byone update strategy）[25]采用諧波平均距離估計決策空間中解的平均密度，只允許粒子與決策空間鄰域內的個體進行信息交互，并基于密度逐步更新粒子，實驗證明算法提高了決策空間的多樣性。

以上算法大多基于粒子群的搜索方式更新粒子的位置，而鴿群優化算法（pigeon-inspired optimization algorithm PIO）[26]的局部搜索能力強，對求解多模態多目標優化問題有較好的性能。PIO自提出以來, 有許多文獻對其進行改進研究，例如，利用反向學習策略[27]、混沌映射策略[28]初始化種群，引入高斯因子[29]、非線性變異策略[30]等。PIO 雖然得到了許多改進，但對于多模態多目標優化問題的研究仍不多見?；诖?，為解決多模態多目標優化問題，提高種群多樣性以及尋找更多的Pareto 最優解，本文引入聚類、自適應物種形成策略結合改進的鴿群算法，提出一種融合聚類和小生境搜索的多模態多目標優化算法（multimodal multi-objective pigeon-inspired optimization algorithm with clustering and searching strategy, CSSMPIO）。

1 相關理論

1.1 多模態多目標優化

最小化多目標優化問題[2]定義如下：

式中：m表示待優化的目標個數，x=[x1x2···xn]是n維決策變量，gi(x)≤0,i=1,2,···,k為k個不等式約束，hj(x)=0,j=1,2,···,p為p個等式約束。

在多目標優化問題中，根據Pareto 解的支配關系可以比較不同解的優劣，若有兩個可行解x1,x2∈X，對 ?i=1,2,···,m，都有fi(x1)≤fi(x2)，則稱x1支 配x2。如果一個解不受任何其他解的支配，那么它就被稱為非支配解，決策空間中非支配解組成的集合稱為非支配解集，即PSs，Pareto 最優前端（Pareto-optimal front, PF）是目標空間中與Pareto最優解對應的所有向量的集合。

多模態多目標優化[31]是一種特殊的多目標優化，如果一個多目標優化問題[2]滿足以下條件之一就屬于多模態多目標優化問題：

1) 存在至少一個局部最優解；

2) 存在兩個以上全局最優解。

同一問題最優目標值，可能對應著多個不同的解決方案，即PF 中的某一點可能對應著決策空間中至少一個局部最優解或兩個以上的全局最優解。路徑規劃問題[22]就是典型的多模態多目標優化，如圖1 所示，出行者想要在最短的時間從起點到終點，方案1 和方案6、方案2 和方案4、方案3 和方案5 分別對應目標空間的同一點，各自的區別在于有無加油站以及交叉路口的個數，出行者可以根據不同的需求選擇適合自己的出行路線，由此可見，僅得到一個Pareto 最優解是不能滿足出行者的需求的。多模態多目標問題的重點就是在保證目標空間PF 優越性的同時，找到決策空間更多的PSs。

圖1 路徑優化問題Fig.1 Path planning problem

1.2 鴿群優化算法

鴿群算法[26]由地圖指南針算子和地標算子兩階段組成，這兩個算子處于獨立運行階段，即先在地圖指南針算子階段對鴿子的位置和速度進行初始化并迭代更新，然后在地標算子階段，每次迭代都會使鴿子數量減少一半，舍棄遠離目標的鴿子，對于剩余中心位置的鴿子作為飛行參考方向。

地圖指南針算子階段（Map/compass operator）:

式中：Rs為 地圖指南針算子，通常?。?,1）；t為當前迭代次數；xgbest為全局最佳位置；N為假設的鴿子數量；rand()為介于（0,1）之間均勻分布的隨機數。

地標算子階段（LandMark operator）：

其中 fitness(x)為每只鴿子的適應度值。

2 融合聚類和小生境搜索的優化算法

本文提出融合聚類和小生境搜索的多模態多目標優化算法，稱作CSSMPIO 算法。主要由基于聚類的特殊擁擠距離排序和自適應物種形成多個子種群兩部分組成。

2.1 聚類排序初始化種群

聚類算法將同一非支配層的解劃分為多個類，同一類中的個體將來自同一局部區域。將聚類算法與特殊擁擠距離非支配排序（special crowding distance, SCD）方法[10]結合，形成基于聚類的特殊擁擠距離排序（cluster special crowding distance,CSCD）[24]方法，可以有效地解決SCD 不能正確識別鄰域解的問題。在CSCD 中，個體的鄰域解只能從同一類中識別出來。如圖2（a），把解分成3 類，第1 類（1, 2, 3, 4, 5）第2 類（6, 7, 8），第3 類（9）。

圖2 多模態多目標優化問題Fig.2 Multimodal multi-objective optimization problem

以解4 為例，則基于聚類的特殊擁擠距離值CSCD(4)的計算公式如下：

式中：CD(4,x)為 解4 在決策空間的擁擠距離，CD(4,y)為解4 在目標空間的擁擠距離，CD(avg,x)和CD(avg,y)分別為決策空間和目標空間的平均擁擠距離。

基于聚類的特殊擁擠距離初始化種群步驟如下：

輸入種群P

1) 種群P進行非支配排序，得到多個非支配層次，定義為F1,F2,···,Fnum（num為層數），j=1,2,···,num表示個體在Fj中的非支配排序；

2) 計 算kj值：kj=表 示Fj中 的 個 體數，n為正整數；

3) 根據k-means 算法將Fj分成多個聚類；

4) 利用同一類內的鄰域關系計算每個個體的CSCD值。

輸出根據種群的非支配排序和CSCD值對種群P進行排序，輸出一個新的種群P* 。

2.2 小生境搜索過程

種群經過基于聚類的特殊擁擠距離排序初始化后，被分成了多個類，然后采用自適應物種形成策略生成穩定的小生境，物種形成是根據個體之間相似性將個體劃分為多個子種群。如把S1,S2,···,Sk種群劃分為多個子種群，個體x*∈Si，若對于個體y∈Si，都有個體x*的非支配等級高于個體y，且個體x*到個體y的歐氏距離dis小于物種半徑R，則個體y向x*學習：

該定義并不意味著如果一個物種Si以非支配個體x*為 中心，則x*的物種半徑范圍內的所有個體都屬于該物種。如圖3 所示，一個占優勢的個體可能會支配多個物種內的個體。

圖3 物種在二維區域的分布Fig.3 Distribution of species in a two-dimensional region

自適應物種形成中，物種種子經過特殊擁擠距離排序選擇后，直接根據物種半徑確定其物種內所包含的個體。若個體同時在兩個物種種子的物種半徑內，則由非支配等級更高的物種種子支配該個體。其主要步驟如下：

1) 種群進行基于聚類的非支配特殊擁擠距離升序排序，輸出新種群，存儲到spop 中；

2) 將NPspop作為spop 中集合的數目，spop 中的第一個個體記為物種種子xspeciesseed(j)；

3) 獲得物種種子xspeciesseed(j)后，迭代更新形成互不重疊的物種；

4) 當NPspop≠0 時，執行以下操作：

計算xspeciesseed(j)與spop(j)的歐氏距離；若dis≤R，則個體i位于該物種；同時清除spop 中已經分配給第j個物種種子的個體，spop 得到更新。

輸出更新后的多個子種群。

2.3 改進的位置更新策略

為平衡個體的探索與開發過程，受多目標鴿群啟發算法（multi-objective pigeon-inspired optimization algorithm, MPIO）[32]的影響，結合粒子群優化算法，將地圖指南針算子和地標算子結合起來，個體在每個子種群的位置更新如圖4。

圖4 單個物種中個體位置更新方式Fig.4 Individual position updating in a single species

個體的速度更新公式如下：

式中：wmax與wmin分別表示慣性權重的最大最小值；xspeciesseed為物種種子；rand為0～1 之間的隨機數；xcenter表示鴿群中心坐標位置；T為最大迭代次數；iwt為非線性慣性權重。

為了保留更多的解，對最優解執行精英學習策略，避免早熟收斂，公式如下：

式中：ub、lb分 別為變量的上下界； G uass(0,pr2)為均值為0，標準差為pr的 高斯分布，pr0值從0.2 線性下降到0.05。進化初期，較大的變異范圍有利于算法的全局搜索，隨著迭代的進行，算法需要在局部范圍找到更精確的解，因此小的變異范圍更適合。

2.4 CSSMPIO 算法流程

輸入種群規模Popsize；最大評估次數MaxGen；鴿群參數：wmax、wmin；變異算子pr0；外部存檔集Pachive；

1) 初始化個體的速度和位置，記為POA，并評估POA；

2) 種群P=POA；

3) 當迭代t≤MaxGen時，執行以下操作：

種群P執行2.2 節操作，輸出新種群P*；對新種群P* 執行步驟2.3 節操作；

4) 更新個體的位置和速度，步驟如下：

選出pbest和xspeciesseed(j)；pbest為種群P中的最優個體，xspeciesseed(j)物種中的最優個體；對pbest進行非支配排序，依據式(5)將其轉換成xcenter；依據式(11)、(3)更新個體的速度和位置，式(13)對子代執行精英學習策略，更新P*；對更新后的P* 進行評估；將P*放入POA 中，對POA 中的個體進行排序；

5）當前迭代次數滿足t＞MaxGen時，結束循環，否則返回3）。

輸出PS，PF。

在CSSMPIO 中，聚類排序首先對粒子進行初始化，然后采用自適應物種形成策略在決策空間生成穩定的小生境子種群，鴿群算法的局部搜索能力強，因此可以增強子種群的局部搜索能力，在決策空間中搜索到大量的PSs，最后再引入精英學習策略，對子種群中的最優解進行變異，避免早熟收斂。

2.5 CSSMPIO 時間復雜度分析

CSSMPIO 算法的主要時間成本來源于基于聚類的特殊擁擠距離排序初始化種群和自適應物種形成策略兩部分組成。設種群規模為N，目標維數為M。基于聚類的特殊擁擠距離排序初始化種群時間復雜度為O(N)。自適應物種形成策略中假設有N個個體被排序并存儲在spop 中，其大小為NPspop，for 循環NPspop次，以查看該個體是否在當前種子的半徑R內。最好的情況是，所有的個體都在第一個種子的物種半徑中，因此for 循環只執行了N次。在最壞的情況下，當所有N個個體都是N個獨立物種的種子時，for 循環執行N(N+1)/2次。表明該過程的復雜度最高為O(N2)。并且自適應物種形成過程中，已分配給某些物種的個體被從種群中移除，種群中剩余的個體不再計算與之前物種種子的歐氏距離。因此，其復雜度僅依賴于N，計算次數在物種形成過程中迅速減少。因此，CSSMPIO 最壞的時間復雜度為O(MN3)。

3 實驗結果與分析

3.1 評價指標

多模態多目標優化問題既要求目標空間的分布性能良好，又要保證找到決策空間更多的等價PSs，因此本文采用了以下評價指標對所提算法進行評價。

1) PSP （Pareto set proximity）[31]：

式中：Rc（cover rate, CR）表示算法求得的PSs 對真實PSs 的覆蓋率；xIGD為求得的PSs 與真實PSs 之間的歐氏距離IGDx，因此PSP 反映的是真實PSs 與獲得的PSs 之間的相似性，PSP 越大算法性能越好。

2) IGDx[31]：

式中： |P*|表 示參考點的數目，O表示一組已得到的解，d(v,O)表示v和O中所有點之間最小的歐氏距離。如果參考解集能很好地表示真實PSs，那么IGDx就能較好地衡量決策空間的收斂性和多樣性。IGDx 的值越小，說明算法求得的PSs 和實際PSs越接近。

3.2 實驗設置

為進一步驗證所提算法的性能，將CSSMPIO 算法與自適應物種形成粒子群優化算法SS_MOPSO[7]、基于決策空間小生境算法DN_NSGAII[8]、基于環形拓撲結構的多模態多目標粒子群優化算法MORing-PSO-SCD（MRPS）[10]、自組織多模態多目標粒子群優化算法SMOPSO-MM[12]、自組織多模態多目標鴿群優化算法 MMOPIO[13]、基于雙存檔模型的高效混合進化多模態多目標優化算法MMOHEA[17]算法和多目標優化算法MOEAD[33]進行對比實驗研究。所有算法的最大評估次數為80 000次，種群規模為800，算法在每個測試函數上運行20 次，算法參數設置如表1。

表1 算法的參數設置Table 1 Parameters setting of algorithms

選取14 個多模態多目標問題[31]進行測試。其中，8 個MMF 函數[10]、3 個SYM-PART 函數[34]、3個OMNI 函數[35]。所有優化問題的目標個數均為2，MMF 函數與SYM-PART 函數的空間維度為2，OMNI 函數的空間維度分別為3、4、5。一般來說，在每個維度上PSs 重疊的測試函數比沒有重疊的測試函數更復雜，此外，當一個函數的PSs數目較多時，它也會變得更加復雜。MMF1和MMF2是相對簡單的測試函數，MMF3比MMF1和MMF2復雜。MMF4和MMF8與表中其他測試函數相比，PF 是凹的，它們有4 個PSs，每個維度都不重疊。MMF6有4 個PSs，它們在每個維度上重疊，MMF7的PSs 呈不規則曲線。SYM-PART2測試函數是由SYM-PART1旋轉生成的，因此比SYMPART1更復雜。在SYM-PART 函數中，PSs 的數量都是9 個。Omni-test 中PSs 的數量最多，分別為27、72、360，而且每個維數都有重疊。因此，Omni-test 是14 個測試函數中最復雜的。測試系數特征如表2。

表2 測試函數特征Table 2 The characteristics of test problems

3.2.1 種群規模popsize 分析

在本節中，分析種群規模popsize 對算法性能PSP 的影響，由于MMF1、MMF3、MMF4和MMF6這4 個測試函數的PSs 的數量以及維度重疊是不同的，因此對比算法性能在該4 個測試函數上隨種群規模的變化情況，并將種群規模設置為200、400、600、800、1 000，其他參數設置如表1。

實驗結果如圖5 所示，可以看出，MOEAD 作為多目標優化算法，種群規模的改變對算法性能沒有多大的影響。雖然DN_NSGAII 的PSP 值較低，但算法性能隨種群規模的增大而增大。MMOHEA僅在MMF3上算法性能隨種群規模有所改變，這是因為MMF3的測試函數復雜，且PSs 的曲線更加平滑。MMF3測試函數中，除SS-MOPSO 算法，算法性能都隨種群規模的增大而增大，在種群規模小于600 時，SS_MOPSO 性能最好，但當種群規模高于600 時，算法性能幾乎不變。除以上算法，其他算法性能都隨種群規模的增大而變化，由于MMOPIO 和SMPSO_MM 采用SOM 機制來獲得更好的解集，所以在種群規模小于800 時，MMOPIO 和SMPSO_MM 性能優于CSSMPIO，MRPS算法性能變化明顯，且一直低于CSSMPIO。

圖5 不同種群規模的PSP 值Fig.5 PSP values with different population sizes

綜合來看CSSMPIO 的性能隨種群規模的變化更優于對比算法，并且所有算法性能在不同的測試函數上大都受種群規模的影響，在計算資源有限的情況下，所提算法的種群規模仍設置為800。

3.2.2 物種半徑R分析

自適應物種形成策略生成小生境子空間，其中物種半徑確定子種群的大小，物種半徑的大小對算法的性能有一定的影響，一般情況下，物種半徑設置為決策變量范圍的1/20～1/10，因此本小節驗證在不同測試函數上算法性能隨物種半徑變化情況。本實驗選定MMF2、MMF5、SYM-PART1和Omni-test1測試函數分析不同物種半徑對CSSMPIO 性能的影響，10 次實驗的平均PSP 值如圖6，其他參數設置同表1。圖中顯示，測試函數的PSP 值都隨物種半徑的增大而減小，這是因為隨著物種半徑的增大，決策空間中形成的物種數量減少。此外，與SYM-PART1和Omni-test1相比，隨著半徑的增加，MMF2、SYM-PART1和Omni-test1的PSP 值顯示出較小的變化。產生這種現象的原因是測試函數決策變量變化范圍小，因此半徑的變化很小，這對算法的性能影響很小。因此將物種半徑設置為決策變量范圍的1/20 時，CSSMPIO可以找到決策空間更多Pareto 解集，提高決策空間的種群多樣性。

圖6 不同物種半徑的PSP 值Fig.6 PSP values with different radius

3.2.3 聚類數目k分析

在所提算法中，初始化種群中聚類數目k值的確定也會影響算法的性能。如2.1小節所示，k=表示Fj中的個體數，n為正整數，可以看出，參數n間接決定了k的值，當n較大時，k越小。本小節驗證不同n值[24]對算法性能的影響，參數設置如表1，實驗結果如表3。從表3 可以看出，大多數測試函數在n=10 時，算法性能最好，尤其是表現在復雜函數中。即使n=10 時MMF2和MMF8函數的PSP 值不是最高的，但與表現最好的也相差不大。由于一個解和它的鄰域解應來自同一局部區域，所以參數n越小越好，但如果同一類中解的個數過少，則會影響邊界解的CSCD 值。綜合考慮，取參數n=10。

表3 CSSMPIO 使用不同參數 n獲得的PSP 值Table 3 PSP values obtained by CSSMPIO with different n values

3.3 實驗結果與對比

3.3.1 PSP 指標對比實驗和分析

CSSMPIO 與其他比較算法所得的PSP 值的平均值與標準方差的統計結果如表4 所示，其中最佳結果被突出顯示。同時，采用Wilcoxon 秩和檢驗[36]表明CSSMPIO 的結果與其他比較算法在0.05 顯著水平上的差異性，“+”“-”和“=”分別表示比較算法與CSSMPIO 相比體現出明顯優越、明顯差、沒有顯著差異的性能。從表4 可以看出，CSSMPIO 取得的PSP 最優值數量為8 個，SMPSO_MM 取得的最優值數量為3 個，SS_MOPSO 求得的最優值數量為3 個。CSSMPIO在14 個測試函數上的PSP 結果顯著優于MOEAD 和DN_NSGAII。MOEAD 是典型的多目標算法，對于求解多模態多目標測試函數的效果最差。DN_NSGAII 在所有函數上的性能表現都較差，這是因為DN_NSGAII 只考慮了決策空間的擁擠距離，而忽略了目標空間。MMOHEA 算法在Omni-test 測試函數上的性能較好，雖然在其他測試函數上PSP 性能較差，但是算法運行所需的時間較短，并且算法性能比較穩定。而MRPS 性能略低的原因在于僅考慮了環形拓撲鄰域結構，沒有進行非支配特殊擁擠距離排序，在決策空間的解分布不夠均勻。SMPSO_MM和MMOPIO 采用SOM 機制來建立粒子的鄰域，使其更適合求解較復雜的問題。在SS_MOPSO 中，不同物種重疊粒子的分配僅取決于物種種子的非支配等級，粒子會向非支配等級更高的物種種子學習，這會影響種群的多樣性，得到的PSs 是不完整、不均勻的。

表4 所有算法得到的PSP 平均值與標準方差Table 4 Mean and standard variance of PSP obtained by all algorithms

此外，CSSMPIO 對MMF2、MMF3、MMF4、SYM-PART 與Omni-test1測試函數的性能顯著優越，尤其是對SYM-PART 和MMF8測試函數，CR值達到1.0，這意味著求得的PSs 全部覆蓋了真實PSs。CSSMPIO 與SMPSO_MM 在MMF1、MMF5和MMF6上的結果相近，這是因為算法在決策空間表現相似，而CSSMPIO 在MMF7表現較差的原因是MMF7的PSs 的分布呈不規則曲線。由于鴿群算法的局部搜索能力強，CSSMPIO與MMOPIO 都適于求解SYM-PART 測試函數，并且對于多個PSs 的Omni-test 測試函數CSSMPIO 也表現較好。

表5 反映了CSSMPIO 與對比算法的HV 值，HV 反映了目標空間的收斂性和多樣性[31]。從表5可以看出，CSSMPIO 在MMF5、SYM-PART2和SYM-PART3測試函數上的HV 最高；DN_NSGAII和MOEAD 的HV 大都表現較好，原因是這兩個算法都是多目標算法，考慮了目標空間而未考慮決策空間。雖然CSSMPIO 與其他算法相比沒有表現出最佳HV，但從統計結果來看，結果相差不大。綜合來講CSSMPIO 不僅在決策空間有較好的收斂性和多樣性，而且也考慮到在目標空間的分布。

表5 所有算法得到的HV 平均值與標準方差Table 5 The mean and standard variance of HV obtained by all algorithms

3.3.2 IGDx 指標對比實驗和分析

CSSMPIO 與其他比較算法所得的IGDx 值的平均值和標準方差見表6。同時， Wilcoxon 得到的統計分析結果也在表6 中顯示。從表中可以看出，相比于MOEAD 和DN_NSGAII，CSSMPIO 在14 個測試函數上都表現出了較好的性能。CSSMPIO在MMF1、MMF5和MMF6測試函數上的IGDx值與SMPSO_MM 算法相比沒有顯著差異。CSSMPIO 在規則曲線測試函數MMF2和MMF3上的IGDx 值較小，說明在這兩個測試函數上獲得的PSs 與真實PSs 值的歐氏距離較小，算法求得的解集和參考解集越接近。在MMF4上，SMPSO_MM 取得了較好的效果，由于MMF7和MMF8的解分布為不規則的曲線，而SOM 映射網絡適于求解此類問題，所以SMPSO_MM 和MMOPIO 求得的解集和參考解集更接近。在更復雜、空間維度更高的測試函數SYM-PART 與Omni-test 上的性能指標表示，CSSMPIO 卻取得了更好的結果，這意味著更接近真正的PSs。并且MMF1、MMF4、MMF5、MMF7和MMF8是除MMF6之外在每個維度上沒有重疊的簡單測試函數，從結果中可以看出，CSSMPIO 對求解復雜的測試函數效果更優越一些。

表6 所有算法得到的IGDx 平均值與標準方差Table 6 Mean and standard variance of IGDx obtained by all algorithms

3.3.3 決策空間PSs 分布分析

圖7～9 比較了算法在MMF1、MMF3和SYMPART1測試函數上得到的PSs，圖中的水平坐標和垂直坐標分別表示對應決策變量的邊界范圍。從圖中可以看出，MOEAD 求得的PSs 最差。在MMF1測試函數上，不僅3.3.1 和3.3.2 小節部分CSSMPIO 求得PSP 值和IGDx 值更優越，而且從圖7 可以看出CSSMPIO 求得的PSs 分布也更均勻。對于性能表現較好的MMF3和SYM-PART1測試函數來說，圖8、圖9 更直觀地體現了CSSMPIO 找到更多的Pareto 最優解，且解的分布也更均勻。

圖7 不同算法在MMF1 上得到的PSsFig.7 PSs obtained on MMF1 with different algorithms

圖8 不同算法在MMF3 上得到的PSsFig.8 PSs obtained on MMF3 with different algorithms

圖9 不同算法在SYM-PART1 上得到的PSsFig.9 PSs obtained on SYM-PART1 with different algorithms

為了更準確地說明這一點，圖10 表示CSSMPIO 在其他測試函數上得到的決策空間Pareto解集的分布和真實Pareto 解集分布的圖像，“○”代表的是獲得的PS，“+”代表的是真實PS。從圖中可以看出，CSSMPIO 求得的PSs 大多可以覆蓋于真實的PSs，且PSs 的分布是均勻的。尤其在復雜函數SYM-PART2上取得了更優的效果。綜合各算法的PSP 值和IGDx 值以及Pareto 解集的分布結果，所提CSSMPIO 獲得的PSs 能夠較好地覆蓋真實PSs，相比于其他算法具有更好的收斂性和多樣性，在決策空間和目標空間上實現更好的平衡。

圖10 CSSMPIO 在測試函數上得到的決策空間PSs 分布Fig.10 The PSs distribution of decision space obtained by the CSSMPIO algorithm in test functions

3.4 算法運行時間對比分析

圖11 可視化了不同算法在測試問題上計算一次的平均運行時間，運行時間刻度設置為log10。從圖11 可以看出，MMOHEA 的時間成本最低，這是因為算法采用了有效支配排序策略，但是該算法的計算結果較差。MOEAD 的運行時間是不穩定的；CSSMPIO 采用了小生境搜索策略，算法運行時間相較MRPS、DN_NSGAII 較長；相較于SMPSO_MM、MMOPIO 來說，CSSMPIO 算法的運行時間相差不多，但是算法的求解結果更好，綜合來看，CSSMPIO 算法的效率較高。

圖11 比較算法在14 個測試函數上的運行時間Fig.11 Runtime of different comparison algorithms on 14 test functions

4 基于地圖測試問題的應用

為驗證CSSMPIO的性能，采用基于地圖的測試問題[37]，測試問題是從實際地圖生成的，如圖12（a）所示，涉及6 所小學（紅色圓圈）、3 所中學（綠色圓圈）、13 家便利店（藍色圓圈）和3 個火車站（黑色圓圈），利用決策空間（即地圖中的點）中解x的歐氏距離定義了4 個最小化目標：f1(x)：距離最近的小學（紅色圓圈）；f2(x)：距離最近的中學（綠色圓圈）；f3(x)：距離最近的便利店（藍色圓圈）；f4(x)：距離最近的火車站（黑色圓圈）。

圖12 基于地圖的測試問題及Pareto 區域Fig.12 The map-based test problems and the Pareto regions

圖12（b）中的綠色部分表示該問題的帕累托最優區域，并通過檢查101×101 個點(x1=0, 1, ···,100；x2=0, 1, ···, 100)中每個點的Pareto 最優性來描述。

為了證明CSSMPIO 的有效性，將CSSMPIO與MRPS 在基于地圖的問題上進行了比較，參數設置如表1。結果如圖13 所示，CSSMPIO 可以覆蓋所有Pareto 區域，而MRPS 獲得的Pareto 區域是不完整的。這表明CSSMPIO 的性能優于MRPS，證明了CSSMPIO 的有效性。

圖13 兩種算法得到的解Fig.13 Obtained solutions by two algorithms

5 結束語

針對多模態多目標優化中種群多樣性難以維持以及等價Pareto 最優解數量不足問題，本文提出一種融合聚類和小生境搜索的多模態多目標優化算法（CSSMPIO）。CSSMPIO 采用基于聚類的特殊擁擠距離排序（CSCD）克服了非支配特殊擁擠排序（SCD）不能正確識別鄰域的缺點，并且考慮到了決策空間和目標空間的擁擠距離，個體在自適應形物種形成策略中形成的小生境子種群中利用改進的鴿群優化算法并行搜索等價Pareto 最優解，最后執行精英學習策略，從而在決策空間和目標空間中獲得一個均勻分布的群體。

綜合分析CSSMPIO 算法與其他7 種多模態多目標算法在14 個測試函數上的結果發現，CSSMPIO 算法能夠找到更多的PSs，提高了決策空間的多樣性以及算法搜索能力。另外求得的解集接近于真實解集，具有較好的收斂性和多樣性，在決策空間和目標空間上實現更好的平衡。

但是本文所提算法是連續優化算法，不適于求解離散優化問題，在未來的工作中，設計出離散優化多模態算法將是研究的方向。