周文峰，梁曉磊*，唐可心，李章洪，符修文

（1.武漢科技大學(xué)汽車與交通工程學(xué)院，武漢 430065；2.上海海事大學(xué)物流科學(xué)與工程研究院，上海 201306）

（*通信作者電子郵箱liangxiaolei@wust.edu.cn）

0 引言

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法是由Kennedy 和Eberhart［1-2］受鳥群等聚類生物尋覓食物行為的啟發(fā)而提出的一種群體智能優(yōu)化算法。PSO 算法具有原理簡單、結(jié)構(gòu)簡潔、參數(shù)少和魯棒性強等特點，在生產(chǎn)調(diào)度問題、車輛路徑問題、神經(jīng)網(wǎng)絡(luò)優(yōu)化和配送中心布局問題等領(lǐng)域得到廣泛應(yīng)用。和其他智能算法一樣，在求解復(fù)雜高維度的函數(shù)時，PSO 算法容易出現(xiàn)早熟和陷入局部最優(yōu)的現(xiàn)象。針對以上問題，國內(nèi)外學(xué)者做了大量研究。張藝瀛等［3］提出了基于動態(tài)鄰域的多策略進化的量子粒子群優(yōu)化算法，定義了一種動態(tài)鄰域選擇機制和三個不同策略的局部吸引子更新方程。翟亞飛等［4］提出了改進PSO，根據(jù)需要求解的問題設(shè)計了編碼和解碼機制，并引進了變異機制和改進了傳統(tǒng)的迭代機制。范厚明等［5］提出了混合粒子群算法，結(jié)合變鄰域下降搜索為主體的適應(yīng)性擾動機制，采用適應(yīng)性選擇鄰域策略，并在鄰域搜索中設(shè)置了可變的循環(huán)次數(shù)。劉寧慶等［6］提出了一種改進粒子群算法，對基本粒子群算法速度更新公式進行修改，設(shè)計了權(quán)重系數(shù)。劉明等［7］提出了一種基于定期競爭學(xué)習(xí)機制的多目標(biāo)粒子群算法，將粒子群算法與競爭學(xué)習(xí)機制融合，提高了算法收斂性。張鑫等［8］等將二范數(shù)原理和差分算法中的交叉算子引入粒子群算法中，提出了一種含交叉項的混合二范數(shù)粒子群優(yōu)化算法。Chang 等［9］提出了一種動態(tài)多種群粒子群算法，在進化過程中通過計算群距、群度和位置精度等一系列動態(tài)參數(shù)，將子群合并成更大的子群來加強個體之間的信息交流。Ghasemi 等［10］從數(shù)學(xué)中的向量理論出發(fā)，將向量模型與優(yōu)化算法結(jié)合，提出了一種新的粒子群優(yōu)化算法。Ebtehaj 等［11］提出了一種新的混合進化算法，將粒子群算法與自適應(yīng)神經(jīng)模糊推理系統(tǒng)相結(jié)合，對模糊隸屬度函數(shù)值進行優(yōu)化。

如何將粒子的拓撲結(jié)構(gòu)進行時變和有效地改進迭代機制等問題，文獻沒有進一步的研究和討論。本文從改變拓撲結(jié)構(gòu)和改進粒子迭代機制的角度出發(fā)，提出了一種具有拓撲時變和搜索擾動的混合粒子群（Hybrid PSO with Topological time-varying and Search disturbance，HPSO-TS）算法，首先采用K-medoids 聚類算法對種群進行動態(tài)分割，形成多個簇，根據(jù)自身搜索到的解與鄰域最好解進行比較，指導(dǎo)粒子搜索方向，這樣不僅加強粒子間的信息交流，而且還提高粒子的搜索效率；然后在更新速度時引入非線性變化的極值擾動，增加粒子的多樣性，幫助粒子跳出局部最優(yōu)；最后通過引進全局搜索與局部搜索相互轉(zhuǎn)換機制，并且在全局搜索中混合獅群算法和局部搜索中加入正弦擾動因子，不僅增加了粒子搜索方式的多樣性和搜索的精度，平衡了全局搜索和局部搜索，還提高了算法跳出局部最優(yōu)的能力。

