?

一種改進(jìn)的粒子群優(yōu)化算法

主要研究信息安全、計(jì)算機(jī)視覺(jué)。

徐仙偉，楊雁瑩，曹霽

(南京森林警察學(xué)院信息技術(shù)系，南京 210023)

摘要：標(biāo)準(zhǔn)粒子群算法能夠解決各類(lèi)優(yōu)化問(wèn)題，得到了廣泛的應(yīng)用，也引起很多研究人員的關(guān)注。為了提高全局搜索能力，使其不易陷入局部最優(yōu)，提出了一種新的優(yōu)化策略。首先，采用了佳粒子的概念，每次更新時(shí)，對(duì)所有粒子進(jìn)行排序；然后，在此基礎(chǔ)上，對(duì)所有的粒子進(jìn)行評(píng)估，衡量每個(gè)粒子是否可以保留；最后，刪除那些不符合保留要求的粒子，同時(shí)生成相應(yīng)數(shù)目的新的粒子，以保持種群的規(guī)模，從而提高種群的整體適應(yīng)性能。實(shí)驗(yàn)數(shù)據(jù)表明，新算法提高了算法的性能，具有更好的全局性能。

關(guān)鍵詞：粒子群算法；優(yōu)化；淘汰

0引言

1995年，受到自然界鳥(niǎo)群運(yùn)動(dòng)模型的啟發(fā)，Kennedy和Eberhart[1]提出了一種基于鳥(niǎo)群運(yùn)動(dòng)的優(yōu)化搜索算法——粒子群優(yōu)化算法(Particle Swarm Optimization， PSO)。這種算法的思路是把所求的解在問(wèn)題空間中可能的位置，視為鳥(niǎo)群在運(yùn)動(dòng)模型中的棲息地，然后通過(guò)個(gè)體之間的信息傳遞，逐步把求解過(guò)程中較好的解出現(xiàn)的可能性提高，并且引導(dǎo)群體中所有的粒子都向著可能的解的位置不斷靠攏聚集[1-4]。

經(jīng)典PSO算法是一種基于智能群體方法的計(jì)算技術(shù)，優(yōu)勢(shì)在于簡(jiǎn)單而又容易實(shí)現(xiàn)，同時(shí)又有深刻的生物背景，更進(jìn)一步而言，也包括其沒(méi)有許多參數(shù)需要調(diào)整，具有較高的使用價(jià)值。大量的研究表明經(jīng)典PSO算法對(duì)于單目標(biāo)優(yōu)化問(wèn)題而言，與其他演化算法相比較，其收斂速度更快，需要設(shè)置的參數(shù)更少，數(shù)學(xué)描述更加簡(jiǎn)單[4]。因此，經(jīng)典PSO算法得到了很多學(xué)者的廣泛研究，在很多領(lǐng)域得到了應(yīng)用，產(chǎn)生了很多研究成果。經(jīng)過(guò)反復(fù)的討論和研究，證明PSO算法能夠適用于各類(lèi)優(yōu)化的問(wèn)題，具備明顯的性能優(yōu)勢(shì)。

但是，在PSO算法被廣泛應(yīng)用于各類(lèi)科學(xué)問(wèn)題求解的同時(shí)，其缺陷也逐漸顯現(xiàn)[5-6]。為此針對(duì)不同的應(yīng)用領(lǐng)域，當(dāng)前研究人員提出了各種改進(jìn)措施，主要包括基于慣性權(quán)值的改進(jìn)方法、基于加速因子的改進(jìn)方法、基于鄰近群拓?fù)涞母倪M(jìn)方法、基于種群規(guī)模的改進(jìn)方法、混合粒子群優(yōu)化算法的改進(jìn)方法等[7]。盡管每種改進(jìn)方法從不同角度對(duì)PSO算法進(jìn)行了優(yōu)化，取得了一定的效果，但仍然做不到面面俱到?？傮w來(lái)講，目前PSO算法中最突出的問(wèn)題有：1)算法易陷入局部極值，造成過(guò)早收斂；2)在多維復(fù)雜空間的進(jìn)化過(guò)程中有一定的局限性，使得解的精確度難以穩(wěn)定提高等[8]。

