基于種間競爭的協(xié)同差分進化算法

徐萍+王友才+王凱

0 引言

差分進化算法（Differential Evolution， DE）作為一種新興的進化計算技術(shù)[1]具有算法操作簡單、適應(yīng)性強、魯棒性強、精確度高、收斂速度快等優(yōu)點。但由于在DE算法是通過父代個體差異和“貪婪”的選擇方式生成子代個體，個體之間僅存著競爭關(guān)系，通過個體之間的競爭而淘汰差的個體，保留優(yōu)秀個體，從而使解群體不斷向最優(yōu)解逼近，而沒有考慮其進化的環(huán)境和個體之間的復(fù)雜合作關(guān)系。使其存在著收斂速度和搜索魯棒性相沖突，算法隨著進化代數(shù)的增加和群體多樣性降低，后期收斂速度變慢，容易陷入局部最優(yōu)解等問題。

在生態(tài)學(xué)中認為，生存在一定自然環(huán)境資源制約中的種群，通過相互之間的競爭協(xié)同，能夠使雙方相互驅(qū)動提高性能和復(fù)雜性，從而實現(xiàn)種群之間的協(xié)同進化，已有的證據(jù)表明協(xié)同進化能大大加快生物進化的歷程[2]。而協(xié)同進化算法正是源于競爭協(xié)同的思想而發(fā)展起來的一種算法。在協(xié)同進化算法中，個體之間不僅存在競爭關(guān)系，同時也存在相互合作、相互促進的關(guān)系，各個子群體之間通過適應(yīng)度的關(guān)聯(lián)而共同進化。與傳統(tǒng)進化算法的區(qū)別在于協(xié)同算法在進化算法的基礎(chǔ)上，考慮了種群與環(huán)境之間、種群與種群之間在進化過程中的協(xié)調(diào)。由于協(xié)同進化算法的諸多優(yōu)越性，越來越多的學(xué)者對此進行了研究[3～6]，成為當(dāng)前進化計算的一個熱點問題。

1 種間競爭的協(xié)同進化

由生態(tài)學(xué)研究可知，進化的基本單位是個體或種群，種群是指在特定時間內(nèi)，由分布到同一區(qū)域的許多同種生物個體自然組成的生物系統(tǒng)。種群具有共同的基因庫，因此種群是種族生存的前提，是系統(tǒng)發(fā)展的結(jié)果。協(xié)同進化動力學(xué)系統(tǒng)是以種群為基礎(chǔ)的。

在一定生態(tài)環(huán)境中的種群，其進化不僅受到自身適應(yīng)度的影響，同時還受到環(huán)境和其他種群相互競爭的影響。如果不考慮種群間的相互作用，可以用下面的Logistic方程來描述種群增長與環(huán)境間的動力學(xué)特征：

式1中，K表示環(huán)境負荷量，r表示種群的個體增長率，N是種群的大小。這是一個單一種群的增長情況，它只考慮了種內(nèi)競爭，即種群內(nèi)部每增加一個個體，對種群本省增長的抑制作用為1/K。

以Logistic方程為基礎(chǔ)，進一步考慮種群間競爭的協(xié)同進化關(guān)系。假設(shè)有兩個相互競爭的種群P1和P2，均利用同一資源，則Logistic方程可以改成以下方程組來表示每個種群的增長：

式2中，K1和K2表示在沒有競爭的情況下種群P1和P2的環(huán)境負荷量；r1和r2表示種群P1和P2個體的最大瞬時增長率；N1和N2分別是種群P1和P2的大??；α12和α21是競爭系數(shù)，αij表示種群Pi的每個個體對種群Pj的競爭抑制作用。

由競爭方程組可知，種間競爭的結(jié)果主要取決于雙方的競爭抑制（α12和α21的大?。┘捌銴值的相對大小。對于一個由n個不同種群組成的群落，上述競爭方程可改寫成式3。

2 基于種間競爭的協(xié)同差分進化算法

將協(xié)同進化理論應(yīng)用到差分進化算法可以處理約束優(yōu)化問題[7～8] 和合作式協(xié)同差異演化問題[9～10]。而在生態(tài)學(xué)理論中，生物個體在自身進化過程中受個體適應(yīng)度、所處生態(tài)環(huán)境以及其他個體之間的相互競爭等因素的影響。在一定生態(tài)環(huán)境中的種群，其種群進化不僅受到自身適應(yīng)度的影響，同時還受到環(huán)境和其他種群相互之間的競爭協(xié)同的影響。因此，可以將結(jié)合了競爭與合作因素的種群間協(xié)同進化機制引入到差分進化算法中，對其性能進行改善。其中環(huán)境和種群間的協(xié)同競爭因素可以通過種群密度來體現(xiàn)。衡量種群競爭協(xié)同的一個主要因素是種群密度，如果種群密度大，則該種群的競爭能力強，反過來又增強了種群密度。

從式1可以看出，Logistic系數(shù)對種群密度的變化起著一種制動作用，使種群密度總是趨向于環(huán)境負荷量。當(dāng) 時，Logistic系數(shù)是正值，種群密度上升；當(dāng) 時，Logistic系數(shù)為0，此時種群密度不變；當(dāng) 時， Logistic系數(shù)是負值，種群密度下降。利用式1所表示的Logistic方程，提出基于競爭機制的協(xié)同差分進化算法（CDE）。

CDE算法的主要思想是以標(biāo)準(zhǔn)差分進化算法框架為基礎(chǔ)，將完整種群分為若干子種群，再進一步考慮子種群間基于種群密度的協(xié)同進化。算法在每次迭代中都依次進行進化過程和協(xié)同過程，其中進化過程采用標(biāo)準(zhǔn)差分進化算法的操作，協(xié)同過程通過種群競爭方程計算種群密度，并根據(jù)計算出的種群密度調(diào)整各個子種群的規(guī)模，即

