孫文新，穆華平

(1.鶴壁職業(yè)技術(shù)學(xué)院電子信息工程學(xué)院，河南鶴壁458030;2.鶴壁職業(yè)技術(shù)學(xué)院 公共基礎(chǔ)教研部，河南 鶴壁458030)

粒子群優(yōu)化算法(particle swarm optimization，PSO)是一種啟發(fā)式全局優(yōu)化算法，由Kennedy和Eberhart[1]于1995年首次提出，其基本思想源于他們早期對鳥類群體行為的規(guī)律性研究.由于粒子群優(yōu)化算法概念簡單、參數(shù)少，且能根據(jù)當(dāng)前的搜索情況動態(tài)調(diào)整搜索策略，已經(jīng)在電力、化工、通訊和醫(yī)學(xué)等[2-4]眾多領(lǐng)域成功應(yīng)用.然而在處理復(fù)雜環(huán)境中大規(guī)模的優(yōu)化問題時(shí)，效果仍不能盡如人意.

研究證明[5]，粒子群算法中粒子間的關(guān)聯(lián)形式能夠直接影響到算法的優(yōu)化性能.楊雪榕等[6]提出了一種多鄰域的粒子群優(yōu)化算法，粒子按照索引號劃分成若干鄰域，每個(gè)鄰域的第1個(gè)粒子接受全局信息，其他粒子只接受鄰域內(nèi)的信息，這樣就增加了鄰域內(nèi)粒子搜索的獨(dú)立性;Matsushita等[7]基于WS、NW小世界網(wǎng)絡(luò)模型和BA無標(biāo)度模型，研究了靜態(tài)群體結(jié)構(gòu)與粒子群算法搜索性能之間的關(guān)系;穆華平等[8]提出一種基于小世界模型動態(tài)演化鄰域的微粒群算法，群體結(jié)構(gòu)從環(huán)形規(guī)則網(wǎng)絡(luò)逐步進(jìn)化為小世界網(wǎng)絡(luò)，前期保證了種群的多樣性，后期加快了收斂速度;彭虎等[9]提出一種動態(tài)鄰域混合粒子群優(yōu)化算法，將隨機(jī)拓?fù)浜婉T諾依曼拓?fù)湎嘟Y(jié)合形成動態(tài)鄰域，使用粒子鄰域全面學(xué)習(xí)搜索策略，提高算法的全局搜索能力.zhang等[10]根據(jù)微粒的度、適應(yīng)值和微粒間的距離構(gòu)建了一個(gè)動態(tài)的無標(biāo)度結(jié)構(gòu)演化過程.

從復(fù)雜網(wǎng)絡(luò)的形成過程中受到啟發(fā)，提出一種基于自適應(yīng)群體結(jié)構(gòu)的粒子群優(yōu)化算法，粒子群體的結(jié)構(gòu)模式以粒子的實(shí)際尋優(yōu)過程和適應(yīng)值為動力來引導(dǎo)形成.

1 粒子群優(yōu)化算法概述

粒子群優(yōu)化算法是一種基于迭代模式的優(yōu)化方法，算法中引入“群體”和“進(jìn)化”的概念，粒子根據(jù)適應(yīng)值大小采用“速度－位置”模型進(jìn)行搜索.群體中的每個(gè)粒子代表解空間中的一個(gè)解，解的優(yōu)劣程度由適應(yīng)函數(shù)決定.粒子群優(yōu)化算法的數(shù)學(xué)描述如下[11]:

假設(shè)有N個(gè)沒有體積和重量的粒子組成的群體在D維搜索空間中以一定的速度飛行，每個(gè)粒子在搜索時(shí)，考慮到了自己搜索到的歷史最好位置和群體內(nèi)(或鄰域內(nèi))其他粒子的歷史最好位置，在此基礎(chǔ)上變化位置，尋找最優(yōu)解.其中第i個(gè)粒子的當(dāng)前位置Xi=[xi1xi2… xid];飛行速度Vi=[vi1vi2… vid];粒子 i 所經(jīng)歷的最好位置Pi=[pi1pi2… pid]，個(gè)體的最好位置Pig=[pig1pig2… pigd]代表鄰域i內(nèi)所有粒子經(jīng)歷過的最好位置.粒子在找到個(gè)體最優(yōu)位置和全局最優(yōu)位置后，根據(jù)式(1)和(2)更新自己的速度和位置:

