穆華平

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

0 引言

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

1 粒子群算法模型

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

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

2 群體網絡特征屬性

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

（1）平均最短路徑長度

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

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

（2）平均聚集系數(shù)

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

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

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

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

3.1 增刪邊策略

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

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

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

3.2 算法流程

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

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

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

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

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

4 仿真實驗

4.1 實驗設置

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

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

4.2 實驗結果與分析

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

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

圖2 平均聚集系數(shù)變化情況

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

5 結論

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