本文為了進(jìn)一步提高經(jīng)典PSO算法的全局搜索能力，使其不易陷入局部最優(yōu)，提出了一種新的優(yōu)化策略。其主要思想為：首先，采用了佳粒子的概念，每次更新時(shí)，對(duì)所有粒子進(jìn)行排序；然后，在此基礎(chǔ)上，對(duì)所有的粒子進(jìn)行評(píng)估，衡量每個(gè)粒子是否可以保留；最后，刪除那些不符合保留要求的粒子，同時(shí)生成相應(yīng)數(shù)目的的新的粒子，以保持種群的規(guī)模，從而提高種群的整體適應(yīng)性能。并通過(guò)實(shí)驗(yàn)仿真得到的實(shí)驗(yàn)數(shù)據(jù)表明，新算法提高了算法的性能，具有更好的全局性能。

1標(biāo)準(zhǔn)粒子群優(yōu)化算法

1.1標(biāo)準(zhǔn)粒子群優(yōu)化算法

PSO算法數(shù)學(xué)模型如下：

設(shè)種群的規(guī)模為M，決策空間的維度為n，我們表示編號(hào)為i的粒子，在t時(shí)刻的坐標(biāo)位置為

(1)

其更新速度為

(2)

表示第i的粒子在t時(shí)刻的第j(j=1,2,…,n)維子空間中的位移速度、位置為：

(3)

(4)

(5)

其中，ω是慣性權(quán)值。c1、c22個(gè)加速因子是在0到1之間的2個(gè)隨機(jī)數(shù)，正常情況下會(huì)使用一個(gè)常量vmax來(lái)限制它們的最大速度。gj是全局的極值gbest，是整個(gè)群體中的歷史最優(yōu)位置。同時(shí)，gj表示局部粒子群的歷史最優(yōu)位置時(shí)改為lj，表示局部極值lbest。而使用gbest還是lbest是由算法的鄰近拓?fù)浣Y(jié)構(gòu)決定。pij是gbest，即為粒子當(dāng)前最優(yōu)位置[7]。

標(biāo)準(zhǔn)粒子群算法流程如下[7-10]：

步驟1：初始化，設(shè)置規(guī)模種群，隨機(jī)設(shè)置粒子的初始位置、初始速度等參數(shù)。

步驟2：評(píng)估，計(jì)算每個(gè)粒子的適應(yīng)程度，計(jì)算每個(gè)粒子的目標(biāo)函數(shù)。

步驟3：更新并計(jì)算每個(gè)粒子的pbest。

步驟4：更新并計(jì)算整個(gè)群體的gbest。

步驟5：采用式(3)～(5)，計(jì)算和更新所有粒子的位置、速度參數(shù)。

步驟6：檢查終止條件。如果如下條件之一：1)超過(guò)最大迭代次數(shù)預(yù)設(shè)閾值；2)已經(jīng)獲得預(yù)設(shè)的適應(yīng)度范圍；3)最優(yōu)解的變化已經(jīng)停滯，那么終止迭代，執(zhí)行步驟7，否則，返回步驟2。

步驟7：結(jié)束算法，輸出最優(yōu)的位置。

1.2佳粒子、佳粒子距

定義如下：佳粒子[7]的定義是新粒子群中的適應(yīng)度最大的、也是位置為第一個(gè)的粒子。佳粒子距[7]的定義是第i個(gè)粒子在新粒子集中的位置，記為di。

2改進(jìn)算法

為了防止粒子群算法陷入局部最優(yōu)、并提高速度，利用佳粒子距，改進(jìn)算法設(shè)計(jì)如下：

步驟2：評(píng)估每個(gè)粒子在連續(xù)kt次中的表現(xiàn)。如果出現(xiàn)佳粒子距在kt更新中連續(xù)為后t%，即淘汰。

民族武術(shù)社與通背拳研究會(huì)由于社團(tuán)性質(zhì)的根本區(qū)別，傳承空間也截然不同.民族武術(shù)社的生源大多來(lái)自于牛街及附近地區(qū)，學(xué)校及社區(qū)等地合作范圍有限，傳承空間相對(duì)較小.而通背拳研究會(huì)是由通背拳各個(gè)派系傳承人組成，教學(xué)范圍遍布北京市多數(shù)地區(qū)，不斷發(fā)展各個(gè)派系的通背拳.因此，與民族武術(shù)社相比,通背拳研究會(huì)的傳承空間更加廣泛.通過(guò)交談，在詢問(wèn)張斌教學(xué)地點(diǎn)時(shí)，他無(wú)奈地說(shuō)道：“怎么說(shuō)呢，就在馬路邊，因?yàn)檫@個(gè)是事實(shí)，沒(méi)有空間.你要想在商場(chǎng)開(kāi)，一年都得上萬(wàn)，你弄一場(chǎng)地，我哪弄的起啊.”

