張凱波，李 斌

（中國(guó)科學(xué)技術(shù)大學(xué)電子科學(xué)與技術(shù)系，安徽 合肥 230027)

合作型協(xié)同演化算法研究進(jìn)展＊

張凱波，李 斌

（中國(guó)科學(xué)技術(shù)大學(xué)電子科學(xué)與技術(shù)系，安徽 合肥 230027)

合作型協(xié)同演化算法是近年來(lái)計(jì)算智能研究的熱點(diǎn)。它運(yùn)用生物協(xié)同演化的思想，通過(guò)構(gòu)建兩個(gè)或者多個(gè)種群，建立它們之間的合作關(guān)系。兩個(gè)或多個(gè)種群通過(guò)相互合作來(lái)提高各自的性能，適應(yīng)復(fù)雜系統(tǒng)的動(dòng)態(tài)演化環(huán)境以及大規(guī)模演化環(huán)境，從而達(dá)到種群優(yōu)化的目的。主要介紹了合作型協(xié)同演化算法的研究狀況以及國(guó)內(nèi)外研究進(jìn)展，詳細(xì)介紹了它的基本結(jié)構(gòu)及對(duì)應(yīng)的研究、基本算法及一些新興算法，同時(shí)介紹了一些在現(xiàn)實(shí)生活中的應(yīng)用，展望了合作型協(xié)同演化算法的發(fā)展前景。

合作型協(xié)同演化算法；問(wèn)題分解；子空間相關(guān)性

1 引言

合作型協(xié)同演化算法是近年來(lái)計(jì)算智能研究的熱點(diǎn)。它基于divide-and-conquer思想，求解問(wèn)題主要分為以下三步：（1)問(wèn)題分解：將大規(guī)模問(wèn)題分解成若干小規(guī)模子問(wèn)題；（2)子問(wèn)題求解：用一種特定的演化算法求解每一個(gè)子問(wèn)題；（3)子問(wèn)題合并：合并各個(gè)子問(wèn)題的解，構(gòu)成原問(wèn)題的解。

合作型協(xié)同演化算法最早是由Potter A M［1］結(jié)合GA算法提出的，即CCGA。隨著CCGA的提出，對(duì)于合作型協(xié)同演化算法的研究逐漸分為以下三類(lèi)：（1)對(duì)于合作型協(xié)同演化算法結(jié)構(gòu)的探究。包括問(wèn)題分解、子空間的相關(guān)性、協(xié)同個(gè)體適應(yīng)度值分配以及群體多樣性等。（2)將合作型協(xié)同演化算法結(jié)構(gòu)和不同的演化算法或者算子相結(jié)合，得到更多的新的合作型協(xié)同演化算法。（3)運(yùn)用合作型協(xié)同演化算法解決不同類(lèi)型的問(wèn)題，包括數(shù)值優(yōu)化、動(dòng)態(tài)優(yōu)化問(wèn)題、對(duì)偶系統(tǒng)等。

在后文的敘述中，CC（Cooperative Coevolution)表示合作型協(xié)同演化。

2 合作型協(xié)同演化算法結(jié)構(gòu)研究

合作型協(xié)同演化算法是普通演化算法的拓展。隨著自變量維數(shù)的增加，普通演化算法的性能急劇下降。因此，合作型協(xié)同演化算法采用分而治之的方法，通過(guò)將自變量分解到兩個(gè)或多個(gè)子空間中去，子空間之間通過(guò)協(xié)作來(lái)提高各自的性能，從而達(dá)到種群優(yōu)化的目的。本文將從CC算法結(jié)構(gòu)、一個(gè)個(gè)具體的CC算法以及CC算法的應(yīng)用三個(gè)方面分別介紹CC算法。

2.1 問(wèn)題分解

Potter A M 在 CCGA［1］中使用的是relaxation方法，主要思想是為了優(yōu)化一個(gè)n維自變量的問(wèn)題，保持n－1維變量不變，只優(yōu)化剩下的1維向量，即單維分解。這種方法也被用在文獻(xiàn)［2］中。在CCGA的基礎(chǔ)上，Potter A M進(jìn)行了進(jìn)一步的研究［3，4］。他發(fā)現(xiàn)了兩種新的問(wèn)題分解方法：（1)文獻(xiàn)［3］首先讓第一個(gè)子空間進(jìn)行演化，直到演化結(jié)果改進(jìn)小于閾值；然后讓第二個(gè)子空間和第一個(gè)子空間并行演化。這里其他的子空間選擇的是當(dāng)前最優(yōu)個(gè)體協(xié)同演化，直到演化結(jié)果改進(jìn)小于閾值；然后添加第三個(gè)子空間進(jìn)行并行演化，這樣直到最后一個(gè)子空間。（2)基于對(duì)子空間和小生境的進(jìn)一步研究［4］，Potter A M發(fā)現(xiàn)了基于小生境的新的問(wèn)題分解方法。隨著對(duì)問(wèn)題分解方法的進(jìn)一步探究，Potter A M認(rèn)為問(wèn)題分解必須面對(duì)四個(gè)問(wèn)題［5］：（1)子空間能否定位和覆蓋多個(gè)小生境環(huán)境？（2)一般來(lái)說(shuō)，子空間能否演化到一個(gè)合適的水平層次上？（3)當(dāng)子空間的數(shù)目與作用發(fā)生變化時(shí)，CC能否很好地適應(yīng)這個(gè)變化，對(duì)結(jié)果影響大不大？（4)能否得到子種群的合適的數(shù)目？針對(duì)這四個(gè)方面的問(wèn)題，Potter A M和De Jong根據(jù)一系列實(shí)驗(yàn)作了回答：（1)每個(gè)子空間定位一個(gè)或是兩個(gè)小生境，讓其他的子空間定位其他的小生境；兩個(gè)或是更多的子空間能夠覆蓋一個(gè)普通小生境；但是有些子空間對(duì)于定位和覆蓋小生境沒(méi)有明顯作用。（2)隨著子空間的數(shù)目增加到超過(guò)小生境的數(shù)目時(shí)，結(jié)果越來(lái)越好，然而需要耗費(fèi)更多的計(jì)算代價(jià)。（3)隨著迭代次數(shù)的增加，子空間的作用將穩(wěn)定下來(lái)。隨著子空間數(shù)目和作用的改變，結(jié)果會(huì)呈現(xiàn)出通適性，能夠很好地適應(yīng)子群體數(shù)目和作用的改變。（4)合適數(shù)目的子空間是能夠得到的。

在PotterA M的研究工作的基礎(chǔ)之上，多種不同的問(wèn)題分解的方法相繼產(chǎn)生。其中包括將問(wèn)題的自變量均分為兩半，每一半作為一個(gè)子空間進(jìn)行優(yōu)化的折半分解［6］；每一維自變量都有相同的幾率被分配到任意一個(gè)子空間中去的隨機(jī)分組［7］；在隨機(jī)分組中，隨著隨機(jī)分組次數(shù)的增加，多個(gè)相關(guān)變量被分到一個(gè)子空間的概率大大增加［8］；保證正在優(yōu)化的子空間中的自變量是當(dāng)前方差最大的自變量的方差分組［9］。

隨著對(duì)自變量之間相關(guān)性研究的深入，不僅僅可以將相關(guān)程度較高的自變量合并到一個(gè)子空間［10］，同時(shí)可 以 將 一 個(gè) 子 空 間 分 解［11，12］。 當(dāng) 自 變量之間獨(dú)立時(shí)，子空間分解；當(dāng)自變量之間相關(guān)時(shí)，子空間合并。當(dāng)搜索局部最優(yōu)區(qū)域，子空間合并比子空間分解能夠更有效地逃離局部最優(yōu)。當(dāng)搜索全局最優(yōu)區(qū)域時(shí)，子空間分解能夠更快地找到全局最優(yōu)。如果合并后的子空間在一定時(shí)間內(nèi)不能讓結(jié)果變好，該子空間會(huì)被分解。為了更有效地解決不可分問(wèn)題，一系列新的基于自變量相關(guān)性的分組方法相繼被提出。Ray T［13］通過(guò)計(jì)算自變量之間的相關(guān)系數(shù)，提出對(duì)自變量進(jìn)行分組的方法——CCEA-AVP。Chen Wen-xiang［14］提出了一種新的將相關(guān)自變量分配到同一個(gè)分組中去的分組方法——CCVIL。

近年來(lái)，新的分組方法層出不窮。動(dòng)態(tài)分組規(guī)模［15］方法是通過(guò)一種反饋學(xué)習(xí)機(jī)制動(dòng)態(tài)調(diào)整分組的規(guī)模。Chandra R等［16］基于神經(jīng)元的功能性質(zhì)提出一種新的子空間分解的編碼方案（NSP)，雖然相比CoSyNE［17］，它的模塊化層次低，但是這讓它在初始化階段計(jì)算代價(jià)較小。Shi Min等［18］采用盲目分解的方法解決問(wèn)題。