式中:w稱為慣性權(quán)重，用來調(diào)整粒子的全局和局部搜索能力;c1、c2為學(xué)習(xí)系數(shù)，使粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而向自己的歷史最優(yōu)位置以及群體內(nèi)或領(lǐng)域內(nèi)的全局最優(yōu)靠攏;r1、r2是(0，1)的隨機(jī)數(shù)，使算法具有一定的隨機(jī)性.上述模型為粒子群優(yōu)化算法的局部最優(yōu)模型(Lbest模型)，若式(1)中第3部分的趨向位置是全局最優(yōu)位置時(shí)為全局最優(yōu)模型(Gbest模型).

2 自適應(yīng)群體結(jié)構(gòu)的粒子群優(yōu)化算法

2.1 自適應(yīng)群體結(jié)構(gòu)思想

盡管粒子群優(yōu)化算法在許多優(yōu)化問題上都取得了很好的優(yōu)化性能，但依然存在后期搜索速度慢和“早熟收斂”的問題.這是因?yàn)樗惴ㄔ谒阉骱笃冢姸嗔Ｗ佣紦頂D在歷史最好位置周圍，無法逃離局部最優(yōu)而不斷進(jìn)行重復(fù)性的無效搜索.為了提高算法的空間搜索能力，同時(shí)又保留局部快速收斂的優(yōu)良性能，本文根據(jù)粒子群體在不同階段搜索模式的要求，采用自適應(yīng)群體結(jié)構(gòu)來調(diào)整算法的搜索能力.

觀察現(xiàn)實(shí)中的許多網(wǎng)絡(luò)，發(fā)現(xiàn)大多數(shù)網(wǎng)絡(luò)的形成過程往往是從最初的孤立節(jié)點(diǎn)開始，由于某種稱為“擇優(yōu)連接”的動力學(xué)原因而關(guān)聯(lián)在一起，最終形成了復(fù)雜網(wǎng)絡(luò).結(jié)合粒子群優(yōu)化算法的搜索特性，考慮將復(fù)雜網(wǎng)絡(luò)形成過程中凸顯的這種現(xiàn)象移植到粒子群優(yōu)化算法中.為避免早熟收斂，將多樣性函數(shù)做簡單改進(jìn)[8]，用鄰域內(nèi)最優(yōu)位置代替群體平均位置，具體定義如式(3):

式中:|S|為鄰域內(nèi)粒子的個(gè)數(shù)，|L|為搜索空間的最長對角線的長度，N為問題的維數(shù)，pij為第i個(gè)粒子的第j維分量，pgj為鄰域內(nèi)的最優(yōu)位置的第j維分量.

算法首先將粒子群體初始化為具有少量連接的隨機(jī)網(wǎng)絡(luò)，每個(gè)粒子都帶有一個(gè)搜索標(biāo)志flag，并且初始化狀態(tài) flag=1.若當(dāng)前搜索優(yōu)于前一次搜索，表明本次搜索成功，則flag=l，否則設(shè)置flag=0，此時(shí)檢測該粒子鄰域的群體多樣性，如果粒子過于集中在pgj附近，導(dǎo)致多樣性過低，即diversity(Si)＜dLow時(shí)，在種群中隨機(jī)選擇該鄰域以外的其他粒子建立連接，否則原有連接保持不動.

