秦全德，李麗，程適，李榮鈞

(1.深圳大學(xué)管理學(xué)院，廣東 深圳518060;2.英利利物浦大學(xué)電氣電子工程系，英國(guó)利物浦L69 3GJ;3.西交利物浦大學(xué)電氣電子工程系，江蘇蘇州215123;4.華南理工大學(xué)工商管理學(xué)院，廣東廣州510640)

粒子群優(yōu)化(particle swarm optimization，PSO)算法是一種基于種群搜索的隨機(jī)優(yōu)化技術(shù)，其模擬了鳥群覓食過程中的遷徙和群集行為[1].PSO算法具有概念簡(jiǎn)單、控制參數(shù)少、收斂速度快和易于編程實(shí)現(xiàn)的優(yōu)點(diǎn)[2]，自提出以來受到廣大學(xué)者的關(guān)注.但PSO算法同其他的隨機(jī)搜索方法類似，在求解復(fù)雜多峰函數(shù)時(shí)，容易陷入局部最優(yōu)[3].為了提高算法性能，較多學(xué)者提出了基于不同思想的改進(jìn)算法，可以簡(jiǎn)單歸納為以下幾類:1)調(diào)節(jié)算法的參數(shù)[4-5];2)群體拓?fù)浣Y(jié)構(gòu)的改進(jìn)[6-7];3)與其他優(yōu)化算法混合[8-9];4)嵌入生物行為機(jī)制[10-11];5)設(shè)計(jì)新的學(xué)習(xí)策略[12-13].

在基本PSO算法中，粒子通過向個(gè)體最優(yōu)位置和群體最優(yōu)位置學(xué)習(xí)并不斷調(diào)整其飛行速度和所在位置，從而實(shí)現(xiàn)在搜索空間尋優(yōu).這樣的學(xué)習(xí)策略使得群體內(nèi)的信息交流速度快，但由于學(xué)習(xí)方向的單一性，容易產(chǎn)生“趨同”現(xiàn)象，在算法性能上表現(xiàn)為迭代后期搜索緩慢甚至停滯，容易陷入局部最優(yōu)[14].因此，設(shè)計(jì)新的粒子學(xué)習(xí)策略是提高PSO算法性能的一個(gè)重要途徑.目前，國(guó)內(nèi)外學(xué)者已經(jīng)在這方面開展了一些研究.Liang等提出了廣泛學(xué)習(xí)的PSO算法，其每個(gè)粒子根據(jù)學(xué)習(xí)概率來決定向自身個(gè)體最優(yōu)位置還是其他的個(gè)體最優(yōu)位置進(jìn)行學(xué)習(xí)[12].實(shí)驗(yàn)結(jié)果表明，采用廣泛學(xué)習(xí)策略能夠探索更大的搜索空間，保持了群體多樣性，算法在搜索過程中不容易陷入局部最優(yōu)，適合于多峰函數(shù)的求解.根據(jù)多精英比單精英更能夠引導(dǎo)群體學(xué)習(xí)的社會(huì)現(xiàn)象，Huang等提出了基于榜樣學(xué)習(xí)的改進(jìn)PSO算法[13].文獻(xiàn)[15]引入了超球坐標(biāo)的方式來更新粒子速度，設(shè)計(jì)了一種集成學(xué)習(xí)PSO算法.Wang等提出了一種自適應(yīng)學(xué)習(xí)的PSO算法，該算法依據(jù)搜索的進(jìn)程進(jìn)行調(diào)整學(xué)習(xí)概率，在具有不同優(yōu)點(diǎn)的4種學(xué)習(xí)策略中進(jìn)行自適應(yīng)選擇[16].Peram等提出了適應(yīng)度值－距離－比例的PSO算法，此算法中每個(gè)粒子的每一維根據(jù)適應(yīng)度值－距離－比例原則確定一個(gè)新的學(xué)習(xí)對(duì)象[17].

