協(xié)同進化策略的粒子群優(yōu)化算法

楊蕾 梁永全

摘 ?要： 為了進一步提高粒子群優(yōu)化算法的尋優(yōu)精度，并改善收斂速度慢的問題，本文基于傳統(tǒng)的粒子群優(yōu)化算法，借鑒協(xié)同進化的思想和共生機制，提出了將協(xié)同進化算法和粒子群算法相結合的算法模型（CEA-PSO）。群體內(nèi)部采用精英保留策略保留精英個體，將個體的進化和群體之間發(fā)生信息交換，達到優(yōu)勢互補的效果。實驗結果表明，協(xié)同進化策略的粒子群優(yōu)化算法精度更高，優(yōu)化性能更佳。

關鍵詞： 協(xié)同進化;粒子群優(yōu)化算法;精英保留策略

中圖分類號： TP301.6 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.08.036

本文著錄格式：楊蕾，梁永全. 協(xié)同進化策略的粒子群優(yōu)化算法[J]. 軟件，2019，40（8）：152155

【Abstract】： In order to further improve the optimization precision of the particle swarm optimization algorithm and improve the convergence speed. Based on the traditional particle swarm optimization algorithm， this paper proposes an algorithm model （CEA-PSO） combining co-evolution algorithm and particle swarm optimization algorithm with reference to the idea of co-evolution and symbiosis. Elite retention strategies are used within the group to retain elite individuals， information exchange occurs between the evolution of individuals and groups to achieve complementary effects. The experimental results show that the particle swarm optimization algorithm base on co-evolution strategy has higher precision and better optimization performance.

【Key words】： Co-evolution; Particle swarm optimization; Elite retention strategy

0 ?引言

隨著社會經(jīng)濟和信息技術的快速發(fā)展，各個領域中的問題都可以通過將待決解決問題轉化為優(yōu)化問題來處理，目前存在的優(yōu)化算法大致可以分為兩類：傳統(tǒng)優(yōu)化算法和智能優(yōu)化算法。傳統(tǒng)優(yōu)化算法一般是針對結構化的問題，有較為明確的問題和條件描述，如線性規(guī)劃，二次規(guī)劃，整數(shù)規(guī)劃，混合規(guī)劃，帶約束和不帶約束條件等，即有清晰的結構信息;現(xiàn)代智能優(yōu)化算法主要包括差分進化算法 （Differential evolutionary， DE）[1]、粒子群算法（Particle swarm optimization， PSO）[2，3]、遺傳算法（Genetic algorithm， GA）[4]、蟻群算法（Ant colony optimization， ACO）[5]、人工蜂群算法（Arti?cial bee colony， ABC）[6]等。協(xié)同進化算法[7]（Co-Evolutionary Algorithm， CEA）是研宄者在協(xié)同進化理論基礎上提出的一類新算法。這類算法強調(diào)了在進化過程中種群內(nèi)部的相互影響和種群之間的相互協(xié)調(diào)。這些年來，許多專家學者提出了多種多樣的CEA，較主流的劃分[8]：競爭型協(xié)同進化算法（Competitive Co-Evolutionary Algorithm， Com-CEA）[9]和合作型協(xié)同進化算法（Cooperative Co-Evolutionary Algorithm， Coo-CEA）[10]兩類。

粒子群優(yōu)化算法基于迭代策略，粒子在解空間中對最優(yōu)解進行搜索，計算簡單，已經(jīng)廣泛應用在工程優(yōu)化、神經(jīng)網(wǎng)絡訓練、圖像處理等領域[11-13]。但是在尋優(yōu)精度和收斂速度上有待提高，為解決上述問題，專家學者們進行了各種實驗研究。Asmara 等[14]法的基提出了一種快速的粒子群協(xié)同進化優(yōu)化算法，提高了算法的收斂速度。Zhang等[15]提出一種多粒子協(xié)同進化算法解決多目標優(yōu)化問題。尋優(yōu)精度和收斂有了很大提升，但還是有改進空間。

針對這兩個問題，本文在粒子群算法的基礎上，借鑒合作型協(xié)同進化的思想和共生機制，提出了將協(xié)同進化算法和粒子群算法相結合的算法模型。用實驗結果證明本文算法能改善基本PSO算法中收斂速度慢的問題。

1 ?概述

1.1 ?協(xié)同進化算法

在協(xié)同進化理論中，協(xié)同模型的主要思想是直接將群體中的個體劃分為若干子群體，每一子群體代表解空間中的一個子區(qū)域（子空間），其中的每一個體均代表問題的一個解。所有子群體并行展開局部搜索，所搜索到的優(yōu)良個體將在不同子群體間進行遷移，作為共享信息指導進化的進行，從而有效提高算法的全局收斂效率。

