小生境粒子群優化在多模態優化問題上的研究

尹杰

（四川大學計算機學院，成都610065）

0 引言

基于種群或個體的解搜索算法通常是被設計為定位一個單一的全局解。代表性的例子包括進化算法（Evolutionary Algorithm）和 群 體 智 能（Swarm Intelli?gence）在內的多種算法。由于使用的是全局選擇方案，這些搜索算法通常會收斂到一個單一解。然而，許多現實世界的問題本質上是“多模態”的，即存在多個令人滿意的解。我們可能需要找到許多這樣的解，甚至是所有可接受的解，這樣決策者就可以選擇一個特定問題域中最合適的解。過去已經開發了許多技術來定位多個最優解（optima）。這些技術一般被稱為“小生境”方法。小生境方法可以以串行（sequential）或并行（parallel）的方式整合到標準的基于搜索的優化算法中，從而定位多個全局最優解。串行方式隨著時間的推移逐步找到最優解，而并行方式聚焦于促進和維持一個群體中多個穩定子群體的形成。近期，將小生境技術應用于元啟發式（meta-heuristic）算法，如粒子群優化（Particle Swarm Optimization）[1]、差分進化（Differen?tial Evolution）[2]和進化策略（Evolution Strategy）[3]等均取得了良好的效果。

然而，現有的大部分小生境方法在成功應用于現實世界的多模態問題之前，都有一些需要克服的困難，包括：難以預先指定一些小生境參數；難以在運行中保持發現的解；當維度和模態較高時，可擴展性差等。為了克服上述缺點，本文提出了一種新的小生境方法：基于粒子群優化，引入仿射傳播（Affinity Propagation）[4]聚類形成多個小生境，再對小生境中粒子的pbest加權得到pbestw，然后使用牛頓插值（Newton Interpolation）預估比nbest的適應度更優的插值，接下來使用指數排序選擇（Exponential Ranking Selection）選取pbestw更新的粒子，最后局部搜索（Local Search）尋找更接近最優解的點。

1 基礎知識

粒子群優化是一種受到鳥群行為啟發而發明的算法。在粒子群優化中，每個粒子擁有自己迄今為止訪問過的最優位置記憶，并且能夠與其他粒子共享信息。在每一次迭代中，粒子除了慣性地向原有方向移動外，同時被自身記憶中的最優位置pbest和整個粒子群的最優位置gbest所牽引。每個粒子的速度v和位置x根據以下公式進行更新：

標準粒子群優化的算法流程如下：

（1）設定群體規模N、慣性權重w、加速常數c1和c2，隨機初始化每個粒子的速度v、位置x，并保證初始化位置在位置上界ub（upper bound）和位置下界lb（lower bound）之間。

（2）依照給定的函數評估每個粒子的適應度（fit?ness）。FEs是適應度函數評估（Function Evaluations，FEs），每當一個粒子的被評估了一次適應度，FEs=FEs+1。記每個粒子的當前位置為它的pbest，選擇所有粒子中適應度最優的粒子位置為全局最優位置gbest。

（3）根據更新公式計算每個粒子新的速度和位置。

（4）對每個粒子，評估當前位置的適應度并與歷史最優位置pbest的適應度相比較，如果當前位置更優，則更新pbest為當前位置。同時將所有粒子現在位置的適應度與全局最優位置gbest的適應度作比較，若有粒子的位置優于先前的gbest，則更新gbest為粒子現有位置中適應度最優的。

（5）如果達到實驗設定的MaxFEs（Maximum FEs），算法結束，否則返回步驟（3）。

標準版本的粒子群優化算法只能找到單個解，為了定位多個解，還需要采取一些方法來提升算法的探索能力和分布式的收斂能力。

2 小生境粒子群優化

2.1 仿射傳播聚類

與傳統的聚類算法不同，仿射傳播聚類不需要在運行算法之前確定或估計聚類數，它以數據點之間的相似度（例如歐氏距離作為測度）組成的相似度矩陣作為輸入，在數據點之間交換實值消息，直到生成高質量的聚類中心（exemplar）和相應聚類。

假設x1到xn是一組數據點，s(i,j)＞s(i,k)當且僅當xi和xj的相似度大于xi和xk的相似度，構建相似度矩陣（Similarity Matrix）s 描述任意兩點之間的相似度。開始時，所有數據點都會被看作潛在的聚類中心。算法的執行可以看作兩個消息傳遞（message-passing）步驟的交替，這兩個步驟會更新兩個初始化為零的矩陣：

吸引度（responsibility）矩陣r(i,k)衡量數據點k作為數據點i的聚類中心的適合程度。

歸屬度（availability）矩陣a(i,k)量化數據點i選擇數據點k作為其聚類中心的合適程度。

r(i,k)與a(i,k)越大，數據點k作為最終聚類中心的可能性就越大。

仿射傳播通過消息傳遞迭代地更新吸引度矩陣和歸屬度矩陣，逐漸生成聚類中心，最后將數據點分配給最近的聚類中心形成對應的聚類。

2.2 均衡

2.3 pbestw

將每個粒子的pbest的適應度占小生境中總的pbest適應度的比例作為權值，加權得到pbestw。

wi是小生境中第i個粒子的權值，fpbesti為第i個粒子pbest的適應度。

2.4 牛頓插值

在每個粒子數大于等于3 的小生境中選取適應度最優的Top 3 粒子，使用牛頓插值對其各維度分別構造插值多項式。如果插值多項式存在對應的最值，則將其作為這一維度的插值，否則用該小生境的nbest的相應維度值代替。

牛頓插值的計算過程如下：

2.5 更新

使用指數排序選擇計算每個粒子被選中使用pbestw更新的概率，此時小生境中的粒子以適應度優劣降序排序。

Pi代表小生境中第i個粒子被選中的概率，n是小生境中的粒子數，參數c簡單取0.5。

如果小生境中粒子數多，則其中選用pbestw更新的粒子也多，nmax為擁有最多粒子的小生境的粒子數。

2.6 局部搜索

3 實驗結果

CEC2015 的20 個多模態基準函數[5]中高維度的F16-F20被用于測試小生境粒子群優化的性能表現。實驗在64 位Win10 操作系統，16 Gb RAM 和4.80 GHz CPU 的PC 上的MATLAB 中運行。所有實驗在給定MaxFEs 和精度ε=1.0-5均獨立運行50 次，終止條件是找到所有全局最優解或達到MaxFEs。評價指標Peak Ratio（PR）反映多次運行后找到全局最優解的平均百分比。

表1 在基準函數F16-F20 實驗的Peak Ratio

4 結語

本文提出了一種新的小生境粒子群優化變體，首先通過仿射傳播聚類自動地劃分種群，降低了參數敏感度，同時遷移粒子使得每個小生境的規模均衡，再將pbestw和牛頓插值作為更好的學習對象，加速收斂，最后輔以局部搜索以提高解的精度。

即使小生境粒子群優化在平衡探索（exploration）和開發（exploitation）之間取得了不錯的成績，但在高維復雜的函數上，仍然難以定位所有的全局最優解。未來的研究中，希望能進一步提高性能。