陳 瓊，葉理德

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

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

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

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

1 插值方法

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

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

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

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

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

2 基于插值方法的演化多目標(biāo)策略

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

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

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

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

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

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

(2)計(jì)算出非劣解集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)對(duì)種群P 進(jìn)行內(nèi)插方法，生成新種群P1，并計(jì)算IGD 值得IGD1;

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

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

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

(9)輸出種群P。

3 數(shù)值分析

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

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

圖2 ZDT1 的Pareto 前沿

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

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

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

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

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

表1 NSGAII、HCMEMO 和I－HCMEMO 算法對(duì)ZDT1 和ZDT3 求解時(shí)算法的多樣性熵

表2 NSGAII、HCMEMO 和I－HCMEMO 算法對(duì)ZDT1 和ZDT3 求解時(shí)算法的代間距離IGD

圖3 ZDT3 的Pareto 前沿

4 結(jié)論

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

［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］ 崔遜學(xué).多目標(biāo)進(jìn)化算法及其應(yīng)用［M］.北京:國(guó)防工業(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］ 徐建偉，黃輝先，彭維，等.多目標(biāo)進(jìn)化算法的分布度評(píng)價(jià)方法［J］.計(jì)算機(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］ 吳帆，李石君.一種高效的層次聚類(lèi)分析算法［J］.計(jì)算機(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.