崔鋒哲,王秀坤,滕弘飛,2

(1.大連理工大學計算機科學與技術(shù)學院,遼寧 大連 116024;2.大連理工大學機械工程學院,遼寧 大連 116024)

?

雙系統(tǒng)合作式協(xié)同進化算法求解不可分解函數(shù)

崔鋒哲1,王秀坤1,滕弘飛1,2

(1.大連理工大學計算機科學與技術(shù)學院,遼寧 大連 116024;2.大連理工大學機械工程學院,遼寧 大連 116024)

針對不可分解函數(shù)求解問題,基于合作式協(xié)同進化(cooperative co-evolutionary,CC)框架,發(fā)展一種雙系統(tǒng)協(xié)同進化算法。該算法給出一種雙系統(tǒng)A,B的 CC框架新結(jié)構(gòu)形式及其相應(yīng)的協(xié)調(diào)機制,以增加算法的多樣性和收斂性;給出雙系統(tǒng)A,B各自求解的兩種算法，例如差異進化、改進粒子群算法選擇原則和匹配方式,使該兩種算法具互補性,并且與雙系統(tǒng)A,B各自角色相匹配，目的是提高基于CC框架雙系統(tǒng)算法的計算性能。經(jīng)不可分解函數(shù)集(維數(shù)D=1 000)測試表明,本文算法計算性能(計算精度和標準差)與其他3種典型算法相比,對于其中某些函數(shù)求解占優(yōu),總體上4種算法對函數(shù)集的求解各有所長,具有互補性。

不可分解函數(shù)優(yōu)化; 合作式協(xié)同進化; 雙系統(tǒng)框架; 現(xiàn)代啟發(fā)式算法; 算法選擇和匹配

0　引　言

不可分解函數(shù)優(yōu)化問題的工程背景之一是復雜耦合工程系統(tǒng)優(yōu)化和控制問題,該問題研究有助于揭示復雜耦合系統(tǒng)問題的本質(zhì),開拓求解思路、方法及其應(yīng)用,這是一個重要而又難解問題。單純用現(xiàn)代啟發(fā)式算法(進化算法和群智能算法)求解困難。近年來,用文獻[1]提出的合作式協(xié)同進化算法(cooperative co-evolutionary algorithm,CCEA)的協(xié)同進化 (cooperative co-evolutionary,CC)框架和其他綜合算法求解該問題取得了重大進展[2-4]。

但是,對于測試函數(shù)集(Benchmark)[5-6]的各個測試函數(shù)Fi(i∈n)而言,目前還難有一種算法對每個測試函數(shù)Fi求解結(jié)果都比其他算法更好,而是各種算法對于Benchmark[5-6]中各函數(shù)Fi求解能力各有所長,也即各算法之間具有互補性?，F(xiàn)有的算法對其中某些函數(shù)求解尚缺乏有效求解,遠未達到其最優(yōu)解。

本文算法的基本思想是,基于雙系統(tǒng)CC框架,采用分而治之策略,將系統(tǒng)分解為若干個相對獨立的子系統(tǒng)并行求解。給出新的雙系統(tǒng)CC框架結(jié)構(gòu)形式和協(xié)調(diào)機制[1]。該協(xié)調(diào)機制是針對雙系統(tǒng)CC框架算法改進的協(xié)調(diào)機制,它包括雙系統(tǒng)之間的信息交流,合作個體選擇和其系統(tǒng)評價方式。此外,給出雙系統(tǒng)A,B求解算法選擇和匹配方式。

不可分解函數(shù)的定義[6]:設(shè)一個個體X={xd|d=1,2,3,…,D}表示D維函數(shù)問題的解,如果函數(shù)f(X)的X中任意兩個變量xd是相互關(guān)聯(lián)(耦合)的,則稱f(X)是不可分解函數(shù)。如果其中任意一個變量是相互獨立的,則稱函數(shù)f(X)是可分解的函數(shù)[6]。

1994年,文獻[1]對不可分解函數(shù)Rosenbrock利用合作式協(xié)同進化遺傳算法(cooperative co-evolutionary genetic algorithm,CCGA)求解,函數(shù)變量的合作個體選擇采用(a)最佳合作個體選擇和(b)最佳與隨機個體組合選擇兩種方式,經(jīng)Benchmark[1]測試結(jié)果表明,后者計算結(jié)果較好,原因是它比最佳合作個體選擇更有助于增加種群的多樣性。文獻[3]提出基于CC框架新的協(xié)同進化粒子群算法(novel cooperative co-evolutionary particle swarm optimization,CCPSO2)求解不可分解函數(shù),仿真實驗表明該算法比用進化算法整體優(yōu)化例如基于有效利用種群策略的粒子群算法(efficiency population utilization strategy for particle swarm optimizer,EPUS-PSO)效果好。

基于CC框架算法求解不可分解函數(shù)優(yōu)化問題的研究主要包括以下方面[2-4,7-9]:

(1)發(fā)展CCEA新的求解算法。重點研究基于CC框架的求解算法。2004年,文獻[7]提出了基于CC框架的合作式協(xié)同粒子群算法(cooperative particle swarm optimizer,CPSO),包括CPSO-SK和CPSO-HK。經(jīng)Benchmark[7](維數(shù)D=30)測試結(jié)果表明,CPSO求解不可分解函數(shù)F1,F4的性能要優(yōu)于傳統(tǒng)的粒子群算法(particle swarm optimization,PSO)。2011年,文獻[10]將協(xié)同搜索策略與量子行為的粒子群優(yōu)化算法(quantum-behaved particle swarm optimization,QPSO)相結(jié)合,提出了具有量子行為的協(xié)同粒子群優(yōu)化算法(MQPSO)。經(jīng)Benchmark (D=50)測試結(jié)果表明,MQPSO_20求解不可分解函數(shù)F2的性能要優(yōu)于傳統(tǒng)的QPSO和標準粒子群算法(standard particle swarm optimization,SPSO)。

(2)基于CC框架的不可分解函數(shù)變量集合對半劃分的變量分組。2005年,文獻[8]提出了新的合作式協(xié)同差異進化算法(cooperative co-evolutionary differential evolution,CCDE),并提出將變量集合對半分組策略。經(jīng)Benchmark[9]中的函數(shù)F1-F5(D=100)測試結(jié)果表明,CCDE相對于傳統(tǒng)的差異進化算法(differential evolution,DE)、遺傳算法(genetic algorithm,GA)和CCGA具有更好的計算性能。