在傳統(tǒng)進化算法中[16-18]，個體的適應度由個體的染色體決定，是一種絕對適應度，沒有考慮到個體之間的協(xié)同影響以及種群之間的復雜關系;而在協(xié)同進化算法中，考慮了種群內(nèi)部中個體之間的相互影響以及種群之間在進化過程中的相互協(xié)調(diào)，個體的適應度由個體與周圍個體發(fā)生協(xié)同關系時的表現(xiàn)決定，是一種相對適應度。協(xié)同進化算法具有更的自適應性，能夠克服傳統(tǒng)的進化算法中常見的早熟收斂等現(xiàn)象，具有廣闊的應用前景。合作型協(xié)同進化流程圖如圖1所示。

1.2 ?粒子群優(yōu)化算法

PSO算法通過種群中個體的相互協(xié)作搜索尋優(yōu)空間，確定最優(yōu)目標，實現(xiàn)問題優(yōu)化。PSO算法中，粒子群體包含的任意無質(zhì)量粒子 的運動狀態(tài)由位置向量 和速度向量 ? 表示。其中，D表示決策變量的個數(shù); ，N是種群的粒子個數(shù)。 搜索時，根據(jù)更新粒子的速度和位置。

其中：k表示粒子的搜索迭代次數(shù); 表示搜索的慣性權重系數(shù); ，表示學習因子; 和 是均勻分布在區(qū)間[0，1]內(nèi)的隨機數(shù); 是粒子 的個體最優(yōu)解，稱為個體極值; 是目前種群搜索到的最優(yōu)解，稱為全局極值[19-20]。

粒子群算法步驟如下：

（1）設置種群規(guī)模N、變量范圍R、慣性權重系數(shù)ω、學習因子 和 ，在給定搜索空間內(nèi)隨機初始化包含速度和位置信息的粒子;

（2）計算每個粒子的適應度，設置粒子 的適應度值為其當前的個體極值 ，最好粒子為全局極值 ;

（3）根據(jù)式（2）更新每個粒子的速度和位置;

（4）更新后，比較每個粒子 的函數(shù)值與其個體極值 ，若函數(shù)值較優(yōu)，則設置該函數(shù)值為個體極值;再比較全局極值與全部個體極值，獲得最新全局極值 ;

（5）判斷是否滿足給定的終止條件，若滿足，則終止搜索，輸出優(yōu)化結果;否則，返回步驟（3）繼續(xù)搜索。

2 ?基于協(xié)同進化策略的粒子群優(yōu)化算法

2.1 ?算法的基本思想

協(xié)同進化策略的粒子群優(yōu)化算法在基于傳統(tǒng)粒子群算法的基礎上，借鑒協(xié)同進化的思想和共生機制，提出了將協(xié)同進化算法和粒子群算法相結合的算法模型，將個體的進化與群體聯(lián)系起來。

2.2 ?協(xié)同進化策略的粒子群優(yōu)化算法描述

在協(xié)同進化粒子群優(yōu)化算法中，多個種群有相同的搜索空間，群體內(nèi)部采用精英保留策略來保留精英個體，進化機制采用傳統(tǒng)的進化算法，協(xié)同進化粒子群優(yōu)化算法主要在于個體的進化與群體之間有一定的關聯(lián)，將個體的進化和群體之間發(fā)生信息交換，達到優(yōu)勢互補的效果。

協(xié)同進化粒子群優(yōu)化算法的實現(xiàn)步驟如下：

（1）初始化粒子速度與位置。對每個粒子進行評估，確定種群的個體極值和全局極值。

（2）計算出每個種群中個體的適應度值。

（3）判斷是否滿足終止條件，如果滿足輸出結果，否則更新信息素。

（4）種群中的每個個體根據(jù)公式進行信息素更新。分別按公式（1）與公式（2）分別更新每一個粒子的速度和位置。

（5）每個種群根據(jù)個體適應度值的大小采用精英保留策略保留精英，其余進行進化操作，將進行進化操作的新個體與精英保留策略保留下來的精英組成新的種群。

（6）每個種群選出當前最優(yōu)個體，與不同種群的個體共同構成問題的一個完整解，實現(xiàn)種群信息共享與協(xié)同進化。

（7）判斷是否達到最大迭代次數(shù)，如果是，算法停止輸出結果，否則繼續(xù)計算個體適應度。

3 ?實驗結果與分析

為了驗證所提算法的有效性，選取四個典型的測試函數(shù)，Rosenbrock函數(shù)、Sphere函數(shù)、Griewank 函數(shù)和Rastrigrin函數(shù)。實驗采用Matlab2014，進化迭代參數(shù)分別為：粒子群數(shù)目40，慣性權值最大是 ，最小值 ，迭代常數(shù)分別為 ， ，最大迭代次數(shù)均為100次。

對四個經(jīng)典的測試函數(shù)Rosenbrock、Sphere、Griewank、Rastrigrin進行系列實驗，其中，Rosenbrock和Sphere為單峰函數(shù)，Griewank 和Rastrigrin為多峰函數(shù)，實驗結果如圖3、表1、表2所示。

將基本粒子群優(yōu)化算法和協(xié)同進化策略的粒子群優(yōu)化算法在四個測試函數(shù)Rosenbrock、Sphere、Griewank、Rastrigrin進行試驗。

