李國森 閆 李* 郭倩倩 周同馳 王永林 岳彩通
1(中原工學(xué)院電子信息學(xué)院 河南 鄭州 450007) 2(鄭州大學(xué)電氣工程學(xué)院 河南 鄭州 450001) 3(鄭州大學(xué)產(chǎn)業(yè)技術(shù)研究院 河南 鄭州 450001)
在實際工程應(yīng)用中,往往存在多個目標(biāo)相互沖突的多目標(biāo)優(yōu)化問題[1]。由于目標(biāo)之間的沖突性,這類問題不存在多個目標(biāo)同時最優(yōu)的唯一解,而是存在一組互不占優(yōu)的折衷解,稱為Pareto最優(yōu)解集(Pareto-optimal Set,PS)[2]。近年來,許多解決多目標(biāo)問題的優(yōu)化算法被相繼提出[3],如NSGA-II[4]、PESA-II[5]、SPEA2[6]和MOEA/D[7]等。這些算法得到的Pareto最優(yōu)解集在目標(biāo)空間映射后得到的Pareto前沿(Pareto Front,PF)分布均勻且收斂[8-9]。
在多目標(biāo)優(yōu)化問題中,存在一類問題具有多模態(tài)的特性,如路徑規(guī)劃問題[10]、背包問題[11]、火箭發(fā)動機(jī)設(shè)計問題[12]和作業(yè)車間調(diào)度問題[13]。這些問題存在著多個不同的Pareto解集,對應(yīng)著目標(biāo)空間中的同一個Pareto前沿[14],被稱為多模態(tài)多目標(biāo)優(yōu)化問題。如何設(shè)計多模態(tài)多目標(biāo)算法使其能夠獲得多個不同的Pareto解集是解決這類問題的關(guān)鍵。多個Pareto解集有利于決策者根據(jù)自己的喜好選擇合適的解決方案。
多模態(tài)多目標(biāo)優(yōu)化問題在提出之后,逐漸獲得研究學(xué)者的關(guān)注。Deb等[14]提出了Omni-optimizer算法,將決策空間中擁擠距離的概念引入到非支配排序方法中以提高解在決策空間中的多樣性。Liang等[16]提出了DN-NSGAII算法,采用基于決策空間的非支配排序算法以改善解在決策空間中的分布。Yue等[10]采用基于環(huán)形拓?fù)涞男∩撤椒?,并將特殊擁擠距離嵌入到非支配排序方法中以獲得更多的Pareto解。Liu等[11]利用雙檔案機(jī)制和重組策略指導(dǎo)種群進(jìn)化,提高種群的多樣性和收斂性。Liang等[17]采用自組織映射網(wǎng)絡(luò)在決策空間中建立鄰域關(guān)系,并采用精英學(xué)習(xí)策略避免算法收斂過快。
但是上述研究在解決多模態(tài)多目標(biāo)問題時仍然存在Pareto解集不完整、收斂性較差等問題,本文以多目標(biāo)粒子群算法(Multi-objective Particle Swarm Optimization, MOPSO)[18]為框架,提出了一種基于參考點的多模態(tài)多目標(biāo)粒子群算法(RPMOPSO)。通過引入?yún)⒖键c策略以提高種群多樣性,并采用擴(kuò)散機(jī)制找到更多的Pareto解。利用十二個測試函數(shù),將RPMOPSO與其他六種算法進(jìn)行性能比較,結(jié)果表明RPMOPSO在尋優(yōu)性能和收斂性上表現(xiàn)良好。
如果多目標(biāo)問題在決策空間中存在多個Pareto解集,且這些解集映射到目標(biāo)空間中同一Pareto前沿,則稱為多模態(tài)多目標(biāo)優(yōu)化問題(multimodal multi-objective optimization problems,MMOPs)[10]。該優(yōu)化問題如圖1所示,決策空間中Pareto解集PS1、PS2對應(yīng)著目標(biāo)空間中相同的PF。例如,A1和A2在決策空間中的位置不同,但對應(yīng)目標(biāo)空間中相同的點A′。找到A1和A2這兩個解,可以給決策者不同的選擇方案。
圖1 多模態(tài)多目標(biāo)優(yōu)化問題
設(shè)種群規(guī)模為N的種群,在一個D維的決策空間中進(jìn)行尋優(yōu)。在t時刻,第i個粒子在其個體最優(yōu)位置pi(t)和全局最優(yōu)位置gi(t)的引導(dǎo)下從當(dāng)前位置xi(t)以速度vi(t)飛行[19-20],則該粒子在(t+1)時刻的速度vi(t+1)和位置xi(t+1)可表示為:
vi(t+1)=wvi(t)+c1r1(pi(t)-xi(t))+
c2r2(gi(t)-xi(t))
(1)
xi(t+1)=xi(t)+vi(t+1)
(2)
式中:w為慣性權(quán)重;c1和c2為學(xué)習(xí)因子;r1和r2為區(qū)間[0,1]上的隨機(jī)數(shù)。
隨后為了進(jìn)一步控制粒子的飛行速度,將壓縮因子χ引入粒子的速度公式[21],表示如下:
vi(t+1)=χ(vi(t)+c1r1(pi(t)-xi(t))+
c2r2(gi(t)-xi(t)))
(3)
(4)
在傳統(tǒng)粒子群算法中,每個粒子采用共享的全局最優(yōu)信息更新自身的位置,以促使種群快速收斂,但在一定程度上降低了解的多樣性。
圖2 參考點策略示意圖
因此,在粒子進(jìn)行速度更新時,式(3)重新定義為:
vi(t+1)=χ(vi(t)+c1r1(pi(t)-xi(t))+
c2r2(o*-xi(t)))
(5)
本文采用擴(kuò)散機(jī)制,以幫助粒子跳出局部最優(yōu)。一方面,傳統(tǒng)粒子群算法存在早熟停滯或者陷入局部最優(yōu)的問題;另一方面,如果過多的粒子在某一次迭代中選擇同一參考點,將導(dǎo)致這些粒子聚集在同一最優(yōu)解附近,從而過度開發(fā)某一區(qū)域,而難以找到更多最優(yōu)解。因此,擴(kuò)散機(jī)制的基本思想是改變這些粒子的飛行軌跡,將其擴(kuò)散到更大的區(qū)域,使其有機(jī)會選擇新的參考點。
(pi(t)-xi(t))
(6)
式中:Levy(λ)是服從參數(shù)λ(1<λ≤3)的Levy分布的隨機(jī)數(shù);‖pi(t)-xi(t)‖表示pi(t)和xi(t)之間的距離。在式(6)中,一方面,Levy分布具有長距離和短距離跳躍相間的特性[24-25]。其長跳躍的搜索方式有利于全局探索,且不容易陷入局部停滯;另一方面,粒子根據(jù)歷史最優(yōu)位置和當(dāng)前位置的距離動態(tài)調(diào)整搜索范圍,以提高算法的全局勘探能力。當(dāng)pi(t)和xi(t)距離很近時,粒子的搜索范圍將變得很大,以搜索到更多的解;反之,粒子不會立即收斂到最優(yōu)解,避免陷入局部最優(yōu)。
步驟1設(shè)置算法的種群大小N、學(xué)習(xí)因子(c1、c2)、最大迭代次數(shù)MaxIter,根據(jù)佳點集原理初始化種群P,外部檔案EXA=P,參考點RP=P,參考點用于保留最優(yōu)解的檔案RPA=P。
步驟2計算第j個(j=1,2,…,N)參考點被所有粒子選擇的次數(shù)為φj。
步驟3對于第i個(i=1,2,…,N)粒子P{i},計算該粒子離參考點最近的點(記為RP{j}),則參考點RP{j}所保留的最優(yōu)信息o*為RPA{j}。根據(jù)式(5)計算粒子的速度,然后根據(jù)式(2)計算粒子的位置。
步驟5對于第j個參考點RP{j},計算種群中離其最近的粒子,將該粒子與該參考點保留的最優(yōu)解RPA{j}進(jìn)行比較,保留一個非支配解進(jìn)入檔案RPA{j}。
步驟6更新外部檔案EXA=[P;EXA],對外部檔案進(jìn)行非支配排序,選擇占優(yōu)性強(qiáng)且稀疏的前N個解存入EXA。
步驟7若迭代次數(shù)達(dá)到最大迭代次數(shù)MaxIter,輸出外部檔案;否則,返回步驟2。
本文采用12個經(jīng)典的多模態(tài)多目標(biāo)測試函數(shù)[10],包括MMF1-MMF8、SYM-PART simple、SYM-PART rotate、SYM-PART rot.+ trans. 和Omni-test函數(shù)(D=3)。其中,Omni-test函數(shù)在決策空間中的Pareto解集個數(shù)最多,用來測試算法在目標(biāo)空間的尋優(yōu)能力。
使用六種優(yōu)化算法與RPMOPSO進(jìn)行比較,包括三種多模態(tài)多目標(biāo)算法(MO_Ring_PSO_SCD[10]、Omni-optimizer[9]和DN-NSGAII[16])和三種多目標(biāo)算法(NSGA-II、PESA-II和MOEA/D)。其中,RPMOPSO參數(shù)如下:c1=c2=2.05。其他算法的參數(shù)值與相應(yīng)文獻(xiàn)中的參數(shù)值相同。所有算法的種群大小N和最大迭代次數(shù)MaxIter分別設(shè)置為800和100[10],外部歸檔大小設(shè)置為800,獨立運行25次。采用MATLAB R2014b進(jìn)行仿真,運行環(huán)境為Intel? CoreTMI7-4790處理器,內(nèi)存為16 GB。
本文采用Pareto解集近似性(PSP)[10]和超體積(Hv)[26]指標(biāo)衡量算法性能。PSP用于度量所獲得PS的收斂性和分布性。Hv用于評價所獲得PF的收斂性和分布性。PSP值越大意味著在決策空間中獲得的PS的收斂性和多樣性越好。Hv值越大意味著在目標(biāo)空間中獲得的PF越接近真實的PF。
3.4.1策略性能對比
為了驗證所提策略在解決多模態(tài)多目標(biāo)問題時的有效性,將RPMOPSO算法和MOPSO[10]、RPMOPSO-I(采用參考點策略的MOPSO算法)和RPMOPSO-II(采用擴(kuò)散機(jī)制的MOPSO算法)進(jìn)行比較。表1所示為結(jié)合不同策略的算法的PSP的均值、標(biāo)準(zhǔn)差,以及Wilcoxon秩和檢驗的h值。
表1 各策略PSP指標(biāo)統(tǒng)計
可以看出,RPMOPSO-I的性能優(yōu)于MOPSO,而RPMOPSO-II的性能略優(yōu)于MOPSO。因此,參考點策略和擴(kuò)散機(jī)制能有效地改善基本MOPSO的性能。此外,秩和檢驗的結(jié)果表明,兩種策略的結(jié)合能夠使算法性能得到顯著的提升。其原因在于參考點策略使RPMOPSO能夠找到更多的Pareto最優(yōu)解。參考點策略可以在決策空間中產(chǎn)生穩(wěn)定的小生境,每個粒子在自己的小生境鄰域內(nèi)進(jìn)化,且不會受其他鄰域的影響,以提高種群的多樣性。擴(kuò)散機(jī)制能夠使粒子向更大的范圍內(nèi)尋優(yōu),因此陷入局部最優(yōu)的粒子不僅可以跳出當(dāng)前的最優(yōu)解,而且可以捕捉到更多的最優(yōu)解。
3.4.2算法性能對比
本節(jié)將RPMOPSO與三種多模態(tài)多目標(biāo)算法和三種多目標(biāo)算法進(jìn)行比較。首先,比較不同算法在決策空間獲得PS的能力,不同算法的PSP值如表2所示。結(jié)果表明RPMOPSO在所有測試函數(shù)中具有較好的表現(xiàn),其性能優(yōu)于其他六種算法。MO_Ring_PSO_SCD排第二名,因其使用環(huán)形拓?fù)淠軌蛐纬尚∩?,能夠找到更多Pareto解。DN-NSGAII和Omni-optimizer的表現(xiàn)緊隨其后,兩者采用決策空間的擁擠距離作為環(huán)境選擇提高了算法的性能。NSGA-II、MOEA/D和PESA-II表現(xiàn)較差,其原因在于這三種多目標(biāo)算法沒有考慮決策空間中解的分布。其次,評價算法在目標(biāo)空間中獲得的PF的性能,不同算法的Hv值如表3所示??梢钥闯鯮PMOPSO在Hv性能指標(biāo)上表現(xiàn)不是最好的。實際上,所有算法在同一個測試函數(shù)上的Hv值是很接近的。原因是所有的算法都考慮了最優(yōu)解在目標(biāo)空間中的分布。
表2 不同算法PSP指標(biāo)統(tǒng)計
表3 不同算法Hv指標(biāo)統(tǒng)計
為了進(jìn)一步比較算法的性能,將所有算法在Omni-test測試函數(shù)上獲得的PS和PF分別在圖3、圖4進(jìn)行展示。Omni-test測試函數(shù)有27個PS。從圖3可以看出,RPMOPSO獲得的Pareto最優(yōu)解能夠比較全面地覆蓋真正的PS。MO_Ring_PSO_SCD、DN-NSGAII和Omni-optimizer獲得的PS并不完整。NSGA-II、PESA-II和MOEA/D搜索到的PS更少。其中,MOEA/D僅獲得一個PS。這說明沒有小生境技術(shù)很難維持多個PS。從圖4可以看出,所有算法在Omni-test測試函數(shù)上都能夠較好的覆蓋整個真實的PF,且能夠逼近真正的PF。
圖3 各算法所獲得的PS對比
圖4 各算法所獲得的PF對比
綜上,在獲得近似PF的前提下,RPMOPSO在決策空間中獲得的PS分布性良好。
3.4.3算法收斂性比較
為了比較算法的收斂性[10],將四個多模態(tài)多目標(biāo)算法(RPMOPSO,MO_Ring_PSO_SCD,Omni-optimizer和DN-NSGAII)在測試函數(shù)MMF4上進(jìn)行比較。MMF4在決策空間上有4個PS,如圖5所示,其PS的分布將決策空間劃分為4個子區(qū)域,分別為區(qū)域1、區(qū)域2、區(qū)域3和區(qū)域4。這樣每個子區(qū)域面積相等,且每個子區(qū)域均有一個PS。算法的收斂性可以定義為每一代種群分布在每個子區(qū)域中解的比例[10]。在理想的情況下,如果算法在測試函數(shù)MMF4上收斂性很好,那么每個子區(qū)域中解的比例應(yīng)等于25%。
圖5 測試函數(shù)MMF4的PS分布
圖6為算法迭代過程中,在每個子區(qū)域中解的比例變化曲線。從圖6(a)中可以看出,本文算法中的區(qū)域1、區(qū)域2所在的曲線隨迭代次數(shù)增加而逐漸上升,而區(qū)域3、區(qū)域4所在的曲線呈下降趨勢。在迭代次數(shù)接近50時,四個區(qū)域的解的比例趨于25%。在第80代至第100代時,每個區(qū)域的解的比例基本上接近25%。這說明RPMOPSO具有良好的收斂性。對于MO_Ring_PSO_SCD,圖6(b)中每個區(qū)域的解的比例最終能夠收斂到25%左右,但是區(qū)域1、區(qū)域2的解的比例略大于區(qū)域3、區(qū)域4的解的比例,這說明其收斂性略差于RPMOPSO。對于DN-NSGAII,在第30代以后,區(qū)域1、區(qū)域4的解的比例遠(yuǎn)低于區(qū)域2、區(qū)域3的解的比例。對于Omni-optimizer,在第45代以后,區(qū)域2、區(qū)域3的解的比例低于區(qū)域1、區(qū)域4的解的比例。在圖6(c)、(d)中,每個區(qū)域曲線的變化趨勢為頻繁震蕩,并不穩(wěn)定。這說明DN-NSGAII和Omni-optimizer算法表現(xiàn)出很差的收斂性。
圖6 算法的收斂性對比
可以看出,RPMOPSO在收斂性上具有良好的性能。
本文提出了一種基于參考點的多模態(tài)多目標(biāo)粒子群算法(RPMOPSO)。采用了參考點策略和擴(kuò)散機(jī)制,參考點策略的引入促使種群形成若干小生境,每個粒子在它的小生境鄰域內(nèi)獨立進(jìn)化,以提高種群的多樣性。擴(kuò)散機(jī)制能夠改變粒子的飛行軌跡,擴(kuò)散粒子到更大的搜索區(qū)域,極大地提高了粒子捕捉到更多Pareto解的可能性。通過和多模態(tài)多目標(biāo)算法及多目標(biāo)優(yōu)化算法的比較,證明了RPMOPSO能夠找到更多的Pareto解,且具有很好的收斂性。未來將嘗試把算法應(yīng)用于求解實際中的多模態(tài)多目標(biāo)問題。