一種求解大規(guī)模問題的自學習協同粒子群算法

肖根福，劉　歡，李東洋，歐陽春娟

?

一種求解大規(guī)模問題的自學習協同粒子群算法

*肖根福1，劉歡2，李東洋3，歐陽春娟2

(1. 井岡山大學機電工程學院，江西，吉安 343009；2. 井岡山大學電子與信息工程學院，江西，吉安 343009；3. 同濟大學電子與信息工程學院，上海 201804)

隨著工程技術要求的提高，許多實際優(yōu)化問題從低維問題發(fā)展成高維的大規(guī)模優(yōu)化問題，自然計算算法在面對該類問題時容易陷入局部最優(yōu)，而協同粒子群算法是解決大規(guī)模優(yōu)化問題的重要手段之一。本文將子種群劃分自學習策略和慣性權重自適應策略引入到協同粒子群算法中，增強了算法的自學習能力，提高了算法的全局尋優(yōu)能力。實驗結果表明，所提算法的性能超過了傳統(tǒng)協同粒子群等算法，具有求解大規(guī)模問題的較大潛力。

大規(guī)模優(yōu)化；協同粒子群算法；學習自動機；自學習

0　引言

近年來，自然計算在優(yōu)化問題中取得了巨大的成功，進行了較多的實際應用。與傳統(tǒng)的梯度下降法相比，自然計算算法在面對不可微、非線性問題時有較大優(yōu)勢。自然計算算法種類很多，如粒子群算法、微分進化算法、蟻群算法、螢火蟲算法等等。每一種算法又有許多改進的形式，以1995年由kennedy提出的粒子群算法為例，有聚類粒子群[1]、散射學習粒子群[2]、自適應粒子群[3]和綜合學習粒子群（CLPSO）[4]等等。

盡管自然計算算法取得了巨大的成功，但自然計算算法在求解大規(guī)模優(yōu)化問題時性能將迅速惡化，遭遇“維數詛咒”[5]。協同進化策略是解決大規(guī)模問題的重要手段之一，協同進化采用“分而治之”的策略將大規(guī)模問題分解成小的子問題。自從Potter[6]提出協同進化算法框架以來，研究者們提出了多種協同進化算法，如協同進化遺傳算法[7]，協同進化粒子群算法[8]，協同進化微分進化算法[9]。

在協同策略框架中，有兩個關鍵問題值得探討，一是將大規(guī)模問題合理地劃分為子問題，而劃分子問題的關鍵是找到變量間的內在關系，將耦合關系強的變量歸入同一子群；二是平衡子群的全局搜索能力和局部搜索能力，平衡這兩種能力的關鍵是慣性權重的合理選取。

本文針對協同粒子群算法在求解大規(guī)模優(yōu)化問題時容易陷入局部最優(yōu)的特點，采取兩個策略來改進協同粒子群算法，一是利用學習自動機挖掘出問題子維間的耦合關系，將關系相近的子維放入到一個子種群當中；二是將子種群自適應地分成兩個部分，對優(yōu)化效果差的粒子賦予新的慣性權重，令其跳出局部最優(yōu)，加快算法收斂。

1 大規(guī)模優(yōu)化問題

優(yōu)化問題可以用下式描述：

一般來說，所謂大規(guī)模優(yōu)化問題是指決策變量的個數大于100的問題[5]。大規(guī)模優(yōu)化問題的求解主要有兩個難點：一是決策變量的增加使解空間呈指數式增長，在計算資源有限的情況下很難找到最優(yōu)解；二是決策變量增加使多峰函數的局部最優(yōu)解個數呈指數式增長，算法易陷入局部最優(yōu)。

2 自學習協同粒子群算法

2.1 協同粒子群算法

粒子群算法是受飛鳥覓食行為的啟發(fā)而提出的，每個粒子代表一個可行解，粒子追隨個體極值（pBest）和全局極值（gBest）進行尋優(yōu)。在標準粒子群算法中，粒子用下式更新自己：

其中V為當代粒子的移動速度，V是下一代粒子的移動速度，p是當代粒子的位置，p是下一代粒子的位置，p為個體最優(yōu)位置，p為全局最優(yōu)位置，r，r是隨機數，c，c是學習因子，一般為常數，為慣性權重。

在標準粒子群算法中，每個粒子代表一個完整的解向量，包含了所有決策變量，包含了問題的每一子維。每次粒子位置的更新都要更新所有的決策變量，這容易造成“兩步向前、一步向后”的問題，也就是說，雖然在優(yōu)化過程中適應值函數是逐漸減小的，但問題的每一個子維并不都是向最優(yōu)位置靠近，部分子維會遠離最優(yōu)位置，從而削弱算法的全局收斂性，使算法容易陷入局部最優(yōu)。

