李文樺 明夢(mèng)君 張 濤,2 王 銳,2 黃生俊,2 王 凌

多目標(biāo)優(yōu)化問題 (Multi-objective optimization problems,MOPs) 在現(xiàn)實(shí)世界中廣泛存在[1].對(duì)于該類優(yōu)化問題,往往需要考慮存在互斥關(guān)系的多個(gè)優(yōu)化目標(biāo),并且不存在一個(gè)解能夠最優(yōu)化所有優(yōu)化目標(biāo).因此該類問題的最優(yōu)解通常為一組互不支配的Pareto 最優(yōu)解集.在工業(yè)應(yīng)用和現(xiàn)實(shí)工程問題中,決策者經(jīng)常遇到多個(gè)不同的最優(yōu)解其目標(biāo)函數(shù)值相同的一類問題,例如腦功能成像[2]、柴油機(jī)設(shè)計(jì)問題[3]、游戲地圖生成問題[4]等.對(duì)于Pareto 前沿上的某個(gè)目標(biāo)向量,在決策空間中可以找到多個(gè)對(duì)應(yīng)的決策向量.這類問題通常稱為多模態(tài)多目標(biāo)優(yōu)化問題[5](Multimodal multi-objective optimization problems,MMOPs).圖1 展示了一個(gè)兩目標(biāo)兩決策變量的MMOP,從中可以看到,A點(diǎn)和B點(diǎn)都對(duì)應(yīng)于Pareto 前沿上的P點(diǎn).對(duì)于決策者來(lái)說,如果能夠獲得待優(yōu)化問題的全部最優(yōu)解,一方面可以更深入地了解該問題,對(duì)于刻畫問題屬性、提出改進(jìn)方向、尋找最優(yōu)解等具有重要作用;另一方面,一旦其中一個(gè)最優(yōu)解因環(huán)境變化等因素導(dǎo)致不可用,決策者可以方便快速地轉(zhuǎn)變到另一個(gè)最優(yōu)解.對(duì)于工業(yè)生產(chǎn)來(lái)說,多個(gè)最優(yōu)解意味著有更多的生產(chǎn)方案可供選擇.在某些情況下,決策者甚至?xí)邮苣繕?biāo)值稍劣的解[6].例如某個(gè)解決方案要達(dá)到的加工條件較為苛刻,或者對(duì)加工精度要求極高,那么決策者將偏向于選擇對(duì)條件要求不苛刻的解而接受其目標(biāo)函數(shù)值上的劣勢(shì).因此,如何獲得MMOPs的全部最優(yōu)解成為亟待解決的問題之一.

圖1 兩目標(biāo)兩決策變量多模態(tài)問題示意圖 (左圖和右圖分別表示問題的決策空間和目標(biāo)空間)Fig.1 Diagram of a two-objective two-decision-variable MMOP (the left figure and right figure are decision space and objective space respectively)

多目標(biāo)進(jìn)化算法 (Multi-objective evolutionary algorithms,MOEAs) 在求解非線性、決策類型多樣、決策空間復(fù)雜的MOPs 上的有效性已經(jīng)得到了廣泛的驗(yàn)證[7-8].鑒于MOEAs 在MOPs 的標(biāo)準(zhǔn)測(cè)試問題和實(shí)際工程問題上的優(yōu)異性能,多種MOEAs 被拓展以用于解決MMOPs.研究者將種群多樣性保持機(jī)制與現(xiàn)有MOEAs 結(jié)合,以獲得問題的全部最優(yōu)解集,這類算法統(tǒng)稱為多模態(tài)多目標(biāo)進(jìn)化算法 (Multimodal multi-objective evolutionary algorithms,MMEAs).但由于MMOPs 比傳統(tǒng)的MOPs 具有更復(fù)雜的決策空間和映射關(guān)系,目前所提出的MMEAs 在求解MMOPs 時(shí)仍存在許多困難[9],例如,如何平衡決策空間的多樣性和目標(biāo)空間的收斂性,如何保留目標(biāo)向量相似而決策向量相差較大的個(gè)體.

前期圍繞MMOPs 的大部分工作是獲得此類問題的多個(gè)全局最優(yōu)解集,不考慮問題的局部最優(yōu)解集.在火箭任務(wù)規(guī)劃問題[6]中,對(duì)于相距較遠(yuǎn)的兩個(gè)火箭發(fā)射窗口,其空間飛行時(shí)間和有效載荷相差非常小,因此對(duì)于決策者來(lái)說,獲得這兩個(gè)不同的解具有重要意義.最新的研究也指出,在現(xiàn)實(shí)問題中,存在多個(gè)全局最優(yōu)Pareto 區(qū)域較為罕見.更普遍的情況是,多個(gè)全局最優(yōu)與局部最優(yōu)區(qū)域同時(shí)存在.從另一個(gè)角度來(lái)說,多個(gè)全局最優(yōu)是存在局部最優(yōu)的一種特殊情況,因此,同時(shí)獲得問題的全局最優(yōu)和局部最優(yōu)區(qū)域更為重要[10].遺憾的是,針對(duì)此類問題的研究目前還比較少,仍處于初期階段.為了進(jìn)一步提升MMEAs 在具有局部最優(yōu)解集的MMOPs 上的性能,本文進(jìn)行了積極的探索,創(chuàng)新性體現(xiàn)在以下幾個(gè)方面:

1) 提出了一種局部收斂性指標(biāo) (ILC).具體來(lái)說,區(qū)別于全局收斂性指標(biāo),局部收斂性指標(biāo)只要求個(gè)體與它附近的個(gè)體進(jìn)行對(duì)比.在進(jìn)化過程中,基于局部收斂性指標(biāo)可以保留問題的局部最優(yōu)解.另外,該指標(biāo)可以方便地嵌入到已有的MOEAs 中,從而使算法具有搜索問題局部最優(yōu)Pareto 區(qū)域的能力.