人類社會(huì)中不同群體之間存在資源和特質(zhì)的差異性，個(gè)體不但會(huì)吸收所在群體的經(jīng)驗(yàn)，而且還會(huì)同其他群體進(jìn)行信息交流.因此，人類社會(huì)的學(xué)習(xí)行為可以發(fā)生在個(gè)體與個(gè)體、個(gè)體與群體以及群體與群體之間.啟發(fā)于人類社會(huì)的學(xué)習(xí)行為特點(diǎn)，本文提出了一種由2個(gè)種群組成的交互學(xué)習(xí)的粒子群優(yōu)化算法(interactive learning particle swarm optimization，ILPSO).當(dāng)2個(gè)種群中最佳的全局最優(yōu)位置在連續(xù)一定的迭代次數(shù)內(nèi)沒有改善時(shí)，開始實(shí)施交互學(xué)習(xí)策略.交互學(xué)習(xí)的策略使得粒子學(xué)習(xí)的方向具有了多樣性，為算法擺脫局部最優(yōu)提供了新的額外動(dòng)力.仿真實(shí)驗(yàn)結(jié)果表明，ILPSO在搜索的過程中能夠較好地保持群體的多樣性，具有較好的全局尋優(yōu)能力，是一種求解復(fù)雜問題的有效方法.

1 粒子群優(yōu)化算法框架

PSO算法中的每個(gè)粒子視為問題的一個(gè)可行解.在D維的搜索空間中，粒子i在t次迭代時(shí)的狀態(tài)屬性由位置向量和速度向量進(jìn)行描述其中 ld和 ud分別為搜索空間的下限和上限，d=1，2，…，D，vmin和 vmax是由用戶設(shè)定的粒子飛行的最小和最大速度.粒子的好壞由一個(gè)事先設(shè)定的適應(yīng)度函數(shù)來確定.在算法的迭代過程中，每一個(gè)粒子通過向個(gè)體最優(yōu)位置和群體最優(yōu)位置進(jìn)行學(xué)習(xí)，按照式(1)和式(2)更新飛行速度和位置，從而在搜索空間內(nèi)尋優(yōu).

式中:tmax和t分別表示最大迭代次數(shù)和當(dāng)前的迭代次數(shù)，ωs和ωe分別表示算法初始和停止時(shí)的慣性權(quán)重.文獻(xiàn)[4]的研究結(jié)果表明當(dāng) ωs=0.9，ωe=0.4時(shí)，算法具有較好的性能.將文獻(xiàn)[4]這種慣性權(quán)重按照式(3)遞減的PSO算法稱為標(biāo)準(zhǔn)粒子群優(yōu)化算法(SPSO).

2 交互學(xué)習(xí)的粒子群優(yōu)化算法

2.1 交互學(xué)習(xí)策略

在ILPSO中，粒子分成Swarm1和Swarm22個(gè)種群.算法初始運(yùn)行時(shí)，2個(gè)種群均按照式(1)更新速度.Swarm1中粒子i在t次迭代的位置向量、速度向量、個(gè)體最優(yōu)位置和群體最優(yōu)位置分別記為將上述 4 個(gè)向量的下標(biāo)“1”改成“2”就代表Swarm2相對(duì)應(yīng)的向量.設(shè)的適應(yīng)度表示為表示 t次迭代時(shí) 2 個(gè)種群中最佳的全局最優(yōu)位置，其適應(yīng)度表示為在連續(xù)的k次迭代中如果沒有改善時(shí)，即，表明算法陷入了局部最優(yōu)，2個(gè)種群開始實(shí)施交互學(xué)習(xí)策略，其主要步驟如下:

1)確定學(xué)習(xí)種群和被學(xué)習(xí)種群.啟動(dòng)交互學(xué)習(xí)策略時(shí)，其中一個(gè)種群將仍然維持原有的方式進(jìn)行尋優(yōu)，稱之為被學(xué)習(xí)種群;改變?cè)械膶W(xué)習(xí)方式的種群稱為學(xué)習(xí)種群.根據(jù)的值，采用模擬退火的方法確定Swarm1和Swarm2作為被學(xué)習(xí)種群的概率.這樣的方式使得群體最優(yōu)位置相對(duì)較差的種群將以一定的概率作為被學(xué)習(xí)種群，從而增加了算法的全局搜索能力.用ps表示Swarm1被選擇作為被學(xué)習(xí)種群的概率，依據(jù)模擬退火算法的原理易有式(4):