1 粒子的拓撲結(jié)構(gòu)時變策略和搜索擾動機制

1.1 粒子的拓撲結(jié)構(gòu)時變策略

與社會群體“物以類聚”的思想類似，本文采用K-medoids聚類算法對種群進行動態(tài)分割，將具有相似特性的粒子聚集成一個簇。與倪慶劍等［12］研究多簇結(jié)構(gòu)的可變拓撲策略中定期更換簇數(shù)量不同，本文中粒子的拓撲結(jié)構(gòu)是隨迭代次數(shù)的變化而變化的，每次種群完成位置更新后，將重新確定簇中心，再將種群進行劃分。這樣不僅使每個簇的粒子數(shù)不同，增加簇的多樣性，還加強了簇間的信息交流。

K-medoids 算法是一種運用比較廣泛的聚類方法，和K-means 算法相似。兩者不同的是簇中心的選取，在K-means算法中，將中心點取為當(dāng)前簇中所有個體的平均值，而在K-medoids 算法中，選取當(dāng)前簇中的一個個體作為中心點，且要滿足簇中其他所有點到這個個體的距離最短。粒子群的聚類過程如下：

步驟1 從種群N中隨機選擇K個粒子p1，p2，…，pk作為簇初始中心點。

步驟2 計算其余粒子到各個簇中心的距離dis(xj，pk)=，根據(jù)距離最小原則，將各個粒子劃分到距離最近的簇內(nèi)。

步驟3 對于每個簇，計算簇內(nèi)所有粒子位置的均值，根據(jù)距離最小原則，選取離均值點最近的粒子作為簇中心。

步驟4 重復(fù)步驟2，判斷是否達到終止條件，如果到達，停止迭代，輸出結(jié)果；反之亦然。

1.2 粒子的搜索擾動機制

1.2.1 引入極值擾動

在粒子聚類成簇后，計算簇內(nèi)所有粒子的適應(yīng)度值，選擇其中最優(yōu)的粒子作為當(dāng)前簇的最優(yōu)值。為了加強簇之間的信息交流，本文將每個簇與其鄰域內(nèi)相鄰兩個簇建立合作聯(lián)系。假設(shè)對于簇i，當(dāng)前簇i搜索到的最優(yōu)解為besti，比較與其相鄰兩簇的besti-1和besti+1，選擇三者中最優(yōu)的作為簇i的neibest。借鑒文獻［13］，考慮到個體極值、全局極值和簇極值的影響，重新構(gòu)建種群個體粒子的速度更新公式，如式（1）。并為了讓粒子跳出局部最優(yōu)，引入極值擾動因子d，調(diào)整粒子的個體極值和全局極值，使粒子有更多機會探索新的區(qū)域。采用非線性變化的擾動因子，前期擾動因子較大，粒子可以搜索更大的范圍，后期擾動因子變小，有利于粒子的局部搜索。擾動因子更新公式，如式（2）。其中，為了平衡算法的全局搜索能力和局部改良能力，本文采用非線性的動態(tài)慣性權(quán)重系數(shù)公式，如式（3）：

其中：c1、c2為學(xué)習(xí)因子；dmax為最大極值擾動因子；dmin為最小極值擾動因子；t為本次代數(shù)；T為最大迭代次數(shù)。

1.2.2 引入轉(zhuǎn)換概率平衡搜索能力