2) 為了增強(qiáng)算法保持種群多樣性的能力,提出了一種考慮目標(biāo)空間和決策空間多樣性的指標(biāo),并以此為依據(jù),設(shè)計(jì)了一種能夠同時(shí)獲得問題的全局和局部Pareto 最優(yōu)解的環(huán)境選擇策略.

3) 結(jié)合局部收斂性指標(biāo)和環(huán)境選擇策略,提出了一種多模態(tài)多目標(biāo)優(yōu)化算法用以獲得MMOPs的全局和局部Pareto 解集.通過對(duì)比其他代表性算法在測(cè)試問題上的表現(xiàn),驗(yàn)證了所提算法的有效性.

本文內(nèi)容安排如下:第1 節(jié)介紹多模態(tài)多目標(biāo)優(yōu)化的相關(guān)概念以及該類問題的求解難點(diǎn);第2 節(jié)詳細(xì)介紹本文所提的局部收斂性指標(biāo)以及基于該指標(biāo)的多模態(tài)多目標(biāo)優(yōu)化算法;第3 節(jié)通過實(shí)驗(yàn)對(duì)所提算法的有效性進(jìn)行驗(yàn)證;第 4 節(jié)對(duì)本文研究進(jìn)行總結(jié),并提出未來(lái)可能的研究方向.

1 研究背景

1.1 多目標(biāo)優(yōu)化問題

現(xiàn)實(shí)世界中的許多工程應(yīng)用問題,往往需要考慮多個(gè)優(yōu)化目標(biāo).通常來(lái)說,不同的目標(biāo)是互相制約的,只能通過權(quán)衡來(lái)獲得令決策者滿意的解.不失一般性,MOPs[11-12]可以表示如下

其中,Ω 為問題的可行域,fm(x) 為決策向量x的第m個(gè)目標(biāo)函數(shù)值.與具有單個(gè)全局最優(yōu)值的單目標(biāo)優(yōu)化問題不同,在多目標(biāo)優(yōu)化問題中,存在多個(gè)非支配解,稱為Pareto 最優(yōu)解集.解xA支配解xB當(dāng)且僅當(dāng)

一般來(lái)說,MOEAs 會(huì)給出一組互不支配的解集,稱為Pareto 最優(yōu)解集 (Pareto solution set,PS),并且不存在一個(gè)解能在所有目標(biāo)函數(shù)上都優(yōu)于其他解.而PS 在目標(biāo)空間上的映射稱為Pareto 最優(yōu)前沿 (Pareto front,PF).

1.2 多模態(tài)多目標(biāo)優(yōu)化問題

多模態(tài)多目標(biāo)優(yōu)化問題可以定義[5,9]如下:

定義 1.如果一個(gè)多目標(biāo)優(yōu)化問題滿足以下兩個(gè)條件之一,則稱該問題為多模態(tài)多目標(biāo)優(yōu)化問題.

1) 問題至少有一個(gè)局部Pareto 最優(yōu)解集;

2) 問題至少有兩個(gè)等效全局Pareto 最優(yōu)解集,它們對(duì)應(yīng)相同的PF.

定義 2.對(duì)于解集SL中的任意解x,如果不存在x的鄰居解y,其中‖x-y‖≤δ,使得yPareto支配x,那么SL稱為局部最優(yōu)解集.

定義 3.對(duì)于解集SG中的任意解x,如果不存在解y,使得yPareto 支配x,那么SG稱為全局最優(yōu)解集.

從定義中可以看出,MMOPs 存在兩種情況.情況1 可由圖1 簡(jiǎn)單表示,即在決策空間中存在多個(gè)相距較遠(yuǎn)的PS 對(duì)應(yīng)于相同的PF.換句話說,在目標(biāo)空間Pareto 前沿上的一個(gè)目標(biāo)向量,可以在決策空間上找到距離較遠(yuǎn)的多個(gè)最優(yōu)解.情況2 可由圖2 表示,其中B點(diǎn)對(duì)應(yīng)目標(biāo)空間中的P1點(diǎn),A點(diǎn)對(duì)應(yīng)局部PF 上的P2點(diǎn).在情況1 的基礎(chǔ)上,問題還存在一個(gè)或多個(gè)局部PF.

圖2 具有局部帕累托前沿的兩目標(biāo)多模態(tài)問題 (左圖和右圖分別表示問題的決策空間和目標(biāo)空間)Fig.2 A two-objective MMOP with local Pareto front (the left figure and right figure are decision space and objective space respectively)

由上述定義可知,對(duì)于MMOPs,只存在一個(gè)全局PF,而局部PF 可能有多個(gè),且全局PF和局部PF 對(duì)應(yīng)至少一個(gè)PS.圖3 展示了MMF12 問題和MMF15 問題的PF和PS.從中可以直觀地看到,MMF12 存在一個(gè)全局PF 對(duì)應(yīng)于4 個(gè)等效全局PS,一個(gè)局部PF 對(duì)應(yīng)于4 個(gè)等效局部PS;而MMF15則只有一個(gè)全局PS和一個(gè)局部PS.

圖3 MMF12 (左)和MMF15 (右)問題的PF和PS 示意圖Fig.3 Diagram of PF and PS for MMF12 (left) and MMF15 (right)

