小生境粒子群優(yōu)化在多模態(tài)優(yōu)化問題上的研究

尹杰

（四川大學(xué)計算機(jī)學(xué)院，成都610065）

0 引言

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

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

1 基礎(chǔ)知識

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

標(biāo)準(zhǔn)粒子群優(yōu)化的算法流程如下：

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

（2）依照給定的函數(shù)評估每個粒子的適應(yīng)度（fit?ness）。FEs是適應(yīng)度函數(shù)評估（Function Evaluations，F(xiàn)Es），每當(dāng)一個粒子的被評估了一次適應(yīng)度，F(xiàn)Es=FEs+1。記每個粒子的當(dāng)前位置為它的pbest，選擇所有粒子中適應(yīng)度最優(yōu)的粒子位置為全局最優(yōu)位置gbest。

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

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

（5）如果達(dá)到實驗設(shè)定的MaxFEs（Maximum FEs），算法結(jié)束，否則返回步驟（3）。

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

2 小生境粒子群優(yōu)化

2.1 仿射傳播聚類

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

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

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

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

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

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

2.2 均衡

2.3 pbestw

將每個粒子的pbest的適應(yīng)度占小生境中總的pbest適應(yīng)度的比例作為權(quán)值，加權(quán)得到pbestw。

wi是小生境中第i個粒子的權(quán)值，fpbesti為第i個粒子pbest的適應(yīng)度。

2.4 牛頓插值

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

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

2.5 更新

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

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

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

2.6 局部搜索

3 實驗結(jié)果

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

表1 在基準(zhǔn)函數(shù)F16-F20 實驗的Peak Ratio

4 結(jié)語

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

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