協(xié)同進(jìn)化數(shù)值優(yōu)化算法及其應(yīng)用分析

梁樹杰

（廣東石油化工學(xué)院高州師范學(xué)院，廣東　高州　525200）

協(xié)同進(jìn)化數(shù)值優(yōu)化算法及其應(yīng)用分析

梁樹杰

（廣東石油化工學(xué)院高州師范學(xué)院，廣東高州525200）

探討協(xié)同進(jìn)化數(shù)值優(yōu)化算法在無約束優(yōu)化、約束優(yōu)化、多目標(biāo)優(yōu)化問題及其在不同領(lǐng)域的應(yīng)用情況，旨在充分發(fā)揮協(xié)同進(jìn)化數(shù)值優(yōu)化算法的作用，進(jìn)而為各領(lǐng)域的發(fā)展奠定基礎(chǔ).

協(xié)同進(jìn)化算法；數(shù)值優(yōu)化；應(yīng)用

協(xié)同進(jìn)化作為一種自然現(xiàn)象，具有普遍性，超過兩個(gè)種群間經(jīng)相互影響，便會(huì)出現(xiàn)此現(xiàn)象，可用于解釋種群間的適應(yīng)性，將其用于生物學(xué)研究，促進(jìn)了生物進(jìn)化.在進(jìn)化計(jì)算研究方面，協(xié)同進(jìn)化算法作為一種快速發(fā)展的最優(yōu)化算法，他是傳統(tǒng)進(jìn)化算法的一種擴(kuò)展.這種算法的模型包含了兩個(gè)和多個(gè)種群.不同的種群在生態(tài)系統(tǒng)中協(xié)同進(jìn)化，并且相互作用，最終使得生態(tài)系統(tǒng)不斷進(jìn)化[1].協(xié)同進(jìn)化算法在許多領(lǐng)域得到了廣泛的應(yīng)用[2].在許多非常困難的問題上，協(xié)同進(jìn)化算法都證明了其作為優(yōu)化算法的有效性.文章綜述了國內(nèi)外學(xué)者的研究內(nèi)容，介紹了進(jìn)化算法、協(xié)同進(jìn)化算法等，重點(diǎn)闡述了其在各類問題中的應(yīng)用，旨在為協(xié)同進(jìn)化數(shù)值優(yōu)化算法的推廣提供可靠的理論保障.

1　協(xié)同進(jìn)化數(shù)值優(yōu)化算法的概況

1.1進(jìn)化算法

在人類生存與發(fā)展過程中涉及眾多的優(yōu)化問題，與分析問題相比，優(yōu)化問題屬于逆問題，在求解方面具有較大的難度，造成此情況的原因主要為優(yōu)化問題的可行解為無窮多個(gè)，但要在可行解集合中獲取最優(yōu)化解，通常情況下，利用數(shù)學(xué)規(guī)劃法可實(shí)現(xiàn)對(duì)相關(guān)問題的處理，但實(shí)際計(jì)算過于繁瑣，進(jìn)而難以保證計(jì)算的準(zhǔn)確性與有效性.為了滿足實(shí)際需求，進(jìn)化算法隨之出現(xiàn)，它作為算法工具具有創(chuàng)新性與高效性，適應(yīng)了數(shù)值優(yōu)化問題的求解奠定了堅(jiān)實(shí)的基礎(chǔ).

進(jìn)化計(jì)算技術(shù)屬于人工智能技術(shù)，它主要是通過對(duì)自然界生物進(jìn)化過程及機(jī)制的模擬，以此實(shí)現(xiàn)了對(duì)相關(guān)問題的求解，其具有自組織、自適應(yīng)與自學(xué)習(xí)的特點(diǎn).進(jìn)化算法是由生物學(xué)知識(shí)逐漸發(fā)展而來的，即：生物種群的優(yōu)勝劣汰、遺傳變異等，在此過程中生命個(gè)體對(duì)環(huán)境的適應(yīng)力不斷在增強(qiáng).通過國內(nèi)外學(xué)者的不斷探索與研究，進(jìn)化算法及其相關(guān)的計(jì)算智能方法日漸豐富，其中進(jìn)化數(shù)值優(yōu)化算法吸引了眾多學(xué)者的目光[3].

