一種求解高維多模態(tài)復(fù)雜問題的差分文化算法＊

拓守恒，陶維天

（1.陜西理工學院數(shù)學與計算機科學學院，陜西 漢中 723000；2.甘肅中醫(yī)學院網(wǎng)絡(luò)中心，甘肅 蘭州 730000）

1 引言

隨著人工智能技術(shù)的發(fā)展，許多科學和工程領(lǐng)域大規(guī)模復(fù)雜難題得到了很好的解決，但更加復(fù)雜多維優(yōu)化問題隨之出現(xiàn)，需要學者們不斷探索更好的優(yōu)化處理方法。近10年來仿生智能優(yōu)化算法成為學者們的研究熱點，例如遺傳算法GA（Genetic Algorithm）、微粒群優(yōu)化算法、差分進化算法、蟻群算法和文化算法 CA（Cultural Algorithm）［1］等。文化算法是Reynolds于1994年提出的一種模擬文化進化過程的智能優(yōu)化算法。文化算法通過不斷地從種群進化過程中積累經(jīng)驗知識，然后再利用積累的經(jīng)驗知識去指導種群的進化，從而能夠有效提高算法的收斂性。該算法很適合大規(guī)模復(fù)雜系統(tǒng)的優(yōu)化處理，已成功應(yīng)用于大規(guī)?？臻g數(shù)據(jù)庫的數(shù)據(jù)挖掘、非線性約束優(yōu)化［2］、多目標優(yōu)化和機器學習等問題的處理。

2 文化算法及研究現(xiàn)狀

文化算法由種群空間（Population Space）、信度空間（Belief Space）和交流渠道（Communication Channel）構(gòu)成，交流渠道通過三個函數(shù)（接受函數(shù)Acceptance Function、影響函數(shù)Influence Function和更新調(diào)整函數(shù)Adjust Function）完成。文化算法的框架如圖1所示，種群空間和信度空間是兩個獨立的進化空間，彼此按照通信協(xié)議（Communication Protocol）進行聯(lián)系。

Figure 1 Cultural algorithm framework圖1 文化算法的基本框架

下面是算法的基本過程：

算法1 文化進化算法

由圖1和算法1可以看出，文化算法只是給出了一個進化框架，并沒有對種群空間和信度空間的進化過程進行具體要求和描述，因此研究者是通過將一些仿生智能優(yōu)化算法與文化算法結(jié)合來進行具體問題的處理。文獻［3］中Becerra等將差分進化引入文化算法的種群空間，成功解決了非線性約束優(yōu)化問題。文獻［4］將模擬退火算法引入到文化算法中，實現(xiàn)了移動代理網(wǎng)絡(luò)路由優(yōu)化。文獻［5］將免疫量子進化算法引入文化算法中，采用量子進化算法對種群空間進行優(yōu)化，信度空間采用免疫接種技術(shù)。黃海燕等提出了一種基于多層信念空間的文化算法［6］，通過對多層信念空間的擇優(yōu)選用將提取的知識用于提高進化計算性能，解決約束優(yōu)化問題。高麗麗等提出一種基于文化算法的粒子群優(yōu)化算法［7］，在群體空間采用基于高斯概率分布和柯西概率分布的改進PSO算法，在信念空間根據(jù)形勢知識和規(guī)范化知識指導種群的進化。郭驥等提出一種基于文化算法和高斯變異的多群協(xié)同粒子群算法［8］，用于求解高維多峰函數(shù)尋優(yōu)問題。郭一楠等［9］對文化算法的結(jié)構(gòu)、研究現(xiàn)狀和發(fā)展趨勢作了詳細的分析。

本文針對高維多模態(tài)優(yōu)化問題，提出一種基于差分進化和高斯分布估計的小生境文化進化算法模型，算法在種群空間中利用改進的差分進化算法進化種群，將獲得的小生境傳送到信度空間。在信度空間中，利用高斯分布算法求解每個小生境的最優(yōu)解，將小生境特征存儲記錄下來作為進化知識，然后用進化知識庫再去指導種群空間進行搜索。

3 關(guān)鍵技術(shù)

3.1 自適應(yīng)差分進化算法