在上述聚類過程完成以后，粒子將進行速度和位置的更新。為了平衡粒子的全局搜索和局部搜索，本文將引入花授粉算法（Flower Pollination Algorithm，F(xiàn)PA）［14］中轉(zhuǎn)換機制，在基本花授粉算法中，模擬花粉異花授粉方式為全局搜索，模擬花粉自花授粉為局部搜索，兩種搜索方式通過轉(zhuǎn)換概率p控制，其中p∈[0，1]。轉(zhuǎn)換概率對算法的性能影響較大，當(dāng)轉(zhuǎn)換概率p越小，粒子越容易進行局部搜索，則算法容易陷入局部最優(yōu)；轉(zhuǎn)換概率p越大，粒子越容易進行全局搜索，則算法的搜索精度不高。針對上述問題，本文采用線性變化的轉(zhuǎn)換概率，讓轉(zhuǎn)換概率從最大值pmax線性遞減到pmin，如式（4）：

根據(jù)實驗數(shù)據(jù)可得，一般地，pmax取0.95，pmin取0.4時效果更好。

1.2.3 調(diào)整位置迭代公式

粒子在尋優(yōu)的過程中，會根據(jù)轉(zhuǎn)換概率進行全局搜索和局部尋優(yōu)的轉(zhuǎn)換。在全局搜索過程中，為了加強算法搜索能力，本文將對粒子的搜索策略進行修改，結(jié)合獅群算法［15］中母獅覓食的迭代機制的優(yōu)點，從種群中隨機挑選一個粒子協(xié)助當(dāng)前粒子進行全局搜索，增加了粒子之間的信息交流，如式（5）。在局部搜索過程中，為了幫助算法跳出局部最優(yōu)，本文引入了正弦擾動因子，如式（6）：

1.3 算法步驟

算法流程如圖1所示。

圖1 算法流程Fig.1 Algorithm flowchart

算法具體實施步驟如下：

步驟1 初始化種群。在解空間，隨機產(chǎn)生N個粒子的位置xi和速度vi(i=1，2，…，N)，計算每個粒子的適應(yīng)度值。設(shè)定粒子速度的最大值Vmax和最小值Vmin，位置的最大值Xmax和最小值Xmin，學(xué)習(xí)因子c1、c2，維度D，最大極值擾動因子dmax，最小極值擾動因子dmin，最大迭代次數(shù)T，轉(zhuǎn)換概率的最大值pmax和最小值pmin。

步驟2 隨機選擇K個粒子作為聚類中心，采用1.1 節(jié)中粒子的拓撲結(jié)構(gòu)時變策略將種群分成K個簇。

步驟3 根據(jù)當(dāng)前粒子的速度和位置，計算出每個粒子的適應(yīng)值，得到個體歷史最佳位置pbest、全局的最佳位置gbest和簇內(nèi)最佳位置neibest，從而根據(jù)式（1）更新粒子的速度并進行越界處理。

步驟4 判斷條件rand＜p，若滿足條件則通過式（5）更新粒子的位置并進行越界處理；否則通過式（6）更新粒子位置并進行越界處理。重新計算粒子的適應(yīng)度值，更新gbest和pbest。

步驟5 判斷算法是否滿足迭代的終止條件，若滿足，則轉(zhuǎn)至下一步，否則轉(zhuǎn)至步驟2進行下一步迭代尋優(yōu)。

步驟6 輸出全局最優(yōu)值，算法結(jié)束。

1.4 算法的復(fù)雜度分析

從算法流程來分析HPSO-TS 算法的時間復(fù)雜度，由單次種群搜索行為分析可知，種群初始化的時間復(fù)雜度為O（N·D）；計算所有粒子適應(yīng)度值以及更新個體的pbest和全局粒子的gbest，其時間復(fù)雜度為O（N）；接下來采用K-medoids聚類算法對粒子群進行動態(tài)分簇，形成K個異構(gòu)子群，以此便于子群內(nèi)粒子間信息流通，其時間復(fù)雜度為O（N·K），由于K是常數(shù)且K≥1，所以O(shè)(N·K)=O(N)。在個體行為更新算法中，與基本PSO算法稍有不同，本文算法為了加強簇之間的信息交流，需要選擇鄰域中最優(yōu)的作為neibest，其時間復(fù)雜度為O(||Le||+N·D)，||Le||表示鄰域規(guī)模。因為上述步驟是按流程依次進行計算，所以HPSO-TS 算法的時間復(fù)雜度為max{O(N·D)，O(N)，O(N·D)，O(||Le||+N·D)}。由于D≥1，||Le||≥1 和K是常數(shù)，可知HPSO-TS 算法的時間復(fù)雜度為O(||Le||+N·D)。