2008年文獻[2]提出和探索的上述動態(tài)變量分組工作對于求解高維不可分解函數(shù)是一項新的貢獻,近年來后續(xù)研究也取得進展。該研究意義在于涉及復雜耦合系統(tǒng)的各子系統(tǒng)間耦合和協(xié)同效應(yīng)分析,以及如何處理的核心問題。該問題一旦解決,將有深遠影響。當然,即使不計計算代價,也尚有不少難關(guān)有待攻克。

接下來,介紹雙系統(tǒng)(雙種群)進化算法研究現(xiàn)狀。

近年來有些研究學者研究了現(xiàn)代啟發(fā)式算法的雙種群算法,例如研究雙種群差異進化算法(differential evolution with double population,HDEDP)[13]和雙種群遺傳算法(dual population genetic algorithm,DPGA)[14],該雙種群算法不是基于CC框架。前者用于求解3個較簡單的工程設(shè)計優(yōu)化測試題(焊接梁設(shè)計,壓力容器設(shè)計和耐張力絕緣串設(shè)計問題),案例驗證表明該算法是有效的。后者用于求解多模態(tài)函數(shù)優(yōu)化問題,采用Benchmark測試集[9](與本文的Benchmark[5-6]不同)求解的維數(shù)D=30,計算結(jié)果與其他文獻相比,各有短長。

此外,文獻[15]發(fā)展了一種基于CC框架雙系統(tǒng)(雙種群)進化算法,簡稱雙簧管-CCEA (Oboe-CCEA),用于求解衛(wèi)星艙組件布局優(yōu)化問題。值得說明該算法是針對衛(wèi)星艙組件布局優(yōu)化問題,而不是針對不可分解函數(shù)求解,沒有討論不可分解函數(shù)求解問題。本文與Oboe-CCEA在雙系統(tǒng)結(jié)構(gòu),協(xié)調(diào)機制(包括信息交流合作個體選擇,及其評價),以及雙系統(tǒng)求解算法方面有不同,在文后加以說明。目前,采用這種基于CC框架的雙系統(tǒng)協(xié)同進化算法求解不可分解函數(shù)的討論尚少見。

綜上所述,針對不可分解函數(shù)求解問題,雖然基于CC框架算法(CCEA)研究取得進展,但是求解Benchmark中某些函數(shù),結(jié)果距其最優(yōu)解有相當大的距離。各種算法對于Benchmark中各種函數(shù)求解各有所長。本文探討如何提高基于雙系統(tǒng)CC框架算法求解不可分解函數(shù)問題計算性能。本文目的是發(fā)展一種雙系統(tǒng)合作式協(xié)同進化算法,對于Benchmark中某些函數(shù)求解明顯有效,與現(xiàn)有的經(jīng)典算法具互補性,共同有效地求解盡量多的不可分解函數(shù)。本文求解變量維數(shù)D=1 000。值得說明,動態(tài)變量的分組方式研究是一項很有意義的工作,有待以后討論。

本文重點研究如何提高基于CC框架算法或CCEA求解不可分解函數(shù)優(yōu)化問題的計算性能,從以下兩方面進行研究:①發(fā)展一種新的雙系統(tǒng)CC的結(jié)構(gòu)形式及相應(yīng)的其協(xié)調(diào)機制;②給出CC框架雙系統(tǒng)A,B各自求解的現(xiàn)代啟發(fā)式算法(例如DE,PSO)的選擇和匹配方法。本文著重研究如何提高求解不可分解函數(shù)問題計算性能,采用通用Benchmark[5-6]評價指標:計算精度和魯棒性(標準差),采用通用Benchmark[5-6]測試(變量維數(shù)D=1 000)。文獻[3-4,16]典型算法的評價指標不涉及計算效率或計算復雜度。

1　本文算法DCCDE/PSO

1.1本文DCCDE/PSO算法特點

針對不可分解函數(shù),本文發(fā)展一種雙系統(tǒng)協(xié)同進化算法(dual-system cooperative co-evolutionary differential evolution particle swarm optimization DCCDE/PSO),它是基于文獻[1]提出CCEA的CC框架,與CCEA不同之處是基于雙CC框架。本文基于雙系統(tǒng)A,B的CC框架算法與Oboe-CCEA主要不同之處:

(1)雙系統(tǒng)CC框架的結(jié)構(gòu)形式不同:Oboe-CCEA對A系統(tǒng)沒有采用CC框架,采用整體優(yōu)化和粗-細變粒度策略,雖然有助于A系統(tǒng)的系統(tǒng)優(yōu)化問題整體求解,但是其中某些參數(shù)需人工設(shè)置,比較麻煩,所以本文算法的 A,B系統(tǒng)都是基于CC框架,并行計算。本文A系統(tǒng)不用整體優(yōu)化,所以沒有采用變粒度策略。

(2)協(xié)調(diào)機制不同。①Oboe-CCEA采用最佳合作個體選擇方式[17],不利于迭代前期增加算法的多樣性。在迭代前期,本文采用最佳與隨機個體混合的合作個體選擇的協(xié)調(diào)機制[17],增加種群的多樣性。在迭代后期,本文利用精英保留策略和精英解集檔案(Archive)[18]策略,與Oboe-CCEA不同,A系統(tǒng)從該精英解集檔案中選擇合作個體,有助于算法的收斂性。②A,B系統(tǒng)之間雙向信息交流。本文采用個體遷移方式,而Oboe-CCEA采用部分子個體或個體方式遷移。③完整解的評價。Oboe-CCEA采用A系統(tǒng),本文用A,B系統(tǒng)各自評價。本文目的是提高算法計算精度。因為Oboe-CCEA是B系統(tǒng)基于一個CC框架,發(fā)揮B系統(tǒng)的子系統(tǒng)之間的協(xié)同效應(yīng)。而本文是基于兩個CC框架,不僅發(fā)揮A,B系統(tǒng)各自子系統(tǒng)之間的協(xié)同效應(yīng),而且還發(fā)揮A,B系統(tǒng)之間的互補效應(yīng),有助于提高算法的收斂性。因為本文算法和Oboe-CCEA分別采用兩個或一個CC框架,自然前者比后者耗時多。Oboe-CCEA既沒有討論也不是針對不可分解函數(shù)求解問題,所以文后Benchmark測試沒有與Oboe-CCEA對比。