傳統(tǒng)的MOEAs 的目標(biāo)是獲得一組靠近Pareto最優(yōu)前沿的均勻分布的解集.這一目標(biāo)包含兩個(gè)重點(diǎn):1) 解集具有良好的收斂性,其目標(biāo)向量接近于Pareto 前沿;2) 解集在Pareto 前沿上均勻分布.為了達(dá)成這一目標(biāo),NSGA-II 算法先后使用了兩個(gè)評(píng)價(jià)指標(biāo),即快速非支配排序和目標(biāo)空間的擁擠距離.類似于NSGA-II,其他MOEAs 總是以收斂性為第一準(zhǔn)則,輔以目標(biāo)空間的均勻性選擇策略,從而獲得性能較好的解集.以圖1 為例,在利用MOEAs求解MMOPs 問題時(shí),假設(shè)算法已經(jīng)通過搜索獲得解A(對(duì)應(yīng)于目標(biāo)空間的點(diǎn)P),在新的迭代搜索中,算法得到解B′(對(duì)應(yīng)于目標(biāo)空間的點(diǎn)P′).那么,對(duì)于傳統(tǒng)的MOEAs 來(lái)說,P與P′在目標(biāo)空間將變得 “擁擠”.由于目標(biāo)空間均勻性指標(biāo)的存在,P′將不會(huì)在迭代過程中得到保留,因此算法難以同時(shí)獲得解A和解B.即傳統(tǒng)以收斂性為第一準(zhǔn)則的算法難以求解多模態(tài)多目標(biāo)優(yōu)化問題.另外,對(duì)于存在多個(gè)局部PF 的MMOPs 來(lái)說,由于MOEAs以收斂性作為第一準(zhǔn)則,在沒有其他種群多樣性策略的輔助下,算法將迅速收斂到問題的全局PF,因此不會(huì)保留該問題的局部PF.

為了獲得MMOPs 的全部最優(yōu)解集,近年來(lái)學(xué)者們提出了許多MMEAs.Omni-optimizer[13]可能是最具代表性的MMEA,它基于NSGA-II[14]引入了保持決策空間解的多樣性的策略,包括基于拉丁超立方體采樣的種群初始化方法、限制交配選擇策略和替代擁擠距離.其中,替代擁擠距離旨在評(píng)估目標(biāo)空間和決策空間中解的多樣性.受此啟發(fā),基于niching 的協(xié)方差矩陣自適應(yīng) (Covariance matrix adaptation,CMA) 方法[15]在目標(biāo)和決策空間中引入了聚合距離度量,可以將解集劃分為多個(gè)niches.另外,雙niches 進(jìn)化算法 (Double-niched evolutionary algorithm,DNEA)[16]和基于決策空間的niching NSGA-II (Decision space-based niching NSGA-II,DN-NSGAII)[17]是兩種基于Omnioptimizer 的增強(qiáng)算法,經(jīng)實(shí)驗(yàn)證明,這兩個(gè)算法在MMF 測(cè)試問題上表現(xiàn)優(yōu)異.與傳統(tǒng)采用模擬二元交叉算子 (Simulated binary crossover,SBX) 不同,MO_PSO_MM[18]和MO_Ring_PSO_SCD[19]使用粒子群優(yōu)化 (Particle swarm optimization,PSO) 算子[20]來(lái)生成新的解并在傳統(tǒng)MMOPs 上獲得了良好的性能.此外,差分進(jìn)化 (Differential evolution,DE) 算子[21]也被用來(lái)促進(jìn)決策空間的多樣性,例如MMODE[22]、DE-RLFR[23]等.然而,前期的工作為了更直觀地展示算法獲得不同PS 的能力,測(cè)試問題的決策變量通常被設(shè)計(jì)為2～3 個(gè),并且問題的搜索難度較小,通常能夠在10～50 代內(nèi)找到最優(yōu)解.

最近,Liu 等[24]考慮到現(xiàn)有的測(cè)試問題中,搜索不同PS 時(shí)難度一樣,而在現(xiàn)實(shí)問題中,獲得不同區(qū)域的解集難度往往是不同的.基于此,作者提出了一種新的測(cè)試問題集IDMP (Imbalanced distance minimization benchmark problems).這個(gè)測(cè)試集的主要特點(diǎn)是,搜索不同的區(qū)域需要的解的評(píng)價(jià)次數(shù)不同.經(jīng)過實(shí)驗(yàn),已有的算法在這類問題上表現(xiàn)較差,往往只能找到一個(gè)Pareto 解集.因此,該測(cè)試問題能夠更加準(zhǔn)確地衡量算法保持多樣性和搜索不同PS 的能力.為了解決這類問題,Liu 等提出了一種基于距離的收斂性懲罰方法,并選擇每次只更新一個(gè)解的steady 策略對(duì)種群進(jìn)行更新,形成了CPDEA 算法.受基于指標(biāo)的進(jìn)化算法 (Indicatorbased evolutionary algorithm,IBEA) 啟發(fā),Li 等[25]提出了一種加權(quán)指標(biāo),可以衡量個(gè)體的局部收斂性.Fan 等提出了一種自適應(yīng)分區(qū)搜索 (Zoning search with adaptive resource allocating,ZS-ARA)[26]策略,將整個(gè)搜索空間分成幾個(gè)子區(qū)域進(jìn)行搜索,從而提高算法保持多樣性的能力.經(jīng)過驗(yàn)證,這些算法在IDMP 問題上表現(xiàn)良好.

