?

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

主要研究信息安全、計算機視覺。

徐仙偉，楊雁瑩，曹霽

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

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

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

0引言

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

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

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

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

1標準粒子群優(yōu)化算法

1.1標準粒子群優(yōu)化算法

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

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

(1)

其更新速度為

(2)

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

(3)

(4)

(5)

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

標準粒子群算法流程如下[7-10]：

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

步驟2：評估，計算每個粒子的適應程度，計算每個粒子的目標函數(shù)。

步驟3：更新并計算每個粒子的pbest。

步驟4：更新并計算整個群體的gbest。

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

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

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

1.2佳粒子、佳粒子距

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

2改進算法

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

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

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

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

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

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

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

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

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

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

3仿真實驗

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

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

(6)

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

(7)

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

表1　DeJong函數(shù)測試結果

表2　Rastrigin函數(shù)測試結果

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

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

4結語

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

圖1　 Rastrigin函數(shù)的對比結果

參考文獻

[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ōu)化算法[J].揚州大學學報:自然科學版,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] 郭文忠,陳國龍.離散粒子群優(yōu)化算法及其應用[M].北京:清華大學出版社,2012:5-17.

[8] 陶乾,阮錦新,常會友,等. PSO算法擾動優(yōu)化策略及其收斂性研究[J].華南師范大學學報:自然科學版,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

文獻標志碼：A

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

中圖分類號：TP301

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

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

收稿日期：2015-04-15

doi:10.3969/j.issn.1009-8984.2015.04.025