式中:T表示模擬退火的溫度.依據(jù)ps的大小，采用輪盤賭的抽樣方法確定學(xué)習(xí)種群和被學(xué)習(xí)種群.抽取在[0，1]均勻分布的隨機(jī)數(shù)，小于 ps時(shí)，Swarm1為被學(xué)習(xí)種群，反之Swarm2將作為被學(xué)習(xí)種群.

2)確定學(xué)習(xí)種群中每個(gè)粒子向被學(xué)習(xí)種群學(xué)習(xí)的概率.在ILPSO中，根據(jù)學(xué)習(xí)種群中單個(gè)粒子適應(yīng)度值的排序來決定學(xué)習(xí)概率的大小.學(xué)習(xí)種群中適應(yīng)度好的粒子向被學(xué)習(xí)種群學(xué)習(xí)的概率相對(duì)較小，以盡量維持目前良好的搜索形態(tài);反之學(xué)習(xí)種群中適應(yīng)度值較差的粒子，學(xué)習(xí)概率較大.依據(jù)經(jīng)驗(yàn)公式(5)確定學(xué)習(xí)種群中粒子i向被學(xué)習(xí)種群的學(xué)習(xí)概率 pci.

式中:orderi表示按粒子i在學(xué)習(xí)種群內(nèi)適應(yīng)度的排序;m表示學(xué)習(xí)種群的規(guī)模.

3)更新每個(gè)種群的速度和位置.被學(xué)習(xí)種群的粒子按照式(1)更新速度;在學(xué)習(xí)種群中，如果產(chǎn)生的隨機(jī)數(shù)小于pci，粒子i同時(shí)向個(gè)體最優(yōu)位置、群體最優(yōu)位置和被學(xué)習(xí)種群的群體最優(yōu)位置學(xué)習(xí)更新速度;反之仍然根據(jù)式(1)更新速度.當(dāng)Swarm1是學(xué)習(xí)種群時(shí)，向Swarm2學(xué)習(xí)的粒子速度按照式(6)更新.而當(dāng)Swarm2是學(xué)習(xí)種群時(shí)，向Swarm1學(xué)習(xí)的粒子速度按照式(7)更新.

式中:rij(i=1，2，j=1，2，3)表示在[0，1]內(nèi)均勻分布的隨機(jī)數(shù).

2.2 變異算子

如果Swarm1和Swarm2的群體最優(yōu)位置的適應(yīng)度值相差較大時(shí)，式(4)會(huì)給算法帶來較大的選擇壓力，不利于全局搜索.基于這樣的考慮，本文采用在任意一個(gè)種群中隨機(jī)選擇一個(gè)粒子在任一維上的速度按式(8)發(fā)生變異:

式中:vmax表示粒子飛行的最大速度，r3和r4表示均勻分布在[0，1]的隨機(jī)數(shù).由于只選擇一個(gè)種群中的一個(gè)粒子一維的速度發(fā)生變異，因此幾乎不會(huì)破壞群體的結(jié)構(gòu).但每一個(gè)種群、每一個(gè)粒子和其每一維速度從統(tǒng)計(jì)意義上來說是以同樣的概率被選擇發(fā)生變異.

2.3 ILPSO 主要步驟

ILPSO的主要步驟如下:

1)置t=0;初始化2個(gè)種群粒子的位置和速度，并設(shè)定相應(yīng)的參數(shù);

2)計(jì)算粒子適應(yīng)度值，確定個(gè)體最優(yōu)位置和群體最優(yōu)位置;

4)確定學(xué)習(xí)種群和被學(xué)習(xí)種群;

5)計(jì)算學(xué)習(xí)種群中每個(gè)粒子向被學(xué)習(xí)種群學(xué)習(xí)的概率;

6)更新2個(gè)種群的粒子速度和位置;