為了保證粒子的每個子維都向正確的方向運動，Van den Bergh[8]提出了協同粒子群算法，該算法的基本思想為：將粒子群劃分成多個相互獨立的子種群，分別在問題的不同子維上搜索，每個子種群解決問題的一個子目標，同時，子群體之間保持信息溝通和知識共享，協同進化。在協同粒子群算法中，子種群是依次更新的，當某一子種群的粒子朝某一子維方向移動一次后，與其它子種群獲得的當前最優(yōu)位置結合，構造出一個完整的解向量，并用評價函數計算適應度，之后下一個子種群再朝另一子維移動，直至所有子種群都完成更新。

2.2 子種群劃分自學習

大規(guī)模優(yōu)化問題變量眾多，當大量的變量間存在相關性時問題求解變得更加困難。在協同進化過程中，子種群劃分也就是問題分解是協同進化的最關鍵一步。一般來說，不考慮變量耦合的問題分解策略對可分離問題是有效的，但對不可分離問題，它們的性能將會變差。子種群劃分策略的目標是將獨立的變量分入不同的群，而非獨立的、相關性強的變量則分入同一個子種群。本文利用學習自動機根據環(huán)境反饋，自學習地選擇合理的種群劃分。

近年來，強化學習在推動人工智能技術的發(fā)展中做出了重要貢獻，人工智能圍棋程序AlphaGo Zero正是依靠強化學習實現了無師自通[10]。學習自動機屬于強化學習范疇，由Tsetlin于1961年提出，學習自動機的特點是能夠在未知環(huán)境中找出最優(yōu)參數。

典型的學習自動機由一個四元組{A,R,P,T}定義。其中A={A1,A2,…,An}為學習自動機的動作集合，R={R1,R2,…,Rn}為環(huán)境的反饋集合，反饋分獎賞和懲罰兩種情況，P={P1,P2,…,Pn}是與動作A一一對應的一組概率值，記錄A集合中每個動作被選中的概率，T是更新規(guī)則，不同類型的學習自動機有不同的更新規(guī)則。學習自動機模型如下圖所示。

圖1 學習自動機模型

子種群劃分要解決的問題是子種群應該包含哪些問題子維，在標準的協同粒子群算法中，種群劃分在程序初始化時已經確定，不能隨問題的改變而修改子種群與問題子維的對應關系。本文通過群表來自學習地確定子種群與問題子維的關系，群表如下圖所示，SWARM表示子種群，D表示問題子維，LA則是用來分配問題子維的學習自動機。0/1表示學習自動機的行動（Action），0表示該問題子維不屬于該子種群，1表示問題子維屬于該子種群，同一列只有一個子種群為1。

圖2 群表

每個子種群進化時，如果協同粒子群算法的全局最優(yōu)（gBest）有提高，則將獎勵信號反饋至學習自動機。獲得反饋信號后，采取連續(xù)線性獎懲-不活躍策略（LR-I）更新學習自動機的概率矩陣。通過概率矩陣，學習自動機可以選擇對應行動（0/1），明確問題子維與子種群的對應關系。

2.3　慣性權重自適應

慣性權重是協同粒子群算法中最重要的可調參數之一。若慣性權重較大，則算法的全局搜索能力較強，找到全局最優(yōu)解的概率較大；反之，則局部搜索能力較強，收斂速度較快。大規(guī)模優(yōu)化問題的解空間大，容易使自然計算算法陷入局部最優(yōu)，如果能合理選擇慣性權重策略，平衡全局搜索能力和局部搜索能力，可以加快大規(guī)模優(yōu)化問題的收斂速度，快速找到全局最優(yōu)解。

Y.Shi于1998年在IEEE國際進化計算學術會議中建議在粒子群算法中采用線性遞減慣性權重策略[11]，即：

其中為當前迭代次數，K為最大迭代次數，w為慣性權重的初始值，通常取0.9，w為慣性權重的最終值，通常取0.4。這種策略對一些小規(guī)模優(yōu)化問題會得到較好的效果，但對于不確定較大的大規(guī)模優(yōu)化問題，單純使用線性調整策略有一定局限性。

為了使粒子群算法跳出局部最優(yōu)，慣性權重的非線性微分變化策略被提出，具體表達式如下:

在這種策略中，先逐漸增加到某個較大的數值，然后再微分遞減。該策略與線性遞減策略相比可以在算法初期跳出局部最優(yōu)，加強搜索力度。

