基于不平衡權(quán)重和分布更新規(guī)則的粒子群算法?

李克文 陳振文

（中國石油大學(xué)（華東）計(jì)算機(jī)與通信工程學(xué)院 青島 266000）

1 引言

許多控制和決策問題可以轉(zhuǎn)化為優(yōu)化問題，隨著技術(shù)的發(fā)展，工程實(shí)踐中遇到的許多問題變得越來越復(fù)雜，而一些傳統(tǒng)的計(jì)算方法往往需要優(yōu)化函數(shù)連續(xù)、可微等條件，由于傳統(tǒng)計(jì)算方法的局限性，許多元啟發(fā)式算法被設(shè)計(jì)成求解困難優(yōu)化問題的滿意近似解。

在元啟發(fā)式優(yōu)化算法的研究中，群體智能算法是最活躍的領(lǐng)域之一，一些著名的群體智能算法也因此被提出，其中粒子群優(yōu)化算法是通過受鳥類或魚類的社會(huì)行為啟發(fā)，由Kennedy，J等在1995年提出的［1］。與其他群體智能算法相比，由于其概念簡單，易于理解和實(shí)現(xiàn)，在解決許多現(xiàn)實(shí)世界問題方面具有良好的性能而受到廣泛研究和關(guān)注［2］，許多的變體也因此被提出，例如為了防止粒子的早熟收斂，文獻(xiàn)［3～4］提出了粒子群算法的一種變體，在更新粒子當(dāng)前位置的同時(shí)，粒子的速度會(huì)受到種群gBest、個(gè)體pBest、和隨機(jī)選擇其他粒子pBest 的影響；文獻(xiàn)［5］提出了對(duì)種群的全局最優(yōu)解gBest進(jìn)行擾動(dòng)以減緩種群多樣性的喪失；文獻(xiàn)［6］根據(jù)粒子性能和距離最優(yōu)位置的遠(yuǎn)近來確定每一維的慣性權(quán)重值，提出了一種新的基于穩(wěn)定性自適應(yīng)慣性權(quán)重的粒子群優(yōu)化算法；文獻(xiàn)［7］將粒子分為不同的角色以完成不同的搜索分工并且根據(jù)距離最優(yōu)值的遠(yuǎn)近來動(dòng)態(tài)調(diào)整加速系數(shù)和慣性權(quán)重的大小，以此來改善種群的進(jìn)化速度；文獻(xiàn)［8］在粒子群算法中引入了社會(huì)學(xué)習(xí)機(jī)制，利用粒子群的全局最優(yōu)粒子和其它更優(yōu)的粒子來引導(dǎo)粒子的飛行；文獻(xiàn)［9～10］通過將種群分為多群并利用種群之間的信息交換來平衡算法的探索能力和開發(fā)能力；文獻(xiàn)［11］提出了一種基于交叉操作的粒子群算法，在保持很好差異性的同時(shí)通過對(duì)每個(gè)粒子的個(gè)體最優(yōu)位置進(jìn)行交叉，構(gòu)造出有效的引導(dǎo)樣本，進(jìn)而利用這些高質(zhì)量的樣本來指導(dǎo)粒子群的進(jìn)化；文獻(xiàn)［12］利用粒子的當(dāng)前位置Xi，個(gè)體最有位置pBest 和全局最優(yōu)位置gBest三者的均值和方差基于正態(tài)分布來構(gòu)造新解，以此改善了種群的早熟收斂、停滯現(xiàn)象。此外還有粒子群優(yōu)化算法與其他群智能算法的結(jié)合，例如文獻(xiàn)［13］結(jié)合了遺傳算法和粒子群算法并將其用在了聚類上；文獻(xiàn)［14～18］混合了粒子群算法和人工蜂群算法，利用各自的優(yōu)勢(shì)來提高混合算法的性能；文獻(xiàn)［19］混合了粒子群算法和煙花算法并將其用在了全局優(yōu)化上；文獻(xiàn)［20～21］結(jié)合了粒子群算法和螢火蟲算法等。

在這些粒子群算法中大多數(shù)都是基于粒子的最優(yōu)值與當(dāng)前位置的差值來更新位置的，這種基于差值的更新規(guī)則使得種群在迭代后期大多數(shù)的粒子都聚集在同一搜索范圍內(nèi)，此時(shí)算法很難再產(chǎn)生跳出這一局部范圍的新解，因此種群出現(xiàn)停滯行為。本文在基于分布更新規(guī)則的基礎(chǔ)上引入了不平衡權(quán)重策略和局部搜索的方式，在改善了種群停滯現(xiàn)象的同時(shí)加快了算法的收斂速度。理論分析和實(shí)驗(yàn)結(jié)果表明，本文算法有較好的綜合性能。