7)執(zhí)行變異算子;

8)t=t+1;計(jì)算粒子適應(yīng)度，更新每個(gè)粒子的個(gè)體最優(yōu)位置和群體最優(yōu)位置;

9)判斷程序終止條件是否滿足，若滿足則算法終止，輸出最優(yōu)解，否則轉(zhuǎn)到3).

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

3.1 測(cè)試函數(shù)

本文選取了11個(gè)常用的測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn).其中基本測(cè)試函數(shù)包括f1、f22個(gè)單峰函數(shù)和f3、f64個(gè)多峰函數(shù)，f7、f8和 f9、f11分別是偏移測(cè)試函數(shù)和旋轉(zhuǎn)測(cè)試函數(shù).基本測(cè)試函數(shù)的局部極值點(diǎn)多沿著平行的坐標(biāo)軸，且全局最優(yōu)位于原點(diǎn)，不能較好地反映現(xiàn)實(shí)中優(yōu)化問題的復(fù)雜性.Suganthan等對(duì)基本測(cè)試函數(shù)進(jìn)行了偏移和旋轉(zhuǎn)[18].f7、f8是將基本測(cè)試函數(shù)f2和f3的全局最優(yōu)點(diǎn)隨機(jī)移動(dòng)到每一維具有不同數(shù)值的新位置，并且加上了一個(gè)偏置值O.本文依據(jù)文獻(xiàn)[18]的方法進(jìn)行偏移.旋轉(zhuǎn)測(cè)試函數(shù)f9～f11是通過將一個(gè)正交矩陣左乘f2、f3和f5而得到的，其各個(gè)變量之間變得都不可分.其中正交矩陣的產(chǎn)生采用Salomon在1996年提出的方法[19].表1給出了每個(gè)函數(shù)的名稱、數(shù)學(xué)表達(dá)式、搜索范圍和最優(yōu)值.

表1 測(cè)試函數(shù)及其參數(shù)設(shè)置Table 1 Benchmark function and their settings

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

將ILPSO 同 SPSO、PSOPC、FDR-PSO 和 HPSOTVAC的性能進(jìn)行比較.為公平起見，各種比較算法的粒子數(shù)量設(shè)置為 60，在 ILPSO中 Swarm1和Swarm2的粒子數(shù)量分別設(shè)置為30.SPSO、PSOPC、FDR-PSO、HPSO-TVAC和ILPSO的詳細(xì)參數(shù)根據(jù)文獻(xiàn)[4、10、17、20]進(jìn)行設(shè)置，具體見表 2，其中 Range表示搜索范圍的大小.式(4)中初始溫度T0和退溫方式根據(jù)文獻(xiàn)[21]提出的如式(9)、(10)確定:

式中:λ稱為退溫速率，本文取λ=0.9.

表2 參數(shù)設(shè)置Table 2 Parameter settings of involved algorithms

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

將ILPSO和其他的4種PSO算法在11個(gè)測(cè)試函數(shù)上分別獨(dú)立運(yùn)行25次，最大迭代次數(shù)為6 000次.比較的5種PSO算法的實(shí)驗(yàn)結(jié)果(平均值和標(biāo)準(zhǔn)差)如表3，其中最好的實(shí)驗(yàn)結(jié)果加粗表示.圖1描述了比較的5種PSO算法求解f1～f3，f5～f10平均最優(yōu)值的變化曲線.

表3 各種算法的測(cè)試結(jié)果比較Table 3 Comparisons of experimental results

