進(jìn)化算法在大規(guī)模優(yōu)化問(wèn)題中的應(yīng)用綜述

梁 靜， 劉 睿， 瞿博陽(yáng)， 岳彩通

(1.鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州 450001；2.中原工學(xué)院 電子信息學(xué)院，河南 鄭州 450007)

0 引言

當(dāng)今很多優(yōu)化問(wèn)題已經(jīng)從簡(jiǎn)單問(wèn)題發(fā)展成為復(fù)雜問(wèn)題.許多科學(xué)和工程應(yīng)用問(wèn)題都可以設(shè)計(jì)成大規(guī)模優(yōu)化問(wèn)題來(lái)進(jìn)行求解，例如：大型電力系統(tǒng)、大量的資源調(diào)度問(wèn)題、大規(guī)模交通網(wǎng)絡(luò)的車(chē)輛路徑規(guī)劃等.然而隨著優(yōu)化問(wèn)題越來(lái)越復(fù)雜，一些經(jīng)典的算法已經(jīng)不能滿(mǎn)足實(shí)際需要.最近幾年進(jìn)化優(yōu)化在許多實(shí)值和組合優(yōu)化問(wèn)題上取得了很大的成功，但是大多數(shù)的隨機(jī)優(yōu)化算法都會(huì)遭受“維數(shù)災(zāi)難”.因此，近些年學(xué)者們利用進(jìn)化算法進(jìn)行了多種有價(jià)值的嘗試，并且針對(duì)大規(guī)模優(yōu)化問(wèn)題組織了專(zhuān)題會(huì)議，如Special Session on Evolutionary Computation for Large Scale Global Optimization，設(shè)計(jì)了新的測(cè)試函數(shù)、建立了相關(guān)的網(wǎng)站，并且在IEEE Transactions on Evolutionary Computation、Information Sciences、Soft Computing、Applied Soft Computing等優(yōu)秀期刊也刊登了對(duì)于大規(guī)模問(wèn)題的研究進(jìn)展，顯示出此研究領(lǐng)域的重要性.

1 數(shù)學(xué)表述

大規(guī)模優(yōu)化問(wèn)題可以用式(1)表述：

min/maxF(x)=f(x1,x2,…,xn)，x∈X.

(1)

式中，X?n表示可行解集；n表示搜索空間的維數(shù)(即決策變量的個(gè)數(shù))；x=(x1,x2,…,xn)∈n表示決策變量；f:X→則表示一個(gè)從n維空間映射到一維適應(yīng)度值F(x)的實(shí)值非連續(xù)性目標(biāo)函數(shù).在大規(guī)模設(shè)置中決策變量的個(gè)數(shù)n一般大于100[1]，通常達(dá)到1 000維以上.

2 解決方法

在算法開(kāi)始階段，文獻(xiàn)[2]給出了針對(duì)大規(guī)模問(wèn)題的初始化方法，可以更加有效地尋找極點(diǎn).而對(duì)于算法的主體部分，一般來(lái)說(shuō)主流的策略可以分為兩大類(lèi)：協(xié)同進(jìn)化策略和不分組策略.協(xié)同進(jìn)化策略是由分治策略進(jìn)化而來(lái)，主要思想是把大規(guī)模復(fù)雜問(wèn)題分解成單變量或低維簡(jiǎn)單問(wèn)題逐一解決；而不分組策略是運(yùn)用一些特殊的策略或聯(lián)合其他有效的算法來(lái)改進(jìn)它們?cè)诮鉀Q大規(guī)模問(wèn)題時(shí)的性能.

2.1 種群初始化方法

種群初始化方法主要包括以下5類(lèi)：隨機(jī)方法、定值設(shè)定法、兩步式方法、混合方法和具體應(yīng)用法.隨機(jī)生成是最常用的方法，然而，在面對(duì)大規(guī)模優(yōu)化問(wèn)題(決策變量超過(guò)100)時(shí)，這種初始化方法效果不佳.文獻(xiàn)[2]主要列出了一些不同初始化方法的對(duì)比研究.

在隨機(jī)方法中，比較常用的是使用隨機(jī)數(shù)產(chǎn)生器隨機(jī)生成.而定值設(shè)定法則比較偏向于在搜索空間中產(chǎn)生均勻分布的點(diǎn)，在缺乏問(wèn)題先驗(yàn)知識(shí)的情況下，一個(gè)比較均勻的種群可以促進(jìn)算法在迭代早期的探索能力.近些年，兩步式初始化方法在研究中較為常用，此方法分為前期產(chǎn)生初始點(diǎn)，后期根據(jù)條件改進(jìn)這些點(diǎn).混合方法一般來(lái)說(shuō)是一些基礎(chǔ)方法的組合.具體應(yīng)用法則是指根據(jù)一些特殊的實(shí)值問(wèn)題專(zhuān)門(mén)設(shè)計(jì)的初始化方法.文獻(xiàn)[3]給出了現(xiàn)在常用的8種初始化方法(與DE算法相結(jié)合)的測(cè)試結(jié)果，使用的測(cè)試函數(shù)是CEC’2008[4].