2.2 子空間相關(guān)性

文獻(xiàn)［19，20］在以下幾個(gè)方面對(duì)子空間的相關(guān)性做了細(xì)致的分析和深入的研究。

2.2.1 協(xié)同選擇壓力

協(xié)同選擇壓力是指如何選擇每個(gè)子空間中的個(gè)體進(jìn)行協(xié)同演化。根據(jù)個(gè)體選擇的貪婪程度可以分為五類(lèi)，分別是：（1)每個(gè)子空間只選擇最優(yōu)個(gè)體；（2)每個(gè)子空間只選擇隨機(jī)個(gè)體；（3)每個(gè)子空間只選擇最差個(gè)體；（4)每個(gè)子空間選擇上述三種個(gè)體中的任意兩種個(gè)體；（5)每個(gè)子空間選擇上述三種個(gè)體。實(shí)驗(yàn)發(fā)現(xiàn)，只要子空間選擇了最優(yōu)個(gè)體進(jìn)行協(xié)同演化，結(jié)果就會(huì)比較好。選擇兩種個(gè)體結(jié)果（包括最優(yōu)個(gè)體)和選擇三種個(gè)體結(jié)果差不多。當(dāng)不知道變量相關(guān)性時(shí)，使用（最優(yōu)＋隨機(jī))這種個(gè)體選擇方法會(huì)成為第一選擇。根據(jù)個(gè)體選擇順序可以分為以下三類(lèi)：（1)順序演化：每次迭代只選擇一個(gè)子空間進(jìn)行演化，只更新這個(gè)子空間；（1)并行演化：每次迭代所有的子空間都進(jìn)行演化，等所有的子空間演化結(jié)束再統(tǒng)一進(jìn)行更新；（3)重排方法：隨機(jī)打亂每個(gè)子空間中的個(gè)體順序，然后讓個(gè)體配對(duì)分組。實(shí)驗(yàn)發(fā)現(xiàn)，并行方法比順序方法效果好，重排方法在比較復(fù)雜的問(wèn)題上結(jié)果更好。2.2.2 協(xié)同個(gè)體規(guī)模

當(dāng)選擇一個(gè)或是兩個(gè)協(xié)同個(gè)體，結(jié)果已經(jīng)很好了。對(duì)于變量相關(guān)度很大的復(fù)雜問(wèn)題，協(xié)同選擇壓力的重要性遠(yuǎn)遠(yuǎn)小于協(xié)同個(gè)體規(guī)模，如果計(jì)算允許的話，增加協(xié)同個(gè)體規(guī)模，通常會(huì)使結(jié)果更好。Panait L等［21］用一種簡(jiǎn)單的方法隨時(shí)間改變協(xié)同選擇個(gè)體的數(shù)目。在演化早期，用多個(gè)協(xié)同選擇個(gè)體確定最有希望的空間。這是因?yàn)槌跏蓟瘋€(gè)體之間有較高的多樣性。當(dāng)群體開(kāi)始收斂時(shí)則減少個(gè)體。因?yàn)楫?dāng)其他群體開(kāi)始收斂的時(shí)候，選用更多的協(xié)同個(gè)體不能明顯改進(jìn)解的質(zhì)量。最終結(jié)果表明，隨時(shí)間減少協(xié)同個(gè)體數(shù)目比固定協(xié)同個(gè)體數(shù)目結(jié)果要好。

2.2.3 子空間的適應(yīng)度值分配

任一個(gè)子空間中的不同個(gè)體有不同的適應(yīng)度值，這些不同的適應(yīng)度值必須通過(guò)某種方法得到該子空間一個(gè)特定的適應(yīng)度值。這里有三種方法：（1)將子空間所有個(gè)體中最好的個(gè)體對(duì)應(yīng)的適應(yīng)度值作為該子空間的適應(yīng)度值；（2)將子空間所有個(gè)體中適應(yīng)度值的平均值作為該子空間的適應(yīng)度值；（3)將子空間所有個(gè)體中最差的個(gè)體對(duì)應(yīng)的適應(yīng)度值作為該子空間的適應(yīng)度值。實(shí)驗(yàn)結(jié)果表明方法（1)的結(jié)果最好。

2.2.4 子空間的優(yōu)化策略和時(shí)間策略

子空間優(yōu)化策略主要包括同步策略和異步策略［22］。同步策略是指只有當(dāng)所有的子空間都演化結(jié)束之后才更新全局群體；異步策略是指每演化一個(gè)子空間就更新一次全局群體。實(shí)驗(yàn)證明異步策略和同步策略結(jié)果基本差不多，在部分問(wèn)題上異步策略結(jié)果會(huì)稍好。子空間的演化時(shí)間的不同對(duì)結(jié)果也會(huì)產(chǎn)生一定的影響［21］。子空間演化時(shí)間的改變，可能會(huì)改善結(jié)果，也可能會(huì)讓結(jié)果變差。

2.3 協(xié)同個(gè)體適應(yīng)度值分配

協(xié)同個(gè)體不同的子空間都有不同的適應(yīng)度值，這些不同的適應(yīng)度值必須通過(guò)某種方法得到該協(xié)同個(gè)體特定的適應(yīng)度值。這里有三種方法［19，20］：（1)將個(gè)體最好的協(xié)同子空間對(duì)應(yīng)的適應(yīng)度值作為個(gè)體的適應(yīng)度值；（2)將個(gè)體的協(xié)同子空間的適應(yīng)度值的平均值作為個(gè)體的適應(yīng)度值；（3)將個(gè)體最差的協(xié)同子空間對(duì)應(yīng)的適應(yīng)度值作為個(gè)體的適應(yīng)度值。實(shí)驗(yàn)結(jié)果表明方法（1)的結(jié)果最好。為了逃離局部最優(yōu)，一些新的適應(yīng)度值分配方案相繼被提出，包括全局適應(yīng)度最優(yōu)值（全局適應(yīng)度用類(lèi)似CCGA2［1］的方法得到)和局部適應(yīng)度最優(yōu)值（局部適應(yīng)度是對(duì)每個(gè)子空間的單獨(dú)特征來(lái)計(jì)算，只有訓(xùn)練數(shù)據(jù)中目標(biāo)函數(shù)對(duì)應(yīng)的部分特征會(huì)被用于計(jì)算，其他特征不會(huì)對(duì)局部適應(yīng)度有貢獻(xiàn))取平均值［23］；全局適應(yīng)度最優(yōu)值和局部適應(yīng)度最優(yōu)值平均值根據(jù)一定的概率產(chǎn)生個(gè)體適應(yīng)度［24］。

2.4 群體多樣性

增強(qiáng)群體多樣性，可以解決合作型協(xié)同演化中早熟收斂的問(wèn)題。增強(qiáng)多樣性的方法［25］主要包括增加群體規(guī)模、使用基于小生境的模型和島模型、近鄰搜索等。

2.5 其他方面

對(duì)于CC算法結(jié)構(gòu)的研究和分析除了以上四個(gè)方面外，在其他的一些方面也相繼展開(kāi)。例如，基于參考共享協(xié)同模型，同時(shí)用Pareto支配原則來(lái)衡量個(gè)體的表現(xiàn)，從而解決顯性基因的問(wèn)題［26］；CCGA在單目標(biāo)優(yōu)化問(wèn)題的多適應(yīng)度衡量上出現(xiàn)了三種新的方法［27］：貪婪、非支配排序以及evendistributed排序。同時(shí)，適度的變異能夠明顯提升CCEA對(duì)可分解問(wèn)題的處理［28］，自適應(yīng)變異的引入［29］則讓性能進(jìn)一步改進(jìn)。子空間之間信息交互頻率對(duì)于結(jié)果會(huì)產(chǎn)生一定的影響［30］，降低交互頻率會(huì)讓結(jié)果更精確，但是會(huì)導(dǎo)致早熟收斂。采用動(dòng)態(tài)群體規(guī)模、精英策略等方法［31，32］則能進(jìn)一步改進(jìn)CCEA的性能。

3 合作型協(xié)同演化算法

3.1 合作型協(xié)同演化算法結(jié)構(gòu)和演化算法結(jié)合

隨著Potter A M將GA作用于合作型協(xié)同演化算法結(jié)構(gòu)并提出了CCGA［1］開(kāi)始，不斷有新的演化算法或者結(jié)合新的演化算子的基本演化算法應(yīng)用于合作型協(xié)同演化算法結(jié)構(gòu)的框架中，出現(xiàn)了很多新的合作型協(xié)同演化算法。CC算法結(jié)構(gòu)和演化算法相結(jié)合，主要包括以下幾類(lèi)。

3.1.1 CC和基本演化算法相結(jié)合

CCGA對(duì)解空間進(jìn)行分解，如果自變量之間存在相關(guān)性會(huì)導(dǎo)致早熟收斂，同時(shí)CCGA對(duì)參數(shù)存在嚴(yán)重的依賴(lài)。為了解決這兩個(gè)方面的問(wèn)題，更多的基本演化算法和CC相結(jié)合形成了多種不同的CC算法。