2 基于不平衡權(quán)重和分布更新規(guī)則的粒子群算法

2.1 標(biāo)準(zhǔn)粒子群算法

粒子群優(yōu)化算法是一種基于種群的全局優(yōu)化算法，在標(biāo)準(zhǔn)粒子群算法中，粒子群由N 個(gè)粒子組成，粒子搜索的過程被形象化為解的尋優(yōu)過程，每個(gè)粒子位置表示D維搜索空間中的一個(gè)可行解，解的質(zhì)量由目標(biāo)函數(shù)值或適應(yīng)度函數(shù)值來評(píng)估。每個(gè)粒子用pBest 記錄自己曾經(jīng)尋優(yōu)過的最優(yōu)位置，gBest 表示目前種群尋找到的最優(yōu)位置，每個(gè)粒子在現(xiàn)有速度Vi的基礎(chǔ)上根據(jù)自己的位置Xi、pBest和gBest 來更新速度值，然后粒子利用更新后的速度值來更新自己的位置。

標(biāo)準(zhǔn)粒子群算法的主要步驟如下。

初始化：初始化各種參數(shù)，如最大迭代次數(shù)IterMax，慣性權(quán)重值ω，學(xué)習(xí)因子C1和C2等；利用式（1）在D 維空間內(nèi)隨機(jī)生成N 個(gè)解，Xi=(，…，)表示第i個(gè)解的位置。

其 中i = 1， 2， … ， SN ，j = 1， 2， …， D ，是第j 維位置的下界值，為第j 維位置的上界值，rand 是［0，1］內(nèi)均勻分布的隨機(jī)數(shù)，(0)表示第0代第i個(gè)解的第j維。

利用式（2）初始化粒子的速度。

分別利用式（3）和式（4）初始化pBest 和gBest，在初始化階段，pBest 為第0 代時(shí)的粒子值，gBest 為所有粒子中的最優(yōu)值。

其中i = 1， 2，… ， N ，j = 1， 2， … ， D，f（Xi）表示第i 個(gè)粒子的目標(biāo)函數(shù)值，以尋優(yōu)最小值為例，argmin（）函數(shù)返回具有最小目標(biāo)函數(shù)值粒子的位置Xi給gBest。

以后每代粒子的速度和位置分別按照式（5）和式（6）進(jìn)行更新。

其中ω為粒子的慣性權(quán)重，表示粒子具有一定保持原來速度的能力，C1、C2為學(xué)習(xí)因子，分別表示粒子對(duì)自我和對(duì)群體的認(rèn)知程度。

在完成位置更新后，粒子利用式（7）來對(duì)pBest進(jìn)行更新，種群利用式（8）來對(duì)gBest進(jìn)行更新。

種群中的所有粒子都跟隨著種群的個(gè)體最優(yōu)和全局最優(yōu)來調(diào)整速度進(jìn)而更新自己的位置，通過權(quán)重ω來控制粒子慣性的大小，通過學(xué)習(xí)因子C1和C2來控制對(duì)自我認(rèn)知和對(duì)社會(huì)認(rèn)知的比例。在利用式（1）～（4）初始化粒子后，種群就利用式（5）～（8）迭代運(yùn)行，直到滿足終止條件為止。

2.2 基于不平衡權(quán)重和分布更新規(guī)則的粒子群算法

在標(biāo)準(zhǔn)粒子群算法中粒子位置是基于pBest、gBest 與當(dāng)前位置的差值而產(chǎn)生的，所有個(gè)體都追隨個(gè)體最優(yōu)值pBest 和全局最優(yōu)值gBest 而去，這種產(chǎn)生新解的方式使得種群多樣性下降較快而標(biāo)準(zhǔn)粒子群算法又缺少跳出局部最優(yōu)解的能力，因此在種群進(jìn)化到一定代數(shù)時(shí)，種群易出現(xiàn)進(jìn)化停滯不前的現(xiàn)象，當(dāng)粒子位置Xi和個(gè)體最優(yōu)pBest、全局最優(yōu)gBest 距離較近時(shí)，這種基于差值生成新解的方式將很難再產(chǎn)生新解?；诖宋墨I(xiàn)［12］提出了一種新的更新機(jī)制，利用Xi、pBest和gBest三者的均值和方差基于正態(tài)分布來產(chǎn)生新解，以此改善了種群的停滯現(xiàn)象；而本文則在此基礎(chǔ)上依據(jù)Xi、pBest 和gBest 三者的適應(yīng)度值采用不平衡權(quán)重的策略來生成均值和方差進(jìn)而基于正態(tài)分布產(chǎn)生新解，以此加快種群的進(jìn)化速度；另外，在包含所有粒子的種群完成一次全局搜索后，種群依據(jù)每個(gè)粒子的適應(yīng)度值采用輪盤賭選擇的方式再進(jìn)行一次局部搜索，以使得較優(yōu)的粒子得到更多的進(jìn)化次數(shù)，所提算法的具體內(nèi)容如下。