總體來(lái)說,MMEAs 的有效性得到了廣泛的實(shí)驗(yàn)驗(yàn)證,但是目前的MMEAs 更多地關(guān)注于找到MMOPs 的全局最優(yōu)解.在現(xiàn)實(shí)問題中,存在多個(gè)等效全局最優(yōu)Pareto 區(qū)域往往是比較少的情況,更普遍的情況是,全局最優(yōu)與局部最優(yōu)同時(shí)存在.因此研究同時(shí)獲得問題的全局最優(yōu)和局部最優(yōu)區(qū)域更為重要.遺憾的是,針對(duì)此類問題的研究目前還比較少.其中,PQ,?-MOEA[6]是專門針對(duì)空間任務(wù)設(shè)計(jì)問題而設(shè)計(jì)的算法,其使用?-dominance[27]進(jìn)行后代選擇;MMOPIO[28]基于Pareto 支配關(guān)系設(shè)計(jì),能在一定程度上獲得局部最優(yōu)解;eMOEA/D-ADA[29]是基于分解方法的算法,通過給不同參考向量分配多個(gè)個(gè)體,也具有一定的局部最優(yōu)搜索和保留能力;DIOP[30]則給出一種多樣性的指標(biāo),并使用基于集合的多目標(biāo)優(yōu)化算法框架對(duì)問題進(jìn)行求解,能夠獲得問題的局部最優(yōu)解集;DNEA-L[10]則通過使用一種多前沿檔案集更新方法來(lái)獲取局部PS.但是,由于沒有系統(tǒng)地討論這類問題,因此在性能上仍有提升的空間.

Liang 等[31]提出了具有局部PF 的MMOPs 測(cè)試問題,并舉辦了相關(guān)的競(jìng)賽.在這之后,Lin 等[32]提出了使用基于DBSCAN 的雙重聚類的方法來(lái)維持種群的多樣性,能夠獲得問題的局部最優(yōu)解集.然而,由于基于密度的聚類方法在對(duì)不同的解集區(qū)域進(jìn)行聚類時(shí)存在誤差,因此容易出現(xiàn)性能不穩(wěn)定的情況.Li 等[33]則提出了一種基于分層選擇的多目標(biāo)優(yōu)化算法 (Hierarchy ranking method based evolutionary algorithm,HREA) 來(lái)獲取問題的全局和局部Pareto 解集.Tanabe 等[9]和岳彩通等[5]針對(duì)多模態(tài)多目標(biāo)優(yōu)化進(jìn)行了較為詳細(xì)的綜述總結(jié),總的來(lái)說,雖然獲取MMOPs 的全局和局部最優(yōu)解具有重要意義,但是相關(guān)的算法設(shè)計(jì)仍然處于起步階段,設(shè)計(jì)一種魯棒性高、性能好的考慮局部PS 的MMEA 成為MMOPs 研究領(lǐng)域的前沿問題.

2 基于局部收斂性指標(biāo)的多模態(tài)多目標(biāo)優(yōu)化

2.1 局部收斂性指標(biāo)

傳統(tǒng)的MOEAs 更多地關(guān)注解集的收斂性,因此絕大多數(shù)算法都選擇收斂性作為第一準(zhǔn)則進(jìn)行后代個(gè)體的選擇[14].基于傳統(tǒng)MOEAs 設(shè)計(jì)的多模態(tài)多目標(biāo)優(yōu)化算法考慮了決策空間的多樣性,因此能夠獲得更多的等效PS.然而,傳統(tǒng)算法往往只關(guān)注獲得全局PS,從而舍棄局部PS 的搜索.為了加強(qiáng)算法對(duì)局部PS 的搜索能力,參考SPEA2 算法[34]中所提的元適應(yīng)度值,本文提出一種局部收斂性指標(biāo),對(duì)于解xi,其局部收斂性指標(biāo)計(jì)算如下

圖4 為本文所提的局部收斂性指標(biāo)計(jì)算示意圖.與SPEA2 算法所提的元適應(yīng)度值需要跟種群中所有的個(gè)體進(jìn)行比較不同,在局部收斂性指標(biāo)的計(jì)算中,個(gè)體只跟自己的鄰居解進(jìn)行比較,從而提高局部最優(yōu)解的收斂能力.具體來(lái)說,對(duì)于決策空間中的解A來(lái)說,其處于局部PS (圓圈區(qū)域)中.在傳統(tǒng)的MOEAs 中,由于全局PS (C點(diǎn)所在線條)的收斂性更好,因此解A和解B被解C支配,在進(jìn)化過程中不會(huì)被保留.在局部收斂性指標(biāo)的計(jì)算中,解A在計(jì)算支配關(guān)系時(shí),只跟自身的鄰居解(在當(dāng)前示意圖中,鄰居只有解B) 進(jìn)行比較,此時(shí)解A屬于非支配解,能夠保留并順利進(jìn)入下一次的進(jìn)化.局部收斂性指標(biāo)的計(jì)算中使用了鄰居的概念,而決策空間中鄰居解的定義是偏主觀的,需要引入?yún)?shù)[4].不失一般性,在本文中,稱兩個(gè)解xi和xj為鄰居,當(dāng)且僅當(dāng)它們的歐幾里得距離小于V,計(jì)算如下

圖4 局部收斂性指標(biāo)示意圖Fig.4 Diagram of local convergence indicator

其中,D表示決策變量的個(gè)數(shù);分別代表第d個(gè)決策變量的最大值和最小值.

2.2 算法框架

