適應(yīng)值引導(dǎo)下的粒子群算法群體特性分析

穆華平

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

0 引言

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

1 粒子群算法模型

粒子群算法是將優(yōu)化問(wèn)題的潛在解看作一個(gè)個(gè)沒(méi)有質(zhì)量、沒(méi)有體積的“粒子”，以一定的初速度在解空間中飛行搜索，其搜索的軌跡由自身的狀態(tài)和飛行中學(xué)習(xí)其它優(yōu)秀粒子的結(jié)果共同決定[4]。假設(shè)規(guī)模為N的粒子群體在D維空間中飛行，每個(gè)粒子的當(dāng)前位置為Xi=(xi1,xi2,...,xiD)，當(dāng)前速度為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)的第一部分是粒子自身的速度慣性對(duì)飛行軌跡的影響；第二部分是粒子的歷史最優(yōu)位置對(duì)其飛行軌跡的影響；第三部分是粒子所在鄰域內(nèi)其它粒子對(duì)其飛行軌跡的影響。顯然，群體的規(guī)模大小和連接方式能夠影響鄰域的范圍，進(jìn)而影響粒子的尋優(yōu)軌跡。當(dāng)鄰域?yàn)檎麄€(gè)群體時(shí)群體結(jié)構(gòu)為完全連接，鄰域內(nèi)最優(yōu)位置即為整個(gè)群體的歷史最優(yōu)位置；當(dāng)鄰域只包含自身時(shí)群體結(jié)構(gòu)完全離散，鄰域內(nèi)最優(yōu)位置與自身歷史最優(yōu)位置相同。

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

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

（1）平均最短路徑長(zhǎng)度

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

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

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

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

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

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

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

3.1 增刪邊策略

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

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

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

3.2 算法流程

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

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

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

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

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

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

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

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

圖1 平均最短路徑長(zhǎng)度變化情況

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

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

5 結(jié)論

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