徐萍+王友才+王凱

0 引言

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

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

1 種間競(jìng)爭(zhēng)的協(xié)同進(jìn)化

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

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

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

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

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

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

2 基于種間競(jìng)爭(zhēng)的協(xié)同差分進(jìn)化算法

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

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

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

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

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

（2）種群初始化。

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

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

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

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

3 算法測(cè)試與性能分析

為驗(yàn)證CDE算法的有效性，通過對(duì)五個(gè)典型的無(wú)約束測(cè)試函數(shù)進(jìn)行測(cè)試，分別是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）算法進(jìn)行比較。

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

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

4 結(jié)語(yǔ)

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

參考文獻(xià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é)同進(jìn)化計(jì)算與多智能體系統(tǒng)，科學(xué)出版社，2006年。

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

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

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

[6] 吳斯，曹炬。帶記憶信息的協(xié)同進(jìn)化算法[J]，計(jì)算機(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].中國(guó)地質(zhì)大學(xué)碩士學(xué)位論文，2008年5月.

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

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