與傳統(tǒng)優(yōu)化算法相比，進(jìn)化算法具有一定的特殊性，其優(yōu)勢(shì)顯著，主要表現(xiàn)在以下幾方面：處理對(duì)象為編碼，通過編碼操作，使參數(shù)集成為個(gè)體，進(jìn)而利于實(shí)現(xiàn)對(duì)結(jié)構(gòu)對(duì)象的直接操作；便于獲得全局最優(yōu)解，借助進(jìn)化算法，可對(duì)群體中的多個(gè)個(gè)體進(jìn)行同時(shí)處理，從而提高了計(jì)算準(zhǔn)確性，降低了計(jì)算風(fēng)險(xiǎn)性；不需要連續(xù)可微要求，同時(shí)可利用隨機(jī)操作與啟發(fā)式搜索，從而保證了搜索的明確性與高效性，在此基礎(chǔ)上，它在各個(gè)領(lǐng)域的應(yīng)用均取得了顯著的成效，如：函數(shù)優(yōu)化、自動(dòng)控制、圖像處理等.但進(jìn)化算法也存在不足，主要表現(xiàn)為其選擇機(jī)制仍為人工選擇，在實(shí)際問題處理過程中，難以發(fā)揮指導(dǎo)作用；同時(shí)，局部搜索能力相對(duì)較差，難以保證解的質(zhì)量[4].

為了彌補(bǔ)進(jìn)化算法的不足，相關(guān)學(xué)者通過研究提出了新型計(jì)算智能方法，具體包括免疫進(jìn)化算法，它主要是利用自然免疫系統(tǒng)功能獲得的，此方法在數(shù)據(jù)處理、故障診斷等方面均扮演著重要的角色；Memetic算法屬于混合啟發(fā)式搜索算法，其利用了不同的搜索策略，從而保證了其應(yīng)用效果；群智能算法主要分為兩種，一種為蟻群算法，另一種為粒子群算法，前者可用于多離散優(yōu)化問題方面；后者主要利用迭代從而獲取了最優(yōu)解，由于其具有簡便性與實(shí)用性，因此其應(yīng)用較為廣泛；協(xié)同進(jìn)化算法作為新型進(jìn)化算法，其分析了種群與環(huán)境二者間的關(guān)系，并對(duì)二者進(jìn)化過程中的協(xié)調(diào)給予了高度關(guān)注[5].

1.2協(xié)同進(jìn)化算法

表一　協(xié)同進(jìn)化算法與傳統(tǒng)優(yōu)化算法的對(duì)比

在數(shù)值優(yōu)化領(lǐng)域中應(yīng)用協(xié)同進(jìn)化算法，相關(guān)的研究成果主要體現(xiàn)在無約束優(yōu)化、約束優(yōu)化與多目標(biāo)優(yōu)化等方面.在第一類問題方面.對(duì)于進(jìn)化算法而言，其經(jīng)典的應(yīng)用領(lǐng)域便是無約束數(shù)值優(yōu)化，經(jīng)過不斷實(shí)際，此技術(shù)的應(yīng)用日漸成熟，但在問題規(guī)模不斷增大基礎(chǔ)上，其應(yīng)用難度日漸增加，因此，學(xué)者紛紛關(guān)注高維無約束數(shù)值優(yōu)化問題，經(jīng)研究提出了相應(yīng)的算法，如：合作型協(xié)同進(jìn)化遺傳算法，組織優(yōu)化算法；在第二類問題方面，隨著進(jìn)化算法應(yīng)用的日漸廣泛，相關(guān)的約束優(yōu)化進(jìn)化算法也具有了豐富性與多樣性，如：罰函數(shù)法、分離約束與目標(biāo)算法、各種混合算法等；在第三類問題方面，在進(jìn)化計(jì)算領(lǐng)域中進(jìn)化多目標(biāo)優(yōu)化逐漸成為了研究了焦點(diǎn)，通過不斷努力，國外學(xué)者提出了捕食者-獵物模型、競(jìng)爭(zhēng)協(xié)同進(jìn)化模型、合作協(xié)同進(jìn)化模型等[6].

目前，關(guān)于協(xié)同進(jìn)化算法的概念缺少統(tǒng)一性與嚴(yán)謹(jǐn)性，為了對(duì)其進(jìn)行準(zhǔn)確的界定，應(yīng)對(duì)其展開深入的研究與探討，并將其用于實(shí)際問題，以此驗(yàn)證其有效性與可行性.

2　協(xié)同進(jìn)化數(shù)值優(yōu)化算法的應(yīng)用

2.1求解無約束優(yōu)化問題

