基于插值方法的EMO 多樣性保持策略

陳 瓊，葉理德

(中冶南方工程技術(shù)有限公司技術(shù)研究院，湖北 武漢430223)

演化算法種群的多樣性是指種群包含的個體不能過于單一，即種群中既要包含優(yōu)秀的個體又要包含較差但有潛力的個體，盡可能地保留最終有潛力成為非劣解但因為選擇機制而過早被淘汰的個體的基因，使它們有參與競爭演化的機會。多樣性保持策略既要保證演化多目標優(yōu)化算法［1－4］得到的非劣解集具有較好的分布性，也要兼顧算法的效率，使得算法具有較快的收斂速度。

在演化前期或某一代演化迭代結(jié)束后，由于非劣解數(shù)目缺乏，會出現(xiàn)導致算法搜索到的近似Pareto 前沿間斷或不完整的現(xiàn)象。針對該現(xiàn)象，提出了基于插值方法的演化多目標優(yōu)化多樣性保持策略，其主要思想是在算法沒有搜索到的新區(qū)域，進行內(nèi)插或外推，引導算法在新區(qū)域進行搜索，期望算法搜索到更多更優(yōu)質(zhì)量的非劣解。

采用單一的性能評價方法對演化多目標優(yōu)化算法的性能進行度量會產(chǎn)生偏差，而僅僅采用近似Pareto 前沿與Pareto 前沿的逼近程度或非劣解集的多樣性，都不能全面地評價解的好壞［5］。因此，可采用收斂性，即轉(zhuǎn)化的代間距離［6］(inverted generational distance，IGD)和多樣性［7］(多樣性熵)兩個指標綜合評價算法的性能。

1 插值方法

插值方法是根據(jù)算法搜索到的非劣解信息插入新解的過程。按照插入新解的位置，插值方法分為內(nèi)插法和外推法，其中，內(nèi)插法包含均值插值法和凸組合插值法。

均值插值的特點是對于任何一種曲線進行無限等分，兩點之間的曲線可以用兩點之間的直線近似代替。因此，在無限等分的情況下在兩點之間的連線中點插入一個新個體就等同于在兩點之間的曲線段上插入一個新個體。插入的新個體為算法在已知的兩個非劣個體之間的區(qū)域上進行搜索提供了更多的機會，并為算法可能搜索到更多的非劣解創(chuàng)造了條件。

凸組合插值方法［8］是根據(jù)算法搜索到非劣解的信息，在兩個非劣解之間的區(qū)域內(nèi)進行搜索，引導算法開辟更多的搜索區(qū)域。

對Pareto 前沿曲線進行無限劃分時，任意兩個個體之間的曲線段可以視為一條直線段，但是，在插值過程中，若兩個已知個體之間的距離過大，雖然可以利用均值插值在兩個已知個體之間插入新個體，引導算法在其區(qū)域上搜索，但是當兩個已知個體之間的距離過大時，兩點之間的直線段和兩點之間的曲線段不一致，使插入的新個體遠離近似Pareto 前沿，可能導致算法的無效搜索。為了使插入的新個體盡量位于相應(yīng)近似Pareto 前沿附近，借助于凸組合插值方法來進行插入新個體，以保持種群的多樣性。

根據(jù)算法搜索到的一部分非劣解集信息，在其非劣解分布區(qū)域外插入新個體，為算法在非劣解外部的新區(qū)域內(nèi)進行搜索提供了機會，引導算法搜索到更多的非劣解。

2 基于插值方法的演化多目標策略

插值策略主要是根據(jù)已知的非劣解，在其附近的區(qū)域插入新個體，使算法搜索到更多的非劣解，而在算法搜索到的近似Pareto 前沿非劣解集中，根據(jù)個體之間鄰近距離的大小進行判斷，無疑對算法進行插入新個體具有重要的指導意義。由概率論可知，以個體之間的鄰近距離作為一個變量是服從高斯概率分布的，而插入新個體的情況，即兩個非劣解之間或一些非劣解的外部區(qū)域內(nèi)是否插入新個體，可以依據(jù)其累積分布函數(shù)表示，度量是否插入新個體。

有多種插值方法可以對算法搜索到的近似Pareto 前沿非劣解集插入新個體，如內(nèi)插、外推、內(nèi)插外推相結(jié)合等方法。另外，如果非劣解集的多樣性較好，則不需要插入新個體。在任意兩個非劣解之間或外部區(qū)域插入新個體之前，應(yīng)該考量插入新個體的依據(jù)，判斷是否要插入新個體。通過人為方式控制算法內(nèi)插、外推或內(nèi)插外推相結(jié)合插入新個體是非常困難的，也就是說，算法應(yīng)該能夠根據(jù)不同的情況采用相應(yīng)的插值策略。因此，提出了自適應(yīng)控制策略，對每次演化得到的近似Pareto 前沿上的非劣解集是否需要插入新個體進行評估，若需要插值，則進一步確定采取何種插值方法，如內(nèi)插、外推和內(nèi)插外推相結(jié)合。