可得結(jié)論，在固定迭代次數(shù)T下，HPSO-TS 算法的時間復(fù)雜度為O(T·(||Le||+N·D))。由于N·D＞＞||Le||，||Le||可忽略不計，因此本文算法的時間復(fù)雜度與基本PSO 算法的時間復(fù)雜度O(T·N·D)相近。

2 實驗分析

2.1 測試函數(shù)

為了分析和比較算法的有效性，本文選擇了花授粉算法FPA［14］、PSO［1-2］、改進粒子群（Improved PSO，IPSO）算法［4］、具有動態(tài)拓撲結(jié)構(gòu)的粒子群（PSO with Topology，PSO-T）算法和本文的算法HPSO-TS 進行性能比較。8 個經(jīng)典測試函數(shù)用于分別對以上5種算法進行實驗測試。

1）Sphere函數(shù)。函數(shù)在xi=0時取得最小值0，為單峰函數(shù)。函數(shù)表達式見式（7）：

2）Quadric 函數(shù)。函數(shù)在xi=0時取得最小值0，為單峰函數(shù)。函數(shù)表達式見式（8）：

3）Griewank函數(shù)。函數(shù)在xi=0時取得最小值0，為多峰函數(shù)。函數(shù)表達式見式（9）：

4）Ackley 函數(shù)。函數(shù)在xi=0時取得最小值0，為多峰函數(shù)。函數(shù)表達式見式（10）：

5）Rastrigin 函數(shù)。函數(shù)在xi=0時取得最小值0，為多峰函數(shù)。函數(shù)表達式見式（11）：

6）Step 函數(shù)。函數(shù)在xi=0時取得最小值0，為多峰函數(shù)。函數(shù)表達式見式（12）：

7）Sumsquares 函數(shù)。函數(shù)在xi=0時取得最小值0，為多峰函數(shù)。函數(shù)表達式見式（13）：

8）Tablet 函數(shù)。函數(shù)在xi=0時取得最小值0，為多峰函數(shù)。函數(shù)表達式見式（14）：

2.2 實驗1：算法性能的統(tǒng)計學(xué)分析

PSO和IPSO中學(xué)習(xí)因子c1=c2=2.5，慣性權(quán)重采用線性遞減方式wmax=0.95，wmin=0.4，此時兩種算法有較好的性能。PSO-T和HPSO-TS中c1=c2=1，K=5。

為降低算法的隨機性對實驗結(jié)果的影響，以30 次獨立運行實驗的平均值作為評價算法性能的結(jié)果。表1 和表2 僅列舉有代表性的函數(shù)在D=30 和D=50 上的最優(yōu)值、最差值、平均值和方差。測試平臺：Windows 7（64 位），Intel i5-4210U，2.40 GHz，4 GB RAM；在Matlab 2015b統(tǒng)一實現(xiàn)。

從實驗數(shù)據(jù)來看，無論是D=30 還是D=50，對于大多數(shù)函數(shù)來說，HPSO-TS 算法搜索解的質(zhì)量和穩(wěn)定性都優(yōu)于其他四種算法，這說明本文算法采用的聚類方式，有利于保持種群的多樣性，使其不斷搜索最優(yōu)解；搜索解的精度也好于其他四種算法，這說明本文算法采用的搜索擾動機制，有利于保持種群的活性和粒子的多樣性，使粒子搜索更多的區(qū)域，幫助粒子在迭代后期跳出局部最優(yōu)，搜索精度更優(yōu)的解。其中HPSO-TS 算法均可以搜到8 個函數(shù)的理論極值，同時搜索到解的質(zhì)量和精度都好于其他四種算法。但是在D=30時，HPSO-TS 算法對于求解函數(shù)f4的穩(wěn)定性提升有待提高，最優(yōu)值可以達到理論極值0，而最差值只能到-15 數(shù)量級。函數(shù)f3是多峰函數(shù)，從函數(shù)圖像可以看出此函數(shù)有很多峰值，本文算法求解時極易陷入局部最優(yōu)；在D=50時，HPSO-TS算法均可以搜到所有函數(shù)的理論極值，求解表現(xiàn)較為優(yōu)秀。