演化規(guī)劃應(yīng)用于CC框架中去得到的FEPCC［2］極大地加快了CC算法解決大規(guī)模問(wèn)題時(shí)的收斂速度。

演化策略和CC結(jié)合得到的CCES［33］對(duì)于解決自變量之間具有相關(guān)性的高維問(wèn)題效果更好。

CPSO［34］是由CC算法結(jié)構(gòu)和PSO算法結(jié)合得到的。因?yàn)闃?biāo)準(zhǔn)PSO應(yīng)用到CC中去得到的CPSO-Sk仍然可能陷入局部最優(yōu)，因此文獻(xiàn)［34］提出了CPSO-Hk。在CPSO-Hk中，CPSO-Sk和標(biāo)準(zhǔn)PSO交替運(yùn)行，共享它們的全局最優(yōu)解信息，最終找到全局最優(yōu)解。

差分演化算法結(jié)合CC框架得到的CCDE［35］嘗試將解空間分解成每一維自變量一個(gè)子空間。實(shí)驗(yàn)結(jié)果表明這種分解并不總是比解空間分為兩部分的結(jié)果好。

3.1.2 群體覓食算法和CC結(jié)合

近年來(lái)隨著群體覓食算法的興起，不斷有CC與群體覓食算法相結(jié)合，擴(kuò)展CC算法的范圍，人工蜂群算法就是其中一種。人工蜂群算法ABCA（Artificial Bee Colony Algorithm)和CC算法框架結(jié)合得到CABCA［36］，改善了ABCA的實(shí)驗(yàn)結(jié)果、收斂速度和魯棒性。

ABCA是Karaboga D［37］于2005年通過(guò)模擬蜜蜂群的智能采蜜行為提出的一種群智能隨機(jī)優(yōu)化算法。在該算法中蜜蜂根據(jù)各自的分工進(jìn)行不同的活動(dòng)，并實(shí)現(xiàn)蜂群信息的共享和交流，從而找到要求解的問(wèn)題的最優(yōu)解。

在ABCA中，人工蜂群包含采蜜蜂、觀察蜂和偵察蜂三個(gè)組成部分，每個(gè)蜜源的位置代表優(yōu)化問(wèn)題的一個(gè)可能解，蜜源的花蜜量對(duì)應(yīng)于相應(yīng)解的質(zhì)量或適應(yīng)度。

首先，ABCA隨機(jī)產(chǎn)生初始群體即個(gè)初始解（為采蜜蜂數(shù)也為蜜源數(shù)目)。每個(gè)解為一個(gè)維的向量（d為優(yōu)化自變量的個(gè)數(shù))。經(jīng)過(guò)初始化之后，首先是采蜜蜂工作階段：采蜜蜂根據(jù)記憶中的位置信息產(chǎn)生一個(gè)變化的位置并檢查新位置的花蜜量。若新位置的花蜜量比原來(lái)的多，則該蜜蜂記住新位置并忘記原位置。等到所有的采蜜蜂完成搜索過(guò)程后，采蜜蜂將蜜源信息與觀察蜂共享進(jìn)入到觀察蜂工作階段。觀察蜂根據(jù)與不同位置的花蜜量相關(guān)的概率選擇一個(gè)蜜源位置，像采蜜蜂那樣對(duì)記憶中的位置做一定的改變，并檢查新候選位置的花蜜量。若新位置優(yōu)于記憶中的位置，則用新位置替換原位置。一個(gè)觀察蜂選擇某個(gè)蜜源的概率為：

其中，fitnessi是基于第i個(gè)個(gè)體的適應(yīng)度值（花蜜量)。根據(jù)記憶位置產(chǎn)生一個(gè)新的位置：

其中，k∈｛1，2，…，sn｝和j∈｛1，2，…，d｝是隨機(jī)選擇的下標(biāo)，k≠i；是在［－1，1］的隨機(jī)數(shù)?？刂屏藊ij鄰域內(nèi)新解的產(chǎn)生并代表蜜蜂對(duì)兩個(gè)可視范圍內(nèi)蜜源位置的比較。隨著參數(shù)的xij－xkj值越來(lái)越小，對(duì)于位置xij的擾動(dòng)也越來(lái)越小。

假設(shè)一個(gè)蜜源經(jīng)過(guò)限定的循環(huán)次數(shù)之后不能被改進(jìn)，則該蜜源的采蜜蜂轉(zhuǎn)變成為偵察蜂。該蜜源的位置會(huì)被偵察蜂在解空間內(nèi)隨即發(fā)現(xiàn)的新位置替代。偵察蜂發(fā)現(xiàn)新位置的操作為：

和ABCA相比，CABCA處理問(wèn)題的結(jié)果更好，收斂速度更快，魯棒性也更好。

3.1.3 多種演化算法和CC結(jié)合

Vanneschi L［38］根據(jù) GP 能夠優(yōu)化結(jié)構(gòu)、GA能夠優(yōu)化數(shù)值的特點(diǎn)，提出了基于GA和GP混合的協(xié)同演化：根據(jù)GA、GP不同的運(yùn)行階段主要有四種結(jié)構(gòu)：

（1)基本算法：GA和GP交替進(jìn)行。

（2)延遲算法：在GA和GP交替進(jìn)行之前，GP先單獨(dú)迭代一段時(shí)間，找到較好的優(yōu)化結(jié)構(gòu)。

（3)CINI算法：首先讓GP單獨(dú)迭代直到結(jié)果沒(méi)有顯著的改進(jìn)，然后進(jìn)行GA和GP交替優(yōu)化。

（4)AUTO算法：根據(jù)GA和GP對(duì)于結(jié)果的改進(jìn)大小決定到底是運(yùn)行GA還是GP。

實(shí)驗(yàn)結(jié)果表明，以上四種算法中CINI算法性能最好。

3.1.4 層次CC算法

Maniadakis M［39］提出并分析了層次合作型協(xié)同演化算法（HCCE)，HCCE不僅突出不同層次的局部部分的獨(dú)立的作用，而且強(qiáng)調(diào)它們作為一個(gè)整體系統(tǒng)的作用。局部部分由自身動(dòng)態(tài)性驅(qū)使，滿(mǎn)足每個(gè)部分的特殊的目標(biāo)；同時(shí)，高層次的演化過(guò)程探索完整的結(jié)構(gòu)，協(xié)調(diào)低層次部分的演化。

3.1.5 微演化算法與CC框架相結(jié)合

兩者結(jié)合可以得到快速收斂的微協(xié)同演化算法，主要包括：基于 DE算法的 CC-Micro-DE［40］以及基于PSO算法的CC-Micro-PSO［41］。

微演化算法和普通演化算法的區(qū)別是群體規(guī)模較小，這會(huì)限制它的搜索能力，特別是在復(fù)雜環(huán)境中的搜索能力。同時(shí)，群體規(guī)模小會(huì)導(dǎo)致群體早熟收斂，在早期迭代中降低了群體的多樣性。對(duì)于CC-Micro-DE和CC-Micro-PSO，群體規(guī)模為6是一個(gè)合適的選擇。通常p＝n（自變量維數(shù))/N（群體規(guī)模)暗示一個(gè)算法解決給定問(wèn)題的困難度。大多數(shù)情況下p的值越大，微演化算法越難解決問(wèn)題。

比較基本的微演化算法，微演化算法和CC框架結(jié)合后的算法解決高維問(wèn)題的能力變強(qiáng)，性能也更好，較為有效地克服了微演化算法解決高維問(wèn)題時(shí)遇到的早熟收斂問(wèn)題。

3.1.6 CC結(jié)構(gòu)和Memetic算法相結(jié)合

CC結(jié)構(gòu)和Memetic算法相結(jié)合用于解決神經(jīng)網(wǎng)絡(luò)問(wèn)題。主要包括結(jié)合CC結(jié)構(gòu)以及通過(guò)交叉的局部細(xì)化的XLCC算法［42，43］，基于交叉的局部細(xì)化的局部搜索可以在合適的時(shí)機(jī)產(chǎn)生優(yōu)勢(shì)個(gè)體，提升算法性能。XLCC中，不是對(duì)每個(gè)子群體都進(jìn)行局部搜索，而是當(dāng)一次循環(huán)完成之后，再對(duì)子群體合并后的個(gè)體進(jìn)行局部搜索。每次循環(huán)完成之后，所有子群體中的最優(yōu)個(gè)體合并成一個(gè)meme。然后用局部搜索的方法對(duì)該meme進(jìn)行交叉操作，用交叉后的meme代替每個(gè)子群體中的最差個(gè)體。

XLCC的性能比標(biāo)準(zhǔn)的CC算法要好，這為進(jìn)一步利用其他的局部搜索策略打下了良好的基礎(chǔ)。但是，XLCC最大的缺點(diǎn)在于參數(shù)設(shè)置的計(jì)算代價(jià)太大。