2.2 不分組策略

學(xué)者們一般根據(jù)算法在不同階段的特性設(shè)置不同的策略來(lái)解決低維問(wèn)題，所以，針對(duì)大規(guī)模優(yōu)化問(wèn)題改進(jìn)這些策略是一種比較常用的方法.

2.2.1 子代產(chǎn)生策略

一般來(lái)說(shuō)，每種進(jìn)化算法都有固定的子代產(chǎn)生策略.但是，對(duì)于大規(guī)模問(wèn)題，使個(gè)體廣泛分布在高維空間中比較困難.在每次迭代過(guò)程中，算法不斷的收斂，因此下一代的學(xué)習(xí)策略很重要，不僅要向好的方向進(jìn)化還要在搜索空間中廣泛探索.文獻(xiàn)[5]提出了反向?qū)W習(xí)策略，這種產(chǎn)生策略具有空間的導(dǎo)向性，可以增加種群的多樣性，因此將其融入DE算法來(lái)解決大規(guī)模優(yōu)化問(wèn)題.文獻(xiàn)[6]提出了基于廣義反向?qū)W習(xí)的DE算法，該算法用廣義反向?qū)W習(xí)方法(generalized opposition-based learning，GOBL)產(chǎn)生子代個(gè)體，用DE算法對(duì)產(chǎn)生的個(gè)體進(jìn)行優(yōu)化. 圖1表示4個(gè)不同的廣義反向?qū)W習(xí)的模型，其中，x是當(dāng)前解，x*是反向解.

圖1 4個(gè)不同的廣義反向?qū)W習(xí)模型Fig.1 Four different GOBL models

圖 1分別表示了文獻(xiàn)[6]中所使用的4個(gè)GOBL模型，其中a表示搜索空間的下界，b表示搜索空間的上界，而GOBL-R模型是上述模型的一般表達(dá)式.當(dāng)k=0時(shí)，是GOBL-SS模型；當(dāng)k=1/2時(shí)，是GOBL-SI模型；當(dāng)k=1時(shí)，是OBL模型.這些模型用于產(chǎn)生新個(gè)體并與原始個(gè)體混合進(jìn)行選擇.

2.2.2 新的變異策略

JADE是Zhang于2009年提出把變異策略和外部存檔策略相結(jié)合的自適應(yīng)方法[7].在無(wú)存檔策略中，突變向量用式(2)產(chǎn)生：

Fi·(xr1,g-xr2,g)，

(2)

筆者在比較當(dāng)前種群時(shí)，發(fā)現(xiàn)劣解可以為種群進(jìn)化方向提供有用的信息.定義A為劣解歸檔集;P為當(dāng)前種群;有存檔的突變策略“DE/current-to-pbest/1”的突變向量用式(2)產(chǎn)生時(shí)，xr2,g是從P∪A中隨機(jī)選擇的個(gè)體.

文獻(xiàn)[8]則給出了針對(duì)大規(guī)模全局優(yōu)化的連續(xù)差分進(jìn)化鄰域搜索算法(sequential differential evolution enhanced by neighborhood search，SDENS)，此算法主要分為兩部分：①針對(duì)每個(gè)個(gè)體通過(guò)局部和全局鄰域搜索策略產(chǎn)生兩個(gè)實(shí)驗(yàn)個(gè)體；②從當(dāng)前個(gè)體和兩個(gè)新產(chǎn)生的實(shí)驗(yàn)個(gè)體中選取合適的一個(gè)作為新的當(dāng)前個(gè)體.局部和全局鄰域搜索策略在文獻(xiàn)[8]中是一種突變策略.

一般來(lái)說(shuō)，DE/target-to-best/1突變策略(如式(3)所示)主要著重于開(kāi)發(fā)(exploitation)，即所有的個(gè)體都會(huì)向同樣的最優(yōu)點(diǎn)Xbest移動(dòng)，這樣就造成算法收斂過(guò)快[9].Das等在文獻(xiàn)[9]中改進(jìn)了DE/target-to-best/1突變策略，提出了兩個(gè)突變策略：局部鄰域和全局鄰域.

Vi,G=Xi,G+F·(Xbest,G-Xi,G)+