為了更好對比上述五種算法的尋優(yōu)能力，圖2、3 給出了有代表性函數(shù)的曲線收斂圖，其他函數(shù)測試結(jié)果類似。為了便于觀察，在不影響算法收斂特征下將縱坐標(biāo)適應(yīng)度值取以10為底的對數(shù)。結(jié)合表中數(shù)據(jù)和函數(shù)測試曲線，分析如下：

1）當(dāng)D=30時，對于f4，HPSO-TS算法的求解精度要優(yōu)于其他四種算法，但是依照測試曲線圖的趨勢，IPSO 算法收斂不明顯。對于其他函數(shù)，HPSO-TS算法的求解質(zhì)量、精度和魯棒性都要明顯強于另外四種算法。本文算法可以搜索到8 個函數(shù)的理論極值。其中從f6和f7測試曲線圖可以看出，在算法迭代到300 次左右時，曲線下降很快，算法迅速收斂，這說明HPSO-TS算法引入搜索擾動機制，增加了粒子的活力，能有效地幫助粒子跳出局部最優(yōu)，搜索到更優(yōu)的解，進一步提高算法的求解能力。

2）當(dāng)D=50時，在求解函數(shù)時，HPSO-TS 算法在求解精度、質(zhì)量和算法穩(wěn)定性方面都明顯好于其他四種算法。尤其是本文算法可以搜索到所有函數(shù)理論極值。其中從函數(shù)f8曲線圖可以看出，在算法迭代的次數(shù)1 000 以內(nèi)時，曲線下降的速度很快，算法迅速收斂，這說明HPSO-TS 算法引入搜索擾動機制，增加了粒子的活力，有效地幫助粒子跳出局部最優(yōu)，搜索到更優(yōu)的解，進一步提高了算法的求解的能力。

綜上所述，無論是對單峰還是多峰函數(shù)，HPSO-TS算法均可以獲得高質(zhì)量優(yōu)化結(jié)果。與其他算法相比，本文算法具有更好的穩(wěn)定性和搜索能力。該算法很好地緩解了早熟和收斂速度的矛盾，有效地平衡了全局搜索和局部搜索。

表1 函數(shù)測試實驗結(jié)果（D=30）Tab.1 Experimental results of function tests（D=30）

表2 函數(shù)測試實驗結(jié)果（D=50）Tab.2 Experimental results of function tests（D=50）

2.3 HPSO-TS算法的收斂曲線特性分析

參照圖2 和圖3中6 個函數(shù)的算法收斂曲線，將本文HPSO-TS算法與FPA 算法、PSO 算法、IPSO 算法和PSO-T 算法比較，進行收斂性分析。

在f2和f6上，大部分算法能夠求得較高精度的解，收斂曲線在1 000代內(nèi)下降幅度明顯，本文HPSO-TS算法收斂時所用的迭代次數(shù)更少，收斂曲線下降速度快，并且都能求得最優(yōu)解。在f3上，其他四種算法收斂曲線圖的趨勢大體一致，曲線下降平緩，本文HPSO-TS算法在200代左右收斂，收斂速度較快，并可以求得函數(shù)的理論極值點。在f4上，五種算法都能求得較優(yōu)的解，從收斂曲線圖可以看出，本文算法收斂的速度和精度是最優(yōu)的。在f7和f8上，從曲線圖上可得其他四種算法收斂均較平緩，求得的函數(shù)解精度不高，本文HPSO-TS 算法收斂曲線下降速度快，能求得函數(shù)最優(yōu)值。