前面具體介紹了局部收斂性指標(biāo)的思想以及計(jì)算過程,基于該指標(biāo),本文提出了一種基于局部收斂性指標(biāo)的多模態(tài)多目標(biāo)優(yōu)化算法 (MMEA based on local convergence indicator,ILC-MMEA).ILC-MMEA 的算法框架由算法1 表示.與大多數(shù)MOEAs一樣,ILC-MMEA 由以下步驟組成:種群初始化,交配選擇,后代生成,環(huán)境選擇.本文引入了局部收斂性指標(biāo)來(lái)搜索全局和局部的PS.并且在挑選父代個(gè)體時(shí) (步驟 3)),使用了局部收斂性指標(biāo)作為二元競(jìng)爭(zhēng)的準(zhǔn)則,從而加快算法的收斂速度和提升局部探索能力.具體來(lái)說,首先從當(dāng)前種群Pop里隨機(jī)挑選兩個(gè)解并比較它們的局部收斂性指標(biāo)值,較好的個(gè)體將被選擇;如果它們的局部收斂性指標(biāo)值一致,則擁擠距離小的個(gè)體被選擇;這一過程將被重復(fù)執(zhí)行,直到挑選出N個(gè)個(gè)體.之后,被挑選的父代個(gè)體將使用SBX和多項(xiàng)式變異 (Polynomial mutation,PM) 產(chǎn)生后代個(gè)體 (步驟 4)).另外,針對(duì)局部PS 的搜索問題,本文設(shè)計(jì)了一種新的環(huán)境選擇策略.

算法 1.ILC-MMEA 算法框架

2.3 環(huán)境選擇策略

在這一節(jié)中,將詳細(xì)討論基于ILC的環(huán)境選擇策略,其基本思路由算法2 表示.

算法2.環(huán)境選擇策略

首先,將種群與新生成的后代個(gè)體進(jìn)行合并,并計(jì)算合并后種群的局部收斂性指標(biāo)ILC(步驟 1)、步驟 2)).根據(jù)式 (3),當(dāng)=0 時(shí),表明解xi不被它的任何鄰居解支配.因此本文設(shè)計(jì)了一種二次選擇策略,具體為:當(dāng)局部非支配解的個(gè)數(shù)小于種群大小N時(shí),按照ILC的值對(duì)種群進(jìn)行排序,隨后選擇前N個(gè)個(gè)體進(jìn)入下一代 (步驟 4));否則,算法將首先挑選出局部非支配解,然后計(jì)算它們的擁擠距離,隨后刪除擁擠距離較大的解,從而保持新種群的大小為N(步驟 5)、步驟 6)).

ILC-MMEA 使用擁擠距離作為第二準(zhǔn)則對(duì)種群中的個(gè)體進(jìn)行挑選.一般來(lái)說,傳統(tǒng)的MOEAs更多地關(guān)注目標(biāo)空間中解集分布的均勻性,而MMEAs 則更多地關(guān)注決策空間的均勻性[5,9],這一點(diǎn)可以通過圖5 對(duì)目標(biāo)空間和決策空間的分布性進(jìn)行說明.圖5 中左邊表示解在決策空間的分布性很好,但是在目標(biāo)空間的分布性較差,對(duì)應(yīng)于傳統(tǒng)的MMEAs;圖5 中間表示解在決策空間的分布性很差,但是在目標(biāo)空間的分布性很好,對(duì)應(yīng)于傳統(tǒng)的MOEAs;理想狀態(tài)的解分布應(yīng)該如圖5 中右邊所示,即解在決策空間和目標(biāo)空間的分布性都很好.為了實(shí)現(xiàn)這一目標(biāo),本文提出了一種改進(jìn)的種群擁擠距離計(jì)算方法,具體如下

圖5 目標(biāo)空間和決策空間的分布均勻性Fig.5 Distribution uniformity in the objective space and the decision space

其中,‖xj -xi‖表示xi和xj的歐氏距離,f(xi) 則代表解xi對(duì)應(yīng)的目標(biāo)向量歸一化之后的值.值得注意的是,在計(jì)算之前,需要對(duì)xi和xj的值進(jìn)行歸一化.

新提出的擁擠距離充分考慮了解集在目標(biāo)空間和決策空間的相對(duì)位置,因此可以獲得在兩個(gè)空間中分布更加均勻的解集.另外,為了更好地平衡兩個(gè)空間的差異,算法對(duì)兩個(gè)空間的向量使用了統(tǒng)一的歸一化策略.

2.4 算法計(jì)算復(fù)雜度分析

本節(jié)將討論ILC-MMEA 在最壞情況下的計(jì)算運(yùn)行時(shí)間復(fù)雜度.對(duì)于每一代,主要執(zhí)行三個(gè)步驟:交配選擇,個(gè)體交叉變異,環(huán)境選擇.假設(shè)種群大小、問題的目標(biāo)數(shù)量和決策變量的數(shù)量分別為N,M,D.對(duì)于每一代,交配選擇需要 O (MN2) 的時(shí)間復(fù)雜度.采用SBX 來(lái)執(zhí)行交叉操作,需要的運(yùn)行時(shí)間為 O (DN). 另外,對(duì)于環(huán)境選擇,算法需要計(jì)算ILC,其時(shí)間復(fù)雜度為 O (MN2/2);而二次選擇的時(shí)間復(fù)雜度為 O (D2);因此環(huán)境選擇的總復(fù)雜度為max{O(MN2/2),O(D2)}. 那么,ILC-MMEA 算法的最終時(shí)間復(fù)雜度為 m ax{O(GMN2/2),O(GD2)},其中G表示迭代次數(shù).通常有N＞D,因此,可以確定ILC-MMEA 的運(yùn)行時(shí)間復(fù)雜度為 O (GMN2).作為比較,Two_Arch2、IBEA和NSGA-III 的運(yùn)行時(shí)間復(fù)雜度分別為 m ax{O(),O(MN2)},O(N2),O(MN2)}[35].從理論分析來(lái)看,ILC-MMEA 的計(jì)算效率很高.此外,在后續(xù)實(shí)驗(yàn)部分,算法的運(yùn)行時(shí)間將與其他代表性MMEAs 進(jìn)行比較.

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

3.1.1 測(cè)試問題和對(duì)比算法