F·(Xr1,G-Xr2,G),

(3)

式中：Xbest,G表示在當(dāng)前代G種群的最優(yōu)位置；r1、r2∈{1,2,…,Np}，且i≠r1≠r2.

局部鄰域突變中最優(yōu)位置是小鄰域中的最優(yōu)位置，不是全部種群的最優(yōu).改進(jìn)后的模型表示如式(4)：

Li,G=Xi,G+α·(Xn-besti,G-Xi,G)+

β·(Xp,G-Xq,G),

(4)

式中：下標(biāo)n-besti，G表示Xi,G鄰域的最優(yōu)個(gè)體;鄰域大小是k；p、q∈[i-k,i+k]且p≠q≠i.個(gè)體會(huì)向其相應(yīng)鄰域的最優(yōu)點(diǎn)靠近，特殊點(diǎn)的吸引力減弱，這樣就避免陷入局部最優(yōu).

全局鄰域突變?cè)谠糄E/target-to-best/1突變策略中加上了α和β這兩個(gè)比例因子，如式(5)所示：

Gi,G=Xi,G+α·(Xbest,G-Xi,G)+

β·(Xr1,G-Xr2,G).

(5)

針對(duì)這兩個(gè)突變策略，文獻(xiàn)[9]采用一個(gè)權(quán)重w∈(0,1)合并成一個(gè)新的突變策略，如式(6)所示：

Vi,G=w·Gi,G+(1-w)·Li,G.

(6)

2.2.3 自適應(yīng)策略

自適應(yīng)策略可以適應(yīng)多種類(lèi)型的測(cè)試函數(shù)集，對(duì)于全局優(yōu)化的問(wèn)題比較有效，但是此策略一般都局限在低維問(wèn)題中.所以Yang在文獻(xiàn)[10]中針對(duì)大規(guī)模優(yōu)化問(wèn)題對(duì)自適應(yīng)策略進(jìn)行了擴(kuò)展，提供了更加廣泛的參數(shù)自適應(yīng)方案，提出了廣義自適應(yīng)差分進(jìn)化算法(generalized adaptive DE, GaDE).一般的自適應(yīng)策略可以被分為兩類(lèi)：基于啟發(fā)式規(guī)則的和基于概率分布規(guī)則的.基于啟發(fā)式規(guī)則的策略一般會(huì)引進(jìn)一些新的參數(shù)，而且這些參數(shù)在某些情況下設(shè)置比較困難，JDE和DEGL算法就是用的此類(lèi)策略.而SaDE、SaNSDE和JADE則屬于基于概率分布的自適應(yīng)方法.在這類(lèi)算法中，不同的參數(shù)值是根據(jù)某一概率分布隨機(jī)產(chǎn)生的，在進(jìn)化操作和選擇過(guò)程之后，好的參數(shù)值將作為下一次進(jìn)化的分布規(guī)律被記錄下來(lái)，用于產(chǎn)生更好的解.文獻(xiàn)[10]中提出的自適應(yīng)方式用的是第二類(lèi)基于概率分布的策略.對(duì)于一個(gè)給定的進(jìn)化算法，假設(shè)它有一個(gè)基于個(gè)體且非常敏感的參數(shù)A∈[Amin,Amax]，同時(shí)此參數(shù)需要在進(jìn)化過(guò)程中調(diào)整. 對(duì)于大規(guī)模優(yōu)化問(wèn)題，自適應(yīng)策略不僅用在算法的參數(shù)調(diào)節(jié)上，在2.3節(jié)的分組策略中也有應(yīng)用.

2.2.4 局部搜索策略

文獻(xiàn)[11]把基于局部搜索的動(dòng)態(tài)多種群粒子群優(yōu)化算法(dynamic multi-swarm particle swarm optimizer with local search, DMS-L-PSO)擴(kuò)展到大規(guī)模問(wèn)題上，并取得了良好的效果.DMS-PSO是根據(jù)鄰域結(jié)構(gòu)把大種群分成很多小種群，這些小種群利用不同的重組策略被頻繁重組，在頻繁重組的過(guò)程中，種群不斷交換它們之間的信息.而局部搜索策略是解決大規(guī)模優(yōu)化問(wèn)題的一種有效方法，主要加強(qiáng)算法的局部搜索能力.

把局部搜索策略加入DMS-PSO算法中：①每L代，根據(jù)小種群適應(yīng)度值進(jìn)行排序，利用準(zhǔn)牛頓法根據(jù)局部最優(yōu)解抽取小種群的前25%；②在搜索算法的結(jié)尾，利用準(zhǔn)牛頓法更改當(dāng)前的最優(yōu)解.

2.2.5 新的進(jìn)化策略