3.1.7 CC-Rank

CC-Rank［44］用并行 CC學(xué)習(xí)排名問(wèn)題。它用兩階段的方法從訓(xùn)練數(shù)據(jù)集中學(xué)習(xí)排名函數(shù)。首先，CC-Rank進(jìn)入問(wèn)題分解階段：隨機(jī)在整個(gè)特征空間初始化用樹(shù)結(jié)構(gòu)表示的L個(gè)解之后，將每一個(gè)解分解成N個(gè)子樹(shù)，這樣就生成了N個(gè)群體，每個(gè)群體包含L個(gè)個(gè)體。問(wèn)題分解階段結(jié)束后，進(jìn)入循環(huán)的演化階段。在該階段，N個(gè)群體并行地協(xié)同演化。每個(gè)群體中適應(yīng)度最好的個(gè)體被選出進(jìn)行協(xié)同。每次循環(huán)結(jié)束后，并行操作將暫停，每個(gè)群體中被選出的適應(yīng)度最好的N個(gè)體將合并構(gòu)成完整解，并且將這個(gè)解放入一個(gè)解決方案池作為排名函數(shù)的候選解。當(dāng)演化階段的循環(huán)全部結(jié)束的時(shí)候，驗(yàn)證數(shù)據(jù)集將從所有的候選解中選取最好的解作為最終的排名函數(shù)。

CC-Rank成功地運(yùn)用于復(fù)雜優(yōu)化問(wèn)題的解決。與當(dāng)前最好的算法相比，在解決排名問(wèn)題的時(shí)候能夠同時(shí)提高算法的精確度和效率。

3.1.8 pCCEA

Bucci A等［45］提出一種用Pareto支配機(jī)制的CCEA-pCCEA。下面以?xún)蓚€(gè)種群為例介紹基于非支配排序的Pareto協(xié)同演化算法。它的具體步驟如下：

（1)根據(jù)問(wèn)題域劃分為兩個(gè)種群（種群A和種群B)，所有的種群構(gòu)成一個(gè)進(jìn)化系統(tǒng)。

（2)初始化兩個(gè)種群，在兩個(gè)種群中分別選擇最優(yōu)的染色體，并隨機(jī)選擇另外一條染色體作為兩個(gè)種群各自的種群代表。

（3)對(duì)種群A的所有個(gè)體和種群B的代表個(gè)體采用遍歷組合法，構(gòu)成新的個(gè)體。

（4)對(duì)于多個(gè)目標(biāo)的每個(gè)目標(biāo)函數(shù)，分別計(jì)算所有個(gè)體的目標(biāo)函數(shù)值。

（5)計(jì)算個(gè)體的非支配水平和密集距離，實(shí)現(xiàn)非支配排序。

（6)取前n個(gè)經(jīng)過(guò)非支配排序的個(gè)體，將其分解為兩個(gè)種群的下一代父?jìng)€(gè)體。

（7)根據(jù)目標(biāo)函數(shù)值選擇兩個(gè)種群的代表，對(duì)兩個(gè)種群的染色體分別進(jìn)行獨(dú)立的演化操作產(chǎn)生子代種群。

（8)重復(fù)（1)～（7)，直到滿(mǎn)足迭代終止條件為止。

pCCEA對(duì)個(gè)體之間信息差異很敏感，相比于標(biāo)準(zhǔn)的CCEA，對(duì)于解決相關(guān)性問(wèn)題的性能更好。

3.1.9 CC結(jié)構(gòu)和新興演化算法結(jié)合

近年來(lái)，隨著對(duì)合作型協(xié)同演化算法的深入研究，一些新興的演化算法應(yīng)用到CC的框架中去，例如，CC算法框架和文化算法的結(jié)合［46］，和分布估計(jì)算法EDA的結(jié)合［47］。

文化算法［45］的主要思想是明確地從進(jìn)化種群中獲得求解問(wèn)題的知識(shí)，并用于搜索過(guò)程。它是由群體空間和信念空間兩部分組成。群體空間是基于傳統(tǒng)群體的進(jìn)化。信念空間是基于信念文化的進(jìn)化，用于知識(shí)經(jīng)驗(yàn)的形成、存儲(chǔ)和傳播。兩個(gè)空間之間既相互獨(dú)立又有著聯(lián)系。文化算法基本步驟如下：

（1)初始化種群空間和信念空間。

（2)演化種群空間的個(gè)體。

（3)搜集種群空間中優(yōu)秀個(gè)體的經(jīng)驗(yàn)知識(shí)，用于更新信念空間。

（4)利用解決問(wèn)題的知識(shí)指導(dǎo)群體空間的進(jìn)化。

（5)根據(jù)規(guī)則從新生成個(gè)體中選擇一部分個(gè)體作為下一代個(gè)體的父?jìng)€(gè)體。

（6)重復(fù)（2)～（5)，直到達(dá)到迭代終止條件。

文化算法和CC結(jié)合能夠有效地加快文化算法的收斂速度，而且知識(shí)空間的信息遷移也比文化算法中個(gè)體遷移策略性能要好。

分布估計(jì)算法［47］作為一種新型的進(jìn)化算法，主要有以下幾方面的特點(diǎn)。首先，從生物進(jìn)化的數(shù)學(xué)模型上來(lái)看，分布估計(jì)算法與傳統(tǒng)進(jìn)化算法不同：傳統(tǒng)進(jìn)化算法是基于對(duì)種群中的各個(gè)個(gè)體進(jìn)行遺傳操作（交叉、變異等)來(lái)實(shí)現(xiàn)群體的進(jìn)化的，是對(duì)生物進(jìn)化“微觀”層面上的數(shù)學(xué)建模；而分布估計(jì)算法則是基于對(duì)整個(gè)群體建立數(shù)學(xué)模型，直接描述整個(gè)群體的進(jìn)化趨勢(shì)，是對(duì)生物進(jìn)化“宏觀”層面上的數(shù)學(xué)建模。其次，分布估計(jì)算法給人類(lèi)解決復(fù)雜的優(yōu)化問(wèn)題提供了新的工具，它通過(guò)概率模型可以描述變量之間的相互關(guān)系，從而對(duì)解決非線性、變量耦合的優(yōu)化問(wèn)題更加有效。

分布估計(jì)算法（EDA)和CC結(jié)合得到的CEDA能夠有效地逃離局部最優(yōu)解，特別是在協(xié)同個(gè)體數(shù)目較少的時(shí)候，但是和標(biāo)準(zhǔn)EDA相比，CEDA耗費(fèi)的計(jì)算代價(jià)更大。

3.2 合作型協(xié)同演化算法結(jié)構(gòu)和改進(jìn)演化算子結(jié)合

還有一些算法是通過(guò)對(duì)已有的算法中的算子進(jìn)行修改或增減，然后結(jié)合CC結(jié)構(gòu)來(lái)改善性能。

3.2.1 隨機(jī)分組策略和自適應(yīng)權(quán)值策略

楊振宇等［7］采用隨機(jī)分組策略和自適應(yīng)權(quán)值策略改進(jìn)CCDE，提出了新的更加有效的DECC［7］。隨機(jī)分組策略的“隨機(jī)”指的是每個(gè)變量被分配到任何一個(gè)子問(wèn)題中的機(jī)會(huì)相同，它增加相關(guān)的變量分在同一分組的概率，算法在優(yōu)化的過(guò)程中會(huì)自動(dòng)更新分組結(jié)構(gòu)；自適應(yīng)加權(quán)機(jī)制在CC框架中每個(gè)優(yōu)化周期結(jié)束后，對(duì)每個(gè)組構(gòu)成的決策變量分量增加一個(gè)權(quán)值，然后使用指定演化算法優(yōu)化這m個(gè)權(quán)值構(gòu)成的權(quán)值向量，從而進(jìn)一步提高當(dāng)前解的質(zhì)量。自適應(yīng)加權(quán)機(jī)制對(duì)于處理不可分問(wèn)題效果很明顯。

隨后李曉東等［48］用這兩種策略改進(jìn)CPSO，得到CCPSO。實(shí)驗(yàn)結(jié)果表明，這兩種策略能夠明顯改進(jìn)先前的CC算法解決大規(guī)模問(wèn)題的性能，CCPSO的性能較之CPSO也有了大幅的提升。

