基于改進(jìn)人工蜂群算法的約束多目標(biāo)進(jìn)化算法

基于改進(jìn)人工蜂群算法的約束多目標(biāo)進(jìn)化算法

為了確保滿足多目標(biāo)限制，有必要確保獲得的最合適量解決方案接近真實(shí)的帕德，并均勻分布，這比復(fù)雜的多目標(biāo)邊界問題更復(fù)雜?，F(xiàn)在的約束多目標(biāo)處理方法主要有4種:①把約束違反度作為一個(gè)目標(biāo)重新求解;②利用自適應(yīng)罰函數(shù)法修改目標(biāo)函數(shù)值;③利用約束支配關(guān)系直接求解;④利用外部種群分別存儲(chǔ)可行解和不可行解,是目前最為優(yōu)秀的約束多目標(biāo)算法的處理方式,優(yōu)化效果也較好。遺傳算法、粒子群算法、差分算法等都已成為典型的約束多目標(biāo)算法,它們結(jié)合相應(yīng)的約束處理技術(shù)雖在一定程度上提高了約束多目標(biāo)算法的收斂性和分布性,但要使其穩(wěn)定、有效地找到近似Pareto最優(yōu)解集并同時(shí)保證良好分布性仍很困難。人工蜂群算法是2005年提出的一種新型進(jìn)化算法,因其參數(shù)設(shè)置少、收斂速度快、收斂精度高使其得到學(xué)者的逐漸關(guān)注。文獻(xiàn)提出一種結(jié)合自適應(yīng)罰函數(shù)法的約束多目標(biāo)算法,由于該種約束處理技術(shù)的局限性,雖然取得了一定的效果,但收斂性和分布性都有待提高。本文選擇目前最流行的建立外部種群分別存儲(chǔ)可行解集和不可行解集的約束處理技術(shù),在此基礎(chǔ)上根據(jù)約束多目標(biāo)問題的特點(diǎn),對(duì)外部種群的更新方式、迭代種群的更新方式及人工蜂群算法進(jìn)行改進(jìn)。實(shí)驗(yàn)仿真結(jié)果表明,CMABC相對(duì)于目前性能較好的MOABC及HPSO具有一定優(yōu)勢(shì),能夠在保證良好收斂性的同時(shí),使獲得的Pareto最優(yōu)解集具有更均勻的分布性和更廣的覆蓋范圍,適合于約束多目標(biāo)優(yōu)化問題的求解。1基于人工蜂群算法的限制多目標(biāo)優(yōu)化1.1基于循環(huán)hartonic平均距離的可行解集本文采用文獻(xiàn)中建立外部種群分別存儲(chǔ)可行解集和不可行解集的約束處理技術(shù)。在文獻(xiàn)的可行解集更新中,當(dāng)優(yōu)秀可行解數(shù)目大于其固有容量時(shí),需依靠NSGA2算法中的擁擠距離實(shí)現(xiàn)均勻分布,但這種擁擠距離不能真實(shí)地反映個(gè)體間的疏密程度。研究表明,與NSGA2算法中的擁擠距離相比,harmonic平均距離能夠更好地評(píng)價(jià)種群個(gè)體間的擁擠程度;其次,這種策略忽視了個(gè)體淘汰后對(duì)其鄰域個(gè)體擁擠密度的影響,當(dāng)擁擠距離較小的個(gè)體被刪除后會(huì)導(dǎo)致周圍個(gè)體的擁擠距離變大,按原有方法選擇個(gè)體很可能將現(xiàn)在擁擠距離較大的個(gè)體刪除,不利于分布性指標(biāo)的達(dá)成,而循環(huán)擁擠策略卻考慮了被刪除的個(gè)體對(duì)余下個(gè)體的作用。鑒于此,本文提出循環(huán)harmonic平均距離剪切可行解集。個(gè)體i的harmonic平均距離di定義為di=k1di,1+1di,2+?+1di,k(1)式中:k為目標(biāo)數(shù)減一;di,k為與i距離最近的k個(gè)個(gè)體的歐式距離?；谘h(huán)harmonic平均距離更新可行解集的方式如下:①計(jì)算所有個(gè)體的harmonic平均距離,挑選出最小距離的個(gè)體,將其刪除;②刪除剩余個(gè)體中harmonic平均距離最小的個(gè)體,直至剩余個(gè)體數(shù)目為可行解集容量。從本文采取的改進(jìn)的個(gè)體更新方式可以看出,相比于原有方式,本文方法能夠更為精確地反映個(gè)體間的密度,提高解集分布性。1.2不同算法中的進(jìn)化策略進(jìn)化算法的進(jìn)化策略優(yōu)劣對(duì)其收斂精度、收斂速度都有較大影響,而人工蜂群算法中的進(jìn)化策略主要包括引領(lǐng)蜂、跟隨蜂和偵查蜂的搜索策略,因此有必要根據(jù)約束多目標(biāo)問題的特點(diǎn)對(duì)ABC算法中的搜索策略進(jìn)行改進(jìn)。1.2.1進(jìn)優(yōu)進(jìn)展建議在ABC算法中,當(dāng)某個(gè)解連續(xù)“l(fā)imit”代沒有變化時(shí)會(huì)啟動(dòng)偵查蜂,這時(shí)有可能達(dá)到全局的最優(yōu)搜索,也有可能陷入局部最優(yōu)。若陷入局部最優(yōu),偵查蜂靠隨機(jī)搜索補(bǔ)充多樣性對(duì)算法進(jìn)化至關(guān)重要,但因其是在整個(gè)搜索空間內(nèi)產(chǎn)生一隨機(jī)解參與后續(xù)的引領(lǐng)蜂和跟隨蜂的搜索,如果limit設(shè)置過小,會(huì)較多地引入隨機(jī)性搜索,降低算法的收斂速度,甚至可能破壞種群保持的良好進(jìn)化方向;如果limit設(shè)置過大,對(duì)產(chǎn)生優(yōu)異新解及進(jìn)化方向所起作用不大?？紤]到偵查蜂行為的本質(zhì)就是補(bǔ)充多樣性,完全可以采取其他方式加以代替。分析發(fā)現(xiàn),引領(lǐng)蜂和跟隨蜂在某些選擇壓力的迫使下,隨著進(jìn)化的進(jìn)行,其搜索區(qū)域?qū)⒅饾u縮小,聚集在一個(gè)或幾個(gè)區(qū)域,這是算法容易陷入局部最優(yōu)的原因。其中,跟隨蜂為了加快算法收斂,在引領(lǐng)蜂的基礎(chǔ)上進(jìn)行貪婪搜索,因此引領(lǐng)蜂的搜索策略成為算法多樣性不足的主要原因。為增大種群多樣性及充分利用個(gè)體信息,本文為引領(lǐng)蜂建立如下的兩種搜索策略:將rand<Pm時(shí)的搜索方式稱為方式一,另一種搜索方式稱為方式二。其中,P′i、Pi分別為新舊蜜源,r∈代表貪心程度,k1、k2及k3為當(dāng)代種群中隨機(jī)選取的不同個(gè)體,Pm為按照方式一或方式二搜索的選擇概率,Pk為按如下方式選取的個(gè)體:①每個(gè)初始蜜源(即初始群體中的個(gè)體)按照歐式距離建立各自的固定鄰域。②計(jì)算各鄰域的中心。③按照文獻(xiàn)提出的選擇方法選取距個(gè)體較近的鄰域。④在該鄰域內(nèi)隨機(jī)選擇一個(gè)個(gè)體,即Pk。從上述搜索方式可以看出:搜索方式二保留了基本ABC算法的搜索策略;搜索方式一是本文為增大種群多樣性設(shè)計(jì)的新的搜索策略,與完全破壞原有個(gè)體產(chǎn)生隨機(jī)個(gè)體代替用以補(bǔ)充多樣性的方式相比,本文選擇在個(gè)體最初的鄰域范圍內(nèi)選擇某一個(gè)體參與進(jìn)化,同樣可以達(dá)到擴(kuò)大種群多樣性的目的;在一定程度上保留了原有個(gè)體的方向信息,且以當(dāng)代種群作為步長(zhǎng)擴(kuò)展信息,不會(huì)過多地降低算法的收斂速度。1.2.2基于pbest的可行解提取在ABC算法中,跟隨蜂的作用是在原有蜜源的基礎(chǔ)上,選擇某些優(yōu)秀蜜源進(jìn)行進(jìn)一步探測(cè),加快算法進(jìn)化的收斂速度?；続BC算法是根據(jù)個(gè)體適應(yīng)度值進(jìn)行優(yōu)異蜜源選取的,因每個(gè)個(gè)體都有不止一個(gè)適應(yīng)度值,所以無法賦予個(gè)體一個(gè)特定可比較的值,不適合解決約束多目標(biāo)問題。文獻(xiàn)把個(gè)體之間的支配排序作為個(gè)體適應(yīng)度值,這種賦值關(guān)系存在以下問題:首先,它基于可行解一定優(yōu)于不可行解的原則,不可行解很難參與進(jìn)化,但在約束多目標(biāo)問題中,與可行解一樣,某些不可行解也至關(guān)重要,不能忽略優(yōu)勢(shì)不可行解的作用;其次,當(dāng)種群趨于最優(yōu)時(shí),個(gè)體支配排序值相近,這種方式無法評(píng)價(jià)個(gè)體優(yōu)劣,相當(dāng)于隨機(jī)選取個(gè)體參與進(jìn)化,不利于收斂速度的提高。而在外部種群與其他進(jìn)化算法相結(jié)合解決約束多目標(biāo)問題時(shí),都采用在外部種群中隨機(jī)選取一個(gè)個(gè)體參與進(jìn)化,這種方式的收斂速度也不高。上述方法收斂速度不高的主要原因是未給出合理的個(gè)體優(yōu)劣比較準(zhǔn)則,本文通過深入研究給出基于以下準(zhǔn)則的搜索方式:p′i=r×pbest+(1?r)×pi+(?1+2×rand)×(pk1?pk2)(3)式中:pk1、pk2為在種群中隨機(jī)選取的兩個(gè)不同個(gè)體。經(jīng)分析發(fā)現(xiàn),在外部精英種群中,可行解集一定不空,但不可行解集有可能空,因此pbest需按以下方式有針對(duì)性地選取:(1)當(dāng)不可行解集為空時(shí),精英種群中的個(gè)體彼此是非支配的,因此,可以將擁擠距離作為可行解優(yōu)異的評(píng)價(jià)標(biāo)準(zhǔn),而貪婪的輪盤賭選擇方式容易使算法陷入局部最優(yōu),故以文獻(xiàn)中的選擇方式在外部精英可行解集中選取較優(yōu)個(gè)體作為pbest。(2)當(dāng)不可行解集不空時(shí),鑒于不可行解和可行解在約束多目標(biāo)問題的求解中都占有重要作用,因此等概率地在可行解集和不可行解集中選取個(gè)體,若在不可行解集中搜索,為加強(qiáng)可行域邊界的搜索,按文獻(xiàn)中的選擇方式以距離作為評(píng)判標(biāo)準(zhǔn)選取一個(gè)個(gè)體作為pbest;否則,在可行解集中搜索,按方式一選取pbest。另外,在引領(lǐng)蜂和跟隨蜂的搜索過程中都有超出邊界的情況,由于個(gè)體的每維信息都是在進(jìn)化過程中逐漸積累的,因此以較大概率保留原有信息,以較小概率在邊界內(nèi)隨機(jī)搜索,而不像現(xiàn)有方法一樣將個(gè)體置于邊界上或者在邊界內(nèi)隨機(jī)產(chǎn)生一個(gè)個(gè)體。1.2.3可行性解與不可行解的區(qū)分:迭代種群的可解性迭代種群的確定方式是種群進(jìn)化的主要壓力,對(duì)收斂速度及多樣性都有較大影響,現(xiàn)有的約束多目標(biāo)算法的迭代種群的確定方式有:①按照文獻(xiàn)中的比較準(zhǔn)則對(duì)個(gè)體進(jìn)行更新;②按照NSGA2算法中的精英種群的確定方式。上述的迭代種群確定方式都是以可行解優(yōu)于不可行解為前提的,隨著進(jìn)化的進(jìn)行在某代以后很可能導(dǎo)致最終的迭代種群全部為可行解,這就忽視了不可行解的作用。此外,NSGA2算法中的擁擠距離不是最合理的分布性達(dá)成標(biāo)準(zhǔn)。為充分重視優(yōu)秀不可行解的作用及提高種群的分布性效果,提出如下的迭代種群的確定方式:(1)搜索前后的種群組合形成一個(gè)種群,并把新種群分成可行解集和不可行解集,設(shè)定迭代種群中不可行解數(shù)目TT。(2)新種群中的可行解部分按NSGA2算法中的精英種群的確定方式確定個(gè)體,對(duì)于最后加入精英種群的個(gè)體按1.1節(jié)中的循環(huán)harmonic距離進(jìn)行選擇。為加強(qiáng)可行域邊界的搜索,不可行解選取離可行解距離最近的TT個(gè)個(gè)體。1.3外部種群的篩選綜合以上改進(jìn),MABC算法流程如下:步驟1在約束多目標(biāo)優(yōu)化問題的決策變量空間里隨機(jī)生成NP個(gè)個(gè)體,構(gòu)成初始種群P,并構(gòu)成各個(gè)體的鄰域PP。步驟2計(jì)算P中每個(gè)個(gè)體的適應(yīng)度值及約束違反度,確定外部種群中的優(yōu)秀可行解集和優(yōu)秀不可行解集。步驟3終止條件不滿足則執(zhí)行,否則轉(zhuǎn)至步驟4。(1)對(duì)于種群中每個(gè)個(gè)體Pi1(i=1,…,NP)按1.2.1節(jié)中方式生成子代個(gè)體Ci,并計(jì)算Ci的適應(yīng)度值和約束違反度。(2)合并父代種群P1和子代種群C形成種群R,對(duì)其按照1.2.3節(jié)中方式確定迭代種群p2。(3)更新外部種群。(4)對(duì)p2中每個(gè)個(gè)體按1.2.2節(jié)中方式搜索產(chǎn)生新的種群Q。(5)合并種群p2和Q,按照1.2.3節(jié)中方式確定迭代種群p3,并更新外部種群。(6)p3確定為迭代種群。步驟4輸出外部種群中的優(yōu)秀可行解集。1.4更新所需的時(shí)間復(fù)雜度這里僅考慮種群規(guī)模對(duì)算法時(shí)間復(fù)雜度的影響,設(shè)外部種群中可行解和不可行解的容量分別為N1和N2,種群規(guī)模為N,即引領(lǐng)蜂、跟隨蜂的規(guī)模為N/2,每代生成的可行解、不可行解數(shù)目分別為Na、Ns,迭代種群中的不可行解數(shù)目為TT,目標(biāo)數(shù)目為M。每次迭代的時(shí)間開銷主要在于迭代種群的確定和外部種群的更新,所需的時(shí)間復(fù)雜度計(jì)算如下:(1)迭代種群的確定可行解部分的確定:非支配排序的復(fù)雜度為O(M(Na)2);harmonic循環(huán)擁擠排序的復(fù)雜度為O(∑i=N1N1+NaM(i)log(i)),由于O(∑i=N1N1+NaM(i)log(i))<O(NaM(N1+Na)2);比較算子的復(fù)雜度為O(Nalog(Na)),所以總的可行解部分確定的時(shí)間復(fù)雜度為O(NaM(N1+Na)2);不可行解部分的確定需進(jìn)行Ns×Na次比較,其時(shí)間復(fù)雜度為O(NsNa),總的時(shí)間復(fù)雜度為O(NaM(N1+Na)2)+O(NsNa)。(2)外部種群的更新文獻(xiàn)指出非可行解集更新的最壞時(shí)間復(fù)雜度為O(M(1+N1)(Ns+N2));而對(duì)于可行解集,考慮最差情況,從N1+Na個(gè)微粒中選出全部非劣解需M(Na+N1)2次比較,循環(huán)擁擠排序的計(jì)算復(fù)雜度為O(∑i=N1N1+NaM(i)log(i)),所以可行解集更新的最壞時(shí)間復(fù)雜度不大于O(NaM(N1+Na)2)。2實(shí)驗(yàn)裝置和程序?yàn)榱蓑?yàn)證CMABC算法在約束多目標(biāo)優(yōu)化問題上的求解性能,將其與兩種目前性能最優(yōu)、最具代表性的算法MOABC和CHPSO在CTP測(cè)試函數(shù)集上進(jìn)行對(duì)比實(shí)驗(yàn),所有實(shí)驗(yàn)在硬件配置為IntelCentrinoDuo,CPU:T7250、1GB內(nèi)存、主頻2.0GHz的計(jì)算機(jī)上進(jìn)行,程序采用MATLABR2007編寫。各算法的收斂效果和分布性分別采用TSC(A1,A2)和世代距離SP來對(duì)比。2.1不可行解的2個(gè)代次100%將本文算法與僅去掉某項(xiàng)改進(jìn)的算法進(jìn)行對(duì)比。參數(shù)設(shè)置如下:初始種群設(shè)為100,迭代次數(shù)為250,外部種群中的可行解集和不可行解集的容量N1、N2都為100,鄰域個(gè)體數(shù)目為5,每代保留的不可行解數(shù)目為5,Pm為0.5。2.1.1ctp6測(cè)試外部種群中可行解集更新方式的改進(jìn)主要影響算法的分布性,所以選擇對(duì)分布性效果明顯的CTP6測(cè)試。保持初始種群和參數(shù)設(shè)置相同,對(duì)改進(jìn)前后的算法隨機(jī)運(yùn)行5次,取最好結(jié)果對(duì)比如圖1所示。從圖1可以清晰看出,改進(jìn)后分布效果明顯改善,證明本文提出的有關(guān)外部種群中可行解集更新方式的改進(jìn)是有效的。2.1.2ctp4算法效果對(duì)比測(cè)試將偵查蜂與引領(lǐng)蜂的行為相融合的改進(jìn)搜索方式與算法的收斂效果有關(guān),為驗(yàn)證該種改進(jìn)對(duì)算法效果的影響,對(duì)較易陷入局部最優(yōu)的CTP4進(jìn)行測(cè)試,對(duì)比算法分別選擇常用limit取值30,保證兩種方法的初始種群相同,兩算法各運(yùn)行5次,取最好效果比較,如圖2所示。從圖2最終的分布效果可以看出,改進(jìn)后算法效果明顯改善,證明了這種改進(jìn)的有效性。2.1.3算法有效性驗(yàn)證跟隨蜂的搜索方式主要影響算法的收斂速度,隨機(jī)選取外部種群中的可行解和不可行解作為較優(yōu)個(gè)體,并在其附近搜索,是常用的搜索方式,作為本文改進(jìn)前的搜索策略,為驗(yàn)證本文提出的改進(jìn)策略的有效性,將改進(jìn)前后的效果進(jìn)行對(duì)比,保持初始種群相同,參數(shù)一致,兩種算法各隨機(jī)運(yùn)行五次,取最好結(jié)果,對(duì)比效果如圖3所示。從上述仿真結(jié)果可以看出:在進(jìn)化到40代時(shí),跟隨蜂的搜索策略被改進(jìn)后,算法的收斂效果和分布性效果都有明顯改善,即改進(jìn)后算法的進(jìn)化速度有顯著提高,與分析相符,證實(shí)了本文改進(jìn)方式的有效性。2.1.4精英種群確定迭代種群的更新方式與算法進(jìn)化的收斂效果關(guān)系很大,為驗(yàn)證本文提出方法是否有效,將本文方法與常用的NSGA-II中精英種群確定方式進(jìn)行比較,為對(duì)比明顯,選擇最優(yōu)可行解位于可行域與不可行域邊界的CTP4作為測(cè)試函數(shù),保證對(duì)比算法的初始種群相同,算法參數(shù)設(shè)置完全相同,兩算法各隨機(jī)運(yùn)行5次,取最好結(jié)果對(duì)比,如圖4所示。從圖4可以清晰地看出,改進(jìn)后算法的收斂性和分布性都有明顯改善,由此證明本文改進(jìn)策略的有效性。2.2tsc與mp的運(yùn)行為驗(yàn)證本文提出的基于人工蜂群算法的改進(jìn)約束多目標(biāo)算法,將CMABC算法與CHPSO及MOABC算法在CTP測(cè)試函數(shù)上獨(dú)立運(yùn)行30次,統(tǒng)計(jì)TSC和SP的平均值及標(biāo)準(zhǔn)差,進(jìn)行對(duì)比。為保證比較結(jié)果的公平性,所有算法的種群大小都為100、函數(shù)評(píng)價(jià)次數(shù)都為25000,且相同測(cè)試函數(shù)的所有算法的初始種群都相同。2.2.1真實(shí)圖像結(jié)果表1為各算法對(duì)CTP類測(cè)試函數(shù)的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果,包括TSC的均值(括號(hào)外)和標(biāo)準(zhǔn)差(括號(hào)內(nèi))。這里將本文提出的CMABC算法、CHPSO算法及MOABC算法分別簡(jiǎn)記為A、B、C。從表1可以看出,本文算法得到的TSC結(jié)果更接近于1,這表明,與另兩種方法相比本文算法所得結(jié)果支配或等于其他方法所得結(jié)果的個(gè)體更多,即本文算法所得結(jié)果更為接近真實(shí)的Pareto前沿。此外,與另兩種方法相比本文算法的方差相對(duì)較小,說明本文算法最為穩(wěn)定。2.2.2算法有效性測(cè)試為了對(duì)比3種算法的分布性效果,通過仿真實(shí)驗(yàn)給出了各算法