(3)本文給出雙系統(tǒng)CC框架中A,B系統(tǒng)各自求解算法(DE,PSO)的選擇和匹配方法。Oboe-CCEA的系統(tǒng)A,B都采用GA,沒有討論此問題。本文算法的系統(tǒng)A采用多樣性好、搜索能力強的DE[19]求解;系統(tǒng)B采用具有搜索初期搜索速度快和克服后期易早熟的較好性能的探測粒子群(detecting particle swarm optimization,DPSO)[20]求解,這兩種算法互補性好,并分別與系統(tǒng)A,B功能(角色)相匹配。

1.2本文算法DCCDE/PSO基本框架

本文算法的雙系統(tǒng)框架如圖1所示。

圖1　DCCDE/PSO框架圖Fig.1　Framework of DCCDE/PSO

1.3基于CC框架的系統(tǒng)分解

將系統(tǒng)或測試函數(shù)Fi個體置于CC框架,將測試函數(shù)Fi采用橫向分解方式,將它截成E個子函數(shù)表達式(視為子系統(tǒng)或子個體),則該函數(shù)Fi可以表示為Fi(X),其中X={xi| i∈I=1,2,…,n},Xe={xie| i∈I,e∈E=1,2,…,E} 即將X分解為E個子系統(tǒng)。

附帶說明,上述Fi的分解,相當于變量集合X分組。X={Xp},分成p個相對獨立的小組,p=2,3,…,P,1

1.4本文雙系統(tǒng)DCCDE/PSO協(xié)調(diào)機制

本文雙系統(tǒng)CC框架的協(xié)調(diào)機制是基于CCEA的隱式協(xié)調(diào)機制。CCEA的隱式整體協(xié)調(diào)機制與合作個體的選擇相關(guān),常用的合作個體選擇方法有:隨機選擇、合作者群體選擇、最優(yōu)個體選擇[17]以及檔案(Archive)[16]方法。本文算法將A,B系統(tǒng)分解為E個子系統(tǒng)Ae,Be,e=1,2,…,E,Ae之間,Be之間,存在耦合關(guān)系,以及A,B之間,存在互補關(guān)系。需要在進化過程中保持整體協(xié)調(diào)一致性。

設(shè)本算法系統(tǒng)A,B各自的迭代最大評價次數(shù)為2 500×D,給出迭代前期和后期的判別式

(1)

式中,m和ε分別表示間隔代數(shù)和許用值。

為了增加算法收斂性,A,B系統(tǒng)還采用精英保持策略,并建立精英解集檔案(Archive)[16]。該精英解集檔案作用是,A系統(tǒng)通過該檔案向B系統(tǒng)遷移精英個體,增加算法收斂性。在迭代后期,A系統(tǒng)基于CC框架的合作個體選擇是從精英解集檔案(Archive)中選擇,組成完整解,以提高算法的收斂性。最終使B系統(tǒng)逼近擔任主要角色的A系統(tǒng),A系統(tǒng)逼近P系統(tǒng)(原問題)。本文個體遷移的時機、數(shù)量參見文獻[15]。

1.5CC框架中求解的混合算法選擇和匹配

本文試算經(jīng)驗表明,算法選擇應(yīng)該與雙系統(tǒng)的A,B擔任的角色相匹配。本文算法的A,B系統(tǒng)擔任角色和關(guān)系:一是A,B系統(tǒng)之間既屬于協(xié)同關(guān)系,又屬于主輔關(guān)系;二是B為A提供優(yōu)良的系統(tǒng)完整解(含子個體)資源;三是A系統(tǒng)是最終決策者;四是本文算法收斂過程使B逼近A,A逼近P(原問題)。以上是混合算法選擇和匹配的依據(jù)。

本文系統(tǒng)A,B分別采用DE[19]和DPSO[20]算法求解,這是經(jīng)過采用不同的算法組合(例如DE/PSO,DE/DE,PSO/PSO等)試驗獲得。DE具有全局和局部并行直接搜索、多樣性好的搜索性能,適于求解高維、非線性函數(shù)問題。DPSO[20]是一種改進的PSO,它在PSO種群中選少量的子種群作為探測粒子,做收斂螺旋軌跡探索,從而實現(xiàn)一種普通粒子群體搜索與探測粒子個體搜索協(xié)同的搜索行為,除保持PSO的全局搜索能力好和搜索初期搜索速度快的特點而外,并較好地克服PSO算法后期收斂速度慢,局部搜索能力較弱的缺陷。此外,本文針對DPSO種群的最優(yōu)位置(Globalbest,Gbest)采用Lévy變異算子,可以進一步提高克服容易早熟的能力。

綜上所述,基于CC框架的系統(tǒng)分解,本文的雙系統(tǒng)協(xié)調(diào)機制在迭代前期增加多樣性,在迭代后期增加收斂性。系統(tǒng)B為系統(tǒng)A提供更多的全局搜索的完整解(含子個體),而系統(tǒng)A利用合作個體選擇方式和求解算法DE的多樣性和收斂性兼優(yōu)的特點實現(xiàn)進一步優(yōu)化。在迭代后期,利用精英解集檔案的合作個體選擇構(gòu)成A系統(tǒng)的精英個體,A系統(tǒng)向B系統(tǒng)輸送精英個體。通過雙系統(tǒng)之間個體相互遷移,不斷進化。算法DE和DPSO二者在迭代過程發(fā)揮各自所長和互補性,并與A,B系統(tǒng)承擔角色相匹配。本文算法不僅發(fā)揮雙系統(tǒng)A,B的各自子系統(tǒng)的協(xié)同效應(yīng)(有別于Oboe-CCEA主要發(fā)揮B系統(tǒng)子系統(tǒng)的協(xié)同效應(yīng)),而且更好地發(fā)揮系統(tǒng)A,B之間的協(xié)同效應(yīng),目的是提高其計算能力。最終使系統(tǒng)B逼近系統(tǒng)A,系統(tǒng)A逼近原系統(tǒng)P。