然而，DECC算法框架中仍然存在一個(gè)在實(shí)際應(yīng)用中很難確定的參數(shù)，即分組大小。這主要是因?yàn)樽顑?yōu)的分組大小往往是問(wèn)題相關(guān)的，一般來(lái)說(shuō)子問(wèn)題規(guī)模越小越容易優(yōu)化，所以對(duì)于可分問(wèn)題，分組大小越小越好；而另一方面，對(duì)于不可分問(wèn)題，則分組大小越大越好，因?yàn)樗芴峁└叩母怕蕦⒋嬖谙嚓P(guān)性的決策變量分在同一組。另外，即使對(duì)于同一問(wèn)題的不同優(yōu)化階段，最優(yōu)的分組大小也不易確定，比如在優(yōu)化初期，小的分組大小能更快地幫助算法找到一些有潛力的搜索子空間；而在優(yōu)化后期，大的分組大小能在子問(wèn)題中包含更多的全局信息，這些全局信息對(duì)算法收斂到全局而非局部極值點(diǎn)很有用。所以，如果能根據(jù)問(wèn)題特性及不同的優(yōu)化階段自動(dòng)確定合適的分組大小，將有望使算法發(fā)揮出更好的性能。

因此，楊振宇等［15］采用動(dòng)態(tài)分組規(guī)模的方法進(jìn)一步改進(jìn)DECC，提出MLCC算法。在MLCC算法中，首先根據(jù)不同分組大小設(shè)計(jì)一組問(wèn)題分解器，然后將它們置于一個(gè)問(wèn)題分解器池中，池中的每個(gè)分解器都代表了它所能涵蓋的決策變量相關(guān)層次。當(dāng)使用MLCC算法優(yōu)化一個(gè)給定的問(wèn)題時(shí)，演化過(guò)程仍然被劃分為若干個(gè)演化周期，在每個(gè)周期的開(kāi)始，算法首先根據(jù)其歷史性能表現(xiàn)選擇一個(gè)問(wèn)題分解器，之后該問(wèn)題分解器被用來(lái)將原大規(guī)模問(wèn)題分解成若干個(gè)子問(wèn)題；然后MLCC算法將采用一種指定的演化算法分別對(duì)每個(gè)子問(wèn)題求解，當(dāng)每個(gè)演化周期結(jié)束后，選擇使用的問(wèn)題分解器的性能記錄將用它在當(dāng)前周期的性能表現(xiàn)替代。根據(jù)這種工作機(jī)制，MLCC算法可以在演化過(guò)程中根據(jù)需要自動(dòng)選擇合適的問(wèn)題分解器，達(dá)到分組大小層面的自適應(yīng)。

李曉東等［49］用動(dòng)態(tài)分組規(guī)模的策略改進(jìn)CPSO，得到CCPSO2。

3.2.2 根據(jù)自變量的方差大小進(jìn)行分組

王瑜［9］提出的 VP-DECC［9］中，方差較大的自變量將被選出構(gòu)成當(dāng)前要優(yōu)化的子群體。首先計(jì)算d維自變量的方差，按大小排序，按從大到小的順序分別將個(gè)體分配到子群體中去，保證正在優(yōu)化的子群體中的自變量是當(dāng)前方差最大的一批自變量。VP-DECC能夠進(jìn)一步提升DECC處理復(fù)雜高維問(wèn)題的能力。

3.2.3 基于貢獻(xiàn)的分組方法

基于貢獻(xiàn)的 CC算法——CBCC［50］基于所有子空間對(duì)全局適應(yīng)度的貢獻(xiàn)選擇一定數(shù)目的子空間進(jìn)行進(jìn)一步優(yōu)化，減輕了不同子空間之間的不平衡，允許更有效地利用計(jì)算資源。CBCC的算法流程如下：

（1)隨機(jī)初始化群體，計(jì)算群體適應(yīng)度，得到最優(yōu)適應(yīng)度和最優(yōu)個(gè)體。

（2)根據(jù)每個(gè)子空間對(duì)全局適應(yīng)度的貢獻(xiàn)，按照循環(huán)賽模式選擇子群體。

（3)選擇最大貢獻(xiàn)的子空間進(jìn)一步優(yōu)化。（4)重復(fù)（2)和（3)，直到達(dá)到終止條件。

CBCC的主要缺點(diǎn)是對(duì)于局部改變反應(yīng)慢，且依賴(lài)演化早期的信息積累，這需要用自適應(yīng)的方法維持局部貢獻(xiàn)和全局貢獻(xiàn)之間的平衡。

3.2.4 一些變異因子作用于演化算法，和CC結(jié)構(gòu)相結(jié)合

一些變異因子作用于演化算法，和CC結(jié)構(gòu)相結(jié)合，同樣能夠改善CC算法的性能。

自適應(yīng)的方法已經(jīng)廣泛地應(yīng)用于標(biāo)準(zhǔn)演化算法中改善算法性能，因此一種CCEA［51］用自適應(yīng)變異因子去更新搜索方向和搜索步長(zhǎng)，極大地改善了標(biāo)準(zhǔn)CCEA的性能。

Aichour M［52］第一次將選擇變異因子作用于經(jīng)典GP，設(shè)計(jì)出CCGP來(lái)解決符號(hào)回歸問(wèn)題。主要思想是用變異去關(guān)注沒(méi)有正確演化的基因組區(qū)域。選擇表現(xiàn)最差的子樹(shù)進(jìn)行變異，它將被新的隨機(jī)子樹(shù)替代。子樹(shù)的表現(xiàn)是通過(guò)局部演化來(lái)衡量的，局部演化衡量子樹(shù)的表現(xiàn)，是將子樹(shù)用一個(gè)自然數(shù)替代計(jì)算這個(gè)修改個(gè)體的適應(yīng)度，它和原個(gè)體的適應(yīng)度差值就是子樹(shù)的表現(xiàn)。

3.2.5 PCA策略用于CC結(jié)構(gòu)

Omidvar M［53］用PCA（主成分分析)降低問(wèn)題維數(shù)和用演化過(guò)程中得到的信息改進(jìn)變量分組的概率這兩種策略改進(jìn)DECC。PCA的主要步驟如下：

（1)減去平均值：該階段所有的數(shù)據(jù)項(xiàng)減去群體的平均值，得到平均調(diào)整數(shù)據(jù)。

（2)基于給定的群體計(jì)算協(xié)方差矩陣。

（3)計(jì)算協(xié)方差矩陣的特征值和特征向量。

（4)將協(xié)方差矩陣的特征向量按特征值從大到小排序，特征值最高的特征向量是群體的主成分。因此通過(guò)選擇前n個(gè)最大的特征向量可以降低數(shù)據(jù)集的維數(shù)。

（5)創(chuàng)建新的數(shù)據(jù)集。即（4)中得到的特征向量集乘以（1)中得到的調(diào)整數(shù)據(jù)集。

PCA能夠計(jì)算特征向量任意兩維之間的比率，如果該值在提前設(shè)定的范圍中，這兩個(gè)自變量將放入同一個(gè)子空間。這種方法極大地提升了DECC解決高維相關(guān)性問(wèn)題的性能。

3.2.6 修改已有的算法中的部分算子

Lee Ching-Hung［54］修改 CCDE中 DE的變異策略增強(qiáng)多樣性，運(yùn)用自適應(yīng)縮放因子策略進(jìn)一步提升算法精確度和收斂速度。同時(shí)用BP方法進(jìn)行局部搜索，有效地克服早熟收斂的缺點(diǎn)，改善CCDE的性能。

3.3 非CC算法結(jié)構(gòu)的解決大規(guī)模問(wèn)題的演化算法

還有一些其他的算法并不是利用CC算法結(jié)構(gòu)去有效地解決大規(guī)模問(wèn)題，例如，SOUPDE算法［55］的主要思想是重排策略結(jié)合自適應(yīng)DE中的擴(kuò)展因子；基于動(dòng)態(tài)維數(shù)交叉［56，57］的 PSO 算法；利用自適應(yīng)協(xié)方差矩陣的旋轉(zhuǎn)不變性有效地解決不可分問(wèn)題的CMA-ES算法［58］，不僅允許每一維自變量對(duì)應(yīng)不同的變異步長(zhǎng)，而且用一個(gè)旋轉(zhuǎn)矩陣保證變異沿著解決不可分問(wèn)題的優(yōu)化目標(biāo)的方向前進(jìn)。

4 合作型協(xié)同演化算法的應(yīng)用

合作型協(xié)同演化算法已經(jīng)廣泛應(yīng)用于諸多領(lǐng)域，如電子工程、模式識(shí)別和交通運(yùn)輸規(guī)劃等。

4.1 CC算法解決網(wǎng)絡(luò)問(wèn)題