為了測(cè)試ILC-MMEA 在求解傳統(tǒng)MMOPs和具有局部PS 的MMOPs 時(shí)的性能,本節(jié)將使用IDMP 測(cè)試集[24]和IEEE CEC 2019 MMOP 測(cè)試集[31].相比于其他的MMOPs 測(cè)試集,IDMP 測(cè)試集在搜索不同的PS 時(shí)搜索難度不同,在某種程度上來(lái)說,此類問題更能顯示出算法保持種群多樣性的能力;另外,IEEE CEC 2019 MMOP 測(cè)試集中的部分測(cè)試問題 (MMF10～MMF13,MMF15) 具有局部PS,因此被選擇用來(lái)測(cè)試所提算法獲得局部PS 的能力.

為了驗(yàn)證ILC-MMEA 在解決MMOPs 中的有效性,本文選擇Omni-optimizer[13]、DN-NSGAII[16]、MO_Ring_PSO_SCD[19]、MMEA-WI[25]、CPDEA[24]、DNEA-L[10]和MMOEA/DC[32]作為對(duì)比算法.具體來(lái)說,Omni-optimizer、DN-NSGAII和MO_Ring_PSO_SCD 都是求解MMOPs 的代表性算法,其性能已經(jīng)得到了廣泛驗(yàn)證;MMEAWI和CPDEA 是專門為解決不平衡MMOPs 提出的算法;DNEA-L和MMOEA/DC 則是最新關(guān)注于獲得全局和局部PS 的算法.

為了保證對(duì)比的公平性,對(duì)于所有算法,設(shè)置種群大小N=100D,函數(shù)評(píng)估的最大次數(shù)設(shè)置為NF E=5 000D,其中D是決策變量的數(shù)量.此外,除了MO_Ring_PSO_SCD 采用PSO 算子,其他算法均使用SBX和PM 算子用于生成后代,其中交叉概率和變異概率分別為1和 1 /D,ηc=ηm=20.對(duì)比算法中的具體參數(shù)均按照原論文設(shè)置.所有實(shí)驗(yàn)均基于PlatEMO v1.6[36],計(jì)算機(jī)配置為Intel i9-9900X @ 3.50 GHz,64 GB RAM.為方便多模態(tài)多目標(biāo)相關(guān)領(lǐng)域研究人員的后續(xù)研究工作,本文開放了ILC-MMEA 的源代碼,相關(guān)代碼可從以下網(wǎng)站獲取:https://gitee.com/wenhua-li/ilcmmea.

3.1.2 性能評(píng)價(jià)指標(biāo)

針對(duì)MOEAs 性能的評(píng)價(jià)指標(biāo)包括超體積 (Hypervolume,HV)[37]、世代距離 (Generation distance,GD)[38]和反世代距離 (Inverted generation distance,IGD)[38]等.它們中的大多數(shù)是用來(lái)衡量解集在目標(biāo)空間中接近真實(shí)Pareto 前沿的程度和解集分布的均勻程度.由于MMEAs 旨在獲得所有PS,因此還應(yīng)衡量解集在決策空間中的性能.因此,在本文中采用IGDX[39]作為評(píng)價(jià)指標(biāo),以評(píng)價(jià)獲得的解集與真實(shí)PF和真實(shí)PS 的近似程度.對(duì)于一個(gè)解集X,IGDX 的計(jì)算過程可以表示如下

其中,ED(x,y) 表示解x和解y的歐氏距離,X*代表真實(shí)Pareto 集合中的均勻采樣,|X*|表示集合X*中解的總個(gè)數(shù).IGDX 的值越小,表示解集的收斂性和均勻性越好,當(dāng)IGDX 值為0 時(shí),表示獲得的解集能完全覆蓋參考解集.

3.2 傳統(tǒng)MMEAs 性能對(duì)比

為了測(cè)試ILC-MMEA 在求解傳統(tǒng)MMOPs 時(shí)的性能,本文使用了IDMP 測(cè)試集.具體來(lái)說,相比較前期提出的MMOPs 測(cè)試問題,獲得IDMP 測(cè)試問題的全部Pareto 最優(yōu)解集更加困難,因此更能夠體現(xiàn)出MMEAs 保持種群多樣性和獲取不同PS的能力.表1 列出了所有算法31 次獨(dú)立運(yùn)行的IGDX 的平均值和方差.另外,本文使用Wilcoxon 秩和檢驗(yàn)來(lái)比較ILC-MMEA 與每個(gè)對(duì)比算法的性能差異,其中顯著性水平p設(shè)置為0.05.在表1 的最后一列中,符號(hào) “+”和 “–” 表示當(dāng)前算法與ILC-MMEA 相比,能獲得更好和更差的性能的測(cè)試問題數(shù)量.此外,符號(hào) “=” 表示該對(duì)比算法與ILC-MMEA 之間沒有顯著差異的測(cè)試問題數(shù)量.

從表1 中可以觀察到,ILC-MMEA 在所選測(cè)試問題上表現(xiàn)出比其他代表性算法更好的性能.具體來(lái)說,12 個(gè)測(cè)試問題中,ILC-MMEA 在8 個(gè)問題上表現(xiàn)出了最佳性能.此外,MMOEA/DC、MMEA-WI和CPDEA 分別在2 個(gè)、1 個(gè)和1 個(gè)測(cè)試問題上獲得了最好的IGDX 值.從表1 中可以看出,ILC-MMEA、MMOEA/DC、MMEA-WI和CPDEA 相較于其他對(duì)比算法性能更強(qiáng),其在IGDX指標(biāo)值上有跨越量級(jí)的領(lǐng)先.這是因?yàn)?CPDEA和MMEA-WI 是專門為了解決IDMP 問題提出的,考慮了搜索不同PS 時(shí)的不平衡性問題;ILC-MMEA和MMOEA/DC 則是考慮到了決策空間中存在局部PS 的情況,因此在求解PS 不平衡問題時(shí)依然能夠獲得問題的全部PS.但是,隨著目標(biāo)個(gè)數(shù)的提升,只有ILC-MMEA和MMOEA/DC 能夠獲得較好的結(jié)果,其他算法均不能夠獲得問題的全部PS.雖然DN-NSGAII和Omni-optimizer 是為多模態(tài)多目標(biāo)優(yōu)化設(shè)計(jì)的,但似乎它們?cè)谒x基準(zhǔn)問題上表現(xiàn)不佳.IDMP 測(cè)試問題在搜索不同PS 時(shí)存在不平衡,因此一般的MMEAs 很難獲得所有PS.DN-NSGAII和Omni-optimizer 是MMOPs 早期研究中的兩個(gè)代表性算法,其思想啟發(fā)了眾多針對(duì)MMOPs 的算法和相關(guān)工作,但是在IDMP 測(cè)試問題上表現(xiàn)較差.