以上分析說明HPSO-TS 算法采用的拓撲時變策略增加了種群的多樣性，提高了算法的收斂性，有利于算法的全局搜索。引入的搜索擾動機制，增加了粒子的活力，有效地幫助粒子跳出局部最優(yōu)，搜索更多可行解空間，從而求得更優(yōu)的解，進一步提高了算法的求解的能力。

2.4 實驗2：HPSO-TS算法對參數(shù)p的敏感性分析

在HPSO-TS 算法中，轉(zhuǎn)換概率p是影響算法性能的重要參數(shù)，其作用是平衡個體的全局搜索和局部搜索。為了減少算法性能對p設(shè)置的敏感性，本文算法采用p值線性遞減。實驗中p分別取0.8、0.5、0.2 和線性變化（見式（4）），設(shè)置D=30，算法最大迭代次數(shù)T=4 000。實驗結(jié)果如表3所示。

圖2 三個函數(shù)測試曲線(D=30)Fig.2 Test curves of three functions (D=30)

圖3 三個函數(shù)測試曲線(D=50)Fig.3 Test curves of three functions(D=50)

表3 不同p值的測試函數(shù)結(jié)果對比（D=30）Tab.3 Comparison of test function results with different p values(D=30)

從表3 可以看出，無論是對單峰函數(shù)還是對多峰函數(shù)，相同迭代次數(shù)時p值采用線性變化可以獲得較好的結(jié)果。轉(zhuǎn)換概率p對算法的性能影響較大：p越小，粒子越容易進行局部搜索，則算法容易陷入局部最優(yōu)；p越大，粒子越容易進行全局搜索，則算法的搜索質(zhì)量不高。當(dāng)p=0.8時，算法求解精度不錯，但求解質(zhì)量不如采用線性變化的p值，這時p值較大，大部分粒子進行全局搜索，降低了算法的局部搜索能力；當(dāng)p=0.5時，無論是在求解精度還是在求解質(zhì)量方面，都不如采用線性變化的p值，這是由于p取0～1 的中間值，算法的全局搜索能力和局部搜索能力都沒有達到較高水平；當(dāng)p=0.2時，無論是在求解精度還是在求解質(zhì)量方面，都不如采用線性變化的p值，這時p值較小，影響了算法的全局搜索能力，使得粒子無法在較優(yōu)的局部進行搜索，算法的求解質(zhì)量也受到影響。

綜上所述，采用p值線性變化由大到小遞減的HPSO-TS算法具有很好的穩(wěn)定性和魯棒性，開始階段p值較大有利于粒子進行全局搜索，后期p值較小使得粒子加強局部搜素，尋得更優(yōu)的解，這樣全局搜索和局部搜索都能兼顧。

3 結(jié)語

本文針對基本PSO 算法容易早熟和陷入局部最優(yōu)等問題，深入研究了種群粒子聚類思想和迭代機制，提出了一種基于拓撲結(jié)構(gòu)的改進迭代機制的粒子群算法。在種群初始化時，采用K-medoids算法對種群進行聚類分簇，得到若干個簇，通過比較簇內(nèi)粒子的適應(yīng)度值得到鄰域內(nèi)最優(yōu)的粒子來指導(dǎo)粒子進行迭代更新。然后考慮全局搜索和局部搜索調(diào)整，引入轉(zhuǎn)換率平衡種群兩種搜索行為，并融合獅群算法搜索策略，改進了迭代機制，重新更新粒子的位置，幫助粒子跳出局部最優(yōu)。實驗結(jié)果表明本文算法相比PSO 算法、FPA 具有更高的求解精度質(zhì)量和更好的穩(wěn)定性和魯棒性，達到了預(yù)期效果。