Potter A M將CC算法成功地運(yùn)用于概念學(xué)習(xí) 和 神 經(jīng) 網(wǎng) 絡(luò) 結(jié) 構(gòu) 中 去［59］。Garcia-Pedrajas N等［60］提出一種基于協(xié)作型協(xié)同演化的演化人工神經(jīng)網(wǎng)絡(luò)的方法，稱(chēng)為COVNET。Kimura S等［61］將CC算法用于推斷大規(guī)模基因網(wǎng)絡(luò)的S-system模型。Chandra R等［62］用 Memetic框架結(jié)合CC結(jié)構(gòu)、用NSP（Neuron Based Subpopulation)將網(wǎng)絡(luò)分解到神經(jīng)元級(jí)別。Ruela A S等［63］將CC算法用于WSN的物理拓?fù)涞目焖僭O(shè)計(jì)，目標(biāo)是設(shè)計(jì)出能夠體現(xiàn)高聚類(lèi)系數(shù)和小的平均最短路徑長(zhǎng)度的物理拓?fù)?，改善基于路由的最小化能量消耗和延遲的樹(shù)結(jié)構(gòu)。Carvalho A［64］用CCGA算法學(xué)習(xí)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)，將問(wèn)題分解為兩個(gè)子部分，一個(gè)尋找節(jié)點(diǎn)的順序，一個(gè)尋找優(yōu)化連接矩陣。Supu-domchok S等［65］在CC結(jié)構(gòu)中通過(guò)研究最大化ATP以及最大化所有光通量值之和的ATP來(lái)進(jìn)行枯草桿菌代謝網(wǎng)絡(luò)的流量平衡分析。其中最大化ATP是傳統(tǒng)的線性目標(biāo)函數(shù)，最大化所有光通量值之和的ATP是非線性目標(biāo)函數(shù)。

4.2 CC算法作用于模型設(shè)計(jì)和應(yīng)用問(wèn)題

曹先彬等［66］提出了一種基于協(xié)同演化的行人檢測(cè)系統(tǒng)。滕弘飛等［25］提出基于對(duì)偶系統(tǒng)的協(xié)同演化的衛(wèi)星模型布局設(shè)計(jì)。孫偉等［67］提出將CCGA用于全斷面巖石掘進(jìn)機(jī)圓盤(pán)刀具布置設(shè)計(jì)。Nebti S等［68］用CC改善徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)（RBFNN)用于識(shí)別手寫(xiě)阿拉伯?dāng)?shù)字。Izzah等［69］用CC算法解決云計(jì)算中SaaS（軟件經(jīng)營(yíng))安置問(wèn)題，即SaaS組成部分之間的交互以及SaaS數(shù)據(jù)部分之間的交互。梁昌洪等［70］基于CC提出一種新的分解策略和協(xié)同方法解決無(wú)功優(yōu)化問(wèn)題。分解策略是基于電壓母線的敏感性和動(dòng)力系統(tǒng)中母線的衍化電力距離。Sim等［71］運(yùn)用CCGA解決煉油廠調(diào)度的全局優(yōu)化。Wu A等［72］用一種基于遺傳性的去耦自適應(yīng)CC算法進(jìn)行電力電子電路優(yōu)化設(shè)計(jì)。周翔等［73］提出一種結(jié)合了GA和離散PSO的CC算法解決模糊處理時(shí)間和模糊交貨日期條件下的多處理路徑的車(chē)間作業(yè)調(diào)度。

4.3 CC算法解決其他問(wèn)題

Panait L［74，75］提出了一種在協(xié)作型協(xié)同演化框架下將傳統(tǒng)演化計(jì)算技術(shù)應(yīng)用到多智能體行為學(xué)習(xí)領(lǐng)域的方法。Au C K［76，77］用CC算法解決動(dòng)態(tài)優(yōu)化問(wèn)題。Nema S等［78］結(jié)合了粒子群算法、梯度搜索和CC框架平衡探索和搜索，快速、準(zhǔn)確、高效地解決約束優(yōu)化問(wèn)題。Boonlong K等［79］用CCGA鑒定粒子圖像測(cè)速中的錯(cuò)誤速度矢量。李偉［80，81］用基于CC結(jié)構(gòu)的免疫診斷框架定義及分析誤差診斷，改進(jìn)了誤差診斷方法的精確度，克服動(dòng)態(tài)環(huán)境中誤診的缺陷，由免疫細(xì)胞之間的相互促進(jìn)和抑制的方法來(lái)實(shí)現(xiàn)誤差診斷。

5 結(jié)束語(yǔ)

合作型協(xié)同演化算法與普通演化算法的根本差別在于，合作型協(xié)同演化算法中一個(gè)個(gè)體的適應(yīng)度的計(jì)算是通過(guò)和其他個(gè)體相互交互的過(guò)程中合作進(jìn)行的。本文從合作型協(xié)同演化算法結(jié)構(gòu)（包括問(wèn)題分解、子空間的相關(guān)性、適應(yīng)度值分配以及群體多樣性等幾個(gè)重要方面)的探究、具體的一個(gè)個(gè)合作型協(xié)同演化算法的介紹以及利用合作型協(xié)同演化算法解決不同類(lèi)型的問(wèn)題這三個(gè)方面介紹了合作型協(xié)同演化算法目前的研究進(jìn)展，從目前的發(fā)展情況來(lái)看，作者認(rèn)為合作型協(xié)同演化算法在以下幾個(gè)方面有待進(jìn)一步深入研究。

5.1 問(wèn)題分解策略

對(duì)于合作型協(xié)同演化算法結(jié)構(gòu)，除了自然分解之外，問(wèn)題分解并沒(méi)有普遍性的比較好的分解方法。近年來(lái)，對(duì)于問(wèn)題分解策略的研究是一個(gè)熱點(diǎn)，但是如何能夠得到比較理想的結(jié)果、比較好的分組，還需要進(jìn)一步研究。

5.2 子空間相關(guān)性

當(dāng)前對(duì)于子空間相關(guān)性的研究，主要是通過(guò)統(tǒng)計(jì)計(jì)算兩個(gè)子空間的相關(guān)系數(shù)，然后對(duì)子空間進(jìn)行分解和合并。但是，除了統(tǒng)計(jì)計(jì)算相關(guān)性之外，是否還存在其他的合理的方法得到子空間的相關(guān)性關(guān)系亟待探索。

5.3 合作型協(xié)同演化算法結(jié)構(gòu)和高維優(yōu)化算法相

結(jié)合

目前的合作型協(xié)同演化算法主要是將合作型協(xié)同演化算法結(jié)構(gòu)和基本的演化算法相結(jié)合。除了合作型協(xié)同演化算法結(jié)構(gòu)之外，還有一些別的高維優(yōu)化算法也能夠較為有效地解決大規(guī)模優(yōu)化問(wèn)題，是否能將二者結(jié)合起來(lái)，更加有效地解決高維優(yōu)化問(wèn)題，也是當(dāng)前的研究熱點(diǎn)。

5.4 合作型協(xié)同演化算法結(jié)構(gòu)和新興演化算法相

結(jié)合

近年來(lái)涌現(xiàn)了很多新興的演化算法，主要包括覓食算法（細(xì)菌覓食算法、蜂群覓食算法、人工蜂群算法等)、分布估計(jì)算法等。對(duì)于如何更好地將合作型協(xié)同演化算法結(jié)構(gòu)和新型演化算法相結(jié)合，提升這些算法的效果，這方面還需要深入的探索。

5.5 合作型協(xié)同演化算法的應(yīng)用

合作型協(xié)同演化算法應(yīng)用主要涉及到數(shù)值優(yōu)化、調(diào)度問(wèn)題、博弈策略設(shè)計(jì)、模式識(shí)別以及數(shù)據(jù)挖掘等，在這些領(lǐng)域合作型協(xié)同演化算法有著極為廣闊的研究前景，等著我們一步步探究。

［1］ Potter A M，De Jong K A.A cooperative co-evolutionary approach to function optimization［C］∥Proc of the 3rd International Conference on Parallel Problem Solving from Nature，1994：249-257.

［2］ Liu Y，Yao X，Zhao Q，et al.Scaling up fast evolutionary programming with cooperative coevolution［C］∥Proc of the 2001Congress on Evolutionary Computation，2001：1101-1108.

［3］ Potter A M ，De Jong K A.Evolving neural networks with collaborative species［C］∥Proc of 1995Summer Computer Simulation Conference，1995：340-345.

［4］ Potter A M，De Jong K A，Grefenstette J J.A co-evolutionary approach to learning sequential decision rules［C］∥Proc of the 6th International Conference on Genetic Algorithms，1995：366-370.

［5］ Potter A M ，De Jong K A.Cooperative coevolution：An architecture for evolving co-adapted subcomponents［J］.Evolutionary Computation，2000，8（1)：1-29.

［6］ Shi Y，Teng H，Li Z.Cooperative co-evolutionary differential evolution for function optimization［C］∥Proc of the 1st International Conference on Natural Computation，2005：1080-1088.

［7］ Yang Zhen-yu，Tang Ke，Yao Xin.Differential evolution for high dimensional function optimization［C］∥Proc of IEEE Congress on Evolutionary，2007：1.

［8］ Omidvar M N，Li X，Yang Z，et al.Cooperative co-evolution for large scale optimization through more frequent random grouping［C］∥Proc of IEEE World Congress on Computational Intelligence ，2010：1.

［9］ Wang Y，Li B，Lai X X.Variance priority based cooperative co-evolution differential evolution for large scale global optimization［C］∥Proc of the 2009IEEE Congress on Evolutionary Computation，2009：1232-1239.