在解決大規(guī)模優(yōu)化問(wèn)題上，除了在原有的算法中加入新的策略，Cheng等也提出了一些新的群集智能算法用于解決此類(lèi)問(wèn)題.文獻(xiàn)[12]提出了社會(huì)學(xué)習(xí)的粒子群優(yōu)化算法(social learning particle swarm optimization algorithm, SL-PSO)，不同于經(jīng)典的粒子群優(yōu)化算法(particle swarm optimization, PSO)利用歷史信息(包括整個(gè)種群的最優(yōu)位置global best和每個(gè)粒子的歷史最優(yōu)位置personal best)更新粒子，新算法則是粒子向當(dāng)前種群中比它優(yōu)秀的個(gè)體學(xué)習(xí)， 具體的學(xué)習(xí)方式如圖 2所示.

圖2 SL-PSO的種群排序及學(xué)習(xí)行為Fig.2 Swarm sorting and behavior learning in SL-PSO

首先，對(duì)當(dāng)前種群按適應(yīng)度值排序，如果要更新第i個(gè)粒子，就向比第i個(gè)粒子好的個(gè)體(即圖 2中的被學(xué)習(xí)者)和平均位置學(xué)習(xí).而文獻(xiàn)[13]則提出了競(jìng)爭(zhēng)學(xué)習(xí)算法(competitive swarm optimizer，CSO)，即隨機(jī)從當(dāng)前種群中抽取兩個(gè)個(gè)體比較適應(yīng)度值，失敗者向勝利者學(xué)習(xí)，勝利者并不學(xué)習(xí)直接進(jìn)入下一次循環(huán)，如圖 3所示.

圖3 CSO的一般構(gòu)架Fig.3 The general idea of CSO

2.2.6 小種群搜索策略

文獻(xiàn)[14]介紹了小種群搜索策略(minimum population search, MPS)，這個(gè)策略主要是針對(duì)多模態(tài)問(wèn)題.為了提高M(jìn)PS在解決多模態(tài)問(wèn)題時(shí)的性能，文獻(xiàn)[15]使用了閾值收斂(threshold convergence, TC)方法來(lái)完成有序無(wú)偏的探索(exploration).MPS使用了相對(duì)較小的種群來(lái)提高可擴(kuò)展性，種群越小，循環(huán)的代數(shù)越多，評(píng)價(jià)次數(shù)的利用率越高.如果種群大小n小于問(wèn)題維數(shù)d，將其種群定義為n-1 維超平面.新解要嚴(yán)格按照所定義的超平面產(chǎn)生.在MPS中，每個(gè)種群成員用式(7)的方式初始化：

Sk= (rs1·bound/2,rs2·bound/2,…,

rsi·bound/2,…,rsn·bound/2),

(7)

式中:Sk是第k個(gè)粒子；rsi是介于-1到1之間的隨機(jī)數(shù)；bound是維數(shù)上界.

閾值按式(8)更新：

min_stepi=α·diagonal·([FEs-k]/FEs)γ,

(8)

式中：α是主要空間對(duì)角線的分?jǐn)?shù)；FEs是總評(píng)價(jià)次數(shù)；k是使用過(guò)的評(píng)價(jià)次數(shù)；γ是控制閾值衰減率的參數(shù)(注：max_stepi=2·min_stepi).

根據(jù)式(9)用父代產(chǎn)生子代：

triali=xi+Fi·(xi-xc)+Ostep_i·orth,

(9)

式中：xi和xc分別是父代中的個(gè)體及父代的中心點(diǎn)；Fi是范圍為[-max_step,max_step]均勻分布的隨機(jī)數(shù).為了確保產(chǎn)生的新試探解在閾值范圍之內(nèi)，增加了正交算子.

在大規(guī)模優(yōu)化問(wèn)題中，由于增加了維數(shù)，MPS的種群也會(huì)增加，而這些增加的種群會(huì)使評(píng)價(jià)次數(shù)的有效利用率降低.為了增加這一利用率，MPS的種群大小將會(huì)動(dòng)態(tài)減小如式(10)所示：

pop_sizet=init_pop·((FEs-k)/FEs).

(10)

2.3 分組策略

分組策略是指將原始的大規(guī)模問(wèn)題分解成一系列小且簡(jiǎn)單的子問(wèn)題，用分別優(yōu)化獨(dú)立子問(wèn)題的方式解決.這種被稱(chēng)為分治策略最早是由Descartes在文獻(xiàn)[16]中提出的,后來(lái)Potter在文獻(xiàn)[17]中介紹了分組策略在大規(guī)模問(wèn)題的求解方法，設(shè)計(jì)了協(xié)同進(jìn)化(cooperative coevolution, CC)算法來(lái)改進(jìn)標(biāo)準(zhǔn)遺傳算法的性能.

