適應值引導下的粒子群算法群體特性分析

穆華平

（鶴壁技術學院公共基礎教研部，河南鶴壁，458030）

0 引言

粒子群算法[1]（PSO）是一種具有適應性的搜索算法，由美國的Kennedy 和Eberhart 教授于1995 年共同研究提出。由于該算法模型簡單、收斂速度快并且收斂的精度較其他智能算法要高，因而得到了領域內諸多學者的關注[2-3]。然而隨著應用領域的擴展和深入，早熟收斂的問題日漸突出，尤其對于大規模、復雜的多維優化問題，這種弊端就更加突出。由于復雜網絡的自適應形成過程和特點與粒子群算法的搜索的驅動力之間具有許多相似之處，本文就適應性引導下的粒子群算法群體特性進行研究，探索提高粒子群算法性能的方法。

1 粒子群算法模型

粒子群算法是將優化問題的潛在解看作一個個沒有質量、沒有體積的“粒子”，以一定的初速度在解空間中飛行搜索，其搜索的軌跡由自身的狀態和飛行中學習其它優秀粒子的結果共同決定[4]。假設規模為N的粒子群體在D維空間中飛行，每個粒子的當前位置為Xi=(xi1,xi2,...,xiD)，當前速度為Vi=(vi1,vi2,...,viD)。粒子根據自身的歷史最優位置Pi=(pi1,pi2,...,piD)和鄰域內歷史最優位置Pig=(p ig1,pig2,...,igD pigD)調整自己的飛行狀態，可以得出算法的搜索公式：

公式(1)的第一部分是粒子自身的速度慣性對飛行軌跡的影響；第二部分是粒子的歷史最優位置對其飛行軌跡的影響；第三部分是粒子所在鄰域內其它粒子對其飛行軌跡的影響。顯然，群體的規模大小和連接方式能夠影響鄰域的范圍，進而影響粒子的尋優軌跡。當鄰域為整個群體時群體結構為完全連接，鄰域內最優位置即為整個群體的歷史最優位置；當鄰域只包含自身時群體結構完全離散，鄰域內最優位置與自身歷史最優位置相同。

2 群體網絡特征屬性

粒子群算法的群體模型實質上是通過粒子在尋優過程中對于搜索經驗的借鑒而相互作用形成的關系網絡，根據復雜網絡的相關理論[5]，同時結合圖論的基本概念，抽取能夠描述群體網絡特點的特征屬性來進行研究。

（1）平均最短路徑長度

平均最短路徑長度是指群體網絡中任意兩個粒子之間學習經驗最少要經歷的邊數的平均值，它是用來衡量群體內粒子之間信息傳播速度的重要性能指標，其定義為：

其中，d(p)i,j表示進化概率為P時粒子i和j之間的最少邊數。

（2）平均聚集系數

節點的聚集系數描述的是群體網絡中與某節點直接關聯的所有節點之間的關聯度，即所有與某節點直接相連的節點中實際的連接邊數占全連接情況下邊數的比例。具體定義為：

其中，Hi是與節點i直接關聯的邊的數量；k i(ki-1)/2是最多可能存在的邊的數量。由此可以得出整個網絡的聚集系數為：

3 以適應值為驅動的群體演化機制

粒子群群體隨著算法的搜索，按照適應值的優劣同步完成群體網絡的自適應生長。初始化群體為隨機網絡模型，當搜索陷入停滯狀態或者多次震蕩性搜索時，根據適應值大小增加或者刪除連接，促進算法搜索的同時演化群體結構。

3.1 增刪邊策略

為了使算法跳出局部最優，獲得更佳的優化性能，應當讓適應值好的粒子比適應值差的粒子獲得更多的連接。因此，算法在進入搜索停滯狀態時，要將群體內的所有粒子按照適應值的優劣進行排名，適應值差的粒子在前，適應值好的在后。