步驟3：更新，剔除所有不達(dá)標(biāo)的粒子，隨機(jī)生成相同數(shù)目的新的粒子，繼續(xù)運(yùn)行，直到整體得到最優(yōu)解。

優(yōu)化過(guò)后的PSO算法為：

步驟1：初始化。設(shè)置代數(shù)t=0，設(shè)置所有群粒子即種群的初始位置X及其速度V，初始化每個(gè)粒子的個(gè)體歷史最優(yōu)值位置令pbest=x和全局最優(yōu)值位置。

步驟2：在保證粒子在搜索空間內(nèi)飛行的條件下，更新每個(gè)粒子的速度和位置，并且產(chǎn)生新的種群和個(gè)體歷史最優(yōu)值位置。

步驟3：根據(jù)新的非支配解和已有的外部種群維護(hù)外部種群，防止溢出，同時(shí)為每個(gè)粒子選取全局最優(yōu)值位置。

步驟6：結(jié)束算法，輸出最優(yōu)的位置。

同時(shí)為了防止一些粒子由于本身環(huán)境的影響，使其一直保留在整個(gè)粒子群中的變化滯后位置，即防止這些粒子陷入到局部最優(yōu)，因此進(jìn)行了種群意義上的淘汰工作，并更新同樣數(shù)目的新的粒子。從本質(zhì)上來(lái)講，這是一種結(jié)合了慣性權(quán)值和種群規(guī)模的改進(jìn)方法。

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

本文采用了與文獻(xiàn)[11]中一樣的測(cè)試函數(shù)，即DeJong和Rastrigin函數(shù)，其中DeJong函數(shù)是一個(gè)連續(xù)的、單峰分布的函數(shù)，Rastrigin是一個(gè)非線性、多峰值分布的函數(shù)。從設(shè)計(jì)思路上本算法應(yīng)具有全局最優(yōu)的特點(diǎn)，應(yīng)在多峰值的效果上有一定優(yōu)勢(shì)。

本文采用的DeJong函數(shù)如下：

(6)

采用的Rastrigin函數(shù)[12-13]如下：

(7)

在對(duì)該2項(xiàng)函數(shù)在不同種群大小、不同維數(shù)、不同最大代數(shù)、不同優(yōu)化算法的情況下，進(jìn)行了10次計(jì)算后，對(duì)結(jié)果進(jìn)行了平均，測(cè)試結(jié)果見(jiàn)表1～2。

表1　DeJong函數(shù)測(cè)試結(jié)果

表2　Rastrigin函數(shù)測(cè)試結(jié)果

分析表1～2可見(jiàn)，本算法在單峰值的DeJong函數(shù)上優(yōu)勢(shì)并不明顯，而在多峰值的Rastrigin 函數(shù)上具有一定的優(yōu)勢(shì)，且當(dāng)種群規(guī)模相對(duì)較小時(shí)，效果比較突出。因此，該算法比較適用于多峰的問(wèn)題，具有不會(huì)陷入到局部最優(yōu)的特點(diǎn)。

另外，根據(jù)以上分析，統(tǒng)計(jì)了Rastrigin函數(shù)10次最優(yōu)值迭代的速度結(jié)果，虛線為經(jīng)典算法的計(jì)算效果，實(shí)線為本文所提出的算法效果。由圖1可見(jiàn)，本文提出的算法在速度上更快。

4結(jié)語(yǔ)

本文對(duì)經(jīng)典的PSO算法提出了一種新的優(yōu)化策略。采用了佳粒子的概念，每次更新時(shí)，對(duì)所有粒子進(jìn)行排序，在此基礎(chǔ)上，對(duì)所有的粒子進(jìn)行評(píng)估， 衡量每個(gè)粒子是否可以保留， 刪除那些不符合保留要求的粒子，同時(shí)生成相應(yīng)數(shù)目的新的粒子，以保持種群的規(guī)模，從而提高種群的整體適應(yīng)性能。這種方法使得本算法在多峰值問(wèn)題上具有較好的優(yōu)勢(shì)。實(shí)驗(yàn)數(shù)據(jù)表明，新算法提高了算法的性能，具有更好的全局性能，不易陷入局部最優(yōu)。