對(duì)于高位無約束數(shù)值優(yōu)化問題而言，在實(shí)際解決過程中應(yīng)充分發(fā)揮協(xié)同進(jìn)化與精英策略的作用，不僅要利用M-精英協(xié)同算法，還要構(gòu)建M-精英協(xié)同進(jìn)化模型.MECA算法具有較高的適應(yīng)度，滿足了不同個(gè)體群的需求，其在整個(gè)種群進(jìn)化中扮演著重要的角色，此算法對(duì)整個(gè)種群進(jìn)行了劃分，如：精英種群與普通種群，并由核心精英對(duì)成員進(jìn)行選取，此后組建相應(yīng)的團(tuán)隊(duì)，如果選擇的成員為精英，則可利用所定義的協(xié)作操作來交換該成員和核心精英間的信息，如果選擇的成員來自于普通種群，此時(shí)核心精英則要對(duì)其展開引導(dǎo)操作，其中涉及的寫作操作與引導(dǎo)操作定義是通過不同類型的交叉或變異算子的組合而實(shí)現(xiàn)的.通過理論分析可知，全局最優(yōu)解為算法中的概率為1，經(jīng)過測(cè)試顯示，此算法對(duì)全體測(cè)試函數(shù)而言，均可獲取最優(yōu)解[7]；同時(shí)，將其與傳統(tǒng)進(jìn)化算法、其他協(xié)同進(jìn)化算法進(jìn)行比較，在適應(yīng)度函數(shù)評(píng)價(jià)次數(shù)相同前提下，此算法具有較高的精度、較短的尋優(yōu)時(shí)間、較低的參數(shù)敏感性，因此，它可廣泛應(yīng)用于實(shí)踐[8].

2.2求解約束優(yōu)化問題

在約束優(yōu)化問題中利用協(xié)同進(jìn)化算法，其基礎(chǔ)為M-精英協(xié)同進(jìn)化模型，此后需要借助正交交叉算子、靜態(tài)罰函數(shù)法等，以此保證了M-精英協(xié)同進(jìn)化算法作用的充分發(fā)揮.在實(shí)際應(yīng)用中，采用13各約束優(yōu)化測(cè)試函數(shù)，經(jīng)仿真實(shí)驗(yàn)與參數(shù)分析，其結(jié)果顯示改進(jìn)M-精英協(xié)同進(jìn)化算法優(yōu)點(diǎn)眾多，如：較高的精度、較短的尋優(yōu)時(shí)間及較好的穩(wěn)定性等，它與經(jīng)典約束優(yōu)化進(jìn)化算法及協(xié)同進(jìn)化算法相比，性能顯著，同時(shí)也實(shí)現(xiàn)了對(duì)各類約束優(yōu)化問題有效解決.

2.3求解多目標(biāo)優(yōu)化問題

在M-精英協(xié)同進(jìn)化的影響下，利用非支配鄰近選擇機(jī)制，針對(duì)多目標(biāo)優(yōu)化問題，提出了費(fèi)支配緊鄰協(xié)同進(jìn)化多目標(biāo)優(yōu)化算法，即：NNCA，此算法結(jié)合費(fèi)支配種群的擁擠距離，對(duì)其進(jìn)行了劃分，分別為精英種群與普通種群，前者擁擠距離相對(duì)較大，主要是由非支配個(gè)體構(gòu)成的，在其區(qū)域內(nèi)個(gè)體分布稀疏程度與組建團(tuán)隊(duì)的機(jī)會(huì)呈負(fù)相關(guān)，前者越稀疏，后者機(jī)會(huì)越大，其成員也越多，進(jìn)而利于提高對(duì)區(qū)域搜索的全面性，但如果非支配個(gè)體過少，則會(huì)造成搜索停滯，為了避免此問題的出現(xiàn)，NNCA借助了精神規(guī)模保障機(jī)制.在不同機(jī)制共同作用下，進(jìn)一步增強(qiáng)了算法的搜索能力與收斂性.此后，對(duì)多目標(biāo)優(yōu)化問題進(jìn)行測(cè)試，其結(jié)果表明，與其他算法相比，NNCA優(yōu)勢(shì)顯著，主要表現(xiàn)在最優(yōu)解的寬廣性與逼近性方面[9].

2.4在不同領(lǐng)域的應(yīng)用