1.6基于CC框架的系統(tǒng)分解和變量分組

CCEA基于CC框架的系統(tǒng)分解如第1.3節(jié)所述。將Benchmark中測試函數(shù)Fi的個體分解為若干個子個體,也即相當于從系統(tǒng)角度實現(xiàn)變量分組。變量分組分兩種:一種是靜態(tài)(固定)變量分組,分組后不再改變；另一種是動態(tài)(可變)變量分組[2]。一般情況下,后者比前者有效,當然也需付出代價。本文采用前者方式,意在探討在變量靜態(tài)分組情況下,如何提高本文算法求解不可分解函數(shù)的計算性能,并借此分析不可分解函數(shù)Fi的函數(shù)性質(zhì),以及分析本文算法求解各Fi的能力好或差的原因。

1.7算法流程

DCCDE/PSO流程的偽代碼如下所示。

Algorithm:Pseudocode of DCCDE/PSO

1.{Pe}←DecomposedSystem(P),P={Pe},e∈S

2.{Ae},{Be}←CopySystem(PPe),A={Ae},B={Be},e∈S//the number of AAeis not equal to the number of BBe,that is the subsystem number of system A is not equal to the subsystem number of system B.

3.Ae,Be←initPop()//Random initialize population system A and B,respectively;

4.K=1

5.While (termination criterion not met)do

6.A,B←ParallelComputation()

7.Parallel.for each subsystem Aedo

8.OneDESolve(Ae)//each subsystem AeParallel computation

9.End for

10.Parallel.for each subsystem Bedo

11.OneDPSOSolve(Be)//each subsystem BeParallel computation

12.End for

13.IfK

16.else

19.End if

20.If migration conditions is met do

27.K=K+1

28.End While

2　數(shù)值仿真實驗

2.1測試函數(shù)

本文算法與目前典型的算法CCPSO2[3],改進的協(xié)方差矩陣自適應(yīng)進化策略(smallest possible modification covariance matrix adaptation evolution strategy,sep-CMA-ES)[16]和CBCC-DG[4]這3種典型算法計算結(jié)果相比較。采用相同的Benchmark[5-6]和該Benchmark要求的評價指標:計算精度(誤差平均值MeanΔf)、魯棒性(標準差standard deviation,Std)和相同的函數(shù)變量維數(shù)(dimension,D),本文D=1 000。最大迭代次數(shù)Kmax=5 000×D。

選擇文獻[3,16]采用的Benchmark測試函數(shù)[5]中具代表性函數(shù)F2,F3,F5,F7,F3r,F4r,F5r,F6r,計8個不可分解函數(shù),文獻[3]中的Benchmark[5]中測試函數(shù)F3r,F4r,F5r,F6r經(jīng)坐標變換,使該函數(shù)更復雜難解;文獻[4]采用的Benchmark測試函數(shù)[6]中的17個不可分解函數(shù)F4-F20進行測試。兩Benchmark共計25個測試函數(shù)。

下面較詳細介紹不可分解函數(shù)數(shù)學定義[6]。

定義1如果函數(shù)f(x)滿足式(2)的條件,則稱函數(shù)f(x)是可分解的函數(shù)。

(2)

定義2如果函數(shù)f(x)任意兩個變量是相互關(guān)聯(lián)的,則稱f(x)是不可分解函數(shù)。

有關(guān)測試函數(shù)的其他性質(zhì)參見文獻[5-6],其中有些測試函數(shù)性質(zhì),文后進行分析。

本文DCCDE/PSO算法設(shè)置如下:

(1)每個測試函數(shù)都獨立隨機運行25次,試驗結(jié)果取25次計算的誤差平均值(計算結(jié)果與最優(yōu)解的誤差的平均值Mean Δf)。誤差Δf=f(x)-f(x*),x*為測試函數(shù)的最優(yōu)解。

(2)設(shè)置雙系統(tǒng)A,B各自的種群規(guī)模M為25。本文采用靜態(tài)變量分組,本文A系統(tǒng)橫向分解子系統(tǒng)數(shù)目EA=5(即將函數(shù)Fi表達式截斷后的數(shù)目),B系統(tǒng)橫向分解子系統(tǒng)數(shù)目EB=2EA。A,B種群規(guī)模M數(shù)目分別與EA,EB數(shù)目對應(yīng)。

(3)根據(jù)文獻[19]對Benchmark[5-6]中函數(shù)多次測試推薦:取DE[19]的交叉因子CR=0.9,縮放因子F=0.5,采用的變異交叉策略為Rand1Exp;同樣根據(jù)文獻[20]的推薦:取DPSO[20]的慣性系數(shù)W=0.9,加速度系數(shù)C1=C2=2.05,探測粒子數(shù)Ms=1,探測粒子一次螺旋路徑搜索的采樣點個數(shù)T=10;螺旋運動學習因子Cs1=Cs2=0.8。

(4)文獻[5-6]函數(shù)最大評價迭代次數(shù)分別為Kmax=5 000×D,Kmax=3 000×D (D為變量的維數(shù))。許用值ε=0.5,間隔代數(shù)m=1 000。

(5)本文算法數(shù)值實驗運行環(huán)境為Windows7操作系統(tǒng),Inter(R)I7-3770處理器,8GB內(nèi)存。

2.2結(jié)果和討論

2.2.1結(jié)果

圖2～圖5分別給出了本文算法、CCPSO2和sep-CMA-EM 3種算法求解坐標軸旋轉(zhuǎn)的F3r,F4r,F5r,F6r(1 000維)不可分解函數(shù)誤差平均值(Mean Δf)進化曲線圖。

圖2　F3r誤差平均值(MeanΔf)收斂曲線Fig.2　Diagram of F3r Mean Δf convergence curve

圖3　F4r誤差平均值(MeanΔf)收斂曲線Fig.3　Diagram of F4r Mean Δf convergence curve

本文算法與目前典型的CCPSO2[3],sep-CMA-ES[16]和CBCC-DG[4]的3種算法計算性能的兩評價指標為計算精度(Mean Δf)和魯棒性(標準差Std)。采用上述經(jīng)典算法的評價指標和測試方法是:先進行T檢驗,考慮Mean Δf和Std,計算P-Value。當P-Value≥0.05,認為兩算法相當;當