圖1　 Rastrigin函數(shù)的對(duì)比結(jié)果

參考文獻(xiàn)

[1] Kennedy J, Eberhart R. Particle swarm optimization[M]//Claude Sammut,Geoffrey I Webb.Encyclopedia of Machine Learning.New Yok: Springer US,2010:760-766.

[2] Pedersen M E H, Chipperfield A J. Simplifying particle swarm optimization[J]. Applied Soft Computing,2010,10(2): 618-628.

[3] 王姝,陳崚.基于正交試驗(yàn)設(shè)計(jì)的粒子群優(yōu)化算法[J].揚(yáng)州大學(xué)學(xué)報(bào):自然科學(xué)版,2012,13(2):58-60.

[4] Sharma T,Srivastava L. Evolutionary computing techniques for optimal reactive power dispatch: an overview and key issues[C]// Communication Systems and Network Technologies (CSNT), 2014 Fourth International Conference on .Bhopal:IEEE,2014: 7-9.

[5] Khan S A,Nadeem A.Automated test data generation for coupling based integration testing of object oriented programs using particle swarm optimization [C]//Information Technology:New Generations (ITNG),2013 Tenth Internation Conference.Las Vegas,NV:IEEE,2013:369-374.

[6] Gaing Z L, Lin C H, Tsai M H,et al. Rigorous design and optimization of brushless pm motor using response surface methodology with quantum-behaved pso operator[J].IEEE Transactionss on Magnetics, 2014,50(1):1-4.

[7] 郭文忠,陳國(guó)龍.離散粒子群優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社,2012:5-17.

[8] 陶乾,阮錦新,常會(huì)友,等. PSO算法擾動(dòng)優(yōu)化策略及其收斂性研究[J].華南師范大學(xué)學(xué)報(bào):自然科學(xué)版,2014,46(4):26-30.

[9] Kulkarni R V, Venayagamoorthy G K. Particle swarm optimization in wireless-sensor networks: A brief survey[J]. Systems, Ma, and Cybernetics, Part C: Applications and Reviews, 2011,41(2): 262-267.

[10] Moradi M H, Abedini M. A combination of genetic algorithm and particle swarm optimization for optimal DG location and sizing in distribution systems[J]. International Journal of Electrical Power & Energy Systems, 2012, 34(1): 66-74.

[11] Lovbjerg M, Rasmussen T K, Krink T. Hybrid particle swarm optimiser with breeding and subpopulations[C]//Proceedings of the Genetic and Evolutionary Computation Conference. USA :San Francisco, 2001: 469-476.

[12] Moslehi G, Mahnam M. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search[J]. International Journal of Production Economics,2011, 129(1): 14-22.

[13] Pandey S,Wu L, Guru S M, et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]//Advanced Information Networking and Applications (AINA),2010,24th IEEE International Conference on. Perth,WA:IEEE,2010: 400-407.

An improved particle swarm optimization algorithm

XU Xian-wei, et al.

(DepartmentofInformationTechnology,NanjingForestPoliceCollege,Nanjing210023,China)

Abstract：Standard Particle Swarm Optimization (PSO) algorithm can solve problems of all kinds of optimizations, has been widely used in many fields，and has been caused attention from a lot of researchers. To make Standard PSO have better ability of global search， avoid local optimum，this paper proposes a new optimal strategy. Firstly，the concept of Good Particle has been adopted. In each update，all particles have been sorted; then, on this basis all particles have been evaluated to identify the fitness; lastly，we those particles unsuitable to retain are eliminate. At the same time, the same number new particles are generated randomly to keep the scale of the population to improve the whole fit capability of the population. Experiments results show that this new algorithm has improved the property of the algorithm, and with better generalization performance.

Key words：particle swarm optimization; optimization algorithm; elimination

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-8984(2015)04-0100-04

中圖分類(lèi)號(hào)：TP301

作者簡(jiǎn)介：徐仙偉 (1977-)，女(漢)，江蘇，講師

基金項(xiàng)目：中央高校基本科研項(xiàng)目(LGYB201410)

收稿日期：2015-04-15

doi:10.3969/j.issn.1009-8984.2015.04.025