這樣，在算法初期，群體結(jié)構(gòu)松散，有利于保持群體的多樣性，可以獲取盡可能多的候選解;隨著新連接的不斷加入，由于受到最優(yōu)位置的引導(dǎo)，群體中部分粒子以接近Gbest模型的尋優(yōu)方式進(jìn)行搜索，多數(shù)粒子以接近Lbest模型的尋優(yōu)方式進(jìn)行搜索，在全局搜索和局部搜索之間獲得了很好的折衷;到了算法后期，算法基本圍繞在全局最優(yōu)附近搜索，此時(shí)群體連接更加密集，形成高連通度的群體結(jié)構(gòu)，有利于粒子對最優(yōu)解所在的空間內(nèi)進(jìn)行深度的細(xì)致搜索，進(jìn)而保證算法以較快的速度搜索到全局最優(yōu)位置.

2.2 慣性權(quán)重的調(diào)整

在粒子群優(yōu)化算法中，搜索陷入局部極值，往往表現(xiàn)為算法重復(fù)進(jìn)行無效的搜索，而粒子的位置幾乎靜止不變.為了充分發(fā)揮自適應(yīng)群體結(jié)構(gòu)的效能，本文根據(jù)適應(yīng)函數(shù)值的不同采用不同的慣性權(quán)重，以求全局最小值為例，群體中的粒子按適應(yīng)值fi的變化情況分為以下3種情況:

1)群體中滿足fi＜f'arg的粒子已經(jīng)比較接近全局最優(yōu)，此時(shí)應(yīng)賦予較小的慣性權(quán)重，以促進(jìn)快速收斂于全局最優(yōu).因此將此集合中的粒子的慣性權(quán)重調(diào)整為

取ωmin=0.5，由式(4)可以看出，粒子的適應(yīng)值越好，其對應(yīng)的慣性權(quán)重就越小，進(jìn)而加強(qiáng)了局部尋優(yōu)的能力.

2)如果粒子滿足f'arg＜fi＜farg，則說明這些粒子具有較好的局部和全局的尋優(yōu)能力，此時(shí)應(yīng)保證在前期粒子進(jìn)行“開發(fā)”性搜索，獲得較多候選解，后期進(jìn)行“勘探”性搜索，探索出全局最優(yōu).因此考慮這部分粒子采用經(jīng)典的慣性權(quán)重線性遞減的調(diào)整方法.

3)對于群體中較差的粒子，即fi＞farg時(shí)，借鑒吳浩揚(yáng)等[12]提出的變異方法來調(diào)整慣性權(quán)重:

當(dāng)群體搜索到的最優(yōu)位置長時(shí)間未發(fā)生變化時(shí)，群體根據(jù)粒子的分布特點(diǎn)來調(diào)整慣性權(quán)重.若粒子分布較為分散，則Δ取較大的值來降低粒子的慣性權(quán)重，加強(qiáng)局部尋優(yōu)，使群體趨于收斂;若粒子分布較為聚集，算法陷入局部最優(yōu)，則Δ取較小的值增加粒子的慣性權(quán)重，促使粒子有效地跳出局部最優(yōu).其中參數(shù)k主要用來調(diào)整慣性權(quán)重的上限，文中取 k=1.5.

2.3 算法流程

根據(jù)以上分析，基于 SPS-PSO(particle swarm optimization based on self-adaptive population structure，SPS-PSO)的基本步驟為:先初始化種群;設(shè)置初始化的狀態(tài)標(biāo)志flag=1;計(jì)算每個(gè)粒子的適應(yīng)值，并且評估個(gè)體的歷史最好位置和全局最好位置;果當(dāng)前位置優(yōu)于前一次搜索，則flag=l，否則設(shè)置flag=0;若連續(xù)t次flag的值始終為0，此時(shí)檢測該粒子鄰域的群體多樣性，與最優(yōu)粒子建立新的連接，并依據(jù)適應(yīng)值重新計(jì)算ω的值，然后更新粒子的速度和位置，進(jìn)行下一步的搜索.

SPS-PSO算法的流程圖如圖1.

圖1 SPS-PSO算法流程Fig.1 Flow chart of SPS-PSO algorithm

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