P-Value<0.05,兩算法不相當。這時,兩種算法比較采用Mean Δf評價,愈小愈好。以下兩算法之間比較,采用此方法,每種算法各25次計算。同樣,本文算法與CCPSO2[3]或sep-CMA-ES[16]通過Benchmark[5](包含8個不可分解函數(shù))測試比較,以及本文算法與CBCC-DG[4]通過Benchmark[6](包含17個不可分解函數(shù))測試比較,結(jié)果見表1。

圖4　F5r誤差平均值(MeanΔf)收斂曲線圖Fig.4　Diagram of F5r Mean Δf convergence curve

圖5　F6r誤差平均值(Mean Δf)收斂曲線圖Fig.5　Diagram of F6r Mean Δf convergence curve

Benchmark函數(shù)F2F3F5F7F3rF4rF5rF6rBenchmark[5]CCPSO2[3]××○●×○○×本文算法●●○×●○○●sep-CMA-ES[16]×●○×○●●○本文算法●×○●○××○函數(shù)F4F5F6F7F8F9F10F11F12F13F14F15F16F17F18F19F20Benchmark[6]CBCC-DG[4]●○×○●●●×××●●○××××本文算法×○●○×××●●●××○●●●●

注:1)●表示占優(yōu),○表示相當,×表示較差; 2)陰影背景函數(shù)表示難解函數(shù)。

表2～表4分別給出本文算法與CCPSO2[4],sep-CMA-ES[16]和 CBCC-DG[4]算法計算結(jié)果數(shù)據(jù)比較。

表5給出本文算法對Benchmark[5]Fi(D=1 000)中8個不可分解函數(shù)計算結(jié)果排序,標記出用箱線圖(Boxplot)中的5個統(tǒng)計量:1ST(Best),7th,13th(Median),19th,25th(Worst)的Δf,以及25次計算的Mean Δf和Std。用于說明本文的Mean Δf和Std來源。

上述其他兩種算法基于單系統(tǒng)CC框架算法的迭代最大評價次數(shù)為5 000×D,由于本文算法采用雙系統(tǒng)結(jié)構(gòu),因此本算法系統(tǒng)A,B各自的迭代最大評價次數(shù)為2 500×D,以示公平。

表2　本文算法DCCDE/PSO 與CCPSO2算法25次計算結(jié)果比較(D=1 000)

注:1)F7的最優(yōu)解未知,期望f(x*)值越小越好,CCPSO2計算結(jié)果引自文獻[3]; 2)DCCDE/PSO與CCPSO2采用雙側(cè)T檢驗,α=0.05,如果二者算法的統(tǒng)計結(jié)果有顯著性差異,則最好的計算結(jié)果用黑粗體表示。

表3　本文算法DCCDE/PSO 與sep-CMA-ES 算法25次計算結(jié)果比較(D=1 000)

注:1)DCCDE/PSO與sep-CMA-ES采用雙側(cè)T檢驗,α=0.05,如果二者算法的統(tǒng)計結(jié)果有顯著性差異,則最好的計算結(jié)果用黑粗體表示。

表4　本文算法DCCDE/PSO 與CBCC-DG 算法25次計算結(jié)果比較(D=1 000)

表5　本文DCCDE/PSO算法對8個不可分解函數(shù)25次計算結(jié)果(D=1 000)1)

注1):1ST表示最優(yōu)計算結(jié)果(Best),13th表示中位數(shù)(Median),25th表示最差計算結(jié)果(Worst)。

2.2.2討論

本文算法與CCPSO2[3],sep-CMA-ES[16],CBCC-DG[4]3種典型算法計算結(jié)果見表1～表5,以下對其進行比較和討論。

(1)不可分解函數(shù)F3r-F6r迭代的MeanΔf收斂曲線的討論

按T檢驗和單評價指標MeanΔf評價Benchmark計算結(jié)果,由圖2～圖4可見,當D=1 000時,對于F3r,F6r收斂曲線,本文算法(DCCDE/PSO)與CCPSO2收斂速度相當,而本文算法MeanΔf值最小。對于F4r收斂曲線,與CCPSO2相比,本文算法收斂速度較慢。對于F5r收斂曲線,本文算法在迭代前期趨向收斂較慢,但是在迭代后期下降幅度較大,本文算法MeanΔf值最小,體現(xiàn)了本文算法潛在的較強的計算性能,在圖4中體現(xiàn)尤為明顯。這主要歸因于本文算法采用的雙系統(tǒng)框架,相應(yīng)的協(xié)調(diào)機制,以及雙系統(tǒng)之間的協(xié)同效應(yīng)。本文算法與sep-CMA-ES相比,后者收斂或停滯都較快,例如對F4r,F5r收斂非?？?而對F3,F6r停滯特別快。sep-CMA-ES收斂或停滯比較快的原因是,它利用協(xié)方差矩陣的主元分析,構(gòu)造與前一代搜索方向共軛的新的演化路徑,它的協(xié)方差矩陣是對角陣,有利于引導著種群變異方向引導,當然計算也較復雜。

(2)本文與其他3種算法計算結(jié)果討論

本文算法與CCPSO2[3],sep-CMA-ES[16]和CBCC-DG[4]3種算法計算結(jié)果比較見表1。采用T檢驗和單評價指標MeanΔf評價。

本文對Benchmark[5]和Benchmark[6]中25個函數(shù)Fi進行測試,采用如下方法。

當算法的P-value≥0.05,兩算法相當。對于表2函數(shù)(F5,F4r,F5r),P-value≥0.05,認為本文算法與CCPSO2相當。對于表3函數(shù)(F5,F3r,F6r),同理,本文算法與sep-CMA-ES相當。對于表4函數(shù)(F5,F7,F16),同理,本文算法與CBCC-DG相當。

當算法的P-value<0.05,只考慮MeanΔf值,MeanΔf愈小愈好。

1)本文算法與CCPSO2[3]相比,按照MeanΔf指標進行比較,在Benchmark[5]8個函數(shù)中,①本文算法占優(yōu)的有4個函數(shù),其中對于F3,本文算法的MeanΔf比CCPSO2高1個數(shù)量級,Std小1個數(shù)量級；②相當?shù)挠?個函數(shù)。③本文算法不如CCPSO2的函數(shù)有1個,如表1所示。