對(duì)于f1，ILPSO的求解結(jié)果都優(yōu)于其他4種算法.在對(duì)“香蕉函數(shù)”f2的優(yōu)化中，相較于 SPSO、PSOPC和 FDR-PSO，ILPSO和 HPSO-TVAC在搜索過程中沒有陷入局部最優(yōu).雖然ILPSO實(shí)驗(yàn)結(jié)果的平均值稍差于 HPSO-TVAC，但標(biāo)準(zhǔn)差較小，表明ILPSO具有較好的魯棒性.對(duì)于具有大量局部最優(yōu)點(diǎn)的復(fù)雜多峰函數(shù)f3和f6，ILPSO體現(xiàn)了很好的優(yōu)化效果，在搜索過程中一直沒有陷入局部最優(yōu)，說明了交互學(xué)習(xí)策略能夠擺脫局部最優(yōu)的有效性.比較的各算法在求解函數(shù)f4的性能差別不大，都搜索到比較滿意的結(jié)果.在求解 f5中，SPSO、PSO-FDR和HPSO-TVAC的搜索精度只能達(dá)到 10－2數(shù)量級(jí)，PSOPC的搜索精度為10－3數(shù)量級(jí)，而ILPSO的搜索精度達(dá)到了10－4數(shù)量級(jí)且標(biāo)準(zhǔn)差最小.對(duì)于偏移測(cè)試函數(shù)f7和f8，ILPSO求解結(jié)果的平均值和標(biāo)準(zhǔn)差都明顯好于其他算法.將函數(shù)的坐標(biāo)軸進(jìn)行旋轉(zhuǎn)后，求解的難度將會(huì)提高.ILPSO對(duì)旋轉(zhuǎn)測(cè)試函數(shù)f9～f11的實(shí)驗(yàn)結(jié)果仍表現(xiàn)出了好的搜索精度和魯棒性，表明了其具有很好的適應(yīng)性.綜上分析，ILPSO在對(duì)基本測(cè)試函數(shù)、偏移測(cè)試函數(shù)和旋轉(zhuǎn)測(cè)試函數(shù)的求解中都表現(xiàn)了搜索精度高和魯棒性好的特點(diǎn)，特別對(duì)復(fù)雜的函數(shù)，其優(yōu)秀的搜索性能更加突出.

在ILPSO中，由于交互學(xué)習(xí)策略的作用，每個(gè)粒子群體的多樣性得到維護(hù)，從而提高了全局搜索能力，不容易陷入局部最優(yōu).根據(jù)“沒有免費(fèi)午餐定理”，在維護(hù)粒子群體多樣性的同時(shí)也帶來了收斂速度相對(duì)不夠快的成本.從圖1中可以看出，ILPSO的收斂速度雖然快于SPSO和HPSO-TVAC，但在一些測(cè)試函數(shù)的優(yōu)化上比PSOPC和FDR-PSO的收斂速度稍慢.

圖1 各種算法實(shí)驗(yàn)結(jié)果的平均最優(yōu)值變化Fig.1 The convergence curve of invdved algorithms

4 結(jié)束語

在分析基本PSO算法學(xué)習(xí)策略缺陷的基礎(chǔ)上，啟發(fā)于人類社會(huì)學(xué)習(xí)的特點(diǎn)，本文提出了一種交互學(xué)習(xí)的PSO算法——ILPSO.交互學(xué)習(xí)策略中學(xué)習(xí)種群和被學(xué)習(xí)種群在搜索的過程中能夠相互轉(zhuǎn)換，且改善了粒子學(xué)習(xí)方向“單一性”的缺陷，保證了群體的多樣性，從而提高了算法的全局搜索能力.多個(gè)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果表明ILPSO具有較高的搜索精度和魯棒性，特別在求解復(fù)雜的問題中，體現(xiàn)的優(yōu)化性能更加突出.如何在保證ILPSO搜索精度和魯棒性的同時(shí)，并進(jìn)一步提高收斂速度，以及將ILPSO應(yīng)用到實(shí)際問題的求解中是未來研究的重點(diǎn).

[1]EBERHART R C，KENNEDY J.Particle swarm optimiza-tion[C]//IEEE International Conference on Neural Networks.Perth，Australia，1995:1942-1948.

[2]KENNEDY J，EBERHART R C.Empirical study of particle swarm optimization[C]//Proc of Congress on Evolutionary Computation.Washington，DC，USA，1999:1945-1949.

[3]ANGELINE P J.Evolutionary optimization versus particle swarm optimization and philosophy and performance difference[C]//Proc of 7th Annual Conference on Evolutionary Programming.San Diego，USA，1998:601-610.

