尹杰

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

0 引言

基于種群或個(gè)體的解搜索算法通常是被設(shè)計(jì)為定位一個(gè)單一的全局解。代表性的例子包括進(jìn)化算法（Evolutionary Algorithm）和 群 體 智 能（Swarm Intelli?gence）在內(nèi)的多種算法。由于使用的是全局選擇方案，這些搜索算法通常會(huì)收斂到一個(gè)單一解。然而，許多現(xiàn)實(shí)世界的問(wèn)題本質(zhì)上是“多模態(tài)”的，即存在多個(gè)令人滿意的解。我們可能需要找到許多這樣的解，甚至是所有可接受的解，這樣決策者就可以選擇一個(gè)特定問(wèn)題域中最合適的解。過(guò)去已經(jīng)開發(fā)了許多技術(shù)來(lái)定位多個(gè)最優(yōu)解（optima）。這些技術(shù)一般被稱為“小生境”方法。小生境方法可以以串行（sequential）或并行（parallel）的方式整合到標(biāo)準(zhǔn)的基于搜索的優(yōu)化算法中，從而定位多個(gè)全局最優(yōu)解。串行方式隨著時(shí)間的推移逐步找到最優(yōu)解，而并行方式聚焦于促進(jìn)和維持一個(gè)群體中多個(gè)穩(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)實(shí)世界的多模態(tài)問(wèn)題之前，都有一些需要克服的困難，包括：難以預(yù)先指定一些小生境參數(shù)；難以在運(yùn)行中保持發(fā)現(xiàn)的解；當(dāng)維度和模態(tài)較高時(shí)，可擴(kuò)展性差等。為了克服上述缺點(diǎn)，本文提出了一種新的小生境方法：基于粒子群優(yōu)化，引入仿射傳播（Affinity Propagation）[4]聚類形成多個(gè)小生境，再對(duì)小生境中粒子的pbest加權(quán)得到pbestw，然后使用牛頓插值（Newton Interpolation）預(yù)估比nbest的適應(yīng)度更優(yōu)的插值，接下來(lái)使用指數(shù)排序選擇（Exponential Ranking Selection）選取pbestw更新的粒子，最后局部搜索（Local Search）尋找更接近最優(yōu)解的點(diǎn)。

1 基礎(chǔ)知識(shí)

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

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

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

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

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

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

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

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

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

2.1 仿射傳播聚類

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

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

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

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

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

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

2.2 均衡

2.3 pbestw

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

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

2.4 牛頓插值

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

牛頓插值的計(jì)算過(guò)程如下：

2.5 更新

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

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

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

2.6 局部搜索

3 實(shí)驗(yàn)結(jié)果

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

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

4 結(jié)語(yǔ)

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

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