2)本文算法與sep-CMA-ES[16]相比,按照MeanΔf指標進行比較,本文算法求解的8個不可分解函數(shù)[5]中：①本文算法占優(yōu)的有2個函數(shù)；②相當?shù)挠?個函數(shù)F5,F3r,F6r；③本文算法不如sep-CMA-ES函數(shù)有3個,見表1。

3)本文算法與CBCC-DG[4]相比,按照MeanΔf指標進行比較,在Benchmark[6]17個不可分解函數(shù)中：①本文算法占優(yōu)的有8個函數(shù)；②相當規(guī)則函數(shù)有3個函數(shù)；③本文算法不如CBCC-DG函數(shù)有6個函數(shù),如表1所示。

本文算法的MeanΔf和Std兩項都優(yōu)于CBCC-DG的8個函數(shù),其中5個函數(shù)(F6,F11,F13,F18,F20)為多峰不可分解函數(shù),其余3個為單峰不可分解函數(shù)。對于F11,,本文算法的MeanΔf比CBCC-DG的高14個數(shù)量級,Std小15個數(shù)量級。對于F18,本文算法的MeanΔf比CBCC-DG高6個數(shù)量級,Std小7個數(shù)量級。

(3)算法比較結(jié)果分析

首先分析本文算法對于某些函數(shù)表現(xiàn)差的原因如下:

1)CCPSO2對于F7優(yōu)于本文算法的原因是,F7是最優(yōu)解未知,內(nèi)含有雙重隨機干擾,函數(shù)面崎嶇不平,屬于多峰的不可分解函數(shù)。CCPSO2計算結(jié)果表明,雖然CCPOS2是基于一個CC框架,但是在優(yōu)化的前期和后期,采用動態(tài)隨機調(diào)整變量(動態(tài))分組方式(這比本文的靜態(tài)分組效果較好),并采用基于柯西-高斯相結(jié)合的變異算子更新粒子的鄰接位置(Lbest),以及采用環(huán)形的結(jié)構(gòu)定義局部鄰域,增加了算法的空間探索能力,適用于求解多峰函數(shù)F7。本文算法不具有該針對性搜索性能。

2)sep-CMA-ES對于F4r,F5r優(yōu)于本文算法原因是,該算法采用子代種群規(guī)模變化和自適應(yīng)的變異兩種策略。對于F5r,屬于多峰、坐標軸旋轉(zhuǎn)的不可分解函數(shù),該函數(shù)對于算法子代種群規(guī)模增加不敏感,所以該算法采用自適應(yīng)的變異策略,通過比較當代與父代的均值之間的關(guān)系,更新協(xié)方差矩陣來實現(xiàn)個體變異方向,這種個體變異方向增加了算法的探索能力。對于F4r,屬于多峰、坐標軸旋轉(zhuǎn)函數(shù)。sep-CMA-ES改變求解策略,改采用不斷擴大子代種群規(guī)模,才能在個體均值鄰域周圍更加有效的采集樣本,以獲得較好的計算結(jié)果。本文算法不具有該算法這種針對性的搜索性能。但是sep-CMA-ES算法采用上述何種策略,需要算法對種群規(guī)模變化敏感性進行試算,需要付出相應(yīng)的計算代價。

3)CBCC-DG在17個不可分解測試函數(shù)中,有6個函數(shù)F4,F8,F9,F10,F14,F15優(yōu)于本文算法,其中F14,F15為完全不可分解函數(shù),前者為單峰,后者為多峰,其余的4個為非完全不可分解函數(shù)。以下討論對于F14,F15優(yōu)于本文算法的原因,CBCC-DG算法采用變量自動動態(tài)分組策略,即耦合變量差分分組策略。該策略包含分組結(jié)構(gòu)的識別和優(yōu)化兩個部分,分組結(jié)構(gòu)的識別是按照文獻[4]中定理1:按順序比較第一個變量和其余變量的關(guān)聯(lián)關(guān)系,依次循環(huán)迭代,直到檢測所有變量與第一個變量的關(guān)聯(lián)關(guān)系,此時第一個子種群建立完畢。如果沒有探測到關(guān)聯(lián)關(guān)系,那么該變量被認為或許是可分解的變量,則將它分到其他不同的組,將上述探測過程循環(huán)迭代,直到探測到所有變量之間的關(guān)聯(lián)關(guān)系。但是實現(xiàn)這種兩兩變量組合識別方式相當耗時。CBCC-DG以此量化每個子種群對于測試函數(shù)適應(yīng)度函數(shù)值的貢獻并依次分配計算資源。另外,按上述耦合變量差異進行變量分組策略,對F14和F15以及其余4個函數(shù)進行變量分組,力求使測試函數(shù)的各變量分組相對獨立,有助于優(yōu)化,提高計算精度。本文沒有采用這種動態(tài)變量分組策略,所以對上述6個函數(shù)不占優(yōu)。本文基于CCEA的CC框架進行系統(tǒng)分解(靜態(tài)變量分組),CC框架的系統(tǒng)分解的特點是,并不追求子系統(tǒng)之間(變量分組)嚴格地相對獨立,而是用隱式的協(xié)調(diào)機制實現(xiàn)優(yōu)化,缺乏從使各變量分組相對獨立角度來提高其計算精度的能力。

下面分析本文算法對于某些函數(shù)表現(xiàn)好的原因:綜上所述,采用該Benchmark常用的評價指標和方法:經(jīng)T檢驗之后,按照MeanΔf評價指標評價。對于Benchmark[5]8個函數(shù)計算結(jié)果,與CCPSO2相比,本文占優(yōu)的函數(shù)有F2,F3,F3r,F6r,4個。與sep-CMA-ES相比,本文占優(yōu)的函數(shù)有F2,F7,2個。對于Benchmark[6]17個函數(shù),與CBCC-DG相比,本文占優(yōu)的函數(shù)有F6,F11,F12,F13,F17,F18,F19,F20,8個。本文算法與以上3種算法之間相當函數(shù)如前所述。

沒有發(fā)現(xiàn)能有一種算法求解所有的Fi(i∈I)結(jié)果比其他算法都好的結(jié)果。例如文獻[3]指出CCPSO2[3]與sep-CMA-ES[16]相比,在8個測試函數(shù)中,前者占優(yōu)的2個,后者占優(yōu)的2個,相當?shù)?個,可見,這兩種算法是互補的。