［10］ Weicker K，Weicker N.On the improvement of coevolutionary optimizers by learning variable interdependencies［C］∥Proc of the 1999Congress on Evolutionary Computation，1999：1627-1632.

［11］ Kim M W，Ryu J W.Species merging and splitting for efficient search in coevolutionary algorithm ［C］∥Proc of the 8th Pacific Rim International Conference on Artificial Intelligence（PRICAI 2004)，2004：332-341.

［12］ Kim M W，Ryu J W.An efficient coevolutionary algorithm using dynamic species control［C］∥Proc of the 3rd International Conference on Natural Computation，2007：431-435.

［13］ Ray T，Yao Xin.A cooperative coevolutionary algorithm with correlation based adaptive variable partitioning［C］∥Proc of 2009IEEE Congress on Evolutionary Computation，2009：983-989.

［14］ Chen Wen-xiang，Weise T，Yang Zhen-yu，et al.Largescale global optimization using cooperative coevolution with variable interaction learning［C］∥Proc of Parallel Problem Solving from Nature，2010：300-309.

［15］ Yang Z，Tang K，Yao X.Multilevel cooperative coevolution for large scale optimization ［C］∥Proc of the 2008 IEEE Congress on Evolutionary Computation，2008：1663-1670.

［16］ Chandra R，F(xiàn)rean M，Zhang Meng－jie.Building subcomponents in the cooperative coevolution framework for training recurrent neural networks ［R］.Technical Report，New Zealand：Victoria University of Wellington，2009.

［17］ Gomez F，Schmidhuber J，Miikkulainen R.Accelerated neural evolution through cooperatively coevolved synapses［J］.Journal of Machine Learning Research，2008（9)：937-965.

［18］ Min Shi.Empirical analysis of cooperative coevolution using blind decomposition［C］∥Proc of the 13th Annual Conference Companion on Genetic and Evolutionary Computation，2011：141-142.

［19］ Wiegand R P，Liles W C，De Jong K A.An empirical analysis of collaboration methods in cooperative coevolutionary algorithms［C］∥Proc of the 2nd Annual Conference Companion on Genetic Evolutionary Computation Conference，2001：1235-1242.

［20］ Luke S，Sullivan K，Abidi F.Large scale empirical analysis of cooperative coevolution［C］∥Proc of the 13th Annual Conference Companion on Genetic and Evolutionary Computation Conference，2011：151-152.

［21］ Panait L，Luke S.Time-dependent collaboration schemes for cooperative coevolutionary algorithms［C］∥Proc of the AAAI Fall Symposium on Coevolutionary and Coadaptive Systems，2005：1.

［22］ Cr?ciun C，Nicoar?M，Zaharie D.Enhancing the scalability of metaheuristic by cooperative coevolution［C］∥Proc of the 7th International Conference on Large-Scale Scientific Computing，2010：310-317.

［23］ Zhu F，Guan S.Cooperative co-evolution of GA-based classifiers based on input decomposition［J］.Journal of Engineering Applications of Artificial Intelligence，2008，21（8)：1360-1369.

［24］ Wang Chao，Gao Jing-huai.A new differential evolution algorithm with cooperative coevolutionary selection operator for waveform inversion［C］∥Proc of 2010IEEE International Geoscience and Remote Sensing Symposium（IGARSS)，2011：688-690.

［25］ Teng Hong-fei，Chen Yu，Zeng Wei，et al.A dual-system variable-grain cooperative coevolutionary algorithm：Satellite-module layout design［J］.IEEE Transactions on Evolutionary Computation，2010，14（3)：438-455.

［26］ Shi M，Wu H.Pareto cooperative coevolutionary genetic algorithm using reference sharing collaboration［C］∥Proc of the 11th Annual Conference on Genetic and Evolutionary Computation，2009：867-874.

［27］ Shi M.Comparison of Sorting Algorithms for Multi-fitness Measurement of Cooperative Coevolution［C］∥Proc of the 11th Annual Conference on Genetic and Evolutionary Computation，2009：2583-2588.

［28］ Jansen T，Wiegand R P.Exploring the explorative advantage of the cooperative coevolutionary（1＋1)EA ［C］∥Proc of the 5th Annual Conference on International Conference on Genetic and Evolutionary Computation，2003：310-321.

［29］ Au C-K，Leung H-F.Biasing mutations in cooperative coevolution［C］∥Proc of IEEE Congress on Evolutionary Computation，2007：828-835.

［30］ Popovici E，De Jong K A.The effects of interaction frequency on the optimization performance of cooperative coev-olution［C］∥Proc of the 8th Annual Conference on Genetic and Evolutionary Computation Conference，2006：353-360.

［31］ Popovici E ，De Jong K.Understanding cooperative co-evolutionary dynamics via simple fitness landscapes［C］//Proc of the 2005Conference on Genetic and Evolutionary Computation，2005：507-514.

［32］ Brest J，Zamuda A，Boskovic B，et al.High-dimensional real parameter optimization using self-adaptive differential evolution algorithm with population size reduction ［C］∥Proc of IEEE Congress on Evolutionary Computation，2008：2032-2039.

［33］ Sofge D，De Jong K，Schultz A.A blended population approach to cooperative coevolution for decomposition of complex problems［C］∥Proc of the Congress on Evolutionary Computation，2002：413-418.

［34］ van den Bergh F，Engelbrecht A P.A cooperative approach to particle swarm optimization［J］.IEEE Transactions on Evolutionary Computation，2004，8（3)：225-239.

［35］ Shi Y，Teng H，Li Z.Cooperative co-evolutionary differential evolution for function optimization［C］∥Proc of the 1st International Conference on Natural Computation，2005：1080-1088.

［36］ Zou Wen-ping，Zhu Yun-long，Chen Han-ning，et al.Cooperative approaches to artificial bee colony algorithm［C］∥Proc of the 2010International Conference on Computer Application and System Modeling（ICCASM)，2010：44-48.

［37］ Karaboga D.An idea based on bee swarm for numerical optimization［R］.Technical Report-TR06，Kayseri：Erciyes U-niversity，2005.

［38］ Vanneschi L，Mauri G，Valsecchi A，et al.Heterogeneous cooperative coevolution：strategies of integration between GP and GA［C］∥Proc of the 8th Annual Conference on Genetic and Evolutionary Computation，2006：361-368.

［39］ Maniadakis M，Trahanias P.Assessing hierarchical cooperative coevolution［C］∥Proc of the 19th IEEE International Conference on Tools with Artificial Intelligence （ICTAI-07)，2007：391-398.

［40］ Parsopoulos K E.Cooperative micro-differential evolution for high-dimensional problems［C］∥Proc of the 11th Annual Conference on Genetic and Evolutionary Computation Conference（GECCO 2009)，2009：531-538.

［41］ Parsopoulos K E.Cooperative micro-particle swarm optimization［C］∥Proc of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation，2009：467-474.

［42］ Chandra R，F(xiàn)rean M，Zhang Meng－jie.A memetic framework for cooperative coevolution of recurrent neural networks［C］∥Proc of the 2011International Joint Conference on Neural Networks（IJCNN 2011)，2011：673-680.

［43］ Chandra R，F(xiàn)rean M，Zhang M.A memetic framework for cooperative co-evolutionary feedforward neural networks［R］.Technical Report ECSTR10-22，Wellington：School of Computing and Engineering，Victoria University of Wellington，2010.

［44］ Wang Shuai-qiang，Byron J G，Wang Ke，et al.CCRank：Parallel learning to rank with cooperative coevolution［C］∥Proc of the 25th AAAI Conference on Artificial Intelligence，2011：1249-1254.

［45］ Bucci A，Pollack J B.On identifying global optima in cooperative coevolution［C］∥Proc of the 2005Conference on Genetic and Evolutionary Computation，2005：539-544.

［46］ Guo Yi-nan，Cheng Jian，Lin Yong.Cooperative interactive cultural algorithms adopting knowledge migration ［C］∥Proc of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation，2009：193-200.

［47］ Vo C，Panait L，Luke S.Cooperative coevolution and univariate estimation of distribution algorithms［C］∥Proc of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms，2009：141-150.

［48］ Li Xiao-dong，Yao Xin.Tackling high dimensional non separable optimization problems by cooperatively coevolving particle swarms［C］∥Proc of IEEE Congress on Evolutionary Computation，2009：1546-1553.

［49］ Li Xiao-dong，Yao Xin.Cooperatively coevolving particle swarms for large scale optimization［J］.IEEE Transactions on Evolutionary Computation，2012，16（2)：210-224.

［50］ Omidvar M N，Li Xiao-dong，Yao Xin.Smart use of computational resource based on contribution for cooperative coevolutionary algorithms［C］∥ Proc of the 13th Annual Conference on Genetic and Evolutionary Computation（GECCO’11)，2011：1115-1122.