協(xié)同進(jìn)化策略在早期是靜態(tài)分組的，分組并不會(huì)改變，但是這種方法在解決不可分或部分可分問(wèn)題時(shí)主要依賴(lài)于在初始化時(shí)的分組情況，性能很不穩(wěn)定，所以在改進(jìn)該策略時(shí)使用動(dòng)態(tài)分組方法，包括隨機(jī)動(dòng)態(tài)分組和學(xué)習(xí)動(dòng)態(tài)分組.

2.3.1 基于靜態(tài)分組的協(xié)同進(jìn)化算法

Potter在文獻(xiàn)[17]中提出了協(xié)同進(jìn)化遺傳算法(cooperative coevolutionary genetic algorithms, CCGAs)，但是CCGA-1和CCGA-2只在最高為30維的問(wèn)題中測(cè)試.2004年Frans 等在文獻(xiàn)[18]中將該策略和粒子群優(yōu)化算法(PSO)相結(jié)合，提出了CPSO-SK和CPSO-HK.CPSO-SK將維數(shù)分為K組，每組的維數(shù)是[n/K]，用PSO算法對(duì)每組的維數(shù)進(jìn)行更新.雖然CPSO-SK可以跳出次優(yōu)解，但是在一些測(cè)試函數(shù)中收斂過(guò)快，為了使算法同時(shí)具有PSO的開(kāi)發(fā)能力，CPSO-HK把這兩種算法結(jié)合起來(lái)，一部分使用CPSO-SK算法，將CPSO-SK算法的最優(yōu)解隨機(jī)賦給用PSO優(yōu)化的種群，條件滿(mǎn)足時(shí)停止.

2.3.2 基于動(dòng)態(tài)分組的協(xié)同進(jìn)化算法

對(duì)于不可分問(wèn)題來(lái)說(shuō)，靜態(tài)分組效率十分低.在不可分的測(cè)試函數(shù)中，決策變量存在著一些相互關(guān)系(正相關(guān)或負(fù)相關(guān))，如果把這些相互關(guān)聯(lián)的決策變量一直分在一個(gè)組內(nèi)，結(jié)果并不能收斂到最小.

2.3.2.1 隨機(jī)動(dòng)態(tài)分組

Yang于2008年在文獻(xiàn)[19]中提出了新的協(xié)同進(jìn)化(cooperative coevolution，CC)框架，同時(shí)還加上了自適應(yīng)權(quán)重策略.其中，新的CC框架設(shè)計(jì)成動(dòng)態(tài)改變?nèi)后w結(jié)構(gòu)，這種設(shè)計(jì)增加了相互關(guān)聯(lián)決策變量分在一起優(yōu)化的幾率.此框架的主要思想是將n維的目標(biāo)向量分成m個(gè)s維的子部分(假設(shè)n=m·s)，使用EA算法對(duì)子部分進(jìn)行優(yōu)化；自適應(yīng)權(quán)重策略則是將每個(gè)子部分都設(shè)置一個(gè)權(quán)重，用某一算子對(duì)權(quán)重進(jìn)行優(yōu)化.

文獻(xiàn)[20]對(duì)文獻(xiàn)[19]中的算法進(jìn)行了改進(jìn)，提出了新的多層協(xié)同進(jìn)化算法(multilevel CC algorithm, MLCC)，通過(guò)使用一個(gè)分解池來(lái)使分組的大小和目標(biāo)函數(shù)聯(lián)系的更加緊密. MLCC算法可以自適應(yīng)選擇合適的相互作用層次而不用考慮目標(biāo)問(wèn)題和優(yōu)化階段的特點(diǎn);文獻(xiàn)[7]介紹的JADE算法也使用了分組策略和權(quán)重優(yōu)化的方法來(lái)尋找更加精確的解決方案.同時(shí)，這種解決方法可以加入其他的優(yōu)化算法來(lái)改進(jìn)它們?cè)诖笠?guī)模優(yōu)化問(wèn)題中的性能.Li在文獻(xiàn)[21]中同樣將隨機(jī)分組的協(xié)同進(jìn)化策略與自適應(yīng)權(quán)重用在PSO中，提出了CCPSO算法，并且于次年提出了CCPSO2算法，完善了CCPSO算法，使其在2 000維的問(wèn)題中也有很好的性能.

2.3.2.2 基于學(xué)習(xí)的動(dòng)態(tài)分組