差分進化算法 DE（Differential Evolution）［10］是由Storn和Price提出的一種用于優(yōu)化問題的啟發(fā)式算法。該算法采用實數(shù)編碼，模仿生物進化過程中“優(yōu)勝劣汰，適者生存”的原理，通過對個體進行方向擾動來達到使個體函數(shù)值下降的目的，對函數(shù)的可導性甚至連續(xù)性沒有要求，適用性很強。DE算法的優(yōu)點是實現(xiàn)簡單、參數(shù)少、全局優(yōu)化能力強，在求解高維復(fù)雜優(yōu)化問題時收斂速度快；其缺點是求解精度低。本文提出一種自適應(yīng)差分變異進化算法，自適應(yīng)變異操作是由隨機產(chǎn)生的二進制串ri＝ ｛s1，s2，…，sD｝與變異向量對應(yīng)屬性進行點乘，變異頻率隨著進化代數(shù)的增加逐步減小。

算法2 自適應(yīng)差分進化算法

其中，λ和F是縮放因子，在區(qū)間［0，2］內(nèi)取值，用于控制差分向量的擾動大小。rand（1，D）表示隨機產(chǎn)生一個D維的向量，每一維的值是（0，1）之間的隨機數(shù)。c＝0.9－0.3t／T是差分自適應(yīng)變異因子，用于控制二進制向量rd中1的個數(shù)，隨著c的值從0.9逐步遞減到0.6，rd中1的個數(shù)比例（c－0.5）從40%遞減到10%。其實，rd中1的個數(shù)比例就是差分變異概率。這樣算法在進化初期具有較大的變異概率，具有較強的差分擾動能力，隨著進化的深入，為了避免算法陷入停滯，算法通過逐步降低變異概率，保證算法的擾動能力，并且能夠逐步提高解的精度。算法時間復(fù)雜度為O（N），函數(shù)評價次數(shù)為N次。顯然，算法通過對個體的各維變量同時并行變異，不會隨著函數(shù)維數(shù)的增加而增加算法的時間復(fù)雜度和函數(shù)評價次數(shù)，適用于高維優(yōu)化問題。

雖然該差分進化算法用于高維復(fù)雜問題時，不會隨著維度的增加而增加時間復(fù)雜度，收斂速度快，但同時也存在求解精度低的問題。因此，本文利用小生境技術(shù)和高斯分布估計優(yōu)化算法進行小生境內(nèi)局部搜索，有效地解決了精度問題。

3.2 高斯分布估計優(yōu)化算法

分布估計算法EDA（Estimation of Distribution Algorithms）［11，12］通過概率模型來分析變量的關(guān)系，并根據(jù)當前種群的分布狀況來產(chǎn)生下一代種群。EDA的基本步驟有：

（1）建立解空間的概率模型。模型對當前種群進行評估并構(gòu)建優(yōu)秀個體解集來描述群體的分布概率模型。

（2）根據(jù)（1）構(gòu)建的概率模型產(chǎn)生下一代種群。

分布估計算法用于高維復(fù)雜優(yōu)化問題時能夠有效地降低時間復(fù)雜度，收斂速度快，求解精度高。本文采用高斯分布估計優(yōu)化算法GEDA（Gaussian Estimation of Distribution Algorithms）在一個小生境局部的范圍內(nèi)獲得局部最優(yōu)解。高斯分布估計搜索算法的具體描述如下：

算法3 高斯分布估計優(yōu)化算法

其中，α∈ （0，1），β∈ （0，1）為 學 習 因 子，xbest，j、xworst，j分別表示跟種群中最優(yōu)個體和最差個體所對應(yīng)的第j維的屬性值。

3.3 動態(tài)小生境識別算法

小生境（Niche）在生物學中是指特定環(huán)境下的一種生存環(huán)境。生物在其進化過程中，一般總是和與自己相同的物種在某一特定的地理區(qū)域中生活在一起，共同繁衍后代。小生境技術(shù)的基本思想是將生物學中的小生境概念應(yīng)用于進化計算中，將進化計算中的每一代個體劃分為若干類，每個類中選出若干適應(yīng)度較大的個體作為一個類的優(yōu)秀代表組成一個群，再在種群中，以及不同種群中之間，雜交、變異產(chǎn)生新一代個體群。

在小生境識別技術(shù)中，如何確定小生境半徑的大小是一個難點問題，往往需要先給出確定的半徑然后再去確定小生境個數(shù)。這樣，若小生境半徑設(shè)置過大，雖然有利于保持種群多樣性，但種群進化速度緩慢；若小生境半徑設(shè)置過小，雖然有利于提高算法的收斂速度，但種群多樣性缺失較快，算法容易早熟而陷入局部最優(yōu)［13，14］。作者在文獻［13］中根據(jù)種群中個體適應(yīng)值和個體相似度提出一種動態(tài)小生境識別算法，能夠準確有效地獲得小生境的大小特征。