在本文提出的算法中，增加了計(jì)算粒子適應(yīng)度值和輪盤賭機(jī)制選擇的步驟，如式（9）和式（10）所示。

其中fi表示第i 個(gè)解的目標(biāo)函數(shù)值，fiti表示第i個(gè)解的適應(yīng)度值，abs（）是絕對(duì)值函數(shù)。

其中Pi表示第i個(gè)粒子被選擇的概率。

粒子的位置更新方式更改為如下：

其中m 為粒子位置Xi、pBest 和gBest 三者依據(jù)適應(yīng)度比計(jì)算出來的均值，計(jì)算如式（12）、（13）所示；s 為三者的標(biāo)準(zhǔn)差計(jì)算如式（14）所示，Z 的計(jì)算方式如式（15）所示。

其中r1、r2是屬于［0，1］內(nèi)均勻分布的隨機(jī)數(shù)。

在種群進(jìn)行一次全局搜索后：即種群中的每個(gè)粒子都進(jìn)行了一次位置更新。種群利用式（9）和式（10）得到的選擇概率逐個(gè)可重復(fù)的選出要進(jìn)化的粒子再進(jìn)行位置更新，粒子被選擇的概率和適應(yīng)度值成正比，搜索的次數(shù)往往為粒子的數(shù)目N。相比較全局搜索而言，這是一種和粒子質(zhì)量相關(guān)的局部搜索，適應(yīng)度較大的粒子可以得到更多的進(jìn)化機(jī)會(huì)。改進(jìn)后算法的詳細(xì)步驟如下。

步驟1：初始化階段

初始化各種參數(shù)，利用式（1）、式（2）、式（3）和式（4）分別初始化粒子的初始位置、初始速度、初始個(gè)體最優(yōu)解pBest以及種群最優(yōu)解gBest。

步驟2：全局搜索階段

每個(gè)粒子利用式（11）更新自己的位置。

步驟3：最優(yōu)值更新階段

利用式（7）和式（8）更新粒子的個(gè)體最優(yōu)解pBest和種群的全局最優(yōu)解gBest。

步驟4：局部搜索階段

利用式（10）產(chǎn)生的選擇概率隨機(jī)選擇一個(gè)粒子，使其利用式（11）更新自己的位置，然后同樣利用式（7）進(jìn)行個(gè)體最優(yōu)解pBesti的更新；另外，若其優(yōu)于全局最優(yōu)解gBest 則對(duì)gBest 進(jìn)行更新。本步驟迭代進(jìn)行N次。

步驟5：判斷是否滿足終止條件

如果滿足終止條件，則輸出最優(yōu)值和最優(yōu)解并退出，否則返回步驟2。

在基于不平衡權(quán)重和分布更新規(guī)則中，若種群中的粒子收斂于種群的當(dāng)前最優(yōu)解gBest，則Xi，pBesti，gBest 位于同一位置上，由此生成的標(biāo)準(zhǔn)差s為0，此時(shí)利用式（11）生成的新解與舊解位置相同，無法再產(chǎn)生不同于舊解的新解。為避免此現(xiàn)象的發(fā)生，我們?cè)O(shè)置一個(gè)閾值TSD，當(dāng)s 小于TSD 時(shí)，s取值為均值m的一半。

基于正態(tài)分布產(chǎn)生新解的方式改善了標(biāo)準(zhǔn)粒子群算法因種群多樣性的喪失而導(dǎo)致算法易進(jìn)化停滯的現(xiàn)象，而不平衡權(quán)重的策略進(jìn)一步使得產(chǎn)生的新解有偏向較優(yōu)解進(jìn)化的趨勢(shì)，另外局部搜索方式的加入使得較優(yōu)的粒子得到更多的進(jìn)化機(jī)會(huì)，也加速了種群的進(jìn)化。

3 仿真實(shí)驗(yàn)分析

為了驗(yàn)證所提算法，如表1 所示，本文選取了具有代表性的10 個(gè)基準(zhǔn)函數(shù)來驗(yàn)證算法的收斂精度和穩(wěn)定性等性能，其中，sphere 函數(shù)、rosenbrock函數(shù)、sumSquares 函數(shù)、sumPower 函數(shù)、quartic 函數(shù)為單峰函數(shù)，schwefel2.26 函數(shù)、rastrigin 函數(shù)、ackley函數(shù)、griewank函數(shù)、levy函數(shù)為多峰函數(shù)。