［51］ Au C-K，Leung H-f.Guided mutations in cooperative coevolutionary algorithms for function optimization［C］∥Proc of the 19th IEEE International Conference on Tools with Artificial Intelligence，2007：407-414.

［52］ Aichour M，Lutton E.Cooperative co-evolution inspired operators for classical GP schemes［C］∥Proc of International Workshop on Nature Inspired Cooperative Strategies for Optimization（NICSO’07)，2007：169-178.

［53］ Omidvar M N，Li Xiao-dong，Yang Zhen-yu，et al.Cooperative co-evolutionary algorithm for large scale optimization through more frequent random grouping［C］∥Proc of the 2010IEEE Congress on Evolutionary Computation，2009：1-8.

［54］ Lee Ching-Hung，Chung Pei-yuan，Chang Hao-han.A novel hybrid differential evolution algorithm：A comparative study on function optimization［C］∥ Proc of the International MultiConference of Engineers and Computer Scientists，2011：1-6.

［55］ Weber M，Neri F，Tirronen V.Shuffle or update parallel differential evolution for large-scale optimization ［J］.Soft Computing，2011，15（11)：2089-2107 .

［56］ Hu Cheng－yu，Wang Bo.Particle swarm optimization with dynamic dimension crossover for high dimensional problems［J］.Computing Technology and Automation，2008，28（1)：92-95.（in Chinesee)

［57］ Hu Cheng－yu，Yan Xue-song，Li Chuan-feng.Particle swarm optimization with dynamic dimension crossover for high dimensional problems［C］∥Proc of ISICA’08，2008：750-759.

［58］ Omidvar M，Li X.A comparative study of CMA-ES on large scale global optimization［C］∥Proc of the 23rd Australasian Joint Conference on Advances in Artificial Intelligence，2010：303-312.

［59］ Potter M A.The design and analysis of a computational model of cooperative coevolution［D］.Virginia：George Mason U-niversity，1997.

［60］ Garcia-Pedrajas N，Hervas-Martinez C，Munoz-Perez J.COVNET：A cooperative coevolutionary model for evolving artificial neural networks［J］.IEEE Transactions on Neural Networks，2003：14（3)：575-596.

［61］ Kimura S，Ide K，Kashihara A，et al.Inference of S-system models of genetic networks using a cooperative coevolutionary algorithmc［J］.Journal of Bioinformatics，2005，21（7)：1154-1163.

［62］ Chandra R，F(xiàn)rean M，Zhang Meng－jie.A memetic framework for cooperative co-evolutionary feedforward neural networks［R］.Technical Report ECSTR10-22，Wellington：School of Computing and Engineering，Victoria University of Wellington，2010.

［63］ Ruela A S，Aquino A L L，Guimaraes F G.A cooperative coevolutionary algorithm for the design of wireless sensor networks Track name：Bio-inspired solutions for wireless sensor networks［C］∥Proc of GECCO’11，2011：607-614.

［64］ Carvalho A.A cooperative coevolutionary genetic algorithm for learning Bayesian network structures［C］∥Proc of GECCO’11，2011：1131-1138.

［65］ Supudomchok S，Chaiyaratana N，Phalakomkule C.Cooperative coevolutionary approach for flux balance in bacillus subtilis［C］∥Proc of the 2008IEEE World Congress on Computational Intelligence，2008：1226-1231.

［66］ Cao X，Qiao H，Keane J.A low-cost pedestrian-detection system with single optical camera ［J］.IEEE Transactions on Intelligent Transportation Systems，2008，9（1)：58-67.

［67］ Sun Wei，Huo Jun-zhou，Chen Jing，et al.Disc cutters’layout design of the full-face rock tunnel boring machine（TBM)using a cooperative coevolutionary algorithm ［J］.Journal of Mechanical Science and Technology，2011，25（2)：415-427.

［68］ Nebti S，Boukerram A.An improved radial basis function neural network based on a cooperative coevolutionary algorithm for handwritten digits recognition［C］∥Proc of the 2010International Conference on Machine and Web Intelligence（ICMWI)，2010：464-468.

［69］ Yusoh Z I M，Tang Mao-lin.A cooperative coevolutionary algorithm for the composite SaaS placement problem in the cloud［C］∥Proc of ICONIP’10，2010：618-625.

［70］ Liang C H，Chung C Y，Wong K P，et al.Parallel optimal reactive power flow based on cooperative coevolutionary differential evolution and power system decomposition ［J］.IEEE Transactions on Power System，2007，22（1)：319-323.

［71］ Dias L M S D M，Pacheco M A I C.Refinery scheduling optimization using genetic algorithms and cooperative coevolution［C］∥Proc of the 2007IEEE Symposium on Computational Intelligence in Scheduling（CI-Sched 2007)，2007：151-158.

［72］ Wu A，Zhang Jin，Chung H.Decoupled optimal design for power electronic circuits with adaptive migration in coevolutionary environment［J］.Journal of Applied Soft Computing，2011，11（1)：23-31.

［73］ Zhou Xiang，Bao Zhen-qiang，Wang Gui-jun，et al.Optimization of fuzzy job-shop scheduling with multi-process routes and its co-evolutionary algorithm ［C］∥Proc of the 4th International Conference on Intelligent Computation Technology and Automation，2011：866-870.

［74］ Panait L，Luke S.Cooperative multi-agent learning：The state of the art［J］.Journal of Autonomous Agents and Multi-Agent Systems，2005，11（3)：387-434.

［75］ Panait L，Luke S，Wiegand R P.Biasing coevolutionary search for optimal multi-agent behaviors［J］.IEEE Transactions on Evolutionary Computation，2006，10（6)：629-645.

［76］ Au C-K，Leung H-F.On the behavior of cooperative coevolution in dynamic environments［C］∥Proc of the 2008IEEE Congress on Evolutionary Computation，2008：2827-2836.

［77］ Au C-K，Leung H-F.Investigating collaboration methods of random migrant scheme in cooperative coevolution［C］∥Proc of the 2009IEEE Congress on Evolutionary Computation，2009：2701-2707.

［78］ Nema S，Goulermas J Y，Sparrow G，et al.A hybrid cooperative search algorithm for constrained optimization ［J］.Structural and Multidiscplinary Optimization，2011，43（1)：107-119.

［79］ Boonlong K，Maneeratana K，Chaiyaratana N.Determination of erroneous velocity vectors by cooperative coevolutionary genetic algorithm［C］∥Proc of the 2006IEEE Conference on Cybernetics and Intelligent Systems，2006：1-6.

［80］ Li Wei.Research on the diagnosis learning technology based on the cooperative evolution mechanism［C］∥Proc of the 2009International Conference on Computational Intelligence and Software Engineering，2009：1-4.

［81］ Li Wei.Research on the application analysis technology for cooperative fault diagnosis［C］∥Proc of the 8th World Congress on Intelligent Control and Automation，2010：5790-5793.

附中文參考文獻(xiàn)：

［56］ 胡成玉，王博.基于動(dòng)態(tài)維度交叉的粒子群高維函數(shù)優(yōu)化［J］.計(jì)算技術(shù)與自動(dòng)化，2009，28（1)：92-95.

Research overview of cooperative coevolutionary algorithms

ZHANG Kai-bo，LI Bin
（Department of Electronic Science and Technology，University of Science and Technology of China，Hefei 230027，China)

Cooperative coevolution algorithm is a hot research topic in computational intelligence in recent years.Inspired by the principle of natural selection，cooperative coevolution algorithm constructs two or more groups and establishes the cooperative relationship among the groups.Two or more groups cooperates together to improve their performance，be adapted to dynamic evolutionary circumstance of complicated systems and large-scale evolutionary circumstance，thus achieving the goal of population optimization.The research state and advances of cooperative coevolution algorithms in domestic and foreign are discussed and surveyed.The paper introduces the three main aspects of cooperative coevolution algorithm：basic structure and corresponding studies，basic and improved algorithms，and some applications in the real life.Finally，research prospects are indicated.

cooperative coevolution algorithm；problem decomposition；subspace correlation

TP18

A

10.3969/j.issn.1007-130X.2014.04.018

2012-07-12；

2012-12-19

國(guó)家自然科學(xué)基金資助項(xiàng)目（61071024，U0835002)；教育部基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目

通訊地址：230027安徽省合肥市蜀山同區(qū)潛山路209號(hào)華邦光明世家2#801

Address：Room 801，Building 2，Huabang Guangmingshijia，209Qianshan Rd，Shushan Distric，Hefei 230027，Anhui，P.R.China

1007-130X（2014)04-0674-11

張凱波（1988-)，男，安徽六安人，碩士生，研究方向?yàn)楹献餍蛥f(xié)同演化和大規(guī)模 優(yōu) 化。E-mail：kbzhang＠ mail.ustc.edu.cn

ZHANG Kai-bo，born in 1988，MS candidate，his research interests include cooperative coevolution，and large scale optimization.