4 基于差分進化和高斯分布估計的文化進化算法模型

4.1 算法模型

由于傳統(tǒng)的優(yōu)化算法在求解高維多模優(yōu)化問題時，收斂速度慢、穩(wěn)定性差、求解精度低和容易陷入局部搜索，本文將差分進化算法和高斯分布估計算法引入到文化算法模型中，將差分進化和高斯分布估計算法融合，利用文化算法的智能引導來提高算法的性能。算法描述如下。

算法4 基于差分進化和高斯分布估計的文化進化算法

（1）設(shè)置初始參數(shù)。

（2）種群空間進行種群的初始化，并評價其適應(yīng)值。

（3）利用自適應(yīng)差分進化算法對種群進行Tn代進化。

（4）利用動態(tài)小生境識別算法識別出種群空間中的小生境種群。

（5）接收函數(shù)Accept（）將小生境種群送至信度空間。

（6）在信度空間，對每個小生境種群采用高斯分布估計優(yōu)化算法進行境內(nèi)最優(yōu)解搜索，記錄每個小生境的大?。╱，δ）和境內(nèi)最優(yōu)解，并放入進化知識庫中。

（7）采用影響函數(shù)Influence（）對種群空間中的種群進行選擇：選擇不屬于進化知識庫中小生境內(nèi)的個體直接進入下一代（消去種群空間內(nèi)的小生境，避免以后對該區(qū)域進行重復(fù)密集搜索）。

（8）隨機產(chǎn)生新個體，如果其不在知識庫的某一小生境內(nèi)，將其加入種群中，重復(fù)該步驟，直到滿足種群規(guī)模大小。

（9）如果滿足終止條件，則結(jié)束運行并輸出信度空間進化知識庫內(nèi)的最優(yōu)解；否則，轉(zhuǎn)（3）進行下一代進化。

基于差分進化和高斯分布估計的文化進化算法模型如圖2所示。

4.2 算法分析

Figure 2 Cultural algorithm model based on DE and Gaussian distribution algorithm圖2 基于差分進化和高斯分布估計的文化進化算法模型

利用小生境技術(shù)和高斯分布估計優(yōu)化算法進行小生境內(nèi)局部搜索，雖然能夠有效地解決精度問題，但頻繁利用小生境識別算法和高斯分布估計算法需要付出巨大的時間代價。為了解決該問題，在種群空間中利用算法2進行Tn代的進化后再去識別小生境，一個小生境就對應(yīng)多峰值函數(shù)的一個峰值。將獲得小生境空間大小存入信度空間的進化知識庫。進化知識庫根據(jù)庫內(nèi)小生境的位置和特征將該小生境（峰值）削平，避免了種群再次陷入該區(qū)域進入重復(fù)搜索。并且通過進化知識庫的指導來選擇和產(chǎn)生新一代種群，能夠保證種群的多樣性。

5 仿真分析

為了評估本文算法的性能，選取了四個復(fù)雜高維的多峰值Benchmark函數(shù)（f1：Rastrigin；f2：Ackley；f3：Griewangk；f4：Rosenbrock）進行測試。在四個函數(shù)中f1～f3屬于多峰值函數(shù)，存在多個極值點；函數(shù)f4被稱作變態(tài)函數(shù)，變量之間具有很強的關(guān)聯(lián)性，最優(yōu)解是（1，1，…，1），最優(yōu)函數(shù)值為0，但該函數(shù)在優(yōu)化時，非常容易收斂于點（0，0，…，0）。四個函數(shù)的具體表達式如下：

Rastrigin：

實驗測試結(jié)果分別與混沌差分文化算法（CDECA）［15］和取得較好優(yōu)化效果的改進差分算法Defir DE［16］進行了比較和分析。

5.1 運行環(huán)境與參數(shù)設(shè)置

在測試中，使用微機硬件環(huán)境為華碩筆記本電腦，I3 450CPU，1 GB內(nèi)存，在 MATLAB 2009（a）軟件平臺上進行編程實現(xiàn)。