圖1 所示為自適應(yīng)控制策略結(jié)構(gòu)圖，在某一演化迭代過程中，算法對當前搜索到的非劣解集進行評估，判斷其是否需要進行插值，如需要插值，則需要判斷當前迭代過程中所搜索到的非劣解集，需要進行的是內(nèi)插、外推還是內(nèi)插外推相結(jié)合，否則，不插入任何新個體，結(jié)束此次操作。插值策略不僅可以增強算法的多樣性，保持找到的非劣解集盡可能均勻、離散地分布在近似Pareto前沿上，而且也可以加速算法的收斂速度。由于IGD 指標既可以度量算法搜索到的非劣解集的多樣性，也可以度量算法的收斂性。因此可以用IGD 作為判斷是否插入新個體的依據(jù)。

圖1 自適應(yīng)控制策略結(jié)構(gòu)圖

輸入相關(guān)參數(shù)(種群P);輸出種群P。

(1)從種群P 中，獲取算法搜索到的非劣解集NDSet，并置dur=0 和IGD1=0;

(2)計算出非劣解集NDSet 的IGD 值;

(3)若|IGD1－IGD| ＜0. 01 或IGD1=0，則IGD1=IGD 且dur=dur+1，否則dur=0;

(4)若dur ＞Dur(Dur 為插值策略的間隔閾值)，則跳轉(zhuǎn)至步驟(9)，否則繼續(xù)下一步;

(5)對種群P 進行內(nèi)插方法，生成新種群P1，并計算IGD 值得IGD1;

(6)對種群P 進行外推方法，生成新種群P2，并計算IGD 值得IGD2;

(7)對種群P 進行內(nèi)插外推方法，生成新種群P3，并計算IGD 值得IGD3;

(8)在IGD1、IGD2和IGD3中，選擇最小的IGD 值，并利用對應(yīng)的種群替換種群P;

(9)輸出種群P。

3 數(shù)值分析

基于層次聚類的演化多目標算法(hierarchical clustering model evolutionary multi－objective optimization algorithm，HCMEMO)［9－10］，采用插值策略后，稱之為I－HCMEMO 算法。為了驗證算法的有效性，在標準測試函數(shù)ZDT1 ～ZDT6 上做了實驗，由于篇幅的限制，只列舉了連續(xù)和非連續(xù)的ZDT1 和ZDT3 測試函數(shù)對NSGAII(dominated sorting genetic algorithm II)、HCMEMO 和I－HCMEMO 算法進行的測試結(jié)果，并通過多樣性熵和IGD 指標對測試結(jié)果進行說明。

(1)ZDT1 問題求解。NSGAII、HCMEMO 和I－HCMEMO 算法對問題ZDT1 求解時的Pareto 前沿如圖2 所示。由圖2 可以看出I－HCMEMO 算法求解的近似Pareto 前沿完全覆蓋了NSGAII 算法和HCMEMO 算法，因此，I－HCMEMO 算法的結(jié)果優(yōu)于NSGAII 算法和HCMEMO 算法的結(jié)果。

圖2 ZDT1 的Pareto 前沿

NSGAII、HCMEMO 和I－HCMEMO 算法對問題ZDT1 求解時算法的多樣性熵如表1 所示，可以看出:在演化的前期，種群的多樣性相差不大，隨著演化過程的進行，I－HCMEMO 算法求解的近似Pareto 前沿的多樣性熵在40 代左右達到最大值，并趨于穩(wěn)定狀態(tài)，其效果明顯優(yōu)于NSGAII和HCMEMO 算法，但是I－HCMEMO 算法求解的近似Pareto 前沿多樣性的波動比較大，后期的演化過程中，多樣性的穩(wěn)定性要劣于HCMEMO 和NSGAII 算法。

NSGAII、HCMEMO 和I－HCMEMO 算法對問題ZDT1 求解時算法的收斂性指標轉(zhuǎn)化的代間距離IGD 如表2 所示，可以看出:I－HCMEMO 算法的IGD 指標值在演化的40 代左右開始趨于最小值，并呈現(xiàn)穩(wěn)定狀態(tài)，NSGAII 算法和HCMEMO 算法的IGD 指標趨于最小值，并呈現(xiàn)穩(wěn)定狀態(tài)，分別在60 代、100 代左右，但當NSGAII、HCMEMO 和I－HCMEMO 算法的IGD 指標都趨于穩(wěn)定狀態(tài)時，I－ HCMEMO算法的IGD指標要略高于NSGAII 算法和HCMEMO 算法的IGD 指標。因此，從整體上來看，在算法的收斂性上，I－HCMEMO 算法要略優(yōu)于NSGAII 算法和HCMEMO 算法。