[4]SHI Y，EBERHART R C.A modified particle swarm optimizer[C]//IEEE Congress on Evolutionary Computation Anchorage.AK，NJ，1998:69-73.

[5]FAN S K S，LIANG Y C，ZAHARA E.Hybrid simplex search and particle swarm optimization for the global optimization of multimodal functions[J].Engineering Optimization，2004，36:401-418.

[6]SUGANTHAN P N.Particle swarm optimizer with neighborhood operator[C]//Proc of the IEEE Congress of Evolutionary Computation.Washington DC，USA，1999:1958-1961.

[7]楊雪榕，梁加紅，陳凌，等.多鄰域改進(jìn)粒子群算法[J].系統(tǒng)工程與電子技術(shù)，2010，32(11):2453-2458.YANG Xuerong，LIANG Jiahong，CHEN Ling，et al.Multineighbourhood improved particle swarm optimization algorithm[J].Systems Engineering and Electronics，2010，32(11):2453-2558.

[8]楊帆，胡春平，顏學(xué)峰.基于蟻群系統(tǒng)的參數(shù)自適應(yīng)粒子群算法及其應(yīng)用[J].控制理論與應(yīng)用，2010，27(11):1479-1488.YANG Fan，HU Chunping，YAN Xuefeng.Particle swarm optimization algorithm of self-adaptive parameter based on ant system and its application[J].Control Theory ＆ Applications，2010，27(11):1479-1488.

[9]ZHANG W J，XIE X F.DEPSO:hybrid particle swarm with differential evolution operator[C]//Proc of IEEE International Conference on System，Man and Cybernetic.Washington DC，USA，2003:3816-3821.

[10]HE S，WU Q H，WEN J Y，et al.A particle swarm optimizer with passive congregation[J].BioSystems，2004，78:135-147.

[11]秦全德，李榮鈞.基于生物寄生行為的雙種群粒子群算法[J].控制與決策，2011，26(4):548-552.QIN Quande，LI Rongjun.Two-population particle swarm optimization algorithm based bio-parasitic behaviour[J].Control and Decision，2011，26(4):548-552.

[12]LIANG J J，QIN K，SUGANTHAN P N.Comprehensive learning particle swarm optimization for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation，2006，6(3):281-295.

[13]HUANG H，QIN H，HAO Z F，et al.Exampled-based learning swarm optimization for continuous optimization[J].Information Sciences，2011，182(1):125-138.

[14]CLERC M，KENNEDY J.The particle swarm:explosion，stability，and convergence in multi dimensional complex space[J].IEEE Transactions on Evolutionary Computation，2002，6:58-73.

[15]SABAT S L，UDGATA S K.Integrated learning particle swarm optimizer for global optimization[J].Applied Soft Computing，2011，11(1):574-584.

[16]WANG Y，LI B，WEISE T，et al.Self-adaptive learning based particle swarm optimization[J].Information Sciences，2011，182(20):4515-4538.

[17]PERAM T，VEERAMACHANENI K，MOHAN C K.Fitness-distance-ratio based particle swarm optimization[C]//Proc of the Swarm Intelligence Symposium.Indianapolis，USA，2003:174-181.

[18]SUGANTHAN P N，HANSEN N，LIANG J J，et al.Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[R/OL].http://www.ntu.edu.sg/home/EPNSugan.

[19]SALOMON R.Reevaluating genetic algorithm performance under coordinate rotation of benchmark functions[J].Biosystems，1996，39:263-278.

[20]RATNAWEERA A，HALGAMUGE S K，WATSON H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J].IEEE Transactions on Evolutionary Computation，2004，8(3):240-255.

[21]王凌，李令萊，鄭大鐘.非線性系統(tǒng)參數(shù)估計(jì)的一類有效搜索策略[J].自動(dòng)化學(xué)報(bào)，2003，29:953-958.WANG Ling，LI Lingtai，ZHENG Dazhong.A class of effective search strategies for parameter estimation of nonlinear systems[J].Acta Automatica Sinica，2003，29:953-958.