設(shè)置種群空間中種群規(guī)模N＝100，差分進化算法中縮放因子λ＝0.4，F(xiàn)＝0.6；高斯分布式估計算法中學習因子α＝0.5，β＝0.5；在100和200維時，設(shè)置函數(shù)f1～f3的最大進化代數(shù)為T＝1 000，最高評價次數(shù)為300 000次，設(shè)置函數(shù)f4的最大進化代數(shù)為3 000，最高評價次數(shù)為1 000 000次，在500維時，設(shè)置最大進化代數(shù)為T＝5 000，函數(shù)最高評價次數(shù)為1 500 000次。

5.2 運行結(jié)果與分析

在所有測試函數(shù)中，讓程序各自獨立運行20次，記錄最優(yōu)值 （Best）、平均值（Mean）、最差值（Worst）和標準差（Std.Dev），統(tǒng)計結(jié)果如表1所示。

由表1可以看出，本文算法對每個函數(shù)進行的20次獨立測試中，除了f4函數(shù)在500維時平均最優(yōu)解的精度不夠高外，其它函數(shù)都獲得了高精度全局最優(yōu)解。圖3中顯示了變態(tài)函數(shù)f4在100，200，500維時的進化曲線?？梢钥闯觯?00維和200維時，算法能夠在1 000代進化以內(nèi)發(fā)現(xiàn)最優(yōu)解，在500維時，收斂速度稍低，但也能夠在5 000代進化后發(fā)現(xiàn)最優(yōu)解并逐步收斂。

表2中，在維數(shù)為100和200時，將本文算法和CDECA、Defir DE的平均最優(yōu)解進行了比較。結(jié)果可以看出，對所有函數(shù)f1～f4，在同等條件下，本文算法的平均最優(yōu)解精度都明顯高于CDE－CA和Defir DE算法。從圖4中的函數(shù)收斂曲線可看出，對于函數(shù)f4，本文算法能夠很快地收斂到4 000以內(nèi)，并能夠一直基本保持下降收斂狀態(tài)。由于CDECA和DefirDE算法在優(yōu)化初期為了在整個搜索空間探測全局最優(yōu)解，收斂速度較慢，在進化次數(shù)達到2 000代以后，才進入局部搜索，但限于局部搜索算法的求解精度不高，從而導致全局最優(yōu)解不如本文算法好。

Table 1 Experimental results of the proposed algorithm in this paper表1 本文算法的測試結(jié)果

Table 2 Mean optimal solution comparison of three algorithm（proposed algorithm，CDECA，Defir DE）表2 本文算法和CDECA，DefirDE的平均最優(yōu)解比較

6 結(jié)束語

首先闡述文化算法的基本框架和原理，分析了文化算法的發(fā)展現(xiàn)狀。根據(jù)文化算法的結(jié)構(gòu)特征，將差分進化算法和高斯分布算法應(yīng)用到文化算法中。在種群空間中，利用自適應(yīng)差分進化算法在可行域內(nèi)進行全局的并行搜索。采用小生境識別算法識別小生境種群，將生成的小生境種群送至信度空間并用高斯分布估計算法進行境內(nèi)優(yōu)化，并將優(yōu)化結(jié)果放入進化知識庫，進化知識庫通過Influence函數(shù)指導種群空間進行搜索。算法能夠有效地避免種群在一些局部區(qū)域重復(fù)搜索。最后通過四個高維Benchmark函數(shù)測試表明，本文算法具有全局搜索能力強、收斂速度快、求解精度高和穩(wěn)定性好等優(yōu)勢。

［1］Reynolds R G.An introduction to cultural algorithms［C］∥Proc of the 3rd Annual Conference on Evolutionary Programming，World Scientific，1994：131－139.

［2］Reynolds R G，Michalewicz Z，Cavaretta M.Using cultural algorithms for constraint handling in GENOCOP［C］∥Proc of the 4th Annual Conference on Evolutionary Programming，1995：298－305.

［3］Becerra R L，Coello C A C.Culturizing differential evolution for constrained optimization［C］∥Proc of the 5th Mexican In－ternational Conference in Computer Science，2004：304－311.

［4］Ma Jun，Zhang Jian－pei，Yang Jing，et al.Research on cultural algorithm for solving routing problem of mobile agent［J］.The Journal of China Universities of Posts and Telecommunications，2008（4）：121－125.

［5］Liu Sheng，Yu Xing.A cultural immune quantum evolutionary algorithm and its application［C］∥Proc of Asia Simulation Conference 2008／the 7th International Conference on System Simulation and Scientific Computing，2008：1.