表1 不同算法在IDMP 測(cè)試問題上31 次獨(dú)立運(yùn)行的IGDX 平均值和方差Table 1 Mean and variance of 31 independent runs of IGDX for different algorithms on IDMP test problems

圖6 展示了所有算法在IDMPM3T4 問題上獲得的PS和PF (挑選出每個(gè)算法最接近平均IGDX值的運(yùn)行結(jié)果進(jìn)行展示).從圖中可以看出,ILC-MMEA和MMOEA/DC 能夠獲得所有的PS,而DNEA-L、CPDEA、MMEA-WI和MO_Ring_PSO_SCD 只能獲得其中的部分PS;DN-NSGAII和Omni-optimizer 只能獲得其中一個(gè)PS.另外,圖7展示了所有算法在具有4 個(gè)決策變量的IDMPM4T3問題上獲得的PS.可以看到,僅有考慮了局部PS的DNEA-L、ILC-MMEA和MMOEA/DC 能夠獲得全部的PS,并且ILC-MMEA和MMOEA/DC獲得的解集分布均勻性明顯更好.此外,可以明顯地看到,ILC-MMEA和MMOEA/DC 最終獲得的解集中包含了非支配解.這是因?yàn)檫@兩個(gè)算法都考慮了獲得問題的局部PS,因此還有少量的個(gè)體繼續(xù)在決策空間進(jìn)行探索.

圖6 不同算法在IDMPM3T4 問題上獲得的PS和PFFig.6 PS and PF obtained by different algorithms on IDMPM3T4 problem

圖7 不同算法在IDMPM4T3 問題上獲得的PS (藍(lán)色實(shí)線)和真實(shí)PS (紅色虛線)Fig.7 True PS (red dotted lines) and obtained PS (blue solid lines) by different algorithms on IDMPM4T3 problem

總體來(lái)說,在IDMP 測(cè)試問題上,ILC-MMEA、MMOEA/DC、MMEA-WI和CPDEA 表現(xiàn)良好,而隨著目標(biāo)個(gè)數(shù)和決策數(shù)量的增加,ILC-MMEA和MMOEA/DC 的性能優(yōu)勢(shì)更加凸顯,且ILC-MMEA性能更佳.

3.3 考慮局部最優(yōu)算法性能對(duì)比

本節(jié)展示了ILC-MMEA和對(duì)比算法在具有局部PS 的MMOPs 上的性能.具體來(lái)說,實(shí)驗(yàn)挑選了IEEE CEC 2019 MMOP 中的部分測(cè)試問題,包括MMF10、MMF11、MMF12、MMF13和MMF15.為了降低隨機(jī)性帶來(lái)的影響,所有實(shí)驗(yàn)均獨(dú)立執(zhí)行31 次.與上一節(jié)相同,使用Wilcoxon 秩和檢驗(yàn)來(lái)表示不同算法相比于ILC-MMEA 的性能好壞.

表2 列出了所有對(duì)比算法在測(cè)試問題上獲得的IGDX 的平均值和方差.從表中可以看出,在全部5 個(gè)測(cè)試問題中,ILC-MMEA 在4 個(gè)測(cè)試問題上表現(xiàn)出最好的性能,MMOEA/DC 在1 個(gè)測(cè)試問題上表現(xiàn)最好.DNEA-L、MMOEA/DC和ILC-MMEA 相比于其他算法表現(xiàn)更加出色 (IGDX 值更小).這是因?yàn)?這三個(gè)算法均采取了一定的策略對(duì)局部PS 進(jìn)行搜索并保留.對(duì)于本節(jié)選擇的測(cè)試問題,這三個(gè)算法都能找到并保留局部PS,因此其性能表現(xiàn)優(yōu)異.

表2 不同算法在具有局部PS 測(cè)試問題上31 次獨(dú)立運(yùn)行的IGDX 平均值和方差Table 2 Mean and variance of 31 independent runs of IGDX for different algorithms on MMOPs with local PS

圖8 直觀地展示了所有算法在具有局部PS 問題上的表現(xiàn).可以看到,MMOEA/DC和ILC-MMEA能夠找到問題的全局和局部PS.DNEA-L 在MMF11問題上能夠找到全局和局部PS,但是在MMF12上只能獲得部分PS,且解集分布的均勻性較差.對(duì)于早期提出的MMEAs 而言,由于算法沒有考慮局部PS 的搜索,因此無(wú)法對(duì)局部PS 進(jìn)行保留.ILC-MMEA 獲得的PF 分布性更加均勻.這是因?yàn)?ILC-MMEA 引入了全新的種群擁擠度計(jì)算方式,能夠更好地平衡目標(biāo)空間和決策空間分布的均勻性.在MMF12 問題上,MMOEA/DC 獲得的PF相比于ILC-MMEA 更加均勻,而PS 情況則相反.由于篇幅限制,算法在其他問題上的PF和PS 沒有全部畫出,感興趣的讀者可以在論文代碼開源地址獲得所有數(shù)據(jù)結(jié)果.總體來(lái)說,ILC-MMEA和MMOEA/DC 均能夠獲取問題的全局和局部PS,DNEA-L 能夠獲取問題的部分局部PS,且ILC-MMEA 獲得的解集分布性更好.