3.1 測試函數(shù)和參數(shù)設(shè)置

為了測試新算法對復(fù)雜問題尋優(yōu)的有效性，本文選取了3個(gè)Benchmark測試函數(shù)進(jìn)行仿真實(shí)驗(yàn).實(shí)驗(yàn)環(huán)境為Intel CPU 2.1 GB，Windows XP操作系統(tǒng)、1.0 GB 內(nèi)存，Visual C++6.0 環(huán)境下進(jìn)行編程.為確保實(shí)驗(yàn)結(jié)果的可信度，每個(gè)算法運(yùn)行20次實(shí)驗(yàn)，初始化種群個(gè)數(shù)為100，問題維數(shù)30維，最大進(jìn)化代數(shù)為1 000.算法中，加速因子 c1、c2均取 1.5，ω的初始值取 0.9，dLow取5 ×10－6.

1)Sphere函數(shù).

Sphere函數(shù)為可分離的單峰函數(shù)，用于測試算法的收斂精度，函數(shù)在xi=0處到達(dá)全局極小值0.

2)Rastrigrin函數(shù).

Rastrigrin函數(shù)是不可分離的多峰函數(shù)，較難優(yōu)化，全局最小值在變量為0時(shí)到達(dá)，該函數(shù)有10n個(gè)局部極小點(diǎn).

3)Griwank函數(shù).

Griwank函數(shù)也是不可分離的多峰優(yōu)化函數(shù)，函數(shù)在xi=0時(shí)到達(dá)全局最小值，該函數(shù)有2n個(gè)局部極小值.

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

為了測試新算法的優(yōu)化性能，本文將標(biāo)準(zhǔn)PSO算法、DSWN-PSO(particle swarm optimization with dynamic evolutionary neighbourhood of small-world model)[8]和 DNH-PSO(dynamic neighborhood hybrid-PSO)[9]進(jìn)行對比分析.圖2顯示了Sphere函數(shù)的優(yōu)化對比結(jié)果.通過比較可以看出，SPS-PSO算法始終保持較快的收斂速度，并且最終獲得了比DSWNPSO算法和DNH-PSO算法更好的優(yōu)化性能.

圖2 30維Sphere函數(shù)優(yōu)化對比Fig.2 Comparison of optimizing on 30-D Sphere

從圖3中可以看出，對于Rastrgin函數(shù)來說，SPS-PSO算法能在較短的時(shí)間內(nèi)獲得明顯的優(yōu)化效果，并且仍然呈向全局最優(yōu)的趨勢.算法在400～600代時(shí)，有一個(gè)相對平坦的優(yōu)化過程，這說明算法在此期間停留在局部最優(yōu)位置上徘徊不前，但最終因?yàn)榫W(wǎng)絡(luò)形成過程中根據(jù)適應(yīng)值擇優(yōu)連接的過程，使得算法能及時(shí)從局部最優(yōu)位置跳出來，突破了局部最優(yōu)的束縛，繼續(xù)向全局最優(yōu)位置靠近.

圖3 30維Rastrgin函數(shù)優(yōu)化對比Fig.3 Comparison of optimizing on 30-D Rastrgin

Griewank函數(shù)是一個(gè)多峰、存在許多局部極小值且自變量之間互相影響的、典型的非線性多模態(tài)函數(shù)，極易陷入局部最優(yōu)，從圖4中可以看出，SPSPSO算法能以較快的速度收斂于全局最優(yōu)，并且在實(shí)驗(yàn)中發(fā)現(xiàn)其收斂成功率為100%.其原因在于新連接的加入能適應(yīng)算法的收斂狀態(tài)，使得算法具有較強(qiáng)的抗早熟能力，能夠突破中期短暫的停滯階段，獲得正確的搜索方向.

圖4 30維Griewank函數(shù)優(yōu)化對比Fig.4 Comparison of optimizing on 30-D Griewank