［6］Huang Hai－Yan，Gu Xin－Sheng，Liu Man－Dan.Research on cultural algorithm for solving nonlinear constrained optimization［J］.Acta Automatica Sinica，2007，33（10）：1115－1120.（in Chinese）

［7］Gao Li－li，Liu Hong，Li Tong－xi.Particle swarm based on cultural algorithm for solving constrained optimization problems［J］.Computer Engineering，2008，34（5）：179－181.（in Chinese）

［8］Guo Ji，Peng Xin，Ma Lin－h(huán)ua.Particle swarms cooperative mutative optimization algorithm combining cultural algorithm［J］.Computer Engineering and Applications，2011，45（16）：46－48.（in Chinese）

［9］Guo Yi－nan，Wang Hui.Overview of cultural algorithms［J］.Computer Engineering and Applications，2009，45（9）：41－46.（in Chinese）

［10］Storn R，Price K.Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of Global Optimization，1997，11（4）：341－359.

［11］Zhou Shu－de，Sun Zeng－qi.A survey on estimation of distribution algorithms［J］.Acta Automatica Sinica，2007，33（2）：113－124.（in Chinese）

［12］Zhang Jian－h(huán)ua，Zeng Jian－chao.Estimation of distribution algorithms using empirical distribution function as probability model［J］.Computer Engineering and Applications，2011，47（8）：33－35.（in Chinese）

［13］Tuo Shou－h(huán)eng，Wang Wen－yong.Self－adaptive differential evolution algorithm based on orthogonal and niche elite for high－dimensional multi－modal optimization［J］.Journal of Computer Applications，2011，31（4）：1094－1098.（in Chinese）

［14］Lu Qing，Liang Chang－yong，Yang Shan－lin.An adaptive niche genetic algorithm for multimodal function optimization［J］.Pattern Recognition and Artificial Intelligence，2009，22（1）：91－100.（in Chinese）

［15］Lu You－lin，Zhou Jian－zhong.Differential evolution－based cultural algorithm combined with chaotic search and its application［J］.Journal of System Simulation，2009，21（16）：5107－5111.（in Chinese）

［16］Noman N，Iba H.Enhancing differential evolution performance with local search for high dimensional function optimization［C］∥Proc of 2005 Conference on Genetic and Evolutionary Computation（GECCO 2005），2005：967－974.

附中文參考文獻：

［6］黃海燕，顧幸生，劉漫丹.求解約束優(yōu)化問題的文化算法研究［J］.自動化學報，2007，33（10）：1115－1120.

［7］高麗麗，劉弘，李同喜.基于文化粒子群算法的約束優(yōu)化問題求解［J］.計算機工程，2008，34（5）：179－181.

［8］郭驥，彭鑫，馬林華.結(jié)合文化算法的多種群協(xié)同變異PSO算法［J］.計算機工程與應(yīng)用，2011，45（16）：46－48.

［9］郭一楠，王 輝.文化算法研究綜述［J］.計算機工程與應(yīng)用，2009，45 （9）：41－46.

［11］周樹德，孫增圻.分布估計算法綜述［J］.自動化學報，2007，33（2）：113－124.

［12］張建華，曾建潮.經(jīng)驗分布函數(shù)概率模型的分布估計算法［J］.計算機工程與應(yīng)用，2011，47（8）：33－35.

［13］拓守恒，汪文勇.求解高維多模優(yōu)化問題的正交小生境自適應(yīng)差分演化算法［J］.計算機應(yīng)用，2011，31（4）：1094－1098.

［14］陸青，梁昌勇，楊善林，等.面向多模態(tài)函數(shù)優(yōu)化的自適應(yīng)小生境遺傳算法［J］.模式識別與人工智能，2009，22（1）：91－100.

［15］盧有麟，周建中，李英海，等.混沌差分文化算法及其仿真應(yīng)用研究［J］.系統(tǒng)仿真學報，2009，21（16）：5107－5111.

TUO Shou－h(huán)eng，born in 1978，MS，lecturer，CCF member（E200020808M），his research interests include evolutionary computation，artificial intelligence，and neural network.

陶維天（1976－），男，甘肅蘭州人，碩士，講師，研究方向為計算機應(yīng)用和醫(yī)學信息學。E－mail：lztao＠126.com

TAO Wei－tian，born in 1976，MS，lecturer，his research interests include com－puter applications，and medical informatics.