定義：第t代時粒子i的排名為：Rank i(t)=Indexθ(Xi(t))，其中Index(X i(t)為粒子適應值排名后的粒子的編號，θ為影響因子，來調節粒子間的排名差距。刪除邊的概率定義如下：

對于粒子i和j之間的邊(i,j)，刪除邊的概率根據適應值較差的粒子確定。經過多次的刪邊操作，群體間的連接會大大減少。為了避免出現孤立節點，因而給斷邊后的節點選擇學習對象的機會。增加邊的概率定義如下：

3.2 算法流程

適應值引導下的粒子群算法（Particle Swarm Optim ization Guided by Fitness）的基本流程為：

（1）將粒子按照適應值大小降序排列，記錄排序后的每個粒子的排名Rank(t)；根據公式（4）計算群體中刪除邊的概率；

（2）遍歷粒子群體中的所有連接，根據邊刪除規則刪除邊，根據邊增加規則增加邊；

（3）判斷迭代次數tMOD20=0 是否成立；

（4）結束條件是否成立，如果成立則停止優化并輸出最優值；若不滿足，則進化代數t=t+1 。

4 仿真實驗

4.1 實驗設置

實驗選取典型的Rosenbrock 函數來測試群體結構的演化過程。Rosenbrock 函數是一種非常難以優化的單峰病態函數，全局極值點位于一個類似香蕉形的狹長山谷內，xi=1時達到最小值0，其定義如下：

實驗設置如下：粒子個數為100，問題維數為50 維。慣性權重ω從0.9 線性遞減為0.4，加速因子為1.5，運行環境為Inter i5 CPU，4G 內存，Windows7 系統。函數進化1000 代，每進化200 代記錄一次兩個特征屬性值。

4.2 實驗結果與分析

影響因子θ通過調節粒子適應值的排名差距而影響刪除和添加邊的概率大小，進而達到調整群體進化速度和結構特性的效果，因而對不同的θ取值對于群體結構和算法性能的影響，取θ=1,θ=5,θ=10,θ=20進行對比實驗，結果如圖1 和圖2 所示。

圖1 平均最短路徑長度變化情況

圖2 平均聚集系數變化情況

從圖1～圖2 可以看出，θ=1 時，群體進化過程中邊的刪除概率較小而增加新連接的概率較大，因而刪除邊的速度較慢，增加邊的速度較快，整個群體結構的聚集系數比較大，這說明群體中節點度小的粒子很少，群體結構接近完全連接，這種結構容易導致算法的局部搜索能力降低，容易引起算法在局部最優位置附近徘徊而難以到達全局極值點。θ=10，20 時，群體結構的聚集系數變小，群體的連接程度變得松散，這有利于算法的細致搜索，然而搜索速度大大下降，全局搜索能力降低，并且由于刪除和增加連接邊的概率增大，平均最短路徑長度出現震蕩性變化，進而引起群體模型的大幅度震蕩，對歷史最優位置的記憶能力減弱，有可能導致算法的穩定性降低，不利于算法的尋優。同時，從圖1和圖2 的變化趨勢看，隨著影響因子θ的增加，群體最優粒子能夠吸引更多的粒子通過學習與之產生連接，這必然導致解信息在群體中的傳輸速度不斷加快。搜索速度過快，有可能導致算法跨過全局最優位置，導致算法發無法搜索到全局極值，而θ過小則會導致算法在陷入局部極值時沒有突破局部極值的外力，搜索范圍狹窄而陷入局部最優位置。

5 結論

以適應值為引導的粒子群算法優化過程，同時也是粒子群體結構自適應演化的過程。從仿真結果可以看出在適應值的引導下，群體模型的特征屬性表現出自適應的動態變化。在不同的影響因子的作用下，群體網絡的平均聚集系數和平均最短路徑長度出現較大的差異。這意味著，改變群體結構的特征屬性，能夠影響潛在解的優化信息的傳播方式和速度，進而調整算法的優化方式和性能，是改進粒子群算法性能的一個簡單有效的策略。