楊蕾 梁永全

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

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

中圖分類號(hào)： TP301.6 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.08.036

本文著錄格式：楊蕾，梁永全. 協(xié)同進(jìn)化策略的粒子群優(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 ?引言

隨著社會(huì)經(jīng)濟(jì)和信息技術(shù)的快速發(fā)展，各個(gè)領(lǐng)域中的問(wèn)題都可以通過(guò)將待決解決問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題來(lái)處理，目前存在的優(yōu)化算法大致可以分為兩類：傳統(tǒng)優(yōu)化算法和智能優(yōu)化算法。傳統(tǒng)優(yōu)化算法一般是針對(duì)結(jié)構(gòu)化的問(wèn)題，有較為明確的問(wèn)題和條件描述，如線性規(guī)劃，二次規(guī)劃，整數(shù)規(guī)劃，混合規(guī)劃，帶約束和不帶約束條件等，即有清晰的結(jié)構(gòu)信息;現(xiàn)代智能優(yōu)化算法主要包括差分進(jìn)化算法 （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é)同進(jìn)化算法[7]（Co-Evolutionary Algorithm， CEA）是研宄者在協(xié)同進(jìn)化理論基礎(chǔ)上提出的一類新算法。這類算法強(qiáng)調(diào)了在進(jìn)化過(guò)程中種群內(nèi)部的相互影響和種群之間的相互協(xié)調(diào)。這些年來(lái)，許多專家學(xué)者提出了多種多樣的CEA，較主流的劃分[8]：競(jìng)爭(zhēng)型協(xié)同進(jìn)化算法（Competitive Co-Evolutionary Algorithm， Com-CEA）[9]和合作型協(xié)同進(jìn)化算法（Cooperative Co-Evolutionary Algorithm， Coo-CEA）[10]兩類。

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

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

1 ?概述

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

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

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

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

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

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

粒子群算法步驟如下：

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

（2）計(jì)算每個(gè)粒子的適應(yīng)度，設(shè)置粒子 的適應(yīng)度值為其當(dāng)前的個(gè)體極值 ，最好粒子為全局極值 ;

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

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

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

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

2.1 ?算法的基本思想

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

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

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

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

（1）初始化粒子速度與位置。對(duì)每個(gè)粒子進(jìn)行評(píng)估，確定種群的個(gè)體極值和全局極值。

（2）計(jì)算出每個(gè)種群中個(gè)體的適應(yīng)度值。

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

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

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

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

（7）判斷是否達(dá)到最大迭代次數(shù)，如果是，算法停止輸出結(jié)果，否則繼續(xù)計(jì)算個(gè)體適應(yīng)度。

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

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

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

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

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

4 ?結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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ìn)化在遺傳算法中的應(yīng)用述評(píng)[J]. 計(jì)算機(jī)科學(xué)， 2009， 36（04）： 34-37+63.

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

[9] 聶敬云， 李春青， 李威威， 等. 關(guān)于遺傳算法優(yōu)化的最小二乘支持向量機(jī)在MBR仿真預(yù)測(cè)中的研究[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īng)粒子群優(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ìn)粒子群算法的機(jī)位分配問(wèn)題研究[J]. 軟件， 2015， 36（1）： 72-76.

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

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

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