協同粒子群算法搜索最優(yōu)值時，子種群中的一部分粒子會到達適應值更優(yōu)的位置，而另一部分則可能到達適應值更差的位置。因此根據迭代時適應值的差異，動態(tài)地調整慣性權重策略，使適應值較好的粒子保持原來的慣性權重策略，而適應值更差的粒子則采取新的慣性權重策略，將會增強協同粒子群算法的全局尋優(yōu)和快速收斂的能力。

根據上述原理，本文根據迭代后適應值的變化情況，將協同粒子群算法的每一個子種群均劃分為兩個部分，一個是適應值比上一次迭代時更優(yōu)的部分，另一個是適應值比上一次迭代更差的部分。各粒子慣性權重的取值由下式決定：

式中，x表示第個粒子，為當前迭代次數，為適應值函數。

也就是說，對于適應值比上一步更優(yōu)的粒子，將其慣性權重設置為線性遞減策略，即式(4)，確保快速收斂；對于適應值更差的粒子，將其慣性權重設置為非線性微分變化策略，在算法初期獲得更大的慣性權重值，使子種群保持探索，跳出局部最優(yōu)。

2.4 算法實現

自學習協同粒子群算法（SLCPSO）利用學習自動機找出問題子維之間的關系，自學習劃分子種群，并引入慣性權重自適應策略，具體算法步驟如下：

1）參數設定。包括粒子群算法參數設定，如子種群規(guī)模、迭代次數、學習因子等；學習自動機參數如獎勵參數等；

2）初始化。包括粒子群算法初始化，如粒子的初始位置、初始速度等；學習自動機初始化，如初始化群表、概率矩陣等；

3）根據群表劃分子種群；

4）計算粒子適應值，更新gbest，pbest；

5）如果gbest適應值改善，輸出獎勵信號；反之輸出懲罰信號；

6）利用式(6)確定粒子的慣性權重在動態(tài)調整后的取值；

7）是否子種群內的粒子都迭代完成？沒有則更新粒子序號，返回第4步;

8）根據獎懲信號，更新概率矩陣；

9）是否子種群都迭代完成？沒有則更新子種群序號，返回第4步；

10）根據概率矩陣更新群表；

11）是否迭代次數或收斂精度達到？沒有則返回第3步；

12）輸出結果。

3 算法驗證

為了評價本文提出的SLCPSO算法的性能，用表1所示6個經典的測試函數進行系列實驗。其中，F1-F2為單峰函數，F3-F6為多峰函數，D為問題維數。

表1 測試函數

采用本文提出的SLCPSO算法與下面3種粒子群算法進行比較：慣性權重線性下降的粒子群算法（LWPSO）[11]，綜合學習粒子群算法（CLPSO）[4]和H型協同粒子群算法(CPSO-H)[8]。

實驗中SLCPSO算法參數設置：子種群數量為10個，每個子種群包含50個粒子，最大迭代次數為10000次，慣性權重初值為0.9，終止為0.4，學習自動機的獎勵參數為0.1，測試函數的維數分成小規(guī)模問題（10維）和大規(guī)模問題（100維）兩種情況，通過20次計算得出平均值與標準差。其他三種算法參數參照對應文獻進行設置。

從表2可以看出，對10維的小規(guī)模優(yōu)化問題來說，所有種類的粒子群算法都取得了比較好的效果，本文提出的SLCPSO算法總體來看效果最好，但CLPSO算法在F3、F4函數的計算中取得了比其他所有算法都好的結果，可見對小規(guī)模問題來說，協同類算法（CPSO-H、SLCPSO）并沒有壓倒性優(yōu)勢。而對表3中的100維大規(guī)模問題來說，所有粒子群算法的性能都明顯下降，協同類算法（CPSO-H、SLCPSO）在求解大規(guī)模問題上有較大優(yōu)勢，本文提出的SLCPSO算法對所有的測試函數均取得了比其他3種粒子群算法更好的計算結果。

表2 算法均值與標準差(10維)

Table 2 The mean and standard deviation of algorithms (10 dimension)

表3 算法均值與標準差(100維)

Table 3 The mean and standard deviation of algorithms (100 dimension)

4 結論