為了對(duì)比實(shí)驗(yàn)本文選取了標(biāo)準(zhǔn)粒子群優(yōu)化算法SPSO 和PSOd 算法［12］作為對(duì)比算法，其中PSOd算法是近來經(jīng)常被用來比較的優(yōu)秀算法；標(biāo)準(zhǔn)粒子群優(yōu)化算法粒子的數(shù)量設(shè)置為40，慣性權(quán)重ω從0.9 隨著迭代次數(shù)的增加線性遞減到0.4，學(xué)習(xí)因子C1和C2設(shè) 置 為1.5；PSOd 的 粒 子 數(shù) 目 同 樣 設(shè) 置 為40；由于本文算法加入了局部搜索且局部搜索的次數(shù)為種群粒子的數(shù)目，為了公平比較，保證在一次迭代中的函數(shù)評(píng)估次數(shù)也為40，本文算法的粒子數(shù)量設(shè)置為20；算法的最大迭代次數(shù)IterMax 由公式（16）確定：

其中FEperIt 表示種群每進(jìn)化一代函數(shù)的評(píng)估次數(shù)，D 表示求解問題的維數(shù)。除了上述參數(shù)外，PSOd和本文算法中的TSD設(shè)置為1e-5。

表1 基準(zhǔn)函數(shù)

3.1 算法的收斂精度和穩(wěn)定性分析

為了減少算法的隨機(jī)性影響，每個(gè)算法在每個(gè)測(cè)試函數(shù)的30 維上獨(dú)立運(yùn)行30 次，然后求其平均值和標(biāo)準(zhǔn)差來分別驗(yàn)證算法的收斂精度和穩(wěn)定性，結(jié)果如表2 所示，最優(yōu)結(jié)果加粗顯示，其中uwdPSO表示本文算法。

表2 D=30維時(shí)的測(cè)試結(jié)果

由表2 可知：本文算法在函數(shù)f6上的尋有結(jié)果略差于PSOd算法但依舊明顯優(yōu)于SPSO算法，另外本文算法的標(biāo)準(zhǔn)差最小，表明了本文算法尋優(yōu)的穩(wěn)定性；在函數(shù)f1、f4、f5、f7、f8、f9上取得了和PSOd 對(duì)等的尋優(yōu)結(jié)果；除此之外，本文算法在函數(shù)f2、f3、f10上都取得了明顯的最優(yōu)收斂精度以及最可靠的穩(wěn)定性；另外，PSOd 算法在函數(shù)f10上的尋優(yōu)結(jié)果差于SPSO算法，在其余函數(shù)上也都優(yōu)于SPSO算法。

3.2 算法的收斂速度分析

在函數(shù)f1、f4、f5、f7、f8、f9上算法PSOd 都和本文算法uwdPSO 取得了相同的尋優(yōu)結(jié)果，為了進(jìn)一步對(duì)比，我們給出了它們的收斂曲線如圖1所示。

圖1 部分收斂曲線圖

通過圖1 可知，在f1、f4、f5、f7、f8、f9函數(shù)上本文所提算法的收斂速度要遠(yuǎn)遠(yuǎn)快于PSOd 算法，這是因?yàn)樵谒阉鬟^程中，我們依據(jù)粒子的適應(yīng)度值基于不平衡的策略來分配權(quán)重以獲得均值μ和標(biāo)準(zhǔn)差σ，使得產(chǎn)生的新解有靠近較優(yōu)解的趨勢(shì)，加速了種群的進(jìn)化，另外在進(jìn)行完全局搜索后，根據(jù)個(gè)體適應(yīng)度值依據(jù)概率選擇要進(jìn)化的粒子對(duì)種群進(jìn)行局部搜索的方式也提高了算法的收斂速度。

通過對(duì)本文所提算法收斂精度、穩(wěn)定性和收斂速度的分析表明：本文算法具有較好的綜合尋優(yōu)性能。

4 結(jié)語

針對(duì)標(biāo)準(zhǔn)粒子群算法種群多樣性下降較快導(dǎo)致種群進(jìn)化易出現(xiàn)早熟、停滯現(xiàn)象以及進(jìn)化速度緩慢等不足，本文提出了一種基于不平衡權(quán)重和分布更新規(guī)則的粒子群算法。在分布更新規(guī)則的基礎(chǔ)上引入了不平衡權(quán)重策略以使產(chǎn)生的新解有快速朝向較優(yōu)解進(jìn)化的趨勢(shì)，提高了算法的收斂速度；此外，局部搜索機(jī)制的加入給予適應(yīng)度較大的粒子更多進(jìn)化的機(jī)會(huì)，也加速了種群的進(jìn)化。最后在10 個(gè)經(jīng)典基準(zhǔn)測(cè)試函數(shù)上的測(cè)優(yōu)結(jié)果表明了本文算法具有較優(yōu)的收斂精度、可靠的穩(wěn)定性和較快的收斂速度，是一個(gè)優(yōu)越的尋優(yōu)算法。