資源描述:
《用于約束多目標(biāo)優(yōu)化問(wèn)題地雙群體差分進(jìn)化算法》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。
1、實(shí)用文案用于約束多目標(biāo)優(yōu)化問(wèn)題的雙群體差分進(jìn)化算法孟紅云1張小華2劉三陽(yáng)1(1.西安電子科技大學(xué)應(yīng)用數(shù)學(xué)系,西安,710071;2.西安電子科技大學(xué)智能信息處理研究所,西安,710071)摘要:首先給出一種改進(jìn)的差分進(jìn)化算法,然后提出一種基于雙群體搜索機(jī)制的求解約束多目標(biāo)優(yōu)化問(wèn)題的差分進(jìn)化算法.該算法同時(shí)使用兩個(gè)群體,其中一個(gè)用于保存搜索過(guò)程中找到的可行解,另一個(gè)用于記錄在搜索過(guò)程中得到的部分具有某些優(yōu)良特性的不可行解,避免了構(gòu)造罰函數(shù)和直接刪除不可行解.此外,將本文算法、NSGA-Ⅱ和SPEA的
2、時(shí)間復(fù)雜度進(jìn)行比較表明,NSGA-Ⅱ最優(yōu),本文算法與SPEA相當(dāng).對(duì)經(jīng)典測(cè)試函數(shù)的仿真結(jié)果表明,與NSGA-Ⅱ相比較,本文算法在均勻性及逼近性方面均具有一定的優(yōu)勢(shì).關(guān)鍵字:差分進(jìn)化算法;約束優(yōu)化問(wèn)題;多目標(biāo)優(yōu)化問(wèn)題;中圖分類號(hào):TP181引言達(dá)爾文的自然選擇機(jī)理和個(gè)體的學(xué)習(xí)能力推動(dòng)進(jìn)化算法的出現(xiàn)和發(fā)展,用進(jìn)化算法求解優(yōu)化問(wèn)題已成為一個(gè)研究的熱點(diǎn)[1-3].但目前研究最多的卻是無(wú)約束優(yōu)化問(wèn)題.然而,在科學(xué)研究和工程實(shí)踐中,許多實(shí)際問(wèn)題最終都?xì)w結(jié)為求解一個(gè)帶有約束條件的函數(shù)優(yōu)化問(wèn)題,因此研究基于進(jìn)化算
3、法求解約束優(yōu)化問(wèn)題是非常有必要的.不失一般性,以最小化問(wèn)題為例,約束優(yōu)化問(wèn)題(ConstrainedOptimizationProblem,)可定義如下:(1)其中為目標(biāo)函數(shù),稱為約束條件,稱為維決策向量.將滿足所有約束條件的解空間稱為(1)的可行域.特別的,當(dāng)時(shí),(1)為單目標(biāo)優(yōu)化問(wèn)題;當(dāng)時(shí),(1)為多目標(biāo)優(yōu)化問(wèn)題.為第個(gè)不等式約束,是第個(gè)等式約束.另一方面,對(duì)于等式約束可通過(guò)容許誤差(也稱容忍度)將它轉(zhuǎn)化為兩個(gè)不等式約束:(2)故在以后討論問(wèn)題時(shí),僅考慮帶不等式約束的優(yōu)化問(wèn)題.進(jìn)一步,如果使得
4、不等式約束,則稱約束在處是積極的.在搜索空間中,滿足約束條件的決策變量稱為可行解,否則稱為不可行解.定義1(全局最優(yōu)解)是的全局最優(yōu)解,是指且不劣于可行域內(nèi)任意解所對(duì)應(yīng)的目標(biāo)函數(shù),表示為.對(duì)于單目標(biāo)優(yōu)化問(wèn)題,等價(jià)為,而對(duì)于多目標(biāo)優(yōu)化問(wèn)題是指不存在,使得Pareto優(yōu)于.目前,進(jìn)化算法用于無(wú)約束優(yōu)化問(wèn)題的文獻(xiàn)居多,與之比較,對(duì)約束優(yōu)化問(wèn)題的研究相對(duì)較少[4-6]。文[7]標(biāo)準(zhǔn)文檔實(shí)用文案對(duì)當(dāng)前基于進(jìn)化算法的各種約束處理方法進(jìn)行了較為詳細(xì)的綜述.對(duì)于約束優(yōu)化問(wèn)題的約束處理方法基本上分為兩類:基于罰函數(shù)
5、的約束處理技術(shù)和基于多目標(biāo)優(yōu)化技術(shù)的約束處理技術(shù).由于罰函數(shù)法在使用中不需要約束函數(shù)和目標(biāo)函數(shù)的解析性質(zhì),因此經(jīng)常被應(yīng)用于約束優(yōu)化問(wèn)題,但該類方法對(duì)罰因子有很強(qiáng)的依賴性,需要根據(jù)具體問(wèn)題平衡罰函數(shù)與目標(biāo)函數(shù).為了避免復(fù)雜罰函數(shù)的構(gòu)造,Verdegay等[8]將進(jìn)化算法中的競(jìng)爭(zhēng)選擇用于約束處理,并在比較兩個(gè)解的性能時(shí)提出了三個(gè)準(zhǔn)則,但他的第三個(gè)準(zhǔn)則—可行解優(yōu)于不可行解—這一準(zhǔn)則合理性不強(qiáng).然而該文的這一準(zhǔn)則卻為進(jìn)化算法求解約束優(yōu)化問(wèn)題提供了新思路,獲得了良好效果.因?yàn)樵诂F(xiàn)實(shí)中存在一大類約束優(yōu)化問(wèn)題,
6、其最優(yōu)解位于約束邊界上或附近,對(duì)于這類問(wèn)題,在最優(yōu)解附近的不可行解的適應(yīng)值很可能優(yōu)于位于可行域內(nèi)部的大部分可行解的適應(yīng)值,因此無(wú)論從適應(yīng)值本身還是從最優(yōu)解的相對(duì)位置考慮,這樣的不可行解對(duì)找到最優(yōu)解都是很有幫助的,故如何有效利用搜索過(guò)程中的部分具有較好性質(zhì)的不可行解是解決此類問(wèn)題的難點(diǎn)之一.基于以上考慮,本文擬給出一種求解約束多目標(biāo)優(yōu)化問(wèn)題的基于雙群體機(jī)制的差分進(jìn)化算法,并對(duì)文中算法的時(shí)間復(fù)雜度與NSGA-Ⅱ[9]和SPEA[10]進(jìn)行比較,最后用實(shí)驗(yàn)仿真說(shuō)明文中算法的可行性及有效性.2用于約束優(yōu)化
7、的雙群體差分進(jìn)化算法2.1差分進(jìn)化算法差分進(jìn)化算法是一類簡(jiǎn)單而有效的進(jìn)化算法,已被成功應(yīng)用于求解無(wú)約束單目標(biāo)和多目標(biāo)優(yōu)化問(wèn)題[11-14].該算法在整個(gè)運(yùn)行過(guò)程中保持群體的規(guī)模不變,它也有類似于遺傳算法的變異、交叉和選擇等操作,其中變異操作定義如下:(3)其中,為從進(jìn)化群體中隨機(jī)選取的互不相同的三個(gè)個(gè)體,為位于區(qū)間中的參數(shù).(3)式表示從種群中隨機(jī)取出的兩個(gè)個(gè)體的差,經(jīng)參數(shù)放大或縮小后被加到第三個(gè)個(gè)體上,以構(gòu)成新的個(gè)體.為了增加群體的多樣性,交叉操作被引入差分進(jìn)化算法,具體操作如下:針對(duì)父代個(gè)體的
8、每一分量,產(chǎn)生位于區(qū)間中的隨機(jī)數(shù),根據(jù)與參數(shù)的大小關(guān)系確定是否用替換,以得到新的個(gè)體,其中.如果新個(gè)體優(yōu)于父代個(gè)體,則用來(lái)替換,否則保持不變.在差分進(jìn)化算法中,選擇操作采取的是貪婪策略,即只有當(dāng)產(chǎn)生的子代個(gè)體優(yōu)于父代個(gè)體時(shí)才被保留,否則,父代個(gè)體被保留至下一代.大量研究與實(shí)驗(yàn)發(fā)現(xiàn)差分進(jìn)化算法在維護(hù)群體的多樣性及搜索能力方面功能較強(qiáng),但收斂速度相對(duì)較慢,因此本文擬給出一種改進(jìn)的差分進(jìn)化算法用于多目標(biāo)優(yōu)化問(wèn)題,仿真實(shí)驗(yàn)表明,改進(jìn)的差分進(jìn)化算法在不破壞原有算法維護(hù)群體多樣性的前提下,可改