由上可知，如果某子種群的密度增大，算法隨機產(chǎn)生個體加入該群體，有利于提高該群體的多樣性，從而在一定程度上提高了個體的全局分布。如果密度減少，則刪除適應(yīng)度小的個體。這種處理既體現(xiàn)了進化過程中的種間協(xié)同競爭，也體現(xiàn)出群體內(nèi)部個體之間的相互競爭過程。CDE算法的步驟如下：

（1）確定算法參數(shù)值，包括種群規(guī)模、變異因子、交叉因子、最大迭代次數(shù)、子種群數(shù)目、環(huán)境負荷量、增長率、競爭系數(shù)和精度要求等。

（2）種群初始化。

（3）計算每個個體適應(yīng)值，求出最優(yōu)適應(yīng)度和最優(yōu)個體。判斷最優(yōu)適應(yīng)度是否達到精度要求或是否達到最大迭代次數(shù)，若是則退出。

（4）計算子種群 的增長值，根據(jù)增長值調(diào)整種群規(guī)模。

（5）各子種群按照標(biāo)準(zhǔn)差分進化算法流程進行進化，生成下一代種群。

（6）迭代次數(shù)加1，返回至（3）。

3 算法測試與性能分析

為驗證CDE算法的有效性，通過對五個典型的無約束測試函數(shù)進行測試，分別是Sphere函數(shù)（f1）、Rosenbrock函數(shù)（f2）、Rastrigin函數(shù)（f3）、Griewank函數(shù)（f4）、Schaffer函數(shù)（f5）[11]，并且與標(biāo)準(zhǔn)DE算法中的DE7 [12]（rand/ 1/bin）算法進行比較。

實驗參數(shù)設(shè)置如下：種群規(guī)模60，最大進化代數(shù)10000，變異因子 ，交叉因子CR=0.5，子種群數(shù)目3，子種群初始規(guī)模30，環(huán)境負荷量為50，競爭系數(shù)取為子種群平均適應(yīng)度的比值。所有算法利用Matlab編程實現(xiàn)，為評價算法的收斂性能，以運行一次所得函數(shù)全局極小值點和收斂時間作為算法的衡量指標(biāo)，計算結(jié)果如表1所示。

從表1可以看出，CDE算法能夠以更短的收斂時間，搜索到質(zhì)量優(yōu)于DE7算法的解。圖1、2和3分別是某次搜索f1、f3和f4函數(shù)時CDE和DE7算法最優(yōu)適應(yīng)值的變化曲線。

4 結(jié)語

根據(jù)現(xiàn)有進化算法只考慮種群之間的競爭，而沒有考慮到種群之間的協(xié)同進化的問題，本文提出了基于競爭機制的協(xié)同差分進化算法。該算法除了采用標(biāo)準(zhǔn)差分進化算法個體適應(yīng)度控制進化的方式外，還考慮了種群與環(huán)境之間的相互作用以及種群間的協(xié)調(diào)，即基于種群密度的進化方式，這種方式增強了算法的全局搜索能力。通過對5個典型測試函數(shù)的仿真結(jié)果表明，CDE算法性能優(yōu)于標(biāo)準(zhǔn)差分進化算法，其能夠有效改善早熟收斂和提高收斂速度。

參考文獻

[1] Rainer Storn and Kenneth Price. Differential Evolution-A simple and efficient adaptive scheme for global optimization over continuous spaces [R]. Technical Report， TR-95-012， ICSI， March 1995.

[2] 焦李成，劉靜，鐘偉才著。協(xié)同進化計算與多智能體系統(tǒng)，科學(xué)出版社，2006年。

[3] 曹先彬，羅文堅等。基于生態(tài)種群競爭模型的協(xié)同進化[J]，軟件學(xué)報，2001年，12（4）：556-562。

[4] 李敏強，寇紀(jì)淞。多模態(tài)函數(shù)優(yōu)化的協(xié)同多群體遺傳算法[J]，自動化學(xué)報，2002，28（4）：497-504。

[5] 高鷹，姚振堅，謝勝利?；诜N群密度的粒子群優(yōu)化算法[J]，系統(tǒng)工程與電子技術(shù)，2006，28（6）：922-924，932。

[6] 吳斯，曹炬。帶記憶信息的協(xié)同進化算法[J]，計算機工程與科學(xué)，2008，30（3）：78-81。

[7] Bo Liu， Hannan Ma， Xuejun Zhang. A Co-evolutionary differential evolution algorithm for constrained optimization[C]. ICNC2007

[8] Fu-zhuo Huang， Ling Wang， Qie He. An effective co-evolutionary differential evolution for constrained optimization [J]. Applied mathematics and computation， 2007， 186：340-356.

[9] Yan-jun Shi， Hong-fei Teng， Zi-qiang Li. Cooperative co-evolutionary differential evolution for function optimization[C]. ICNC2005， 1080-1088.

[10] 張萍.協(xié)同差異演化方法在函數(shù)優(yōu)化中的應(yīng)用[D].中國地質(zhì)大學(xué)碩士學(xué)位論文，2008年5月.

[11] 王凌.智能優(yōu)化算法及其應(yīng)用[ M].北京：清華大學(xué)出版社，2001.1-6.

[12] 趙光權(quán)，彭喜元等. 基于混合優(yōu)化策略的微分進化改進算法[J].電子學(xué)報， 2006， 34（12A） ： 2402-2405.