圖8 不同算法在MMF11 問題 (前兩行)和MMF12 問題 (后兩行) 上獲得的PS和PFFig.8 PS and PF obtained by different algorithms on MMF11 (first two rows) and MMF12 (last two rows) problems

3.4 算法運(yùn)行時(shí)間對(duì)比

前文在理論上給出了ILC-MMEA 算法的計(jì)算時(shí)間復(fù)雜度,為了更加直觀地展示不同MMEAs 算法的計(jì)算耗時(shí),本節(jié)將使用實(shí)驗(yàn)的方法對(duì)時(shí)間復(fù)雜度進(jìn)行分析.具體來(lái)說,將使用Multi-polygon 作為基準(zhǔn)測(cè)試問題.該測(cè)試問題可以方便地?cái)U(kuò)展到高維,因此,設(shè)置目標(biāo)函數(shù)個(gè)數(shù)M分別為3、4、8、10,D=4 ,并統(tǒng)一使用N=200 ,NF E=20 000 進(jìn)行31 次獨(dú)立實(shí)驗(yàn),取結(jié)果的平均值進(jìn)行比較.

圖9 展示了不同算法在目標(biāo)個(gè)數(shù)不同的測(cè)試問題上的計(jì)算時(shí)間.可以看到,MMOEA/DC、MMEAWI和ILC-MMEA 的計(jì)算復(fù)雜度隨著目標(biāo)個(gè)數(shù)的提升并沒有明顯的增大.對(duì)于DN-NSGAII和Omni-optimizer 來(lái)說,求解目標(biāo)個(gè)數(shù)為4 時(shí)的優(yōu)化問題所用時(shí)間甚至小于目標(biāo)個(gè)數(shù)為3 時(shí)的求解時(shí)間.進(jìn)一步分析可以知道,這兩個(gè)算法的計(jì)算復(fù)雜度與當(dāng)前種群中非支配解占比息息相關(guān).當(dāng)目標(biāo)個(gè)數(shù)增大時(shí),算法運(yùn)行前期種群中非支配解的占比較低,這導(dǎo)致了計(jì)算時(shí)間的下降.另外,CPDEA、DNEA-L和MO_Ring_PSO_SCD 的計(jì)算時(shí)間隨著目標(biāo)個(gè)數(shù)的增大有微小增加.總體來(lái)說,ILC-MMEA 的計(jì)算時(shí)間在所有對(duì)比算法中處于中間位置,具備較好的計(jì)算效率.

圖9 不同算法在不同目標(biāo)個(gè)數(shù)測(cè)試問題上的計(jì)算時(shí)間Fig.9 Computational time of different algorithms on test problems with different number of objectives

4 結(jié)論

獲得MMOPs 的全部PS 對(duì)于決策者具有重要意義.然而,由于目標(biāo)空間多樣性與決策空間多樣性存在一定的沖突,因此,獲得全部PS 仍然是進(jìn)化計(jì)算領(lǐng)域面臨的一個(gè)巨大挑戰(zhàn).此外,搜索并保留決策者能接受的局部最優(yōu)PS 可以認(rèn)為是保留全部全局PS 的更普遍情況.這是因?yàn)?擁有多個(gè)全局最優(yōu)PS 的問題是具有局部最優(yōu)PS 的一個(gè)特例.研究具備搜索局部PS 能力的算法可以更好地解決MMOPs.在本文中,提出了局部收斂性指標(biāo)和基于雙空間的擁擠距離,并通過實(shí)驗(yàn)驗(yàn)證了所提方法的有效性,說明關(guān)注問題的局部PS 可以更好地解決MMOPs.

目前,針對(duì)MMOPs 的研究大多聚焦在連續(xù)型優(yōu)化上[5,9],且問題的決策空間較小 (決策變量個(gè)數(shù)較少),已有算法重點(diǎn)考慮了解集的分布性而沒有重視算法的搜索能力.然而實(shí)際問題的決策變量可能是多類型或大規(guī)模的.近期,CEC 會(huì)議舉辦了針對(duì)路徑規(guī)劃的多模態(tài)多目標(biāo)競(jìng)賽[40-41],公開了一系列測(cè)試集,研究了多模態(tài)多目標(biāo)優(yōu)化算法在離散型問題上的性能,取得了較多的關(guān)注.另一方面,針對(duì)多模態(tài)多目標(biāo)優(yōu)化算法的實(shí)際應(yīng)用還比較少.這是因?yàn)?決策者難以確定待優(yōu)化問題是否屬于多模態(tài)優(yōu)化問題;并且,已有的MMEAs 在實(shí)際問題上的效果還有待檢驗(yàn).因此決策者更傾向于選擇傳統(tǒng)的MOEAs 對(duì)問題進(jìn)行求解,這對(duì)理解問題的決策空間屬性造成了一定的障礙.因此,如何快速表征某個(gè)問題是否為多模態(tài)多目標(biāo)優(yōu)化問題是推廣此類算法的關(guān)鍵.另外,未來(lái)的研究方向?qū)⒕劢褂谔嵘嗄B(tài)多目標(biāo)優(yōu)化算法在大規(guī)模決策變量問題上的性能以及推動(dòng)多模態(tài)多目標(biāo)優(yōu)化算法的實(shí)際應(yīng)用.