穆華平

（鶴壁技術(shù)學院公共基礎(chǔ)教研部，河南鶴壁，458030）

0 引言

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

1 粒子群算法模型

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

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

2 群體網(wǎng)絡(luò)特征屬性

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

（1）平均最短路徑長度

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

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

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

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

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

3 以適應(yīng)值為驅(qū)動的群體演化機制

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

3.1 增刪邊策略

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

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

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

3.2 算法流程

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

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

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

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

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

4 仿真實驗

4.1 實驗設(shè)置

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

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

4.2 實驗結(jié)果與分析

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

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

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

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

5 結(jié)論

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