在通信系統(tǒng)中，對(duì)實(shí)時(shí)性有著較高的要求，為了適應(yīng)系統(tǒng)發(fā)展的需求，應(yīng)積極解決系統(tǒng)中最大似然檢測(cè)算法過于復(fù)雜的問題，經(jīng)過不斷的探索與研究，對(duì)相關(guān)算法進(jìn)行了優(yōu)化，以此降低了算法的復(fù)雜度、提高了其性能.在通信系統(tǒng)信號(hào)檢測(cè)中主要利用M-精英進(jìn)化算法，為了保證該算法的有效性，采用了經(jīng)典背包問題仿真試驗(yàn)，其結(jié)果為與傳統(tǒng)檢測(cè)算法相比，M-精英進(jìn)化算法促進(jìn)了系統(tǒng)性能的提高.在仿真實(shí)驗(yàn)過程中，選擇了60個(gè)物品的背包問題，利用上述算法，實(shí)現(xiàn)了組合優(yōu)化問題的有效解決，因此，在實(shí)踐中可將其進(jìn)行推廣與應(yīng)用，如：將其用于CDMA系統(tǒng)中，以此解決多用戶檢測(cè)問題.

在衛(wèi)星模塊布局設(shè)計(jì)中，制約設(shè)計(jì)水平提高的核心為求解帶平衡約束的圓形Packing問題，為了有效解決此問題，應(yīng)充分發(fā)揮M-精英協(xié)同進(jìn)化算法的作用.在實(shí)際處理過程中，利用靜態(tài)罰函數(shù)方法，對(duì)問題進(jìn)行轉(zhuǎn)變，使其由約束問題轉(zhuǎn)變?yōu)闊o約束問題，同時(shí)為了驗(yàn)證此算法解決實(shí)際問題的能力，可利用不同的工程設(shè)計(jì)優(yōu)化問題，如：Spring Design、Speed Reducer Design等，此后對(duì)其進(jìn)行測(cè)試，其結(jié)果顯示該算法實(shí)現(xiàn)了復(fù)雜問題的有效處理，并且保證了布局設(shè)計(jì)的質(zhì)量，同時(shí)其花費(fèi)的時(shí)間相對(duì)較少[10].

3　總結(jié)

綜上所述，協(xié)同進(jìn)化機(jī)制具有積極的意義，為了充分發(fā)揮其作用，文章介紹了協(xié)同進(jìn)化數(shù)值優(yōu)化算法的應(yīng)用，在明確進(jìn)化算法、協(xié)同進(jìn)化算法相關(guān)內(nèi)容的基礎(chǔ)上，探討了不同算法在無約束優(yōu)化、約束優(yōu)化、多目標(biāo)優(yōu)化及相關(guān)領(lǐng)域的應(yīng)用，相信在各類復(fù)雜問題有效解決基礎(chǔ)上，各領(lǐng)域?qū)@得更加穩(wěn)定與有序的發(fā)展.

〔1〕張運(yùn)凱,王方偉,張玉清.協(xié)同進(jìn)化遺傳算法與應(yīng)用[J].計(jì)算機(jī)工程,2004（15）.

〔2〕H.Chen,K.P.Wong,D.H.M.Nguyen,and C.Y.Chung,“Analyzing oligopoly electricity market using coevolutionary computation,”IEEE Trans.Power Syst.,vol.21,no.1,pp.143-152,Feb.2006.

〔3〕李碧,林土勝.協(xié)同進(jìn)化在遺傳算法中的應(yīng)用述評(píng)[J].計(jì)算機(jī)科學(xué)，2009(04).

〔4〕陳鵬.基于極值動(dòng)力學(xué)的MEMETIC算法及其在非線性預(yù)測(cè)控制中的應(yīng)用研究[D].上海交通大學(xué),2011.

〔5〕劉偉，趙丹，孫宏偉.基于新型Memetic算法的多目標(biāo)優(yōu)化[J].吉林大學(xué)學(xué)報(bào),2012（03）.

〔6〕鄧武.基于協(xié)同進(jìn)化的混合智能優(yōu)化算法及其應(yīng)用研究[D].大連海事大學(xué),2012.

〔7〕劉朝華.混合免疫智能優(yōu)化算法研究及其在復(fù)雜系統(tǒng)中的應(yīng)用[D].湖南大學(xué),2012.

〔8〕呂琳.結(jié)合學(xué)習(xí)策略的粒子群優(yōu)化算法及應(yīng)用研究[D].西安電子科技大學(xué),2013.

〔9〕丁建立，陳增強(qiáng)，袁著祉.智能仿生算法及其網(wǎng)絡(luò)優(yōu)化中的應(yīng)用研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用,2003（04）.

〔10〕程軍.基于生物行為機(jī)制的粒子群算法改進(jìn)及應(yīng)用[D].華南理工大學(xué),2014.

O224；TP273.1

A

1673-260X（2016）09-0006-02

2016-05-23

廣東省教育研究院課題項(xiàng)目（GDJY-2015_F-b057）；茂名市青年名師培養(yǎng)項(xiàng)目成果