針對協同粒子群算法在求解大規(guī)模優(yōu)化問題過程中容易陷入局部最優(yōu)、收斂速度慢的問題，在協同粒子群算法中引入子種群自學習劃分策略和慣性權重自適應策略，提出一種自學習協同粒子群優(yōu)化算法（SLCPSO）。該算法利用學習自動機挖掘問題子維之間的關系，動態(tài)確定問題子維和子種群的關系，并在適應值較差的部分粒子中采取非線性微分變化慣性權重策略，增強算法初期的尋優(yōu)能力。SLCPSO算法與另外三種粒子群算法一起在測試函數集上進行了比較計算，由實驗結果可知，SLCPSO算法在求解精度方面有顯著的優(yōu)勢，表明該算法是一種求解大規(guī)模優(yōu)化問題的較好方法。

[1] Kennedy J. Stereotyping: Improving particle swarm performance with cluster analysis[C]. Proceedings of IEEE Congress on Evolution. Computing. 2000, (2):1507-1512.

[2] Ren Z, Zhang A, Wen C, et al. A scatter learning particle swarm optimization algorithm for multimodal problems.[J]. IEEE Trans Cybern, 2014, 44(7):1127-1140.

[3] Hu M, Wu T, Weir J D. An Adaptive Particle Swarm Optimization With Multiple Adaptive Methods[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(5):705-720.

[4] Liang J J, Qin A K, Suganthan P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3):281-295.

[5] 劉睿,梁靜. 求解大規(guī)模問題的協同進化動態(tài)粒子群優(yōu)化算法[J].軟件學報,2018,29(9):1-12

[6] Potter M A. The design and analysis of a computational model of cooperative coevolution[M]. George Mason University, 1997.

[7] Yu Y, Yu X. Cooperative Coevolutionary Genetic Algorithm for Digital IIR Filter Design[J]. IEEE Transactions on Industrial Electronics, 2007, 54(3):1311-1318.

[8] Frans V D B, Engelbrecht A P. A Cooperative approach to particle swarm optimization[J]. IEEE Trans.evol.comput, 2004, 8(3):225-239.

[9] Omidvar M N, Li X, Mei Y, et al. Cooperative Co-Evolution With Differential Grouping for Large Scale Optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3):378-393.

[10] Silver D, Schrittwieser J, Simonyan K, et al. Mastering the game of Go without human knowledge[J]. Nature, 2017, 550(7676):354-359.

[11] Shi Y, Eberhart R C. A Modified Particle Swarm Optimization[C]. Proceedings of the Congress on Evolutionary Computation, 1998: 69-73.

AN SELF-LEARNING COOPERATIVE PARTICLE SWARM OPTIMIZATION ALGORITHM FOR SOLVING LARGE SCALE PROBLEMS

XIAO Gen-fu1, LIU Huan2, LI Dong-yang3, OUYANG Chun-juan2

(1. School of Mechanical and Electrical Engineering, Jinggangshan University, Ji’an, Jiangxi 343009, China; 2. School of Electronics and Information Engineering, Jinggangshan University, Ji’an, Jiangxi 343009, China; 3. School of Electronics and Information Engineering, Tongji University, Shanghai 201804, China)

With the improvement of engineering requirements, many practical optimization problems have been developed from low dimensional problems to large-scale optimization problems. The natural computing algorithm is prone to fall into the local optimal in the face of this kind of problem. Cooperative particle swarm optimization (CPSO) is one of the important means to solve large-scale optimization problems. In this paper, sub population partition self-learning strategy and inertia weight self-adaptive strategy are introduced into cooperative particle swarm optimization algorithm, which enhances the self-learning ability of the algorithm and improves the global optimization ability of the algorithm. The experimental results show that the performance of the proposed algorithm exceeds the traditional cooperative particle swarm optimization algorithms, and has great potential for solving large-scale problems.

large scale global optimization; cooperative particle swarm optimization; learning automata; self-learning

1674-8085(2018)03-0032-06

TP301.6

A

10.3969/j.issn.1674-8085.2018.03.008

2018-03-07；

2018-04-18

國家自然科學基金項目（61462046）；江西省自然科學基金項目（2016BAB202049）

江西省教育廳科技項目(GJJ160741,GJJ170633,GJJ170632)；江西省藝術規(guī)劃項目（YG2016250,YG2017381）

*肖根福(1980-)，男，江西贛州人，講師，博士，主要從事智能控制、建模與優(yōu)化研究(E-mail:xiaogenfu@163.com);

劉 歡(1981-)，女，江西吉安人，副教授，博士，主要從事圖像處理、計算機視覺研究(E-mail:liuhuan816618@163.com);

李東洋(1992-)，男，河南南陽人，博士生，主要從事自然計算算法研究(E-mail:lidongyang0412@163.com);

歐陽春娟(1974-)，女，江西吉安人，副教授，博士，主要從事智能優(yōu)化、信息隱寫研究(E-mail:oycj001@163.com).