趙永樂 姜 軍

（華中科技大學(xué)自動(dòng)化學(xué)院 武漢 430074）

1 引言

在實(shí)際科學(xué)研究和工程應(yīng)用中，通常將實(shí)際問題經(jīng)過數(shù)學(xué)建模后轉(zhuǎn)化為數(shù)值函數(shù)的優(yōu)化問題［1］，而函數(shù)優(yōu)化問題成為近十幾年來研究熱點(diǎn)。隨著問題規(guī)模的不斷增加，對優(yōu)化方法的要求也越來越高。

傳統(tǒng)優(yōu)化算法，如梯度法、共軛梯度法、牛頓法、單純形法等，通常針對一些確定形式且需要一定約束條件限制的問題時(shí)，如在對凸優(yōu)化問題［2］等具有明確最優(yōu)解的情況下，具有較好的性能。但在實(shí)際應(yīng)用中出現(xiàn)越來越多的較大規(guī)模的、復(fù)雜的問題，具有高維度、多約束、多局部極值、非凸或者難以建立合適數(shù)學(xué)模型的特點(diǎn)，使得傳統(tǒng)方法受到一定的限制。而啟發(fā)式的優(yōu)化算法如：遺傳算法［3］、粒子群算法［4］、模擬退火算法［5］、蟻群算法［6］等便是應(yīng)對這種問題的一種途徑，其中的粒子群算法因其簡單性和有效性的特點(diǎn)，更受到很多學(xué)者的關(guān)注和研究［7～8］。

粒子群算法是受到鳥群之間溝通方式的啟發(fā)而提出的一種概率搜索優(yōu)化算法，其源于群智能，因其簡單性和有效性，具有很大的研究價(jià)值。但多數(shù)隨機(jī)優(yōu)化算法（包括粒子群算法）和遺傳算法的性能會(huì)隨著搜索空間的維度增加而急劇下降，計(jì)算時(shí)間會(huì)呈指數(shù)級增長，同時(shí)容易導(dǎo)致粒子的早熟而陷入局部最優(yōu)，這種現(xiàn)象被稱作“維數(shù)災(zāi)難［9］”。近年來國內(nèi)外學(xué)者提出了很多改進(jìn)算法［10～13］來試圖解決這些問題。

文獻(xiàn)［11］中提出一種協(xié)作進(jìn)化遺傳算法（co?operative coevolutionary genetic algorithm，CCGA）可以將整個(gè)問題空間分解成多個(gè)小維度的空間的組合，并使用遺傳算法在每個(gè)小的搜索空間內(nèi)進(jìn)行搜索，再將各個(gè)子空間的結(jié)果組合成整個(gè)問題的解來進(jìn)行評估。文中表明這種維度空間分解的方法對比基本GA算法獲得了明顯的性能提升。

文獻(xiàn)［12］將上述思想應(yīng)用到粒子群算法，提出兩種協(xié)作PSO模型，分別為CPSO-Sk和CP?SO-Hk。CPSO-Sk算法直接將CCGA的思想應(yīng)用到標(biāo)準(zhǔn)PSO算法，CPSO-Hk將標(biāo)準(zhǔn)PSO和CP?SO-Sk進(jìn)行結(jié)合。這兩種算法在多數(shù)測試函數(shù)上獲得了明顯的性能提升。

本文在上述思想的基礎(chǔ)上，提出一種層級協(xié)作粒子群算法即CPSO-Hierarchy（Hierarchy coopera?tive particle optimization），設(shè)計(jì)出一種CPSO-Sk和標(biāo)準(zhǔn)PSO之間進(jìn)行切換的層級策略，即每個(gè)種群所包含的維度逐漸增加，充分利用不同維度的子空間的信息，將標(biāo)準(zhǔn)PSO算法的開發(fā)能力和CPSO的探索能力進(jìn)行結(jié)合，具有一定的跳出局部最優(yōu)的能力，在9個(gè)標(biāo)準(zhǔn)函數(shù)中的大部分上獲得了更好的收斂結(jié)果，提高了算法的魯棒性。

2 粒子群算法

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