雖然動(dòng)態(tài)隨機(jī)分組策略對(duì)于靜態(tài)分組來(lái)說(shuō)在解決決策變量相關(guān)性問(wèn)題上比較有優(yōu)勢(shì)，但是決策變量的相關(guān)性并不能完全地區(qū)分出來(lái).為了解決不可分問(wèn)題并且減少?zèng)Q策變量之間的相互關(guān)聯(lián)，Ray在2009年提出CCEA-AVP(自適應(yīng)可變分區(qū)的協(xié)同進(jìn)化算法，cooperative coevolutionary algorithm with adaptive variable partitioning).該算法的過(guò)程類(lèi)似于標(biāo)準(zhǔn)的EA算法，首個(gè)M(一般設(shè)為5)次迭代包含所有的變量.在下一次迭代中，使用前50%的個(gè)體計(jì)算關(guān)聯(lián)矩陣，并且將變量分成多個(gè)子種群.當(dāng)變量之間的相關(guān)系數(shù)大于一個(gè)閾值時(shí)就被分到預(yù)先定義的一個(gè)子種群中，之后的每次迭代都把變量按其相關(guān)性分組.

文獻(xiàn)[22]給出了辨識(shí)變量之間的相互關(guān)系的一個(gè)簡(jiǎn)單方法，“best”是目前的最優(yōu)解；“new”是使用CC算法優(yōu)化第i維后的最優(yōu)個(gè)體；“rand”是隨機(jī)從種群中選擇的個(gè)體.根據(jù)這3個(gè)向量產(chǎn)生新的個(gè)體，如式(11)所示：

(11)

若f(x′)比f(wàn)(x)的適應(yīng)度值好，則維數(shù)i和j相互關(guān)聯(lián)的概率增加.

3 測(cè)試函數(shù)

為了對(duì)比算法的性能，一般用統(tǒng)一的測(cè)試函數(shù)來(lái)測(cè)試.文獻(xiàn)[4]介紹了針對(duì)大規(guī)模優(yōu)化問(wèn)題的CEC’08專(zhuān)題會(huì)議函數(shù)測(cè)試集.CEC’10專(zhuān)題會(huì)議上的大規(guī)模優(yōu)化算法測(cè)試集[4]則包含20個(gè)測(cè)試函數(shù).為了更好地代表實(shí)際問(wèn)題范圍廣泛的特性及對(duì)于基于分組的優(yōu)化算法提供更加完備的測(cè)試，提出了CEC’13的測(cè)試函數(shù)集.與CEC’10的區(qū)別在于：CEC’10編寫(xiě)的不可分子部分的大小是均等的；而CEC’13則根據(jù)實(shí)際問(wèn)題使不可分子部分的大小不均等，其相應(yīng)變量的貢獻(xiàn)度也會(huì)有所區(qū)分，并且不可分子部分也會(huì)有所覆蓋，另外還具有病態(tài)、對(duì)稱(chēng)破裂及不規(guī)則等屬性.CEC’13中包含了15個(gè)測(cè)試函數(shù)，這些測(cè)試函數(shù)均有平移和旋轉(zhuǎn)特性.

4 算法對(duì)比

測(cè)試函數(shù)為CEC’08和CEC’10中的測(cè)試函數(shù)，主要測(cè)試的維數(shù)是1 000維，使用評(píng)價(jià)次數(shù)記錄測(cè)試結(jié)果.在對(duì)比算法時(shí)保證最大評(píng)價(jià)次數(shù)相同，對(duì)算法的優(yōu)化結(jié)果進(jìn)行對(duì)比.

采用CEC’08測(cè)試集的主要有CODE、sep-CPM-ES、CSO、CCPSO、DECC-G、CDECC、MTS、CCPSO2、EPUS-PSO、DMS-PSO、MLCC.文獻(xiàn)[21]中將算法CSO、CCPSO2、MLCC、sep-CMA-ES、EPUS-PSO、DMS-PSO進(jìn)行了對(duì)比，并且采用了T檢驗(yàn)方法對(duì)結(jié)果進(jìn)行了統(tǒng)計(jì).DMS-PSO可以準(zhǔn)確地找出f1和f5的全局最優(yōu)，其他5個(gè)函數(shù)的測(cè)試結(jié)果卻沒(méi)有CSO好.在與MLCC比較時(shí)，對(duì)于函數(shù)f4測(cè)試結(jié)果顯示，MLCC明顯優(yōu)于CSO，而測(cè)試函數(shù)f4是shifted Rastrigin function，具有十分多的局部最優(yōu)解，MLCC中針對(duì)每組的優(yōu)化使用的是微分進(jìn)化變異的方法.而CCPSO2的收斂性是這幾個(gè)算法中最快的.sep-CMA-ES和EPUS-PSO在CEC’08的測(cè)試結(jié)果相比來(lái)說(shuō)并不好.文獻(xiàn)[21]同樣是采用T檢驗(yàn)來(lái)顯示測(cè)試結(jié)果，因?yàn)镃CPSO中含有一些用戶(hù)自定義的參數(shù)，所以文獻(xiàn)中對(duì)每個(gè)參數(shù)進(jìn)行了測(cè)試，總的來(lái)說(shuō)，除了函數(shù)f1、f2和f3，CCPSO2的性能要比DECC-G的好.文獻(xiàn)[24]直接列出了CDECC和MTS在CEC’08上的測(cè)試結(jié)果，并使用Friedman檢驗(yàn)了算法之間是否具有顯著性差異，其置信度為0.05.測(cè)試結(jié)果表明CDECC在函數(shù)f6和f7中結(jié)果比較好，在f3、f4和f5沒(méi)有MTS性能好，但是兩者沒(méi)有顯著性差異.