(2)ZDT3 問題求解。NSGAII、HCMEMO 和I－HCMEMO 算法對問題ZDT3 求解時的Pareto 前沿如圖3 所示，由圖3 可以看出HCMEMO 算法求解的近似Pareto 前沿完全覆蓋了NSGAII 算法求解的近似Pareto 前沿，其結(jié)果要優(yōu)于NSGAII 算法，而I－HCMEMO 算法求解的近似Pareto 前沿要明顯低于HCMEMO 算法和NSGAII 算法，由標準測試函數(shù)ZDT3 的函數(shù)表達式可以看出，曲線越接近于原點結(jié)果越好。因此，I－HCMEMO 算法的求解結(jié)果要優(yōu)于HCMEMO 算法和NSGAII 算法。

NSGAII、HCMEMO 和I－HCMEMO 算法對問題ZDT3 求解時算法的多樣性熵如表1 所示，可以看出:隨著演化過程的進行，I－HCMEMO 算法求解的近似Pareto 前沿的多樣性熵處于較為劇烈的波動狀態(tài)，在第100 代左右逐漸開始趨于穩(wěn)定。當在20 代左右I－HCMEMO 算法的多樣性熵值，開始達到最大值，但在40 代到80 代左右，多樣性波動比較劇烈，并在180 代后，熵值又開始達到最大并高于算法在30 代左右出現(xiàn)的最大熵值，說明I－HCMEMO 算法與NSGAII 算法和HCMEMO 算法相比具有較好發(fā)現(xiàn)新解的能力。但從種群的多樣性上考慮，I－HCMEMO 算法劣于于NSGAII 算法和HCMEMO 算法。

NSGAII、HCMEMO和I－HCMEMO算法對問題ZDT3 求解時算法的收斂性指標轉(zhuǎn)化的代間距離IGD 如表2 所示，可以看出:I－HCMEMO 算法的IGD 指標值在演化的40 代左右開始趨于最小值，并呈現(xiàn)穩(wěn)定狀態(tài)，NSGAII 算法和HCMEMO 算法的IGD 指標趨于最小值，并呈現(xiàn)穩(wěn)定狀態(tài)，分別在40 代、80 代左右，但當NSGAII、HCMEMO 和IHCMEMO 算法的IGD 指標都趨于穩(wěn)定狀態(tài)時，NSGAII 算法的IGD 值要小于HCMEMO 算法的IGD值，HCMEMO 算法的IGD 值要小于I－HCMEMO算法的IGD 值。因此，在算法的收斂性上，NSGAII算法的收斂性要略優(yōu)于HCMEMO 算法，而HCMEMO 算法的收斂性要優(yōu)于I－HCMEMO 算法。

表1 NSGAII、HCMEMO 和I－HCMEMO 算法對ZDT1 和ZDT3 求解時算法的多樣性熵

表2 NSGAII、HCMEMO 和I－HCMEMO 算法對ZDT1 和ZDT3 求解時算法的代間距離IGD

圖3 ZDT3 的Pareto 前沿

4 結(jié)論

通過對插值方法的演化多目標優(yōu)化多樣性保持策略進行試驗測試，從得到的多樣性熵分析和IGD 指標分析的結(jié)果可以看出，基于插值策略的算法性能得到了明顯改進，并優(yōu)于NSGAII 算法和沒有使用插值策略的多樣性保持策略。

［1］ ZITZLER E，THIELE L，BADER J. SPAM:set pref erence algorithm for multi－objective optimization［C］∥Lecture Notes in Computer Science 5199.［S. l.］:［s.n.］，2008:847－858.

［2］ 崔遜學.多目標進化算法及其應(yīng)用［M］.北京:國防工業(yè)出版社，2006:86－87.

［3］ VAN VELDHUIZEN D A，LAMONT G B. Multi－objective evolutionary algorithms:analyzing the state－of－ the－art［J］. IEEE Transaction on Evolutionary Computation，2000，8(2):125－147.

［4］ ZITZLER E. Evolutionary algorithms for multi－objective optimization:methods and application［D］. Zurich:Swiss Federal Institute of Technology (ETH)，1999.

［5］ 徐建偉，黃輝先，彭維，等.多目標進化算法的分布度評價方法［J］.計算機工程，2008，34(20):208－209.

［6］ LI H，ZHANG Q. Multi－objective optimization problems with complicated pareto sets，MOEA/D and NSGA－II［J］. IEEE Transactions on Evolutionary Computation，2009，13(2):284－302.

［7］ FARHANG－MEHR A，AZARM S. Diversity assessment of pareto optimal solution sets:an entropy approach［C］∥Proceedings of Congress on Evolutionary Computation (CEC’2002). Piscataway:IEEE Service Center，2002:723－728.

［8］ GARC＇IA A J，VERDEJO V G，F(xiàn)IGUEIRASVIDAI A R. New algorithms for improved adaptive convex combination of LMS transversal filters［J］. IEEE Tram Signal Processing，2005，54(6):2239－2249.

［9］ 吳帆，李石君.一種高效的層次聚類分析算法［J］.計算機工程，2004，30(9):70－71.

［10］ HU J，GOODMAN E D. The hierarchical fair competition HFC model for parallel evolutionary algorithms［C］∥Proceedings of the 2002 Congress on Evolutionary Computation.［S.l.］:IEEE Press，2002:49－54.