粒子群（Particle Swarm Optimization，PSO）算法，由Kennedy和 Eberhart［4］于1995年提出，是一種受鳥群覓食行為啟發(fā)的基于種群的優(yōu)化技術(shù)。PSO是由一系列粒子組成的種群來進(jìn)行整個(gè)優(yōu)化過程，每一個(gè)粒子代表優(yōu)→化問題的一個(gè)候選解。一個(gè)粒子由n維的向量 x來表示，代表這個(gè)粒子的位置；每一個(gè)粒子都具有一個(gè)由被優(yōu)化函數(shù)決定的適應(yīng)→值，代表這個(gè)候選解的質(zhì)量；以及一個(gè)速度向量 v，決定粒子運(yùn)動(dòng)速度的大小和方向。每一個(gè)粒子可以記錄其搜索到的最佳的位置pbest，同時(shí)可以獲取鄰近粒子發(fā)現(xiàn)的最佳位置gbest。PSO算法通過在整個(gè)搜索空間中移動(dòng)?！觼硭阉髯顑?yōu)值。在每次迭代t，通過增加速度vi(t)到t-1時(shí)刻的位置向量上來更新粒子i的位置x→(t)：

i

粒子的速度由下式來更新：

上式中ω是慣性權(quán)重，控制前一時(shí)刻的速度值對新速度的影響；加速因子c1是用來擴(kuò)展粒子認(rèn)知能力的參數(shù)（式（2）中的第二項(xiàng)），c2控制整體種群狀態(tài)的影響（式（2）中的第三項(xiàng)）；r→(t)和r→(t)

12為服從均勻分布U(0 ，1)的隨機(jī)值；yi(t)為粒子i的個(gè)體最優(yōu)值，即該粒子當(dāng)前時(shí)刻搜索到的最優(yōu)位置；y?(t)為粒子i的鄰域區(qū)域的所有粒子搜索到的最優(yōu)位置。因此每個(gè)粒子逐漸被吸引到該粒子目前的最優(yōu)位置以及種群整體最優(yōu)位置的方向。

粒子群算法的流程如下圖所示：

圖1 PSO算法的偽代碼

2.2 協(xié)作粒子群算法CPSO

協(xié)作學(xué)習(xí)的思想首先在文獻(xiàn)［11］中被應(yīng)用在GA領(lǐng)域。Potter認(rèn)為適應(yīng)函數(shù)的每一維均可以用一個(gè)獨(dú)立的種群進(jìn)行優(yōu)化，這些種群可以共同協(xié)作產(chǎn)生整個(gè)問題的解向量。而文獻(xiàn)［12］將這種協(xié)作學(xué)習(xí)的機(jī)制引入到PSO算法中，即使用N個(gè)各含M個(gè)1維粒子的種群進(jìn)行優(yōu)化，由于一個(gè)種群僅表示一維的搜索空間，無法直接得到這個(gè)種群中個(gè)體的適應(yīng)值，文中設(shè)置了一個(gè)由每個(gè)種群中的最優(yōu)粒子組成一個(gè)N維的背景向量。每個(gè)種群中的粒子只需替換背景向量中的對應(yīng)維度，即可用其來評估該粒子的適應(yīng)值。CPSO算法包含CPSO-S，CP?SO-Sk，CPSO-H和CPSO-Hk算法。其中CPSO-S把搜索空間的每一維作為一個(gè)種群進(jìn)行優(yōu)化，而CPSO-Sk算法把整個(gè)搜索空間分成k份，使用k個(gè)種群進(jìn)行優(yōu)化。因標(biāo)準(zhǔn)PSO算法具有跳出局部最優(yōu)的特點(diǎn)，及CPSO-Sk算法更快的收斂速度，文中CPSO-H和CPSO-Hk算法就是將這兩種優(yōu)點(diǎn)結(jié)合在一起，使得CPSO-Hk包含兩個(gè)階段，第一階段使用CPSO-Sk算法，第二階段使用PSO算法，同時(shí)兩個(gè)階段進(jìn)行一定的信息交互。

算法的流程如下圖2所示。

圖2 CPSO-S算法的偽代碼

3 層級協(xié)作粒子群算法CPSOHierarchy

CPSO-Hk算法通過結(jié)合標(biāo)準(zhǔn)PSO算法和CP?SO-Sk算法的特點(diǎn)，獲得了很好的效果提升，本文在此思想的基礎(chǔ)上，將多個(gè)CPSO-Hk種群組以層級遞進(jìn)的方式連接起來，使用維度生長的策略，逐漸增加粒子的搜索維度，同時(shí)每個(gè)種群組之間的進(jìn)行一定的信息交流，形成一種層級遞進(jìn)的結(jié)構(gòu)，本文將此方法稱作CPSO-Hierarchy算法。該算法充分利用不同維度尺度下的CPSO算法的特性，來增加整個(gè)種群的多樣性。而如何確定多個(gè)k值成為一個(gè)難點(diǎn)，本文中根據(jù)文獻(xiàn)［14］中實(shí)驗(yàn)得出的在k取6時(shí)獲得相對較好的性能，設(shè)定多個(gè)種群中的k=｛6，3，1｝。