使用CEC’10測(cè)試函數(shù)集主要有DECC-DG、MOFBVE、DECC-DML、DECC-G、DECC-D和MLCC等算法.文獻(xiàn)[23]主要對(duì)比了DECC-DML、DECC-G、DECC-D和MLCC算法的測(cè)試結(jié)果，DECC-DML算法在20個(gè)測(cè)試函數(shù)結(jié)果中有14個(gè)函數(shù)的表現(xiàn)比DECC-G和DECC-D好，在與MLCC的比較中有12個(gè)函數(shù)的測(cè)試結(jié)果比較好，并且在文獻(xiàn)[23]中使用多次運(yùn)行的成功率來(lái)顯示算法的性能.文獻(xiàn)[25]主要是DECC-DG和MOFBVE的對(duì)比，MOFBVE算法的7個(gè)測(cè)試函數(shù)結(jié)果比DECC-DG優(yōu)秀，但是在函數(shù)f11和f16中DECC-DG結(jié)果比較好.

5 結(jié)論

筆者主要總結(jié)了幾個(gè)大規(guī)模優(yōu)化的常用方法,解決大規(guī)模問(wèn)題主要面臨以下難點(diǎn)：搜索空間隨著變量增加以指數(shù)形式擴(kuò)大；問(wèn)題的特性隨著維數(shù)的增加變得更難，例如單峰問(wèn)題可能會(huì)轉(zhuǎn)變?yōu)槎喾鍐?wèn)題；算法在解決問(wèn)題時(shí)花費(fèi)的代價(jià)十分大；對(duì)于協(xié)同進(jìn)化策略來(lái)說(shuō)，變量之間是否可分是主要的問(wèn)題.

(1)分組優(yōu)化問(wèn)題.協(xié)同進(jìn)化策略是解決大規(guī)模問(wèn)題的主要方法，但是，決策變量之間是否可分限制了協(xié)同進(jìn)化策略計(jì)算，雖然使用學(xué)習(xí)的方式來(lái)判斷是否可分，但是該方法的代價(jià)隨著變量的增多而迅速加大.

(2)全部可分和全部不可分問(wèn)題.在大多基準(zhǔn)測(cè)試函數(shù)集中，都有全部可分或不可分問(wèn)題，這些問(wèn)題使用一般協(xié)同進(jìn)化方法效果并不明顯.對(duì)于全部可分問(wèn)題，顯然對(duì)每維單獨(dú)優(yōu)化比較好;但是對(duì)于不可分問(wèn)題，變量的分組方式仍然是一個(gè)難題.

(3)不平衡的測(cè)試函數(shù).在實(shí)際問(wèn)題中，一般都會(huì)遇到子部分分布的不平衡特性，CEC’13大規(guī)模優(yōu)化問(wèn)題測(cè)試集中就針對(duì)該特性設(shè)計(jì)了測(cè)試函數(shù).

(4)更加高維的問(wèn)題.在上述算法中，測(cè)試任務(wù)一般是1 000維的，大規(guī)模優(yōu)化方法可擴(kuò)展性是未來(lái)研究工作的一個(gè)至關(guān)重要的要求.

參考文獻(xiàn)：

[1] MAHDAVI S, SHIRI M E, RAHNAMAYAN S. Metaheuristics in large-scale global continues optimization: a survey [J]. Information sciences, 2015, 295: 407-428.

[2] RAHNAMAYAN S，TIZHOOSHH R, SALAM M M A. A novel population initialization method for accelevating evolutionary algorithms[J]. Computers & mathenmatics with applications, 2007,53(10):1605-1614.