由此可見,本文算法具有一定的既可求解單峰、復雜多峰函數(shù)例如F18,F20,也可求解坐標系旋轉(zhuǎn)變換的不可分解的復雜函數(shù)能力。例如本文算法對于4個坐標系旋轉(zhuǎn)變換的函數(shù)中的兩個函數(shù)F3r,F6r占優(yōu),F4r,F5r的求解不足。另外,由此可見本文算法、其他3種典型算法(CCPSO2[3],sep-CMA-ES[16],CBCC-DG[4])這4種算法相互之間具有互補性。

本文算法對于上述函數(shù)表現(xiàn)好的主要原因:一是sep-CMA-ES屬于進化策略算法,不是基于CC的算法,而本文算法是基于CC框架的雙系統(tǒng)結(jié)構(gòu)。本文算法在迭代前期,采用最佳與隨機混合的合作個體選擇,有助于增加種群的多樣性。后期基于精英解集存檔合作個體選擇,有助于增加算法的收斂性。二是CCPSO2和CBCC-DG是基于單系統(tǒng)CC框架,本文算法基于雙系統(tǒng)CC框架,給出了新的雙系統(tǒng)結(jié)構(gòu)和相應(yīng)的協(xié)調(diào)機制(包括信息交流方式,合作個體選擇以及評價方式),發(fā)揮了雙系統(tǒng)的各自的各子系統(tǒng)之間協(xié)同效應(yīng),以及系統(tǒng)A,B之間的互補效應(yīng)。三是求解算法的選擇和匹配,本文利用A,B系統(tǒng)求解的DE和DPSO各自的特點和互補性,并與A,B系統(tǒng)的角色相匹配。

這幾種算法對于兩個Benchmark[5-6]中25個不同函數(shù)(D=1 000)的求解各有短長,本文算法與其他3種算法相比,本文算法對Benchmark中某些函數(shù)計算結(jié)果占優(yōu),總體上各算法之間具有互補性。以往的研究表明,對不可分解函數(shù)Benchmark函數(shù)集[5-6]求解的各種算法計算結(jié)果的比較表明[2-5],難有一種算法對每個測試函數(shù)Fi求解比其他算法都好,一般是各有短長,這也許可借用無免費午餐觀點來解釋。

附帶說明,關(guān)于基于CC框架與非CC框架算法之間的對比問題,本文未涉及,不過文獻[3]表明,算法CCPSO2(前者)與算法EPUS-PSO(后者),用同一種PSO求解,經(jīng)Benchmark[5]的測試結(jié)果表明,前者優(yōu)于后者,也即表明文獻[3]的基于CC系統(tǒng)分解CCPSO2優(yōu)于整體優(yōu)化求解的PSO方法。

3　結(jié)論與展望

不可分解函數(shù)優(yōu)化是一個重要而又難解問題,涉及復雜耦合系統(tǒng)求解的本質(zhì)問題,雖然Benchmark中的不可分解函數(shù)為無約束非線性函數(shù),但是它的工程背景之一是工程耦合系統(tǒng)的優(yōu)化與控制(一般屬于帶約束的非線性、非連續(xù)、多模態(tài)函數(shù)),因此研究如何提高基于CC框架算法(例如CCEA)求解高維不可分解函數(shù)能力,分析各種不可分解函數(shù)Fi及其特有函數(shù)的性質(zhì),以及探索其求解策略和應(yīng)用,是有益的。這是一個引人關(guān)注而又困難的問題。為了提高CCEA算法求解不可分解函數(shù)問題計算性能,本文在前人CCEA和Oboe-CCEA,以及不可分解函數(shù)求解算法的工作基礎(chǔ)上,針對不可分解函數(shù)的求解,發(fā)展一種基于CC框架的雙系統(tǒng)協(xié)同進化算法(DCCDE/PSO)。

本文主要工作是:

(1)發(fā)展一種新的雙系統(tǒng)A,B的 CC框架結(jié)構(gòu),以及相應(yīng)的協(xié)調(diào)機制(包括信息交流、合作個體選擇及其評價)。在迭代前期采用選擇隨機和最佳合作個體方式組成系統(tǒng)完整解,有助于增加算法的多樣性。為了增加算法收斂性,A,B系統(tǒng)還采用精英保持策略,并建立精英解集檔案(Archive)。在迭代后期,從精英解集檔案(Archive)中選擇合作個體方式,有助于增加算法的收斂性。本文迭代前期和后期A,B之間信息交流都采用個體遷移方式實現(xiàn),以及采用基于CC框架雙系統(tǒng)A,B的各自評價方式評價。本文雙系統(tǒng)架構(gòu)不僅發(fā)揮A,B系統(tǒng)各自子系統(tǒng)之間的協(xié)同效應(yīng),而且發(fā)揮了A,B系統(tǒng)之間的互補效應(yīng)。

(2)本文給出針對雙系統(tǒng)CC框架的系統(tǒng)A,B各自求解兩種算法選擇和匹配方法,本文的系統(tǒng)A,B分別采用DE和DPSO[20]求解,發(fā)揮其各自特長和具有互補性特點,并且與系統(tǒng)A,B各自角色相匹配。

(3)本文算法與其他3種典型算法相比較,通過兩個Benchmark[5-6]函數(shù)(D=1 000)測試結(jié)果表明,總體上幾種算法對于上述兩個函數(shù)測試集不同函數(shù)求解各有短長,本文算法與其他3種典型算法相比,對Benchmark中某些函數(shù)計算占優(yōu)(包括難解的F3r,F6r,F17～F20),總體上各算法之間具有互補性,各算法所占貢獻 (有效求解函數(shù)Fi數(shù)目)比重基本相當。

本文期望通過研究提高基于CC框架算法求解能力,并借此分析各種不可分解函數(shù)性質(zhì),以及探索其針對性求解策略,最終目的是期望提高該算法計算性能,并有助于它的工程應(yīng)用。

下一步工作是:針對不可分解函數(shù)求解問題,對于基于CC框架雙系統(tǒng),研究合作型或競爭型協(xié)同進化算法與統(tǒng)計分析方法相結(jié)合方法,以便有助于它在耦合系統(tǒng)優(yōu)化與控制方面應(yīng)用。

