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

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

?

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

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

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

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

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

0　引　言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1　本文算法DCCDE/PSO

1.1本文DCCDE/PSO算法特點(diǎn)

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

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

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

(3)本文給出雙系統(tǒng)CC框架中A,B系統(tǒng)各自求解算法(DE,PSO)的選擇和匹配方法。Oboe-CCEA的系統(tǒng)A,B都采用GA,沒(méi)有討論此問(wèn)題。本文算法的系統(tǒng)A采用多樣性好、搜索能力強(qiáng)的DE[19]求解;系統(tǒng)B采用具有搜索初期搜索速度快和克服后期易早熟的較好性能的探測(cè)粒子群(detecting particle swarm optimization,DPSO)[20]求解,這兩種算法互補(bǔ)性好,并分別與系統(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)或測(cè)試函數(shù)Fi個(gè)體置于CC框架,將測(cè)試函數(shù)Fi采用橫向分解方式,將它截成E個(gè)子函數(shù)表達(dá)式(視為子系統(tǒng)或子個(gè)體),則該函數(shù)Fi可以表示為Fi(X),其中X={xi| i∈I=1,2,…,n},Xe={xie| i∈I,e∈E=1,2,…,E} 即將X分解為E個(gè)子系統(tǒng)。

附帶說(shuō)明,上述Fi的分解,相當(dāng)于變量集合X分組。X={Xp},分成p個(gè)相對(duì)獨(dú)立的小組,p=2,3,…,P,1

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

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

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

(1)

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

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

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

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

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

綜上所述,基于CC框架的系統(tǒng)分解,本文的雙系統(tǒng)協(xié)調(diào)機(jī)制在迭代前期增加多樣性,在迭代后期增加收斂性。系統(tǒng)B為系統(tǒng)A提供更多的全局搜索的完整解(含子個(gè)體),而系統(tǒng)A利用合作個(gè)體選擇方式和求解算法DE的多樣性和收斂性兼優(yōu)的特點(diǎn)實(shí)現(xiàn)進(jìn)一步優(yōu)化。在迭代后期,利用精英解集檔案的合作個(gè)體選擇構(gòu)成A系統(tǒng)的精英個(gè)體,A系統(tǒng)向B系統(tǒng)輸送精英個(gè)體。通過(guò)雙系統(tǒng)之間個(gè)體相互遷移,不斷進(jìn)化。算法DE和DPSO二者在迭代過(guò)程發(fā)揮各自所長(zhǎng)和互補(bǔ)性,并與A,B系統(tǒng)承擔(dān)角色相匹配。本文算法不僅發(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),目的是提高其計(jì)算能力。最終使系統(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中測(cè)試函數(shù)Fi的個(gè)體分解為若干個(gè)子個(gè)體,也即相當(dāng)于從系統(tǒng)角度實(shí)現(xiàn)變量分組。變量分組分兩種:一種是靜態(tài)(固定)變量分組,分組后不再改變；另一種是動(dòng)態(tài)(可變)變量分組[2]。一般情況下,后者比前者有效,當(dāng)然也需付出代價(jià)。本文采用前者方式,意在探討在變量靜態(tài)分組情況下,如何提高本文算法求解不可分解函數(shù)的計(jì)算性能,并借此分析不可分解函數(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ù)值仿真實(shí)驗(yàn)

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

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

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

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

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

(2)

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

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

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

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

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

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

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

(5)本文算法數(shù)值實(shí)驗(yàn)運(yùn)行環(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種算法求解坐標(biāo)軸旋轉(zhuǎn)的F3r,F4r,F5r,F6r(1 000維)不可分解函數(shù)誤差平均值(Mean Δf)進(jìn)化曲線圖。

圖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種算法計(jì)算性能的兩評(píng)價(jià)指標(biāo)為計(jì)算精度(Mean Δf)和魯棒性(標(biāo)準(zhǔn)差Std)。采用上述經(jīng)典算法的評(píng)價(jià)指標(biāo)和測(cè)試方法是:先進(jìn)行T檢驗(yàn),考慮Mean Δf和Std,計(jì)算P-Value。當(dāng)P-Value≥0.05,認(rèn)為兩算法相當(dāng);當(dāng)

P-Value<0.05,兩算法不相當(dāng)。這時(shí),兩種算法比較采用Mean Δf評(píng)價(jià),愈小愈好。以下兩算法之間比較,采用此方法,每種算法各25次計(jì)算。同樣,本文算法與CCPSO2[3]或sep-CMA-ES[16]通過(guò)Benchmark[5](包含8個(gè)不可分解函數(shù))測(cè)試比較,以及本文算法與CBCC-DG[4]通過(guò)Benchmark[6](包含17個(gè)不可分解函數(shù))測(cè)試比較,結(jié)果見(jiàn)表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),○表示相當(dāng),×表示較差; 2)陰影背景函數(shù)表示難解函數(shù)。

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

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

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

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

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

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

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

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

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

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

2.2.2討論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　結(jié)論與展望

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

本文主要工作是:

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

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

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

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

下一步工作是:針對(duì)不可分解函數(shù)求解問(wèn)題,對(duì)于基于CC框架雙系統(tǒng),研究合作型或競(jìng)爭(zhēng)型協(xié)同進(jìn)化算法與統(tǒng)計(jì)分析方法相結(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。

國(guó)家自然科學(xué)基金(61472062)資助課題

TP 391.72

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

崔鋒哲(1977-),男,博士研究生,主要研究方向?yàn)橹悄苡?jì)算、復(fù)雜系統(tǒng)優(yōu)化。

E-mail:Hftdlut@126.com

王秀坤(1945-),女,教授,碩士,主要研究方向?yàn)闆Q策支持系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)。

E-mail:jsjwxk@dlut.edu.cn

滕弘飛(1936-),男,教授,主要研究方向?yàn)楫a(chǎn)品數(shù)字化設(shè)計(jì)與制造、智能計(jì)算、復(fù)雜系統(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