[3] KAZIMIPOUR B, LI X, QIN A K. Initialization methods for large scale global optimization[C]//IEEE Congress on Evolutionary Computation. Cancun: Springer, 2013: 2750-2757.

[4] TANG K, YAO X, SUGANTHAN P N, et al. Benchmark functions for the CEC’2010 special session and competition on large scale global optimization[R]. Hefei: Nature inspired computation and applications laboratory, USTC, China, 2009.

[5] RAHNAMAYAN S, TIZHOOSH H R, SALAMA M M A. Quasi-oppositional differential evolution[C]//IEEE Congress on Evolutionary Computation. Tokyo: Springer, 2007:2229-2236.

[6] WANG H, WU Z, RAHNAMAYAN S. Enhanced opposition-based differential evolution for solving high-dimensional continuous optimization problems[J]. Soft computing, 2011, 15(11): 2127-2140.

[7] ZHANG J, SANDERSON A C. JADE: adaptive differential evolution with optional external archive[J]. IEEE transactions on evolutionary computation, 2009, 13(5):945-958.

[8] WANG H, WU Z, RAHNAMAYAN S, et al. Sequential DE enhanced by neighborhood search for large scale global optimization[C]//IEEE Congress on Evolutionary Computation. Shanghai: Springer, 2010: 1-7.

[9] DAS S, ABRAHAM A, CHAKRABORTY U K, et al. Differential evolution using a neighborhood-based mutation operator[J]. IEEE transactions on evolutionary computation, 2009, 13(3):526-553.

[10] YANG Z, TANG K, YAO X. Scalability of generalized adaptive differential evolution for large-scale continuous optimization[J]. Soft computing, 2011, 15(11):2141-2155.

[11] ZHAO S Z, LIANG J J, SUGANTHAN P N, et al. Dynamic multi-swarm particle swarm optimizer with local search for large scale global optimization[C]//IEEE Congress on Evolutionary Computation. Washington: Springer, 2008: 3845-3852.

[12] CHENG R, JIN Y. A social learning particle swarm optimization algorithm for scalable optimization[J]. Information sciences, 2015, 291(6):43-60.

[13] RAN C, JIN Y. A Competitive swarm optimizer for large scale optimization[J]. IEEE Transactions on Cybernetics, 2014, 45(2):191-204.

[14] BOLUFE R A, FIOL G S, CHEN S. A minimum population search hybrid for large scale global optimization[C]//IEEE Congress on Evolutionary Computation. Sendai: Springer, 2015: 1958-1965.

[15] MONTGOMERY J, CHEN S. A simple strategy for maintaining diversity and reducing crowding in differential evolution[C]//IEEE Congress on Evolutionary Computation. Vienna: Springer, 2012: 692-2699.

[16] DESCARTES R. Discourse on method[J]. Elizabeth haldane & g.r.t.ross the philosophical works of descartes, 1998, 10(1991):11-25.

[17] POTTER M A, JONG K A D. A cooperative coevolutionary approach to function optimization[C]//International Conference on Parallel Problem Solving from Nature. Berlin， Heidelberg： Springer， 1994: 249-257.

[18] FRANS V D B, ENGELBRECHT A P. A cooperative approach to particle swarm optimization[J]. IEEE transactions on evolutionary computation, 2004, 8(3):225-239.

[19] YANG Z, KE T, XIN Y. Large scale evolutionary optimization using cooperative coevolution [J]. Information sciences, 2008, 178(15):2985-2999.

[20] YANG Z, TANG K, YAO X. Multilevel cooperative coevolution for large scale optimization[C]//2008 IEEE Congress on Evolutionary Computation. Washington: Springer, 2008: 1663-1670.

[21] LI X, YAO X. Tackling high dimensional nonseparable optimization problems by cooperatively coevolving particle swarms[C]//2009 IEEE Congress on Evolutionary Computation. Vienna: Springer, 2009: 1546-1553.

[22] WEICKER K, WEICKER N. On the improvement of coevolutionary optimizers by learning variable interdependencies[C]//IEEE Congress on Evolutionary Computation. Washington: Springer, 1999(3):1627-1633.

[23] OMIDVAR M N, LI X, YAO X. Cooperative co-evolution with delta grouping for large scale non-separable function optimization[C]//IEEE Congress on Evolutionary Computation. Shanghai: Springer, 2010: 1-8.

[24] GE H, SUN L, YANG X, et al. Cooperative differential evolution with fast variable interdependence learning and cross-cluster mutation[J]. Applied soft computing, 2015, 36: 300-314.

[25] MAHDAVI S,RAHNAMAYAN S, SHIRIM E. Muctilevel framework for large-scale global optimization[J]. Soft computing, 2017,21(14):4111-4140.