[1] Potter M A,DeJongK A.A cooperative coevolutionary approach to function optimization[J].Lecture Notes in Computer Science,1994,866(1994):249-257.

[2] Yang Z Y,Tang K,Yao X.Large scale evolutionary optimization using cooperative coevolution[J].Information Sciences,2008,178(15):2985-2999.

[3] Li X D,Yao X.Cooperatively coevolving particle swarms for large scale optimization[J].IEEE Trans.on Evolutionary Computation,2012,16(2):210-224.

[4] Omidvar M N,Li X D,Mei Y,et al.Cooperative co-evolution with differential grouping for large scale optimization[J].IEEE Trans.on Evolutionary Computation,2014,18(3):378-393.

[5] Tang K,Yao X,Suganthan P N,et al.Benchmark functions for the CEC'2008 special session and competition on large scale global optimization[R].University of Science and Technology of China,2007.

[6] Tang K,Li X D,Suganthan P N.Benchmark functions for the CEC’2010 special session and competition on large-scale global optimization[R].University of Science and Technology of China,2009.

[7] Van den Bergh F,Engelbrecht A P.A cooperative approach to particle swarm optimization[J].IEEE Trans.on Evolutionary Computation,2004,8(3):225-239.

[8] Shi Y J,Teng H F,Li Z Q.Cooperative co-evolutionary differential evolution for function optimization[C]//Proc.of the International Conference on Natural Computation,2005:1080-1088.

[9] Yao X,Liu Y,Lin G M.Evolutionary programming made faster[J].IEEE Trans.on Evolutionary Computation,1999,3(2):82-102.

[10] Zhou D,Sun J,Xu W B.Quantum-behaved particle swarm optimization algorithm with cooperative approach[J].Control and Decision,2011,26(4):582-586.(周頔,孫俊,須文波.具有量子行為的協(xié)同粒子群優(yōu)化算法[J].控制與決策,2011,26(4):582-586.)

[11] Sayed E,Essam D,Sarker R,et al.Decomposition-based evolutionary algorithm for large scale constrained problems[J].Information Sciences,2015,316:457-486.

[12] Liu J P,Tang K.Scaling up covariance matrix adaptation evolution strategy using cooperative coevolution[C]//Proc.of the International Conference on Intelligent Data Engineering and Automated Learning,2013:350-357.

[13] Huang F Z,Wang L,He Q.A hybrid differential evolution with double populations for constrained optimization[C]//Proc.of the IEEE Congress on Evolutionary Computation,2008:18-25.

[14] Park T,Ryu K R.A dual-population genetic algorithm for adaptive diversity control[J].IEEE Trans.on Evolutionary Computation,2010,14(6):865-884.

[15] Teng H F,Chen Y,Zeng W,et al.A dual-system variable-grain cooperative coevolutionary algorithm:satellite-module layout design[J].IEEE Trans.on Evolutionary Computation,2010,14(3):438-455.

[16] Ros R,Hansen N.A simple modification in CMA-ES achieving linear time and space complexity[C]//Proc.of the International Conference on Parallel Problem Solving from Nature,2008:296-305.

[17] Paul W R,Liles W C,DeJongK A.An empirical analysis of collaboration methods in cooperative coevolutionary algorithms[C]//Proc.of the Genetic and Evolutionary Computation Conference,2001:1235-1242.

[18] Panait L,Luke S,Harrison J F.Archive-based cooperative coevolutionary algorithms[C]//Proc.of the 8th Annual Conference on Genetic and Evolutionary Computation,2006:345-352.

[19] Das S,Suganthan P N.Differential evolution:a survey of the state-of-the-art[J].IEEE Trans.on Evolutionary Computation,2011,15(1):4-31.

[20] Zhang Y N,Teng H F.Detecting particle swarm optimization[J].Concurrency and Computation:Practice and Experience,2009,21(4):449-473.

Dual-system cooperative co-evolutionary algorithm for non-separable function

CUI Feng-zhe1,WANG Xiu-kun1,TENG Hong-fei1,2

(1.School of Computer Science and Technology,Dalian University of Technology,Dalian 116024,China; 2.School of Mechanical Engineering,Dalian University of Technology,Dalian 116024,China)

Aiming at solving the non-separable function optimization problem,a dual-system cooperative co-evolutionary differential evolution particle swarm optimization algorithm (DCCDE/PSO for short)is developed based on the dual-system cooperative co-evolutionary (CC)framework.The proposed algorithm gives a new CC framework of the dual-system A and B and its corresponding coordination mechanism for improving the diversity and convergence,and gives two algorithms for example differential evolution (DE),the improved particle swarm optimization (PSO)that it solves the systems A and B respectively,as well as complementary and matches with the roles that the systems A and B play in the dual system.The purpose is to improve computational performance of the dual system algorithm based on the CC framework.The numerical experimental results of non-separable Benchmark functions (1000-dimensional)show that the performance (computational accuracy and standard deviation)of the proposed DCCDE/PSO compared favorably against other three representative algorithms has advantages for some of functions and as a whole the four algorithms had theirselves’s strengths for the Benchmark functions and each complemented the other.

non-separable function optimization; cooperative co-evolution; dual-system framework; modern heuristic algorithm; algorithm selection and match

2016-06-20；

2016-08-22；網(wǎng)絡(luò)優(yōu)先出版日期：2016-09-30。

國家自然科學基金(61472062)資助課題

TP 391.72

ADOI:10.3969/j.issn.1001-506X.2016.11.30

崔鋒哲(1977-),男,博士研究生,主要研究方向為智能計算、復雜系統(tǒng)優(yōu)化。

E-mail:Hftdlut@126.com

王秀坤(1945-),女,教授,碩士,主要研究方向為決策支持系統(tǒng)、數(shù)據(jù)庫系統(tǒng)。

E-mail:jsjwxk@dlut.edu.cn

滕弘飛(1936-),男,教授,主要研究方向為產(chǎn)品數(shù)字化設(shè)計與制造、智能計算、復雜系統(tǒng)建模和優(yōu)化。

E-mail:tenghf@dlut.edu.cn

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160930.1313.032.html