從測試結果可以看出，基本PSO算法在迭代搜索過程中搜索速度較慢，解的下降過程較平穩(wěn)，CEA-PSO算法收斂速度快，能更好的達到理想精度。

4 ?結束語

針對基本PSO算法收斂速度慢且精度低的問題，本文基于傳統(tǒng)的粒子群優(yōu)化算法，結合合作型協(xié)同進化理論，對算法進行改進，并與基本粒子群優(yōu)化算法進行比較，提出了一種基于協(xié)同策略的粒子群優(yōu)化算法，該算法采用精英保留策略，將個體的進化和群體之間發(fā)生信息交換。幾組經(jīng)典的基準測試函數(shù)表明，本文所提出的優(yōu)化算法在優(yōu)化性能和收斂速度方面有很好的效果。

參考文獻

[1] Das S， Mullick S S， Suganthan P N. Recent advances in differential evolution-An updated survey. Swarm & Evolu- tionary Computation， 2016， 27： 1-30.

[2] Duan H B， Li P， Yu Y X. A predator-prey particle swarm op-timization approach to multiple UCAV air combat modeled by dynamic game theory. IEEE/CAA Journal of Automat- ica Sinica， 2015， 2（1）： 11-18.

[3] Pan Feng， Chen Jie， Gan Ming-Gang， Cai Tao， Tu Xu-Yan. Model analysis of particle swarm optimizer. Acta Automat- ica Sinica， 2006， 32（3）： 368-377.

[4] Long Q， Wu C Z. A hybrid method combining genetic algo-rithm and Hooke-Jeeves method for constrained global op-timization. Journal of Industrial & Management Optimiza-tion， 2017， 10（4）： 1279-1296.

[5] Prakasam A， Savarimuthu N. Metaheuristic algorithms and probabilistic behaviour： a comprehensive analysis of Ant Colony Optimization and its variants. Arti?cial Intelligence Review， 2016， 45（1）： 97-130.

[6] Ma L B， Zhu Y L， Zhang D Y， Niu B. A hybrid approach to arti?cial bee colony algorithm. Neural Computing and Applications， 2016， 27（2）： 387-409.

[7] 李碧， 林土勝. 協(xié)同進化在遺傳算法中的應用述評[J]. 計算機科學， 2009， 36（04）： 34-37+63.

[8] 慕彩紅. 協(xié)同進化數(shù)值優(yōu)化算法及其應用研究[D]. 西安電子科技大學， 2010

[9] 聶敬云， 李春青， 李威威， 等. 關于遺傳算法優(yōu)化的最小二乘支持向量機在MBR仿真預測中的研究[J]. 軟件， 2015， 36（5）： 40-44.

[10] Zhou H， Wang J. A Cooperative Coevolutionary Algorithm with Application to Job Shop Scheduling Problem[C]. IEEE International Conference on Service Operations and Logistics， and Informatics. IEEE， 2007： 746-751.

[11] 丁知平. 量子混沌自適應粒子群優(yōu)化算法的研究[J]. 軟件， 2018， 39（4）： 09-14.

[12] Wang GL， Zhao GQ， Li HP. Research on optimization design of ?the heating/cooling channels for rapid heat cycle moldingbased on response surface methodology and constrained particle swarm optimization. Expert Systems with Applications， 2011， 38（6）： 6705-6719.

[13] Gorai A， Ghosh A. Hue-preserving color image enhancement using particle swarm optimization. 2011 IEEE Recent Advances in Intelligent Computational Systems. Piscataway. IEEE. 2011. 563-568.

[14] Asmara A， Krohling RA， Hoffmann F. Parameter tuning of a computed-torque controller for a 5 degree of freedom robot arm using co-evolutionary particle swarm optimization. Proc. IEEE Conference on Swarm Intelligence Symposium. Pasadena， USA. June. 8-10， 2005. 162-168.

[15] Zhang Y， Gong DW， Ding ZH. Handling multi-objective optimization problems with a multi-swarm ?cooperative particle swarm optimizer. Expert Systems with Applications. 2011， 38（11）： 13933-13941.

[16] 劉露萍， 賈文生. 基于方體剖分和量子免疫粒子群算法的Nash均衡求解[J]. 軟件， 2018 ， 39（6）： 01-03.

[17] 陳驍睿. 基于改進粒子群算法的機位分配問題研究[J]. 軟件， 2015， 36（1）： 72-76.

[18] 肖根福， 劉歡， 李東洋， 歐陽春娟. 一種求解大規(guī)模問題的自學習協(xié)同粒子群算法[J]. 井岡山大學學報（自然科學版）， 2018， 39（03）： 32-37.

[19] 李俊， 汪沖， 李波， 方國康. 基于多策略協(xié)同作用的粒子群優(yōu)化算法[J]. 計算機應用， 2016， 36（03）： 681-686.

[20] 李壘， 岳小冰. 一種多粒子群協(xié)同進化算法[J]. 計算機系統(tǒng)應用， 2015， 24（09）： 156-159.