綜合以上改進(jìn)算法的描述，整個(gè)算法的流程如下圖3所示：

圖3 層次協(xié)同粒子群優(yōu)化算法的流程圖

4 實(shí)驗(yàn)設(shè)置與結(jié)果分析

文章使用［15］中的標(biāo)準(zhǔn)函數(shù)作為實(shí)驗(yàn)的對象，如下表1所示。所有的函數(shù)均為最小化問題定義如下：

D：問題維度；

所有的函數(shù)具有相同的搜索范圍：[- 100，100]D

這些函數(shù)可以分成3組，單峰函數(shù)，基本多峰函數(shù)，復(fù)合函數(shù)。各組中使用的函數(shù)的特點(diǎn)如下表1所示。

對比方法和各自參數(shù)設(shè)置如下。

所有的方法迭代3×103次，或者達(dá)到一定的停止條件，所有的實(shí)驗(yàn)運(yùn)行20次，結(jié)果取20次的平均值，并計(jì)算標(biāo)準(zhǔn)差來評估算法魯棒性。分別針對30，60，90維的搜索空間。使用如下幾種PSO算法進(jìn)行試驗(yàn)：

標(biāo)準(zhǔn)PSO算法：參數(shù)設(shè)置為c1=1.49，c2=1.49，ω=0.72，vmax根據(jù)具體問題進(jìn)行限制；

表1 Benchmark Functions

CPSO-S6：參數(shù)設(shè)置c1=1.49，c2=1.49，ω隨時(shí)間線性下降，vmax根據(jù)具體問題進(jìn)行限制，而搜索空間向量被分成6份；

CPSO-H6：一種混合方法，包含CPSO-S6種群和一個(gè)PSO種群，兩個(gè)部分均使用參數(shù)為c1=1.49，c2=1.49，ω隨時(shí)間線性下降，vmax根據(jù)具體問題進(jìn)行限制。

CPSO-Hierarchy：同樣為混合方法，包含多個(gè)CPSO-Sk種群和一個(gè)PSO種群，參數(shù)設(shè)置為c1=1.49，c2=1.49，ω隨時(shí)間線性下降 vmax根據(jù)具體問題進(jìn)行限制。

實(shí)驗(yàn)結(jié)果：表2、3、4分別列出各優(yōu)化方法在30、60、90維Benchmark Functions的結(jié)果。

由表2、3、4分析可知，在9個(gè)測試函數(shù)上的結(jié)果顯示文中提出的層次CPSO算法CPSO-Hierarchy在多數(shù)的函數(shù)上獲得了最好的結(jié)果，CPSOH6算法在其他函數(shù)上獲得較好的結(jié)果，而標(biāo)準(zhǔn)PSO算法的結(jié)果最差。結(jié)果驗(yàn)證了不同維度分組的策略可以很好的綜合CPSO算法的快速收斂能力以及PSO算法跳出局部最小值能力的特性，并且充分利用在分組大小不同時(shí)這兩種特性的不同特點(diǎn)，使得算法在陷入局部最優(yōu)時(shí)，能夠在不同維度分組的搜索空間中進(jìn)行搜索，而發(fā)現(xiàn)在特定的維度分組時(shí)，可以影響整個(gè)維度空間的結(jié)果，并以此來跳出局部最優(yōu)值。

本文分別使用標(biāo)準(zhǔn)PSO算法、CPSOH6算法和CPSO-Hierarch算法對9組特性各異的Benchmark Functions進(jìn)行評估，以20次實(shí)驗(yàn)的均值和標(biāo)準(zhǔn)差來衡量算法的性能和魯棒性，結(jié)果表明CPSO-Hi?erarch算法具有較好的結(jié)果，可以明顯改進(jìn)CPSOH6算法的優(yōu)化能力，并且具有一定的魯棒性。

表2 不同算法在30維Benchmark Functions上的結(jié)果

表3 不同算法在60維Benchmark Functions上的結(jié)果

表4 不同算法在90維Benchmark Functions上的結(jié)果

5 結(jié)語

本文在對CPSO算法中維度分組不同時(shí)算法表現(xiàn)出的不同性質(zhì)進(jìn)行分析的基礎(chǔ)上，通過組合不同維度分組k的CPSO-Sk算法，得到比CPSOH6算法及標(biāo)準(zhǔn)PSO算法更好的收斂結(jié)果同時(shí)提高了算法的魯棒性，使得算法更適用于不同的模型，增加算法的適用度。