從實(shí)驗(yàn)中發(fā)現(xiàn)，SPS-PSO算法的執(zhí)行效率要高于DSWN-PSO算法，這是因?yàn)镾PS-PSO算法中，搜索前期的粒子在空間中分布較為均勻，因此通過flag參數(shù)作為閾值參數(shù)來檢測粒子的搜索狀態(tài)，避免了前期不必要的多樣性檢測，提高了算法的效率，中后期多樣性函數(shù)的檢測一定程度上避免了算法的局部收斂，促使算法進(jìn)一步向全局最優(yōu)靠近.

4 結(jié)束語

本文將復(fù)雜網(wǎng)絡(luò)形成過程中的動力學(xué)機(jī)制引入粒子群優(yōu)化算法中，并根據(jù)搜索狀態(tài)調(diào)整慣性權(quán)重以適應(yīng)搜索要求，提出了一種自適應(yīng)群體結(jié)構(gòu)的粒子群優(yōu)化算法.隨著算法的搜索，利用多樣性函數(shù)檢測鄰域多樣性，使群體結(jié)構(gòu)從低連通度的分散結(jié)構(gòu)進(jìn)化為連通度較高的復(fù)雜網(wǎng)絡(luò)，由于其進(jìn)化過程符合粒子群優(yōu)化算法對信息共享模式的要求，因此極大地提高了算法的性能.下一步工作將通過對最終形成的群體結(jié)構(gòu)的特性做詳細(xì)研究，以探索更符合粒子間信息交流的群體結(jié)構(gòu).

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

[2]POLI R.An analysis of publications on particle swarm optimization applications[R].London:Department of Computer Science，University of Essex，2007.

[3]POLI R，KENNEDY J，BLACKWELL T.Particle swarm optimization:an overview[J].Swarm Intelligence，2007，1(1):33-57.

[4]KENNEDY J，MENDES R.Population structure and particle swarm performance[C]//Proceedings of the IEEE Congress on Computation Intelligence.Honolulu，USA，2002:1671-1675.

[5]錢曉山.一種改進(jìn)的混沌粒子群優(yōu)化混合算法[J].應(yīng)用科技，2012，39(1):5-8.QIAN Xiaoshan.A hybrid algorithm of the improved chaotic particle swarm optimization[J].Applied Science and Technology，2012，39(1):5-8.

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

[7]MATSUSHITA H，NISHIO Y.Network-structured particle swarm optimizer with various topology and its behaviors[J].Lecture Notes in Computer Science，2009，5629:163-171.

[8]穆華平，曾建潮.基于小世界模型動態(tài)演化鄰域的微粒群算法[J].系統(tǒng)仿真學(xué)報(bào)，2008，20(15):3940-3943.MU Huaping，ZENG Jianchao.Particle swarm optimization with dynamic evolutionary neighbourhood of small-world model[J].Journal of System Simulation，2008，20(15):3940-3943.

[9]彭虎，張海，鄧長壽.動態(tài)鄰域混合粒子群優(yōu)化算法[J].計(jì)算機(jī)工程，2011，37(14):211-213.PENG Hu， ZHANG Hai， DENG Changshou.Dynamic neighborhood hybrid particle swarm optimization algorithm[J].Computer Engineering，2011，37(14):211-213.

[10]ZHANG Chengong，YI Zhang.Scale-free fully informed particle swarm optimization algorithm[J].Information Sciences，2011，181(20):4550-4568.

[11]曾建潮，介婧，崔志華.微粒群算法[M].北京:科學(xué)出版社，2004:5-10.

[12]吳浩揚(yáng)，朱長純，常炳國，等.基于種群過早收斂程度定量分析的改進(jìn)自適應(yīng)遺傳算法[J].西安交通大學(xué)學(xué)報(bào)，1999，33(11):27-30.WU Haoyang，ZHU Changchun，CHANG Bingguo，et al.Adaptive genetic algorithm to improve group premature convergence[J].Journal of Xi’an Jiaotong University，1999，33(11):27-30.