基于種間競爭的協同差分進化算法

徐萍+王友才+王凱

0 引言

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

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

1 種間競爭的協同進化

由生態學研究可知，進化的基本單位是個體或種群，種群是指在特定時間內，由分布到同一區域的許多同種生物個體自然組成的生物系統。種群具有共同的基因庫，因此種群是種族生存的前提，是系統發展的結果。協同進化動力學系統是以種群為基礎的。

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

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

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

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

由競爭方程組可知，種間競爭的結果主要取決于雙方的競爭抑制（α12和α21的大小）及其K值的相對大小。對于一個由n個不同種群組成的群落，上述競爭方程可改寫成式3。

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

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

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

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

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

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

（2）種群初始化。

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

（4）計算子種群 的增長值，根據增長值調整種群規模。

（5）各子種群按照標準差分進化算法流程進行進化，生成下一代種群。

（6）迭代次數加1，返回至（3）。

3 算法測試與性能分析

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

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

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

4 結語

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

參考文獻

[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] 焦李成，劉靜，鐘偉才著。協同進化計算與多智能體系統，科學出版社，2006年。

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

[4] 李敏強，寇紀淞。多模態函數優化的協同多群體遺傳算法[J]，自動化學報，2002，28（4）：497-504。

[5] 高鷹，姚振堅，謝勝利。基于種群密度的粒子群優化算法[J]，系統工程與電子技術，2006，28（6）：922-924，932。

[6] 吳斯，曹炬。帶記憶信息的協同進化算法[J]，計算機工程與科學，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] 張萍.協同差異演化方法在函數優化中的應用[D].中國地質大學碩士學位論文，2008年5月.

[11] 王凌.智能優化算法及其應用[ M].北京：清華大學出版社，2001.1-6.

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