一種改進的高維多目標調(diào)和進化算法

易高明,張永闖, 施武祖，趙 彬

(1.桂林航天工業(yè)學院 a.理學院;b.管理學院， 廣西 桂林 541000;2.蘭州工業(yè)學院 計算機與人工智能學院，甘肅 蘭州 730050；3.天津師范大學 計算機與信息工程學院，天津 300380)

多目標進化方法可以有效求解2-3個目標的低維多目標優(yōu)化問題(MOPs)[1]，當目標的維數(shù)(個數(shù))超過3的時候，多目標優(yōu)化問題轉(zhuǎn)化為它的特殊形式，即高維多目標優(yōu)化問題(LMOPs)[2]。LMOPs的定義雖然只是形式上增加了目標的個數(shù)，但是其計算的難度要遠高于3個目標及以下的低維多目標優(yōu)化問題，主要體現(xiàn)在目標優(yōu)化問題的搜索空間急劇擴大和嚴格的Pareto占優(yōu)機制下的精英選擇策略失效[3]，從而導致難以對進化個體施加足夠強的選擇壓力。收斂性不足且解集的分布性難以維護，進化種群中的Pareto非劣進化個體所占比例急劇上升，造成進化搜索的盲目和停滯不前[4]。

為了解決高維多目標優(yōu)化的問題，國內(nèi)外專家提出了以進化融合為標志的第三代高維多目標進化方法，如r支配[5]、模糊支配[6]、融入決策者偏好的支配[7]、K支配[8]和ε支配[9]等，以及降維法來提高進化個體的精英選擇策略[10]，以上方法在求解高維多目標問題上仍然存在一定的不足，如降維法可能導致目標關(guān)鍵信息的丟失，從而不能達到真實的前沿面。

基于以上分析，本文將決策理論中的調(diào)和模型應用到多目標遺傳算法中，替換Pareto占優(yōu)關(guān)系，利用ELECTRE-I來產(chǎn)生進化個體的優(yōu)劣偏好排序集并輔以雙極偏好占優(yōu)的策略，將該方法嵌入NSGA-II中，并用來求解典型高維多目標問題，與四個優(yōu)秀的高維多目標進化方法做比對實驗，實驗仿真結(jié)果表明本文方法的有效性。

1 問題描述

高維多目標優(yōu)化問題一般蘊含n個決策變量，不低于3個目標以及若干約束組成，其中x表示決策向量，y表示目標向量，X表示決策空間集合，Y表示目標空間集合。高維多目標問題數(shù)學模型表達式如下[11]，即

miny=F(x)=(f1(x),f2(x),...,fk(x))T,

s.te(x)=(e1(x),e2(x),...,em(x))≥0,

x=(x1,x2,...,xn)∈X,

y=(y1,y2,...,yk)∈Y.

(1)

定義1:(Pareto支配)xu=(u1,u2,…,un)，Pareto支配xv=(v1,v2,…,vn)：xu?xv，當且僅當?i=1,2,…,k，fi(xv)≥fi(xu)且?j=1,2,…,k，有fj(xv)>fj(xu)。

定義2:(Pareto最優(yōu)解集)，若P*∈{x∈X|┐?x*∈X,x*?x}，則P*即為Pareto最優(yōu)解集。

定義3:(Pareto前沿)Pareto最優(yōu)解對應的所有目標函數(shù)值的全體集合即為Pareto前沿，記為PF*={F(x)|x∈P*}。

2 調(diào)和模型

ELECTRE(Elimination et Choice Translating Reality，淘汰選擇法)是多屬性決策理論中的一種經(jīng)典方法[12]，自法國人Roy在20世紀60年代提出以來，在決策科學領(lǐng)域得到成功使用。在之后的幾十年，隨著后繼的研究者們將ELECTRE法不斷地發(fā)展和改進，形成了處理不同功能的ELECTRE家族系列。ELECTRE法雖然在多屬性決策領(lǐng)域取得了廣泛的應用，但是很少將該方法應用在高維多目標進化優(yōu)化中。

2.1 ELECTRE-I法

基本思想是決策者采用某種預先設(shè)定的偏好排序策略對決策方案集中的各個方案進行級別關(guān)系的排序和比較檢驗[13]，不斷刪除級別低的或者處于劣勢的方案，讓決策人從剩下的優(yōu)勢方案中挑選出級別高的優(yōu)勢方案，本質(zhì)上是決策人在1組非劣解集中的偏好排序過程，而且這種排序策略是一種比Pareto策略更松弛的高級別關(guān)系排序方法。在實際的高維多目標進化算法操作中，每個遺傳個體的分目標個數(shù)都超過了3(3個以上的屬性值)，傳統(tǒng)的基于Pareto選擇優(yōu)勢個體的策略難以進行比較操作，針對高維多目標優(yōu)化問題中的各個子目標都難以服從絕對優(yōu)于關(guān)系的情況，現(xiàn)介紹一種經(jīng)典的多屬性決策模型方法ELECTRE-I法，主要分為級別高于關(guān)系的構(gòu)造和優(yōu)勢方案集的挖掘[14]。

2.1.1 級別高于關(guān)系的構(gòu)造

首先設(shè)立決策矩陣P=(fj(ai))m×n，對方案集中的任意一對方案ai,ak，不作規(guī)范化操作。為了檢驗方案間的級別高于關(guān)系的存在性，需要作和諧性以及非不和諧性兩種檢驗，詳細步驟如下：

步驟1：決策人為方案的所有屬性分配權(quán)重w,w=(w1,w2,…wn)。

步驟2：屬性序號分類。

為了便于統(tǒng)一說明，這里假定每個屬性fj，j=1,…,n,屬性取值越大則越優(yōu)。

對于某個屬性j有ai絕對優(yōu)于ak，并記為ai?jak；令ai?jak所對應的屬性j的集合表示為J+(ai,ak)，數(shù)學集合為：

J+(ai,ak)={j|1≤j≤n,fj(ai)>fj(ak)}

(2)

與之相似，同樣可以定義符合ai～jak對應的屬性集合J=(ai,ak)以及aijak對應的屬性集合,有

J=(ai,ak)={j|1≤j≤n,fj(ai)=fj(ak)}，

(3)

J-(ai,ak)={j|1≤j≤n,fj(ai)

(4)

計算和諧性指數(shù),

(5)

式中：Iik表示方案ai不劣于方案ak所對應的屬性的權(quán)重和。

(6)

(7)

步驟4：非不和諧性檢驗。定義不和諧性指數(shù)

(8)

通過非不和諧性檢驗當且僅當βik≤β0，其中β0是最大不和諧值，一般情況下應由決策者給出，在這里約定最大不和諧性指數(shù)取不和諧性指數(shù)的均值。

(9)

2.1.2 優(yōu)勢方案集的挖掘

在給出所有方案間的級別高于關(guān)系后，下一步的關(guān)鍵就是利用第一步的級別高于關(guān)系信息的優(yōu)勢，對方案集的優(yōu)勢集進行挖掘以獲得一組符合決策者偏好的調(diào)和解集。具體的思路是在已經(jīng)構(gòu)建的每對方案的級別高于關(guān)系的基礎(chǔ)上，建立指向圖來完成。篩選的步驟如下：

步驟1：若某個方案(指向圖上的節(jié)點)位于有向弧的箭線終點，且該有向弧又不是某個閉環(huán)回路的一環(huán)，那么該節(jié)點即為相對應整個目標集中的至少一個，是級別高于關(guān)系里劣的一方，也是首先刪除的對象方案。

步驟2：指向圖中若是存在閉合回路，則該回路中的全部節(jié)點方案都應該是無差異的。

步驟3：在以上基礎(chǔ)上，刪除掉箭線所指的方案和所有閉合回路上的最少一個方案，于是剩下的沒有被刪除的子方案集則為最小優(yōu)勢子集，記為A1，使得

?ai∈AA1,?ak∈A1akSai.

(10)

若A1集合中不存在級別高于關(guān)系，即在有向圖中節(jié)點之間沒有箭線連接，那么該最小優(yōu)勢子集又稱作方案集A的核，記為A0，且有A0?A1。在得到最小優(yōu)勢子集或者核后，如果它已經(jīng)足夠小，能讓決策者可以簡易的從中挑選出自己滿意的解方案，則ELECTRE-I法完成，否則，決策者可以根據(jù)偏好需要，動態(tài)調(diào)整最低和諧值a和最大不和諧值β0來重新構(gòu)造一個更強的級別高于關(guān)系，進一步壓縮最小優(yōu)勢集中的方案個數(shù)，供決策者決策時使用。

2.2 TOPSIS法

TOPSIS是一種不斷收斂到理想解的排序法，該方法借用決策理論中的絕對理想解和絕對最差解的概念來對目標進行排序操作。其中絕對理想解的目標向量的各個子屬性目標值是該屬性目標中的最好值，也就是說，絕對理想解是所有子目標的最優(yōu)值綜合得到的。而絕對最差解的每個子目標都是來源于最劣的子目標值。TOPSIS的基本思想是建立在上述兩個虛擬解、理想解和最差解定義的歐式距離關(guān)系上，一般認為最好的方案都有這樣一個特征：逼近絕對理想解的同時遠離絕對最差解。因此依據(jù)這樣的思想，來給出方案的優(yōu)劣排序，TOPSIS評價指數(shù)量化了該方案的優(yōu)劣性，又稱作排隊值，排隊值越大，方案越優(yōu)。綜合評價指數(shù)如式(11),即

(11)

(12)

TOPSIS法的個體排序規(guī)則如圖1所示，圖中的理想解即為絕對理想解，厭惡解就是絕對最差解，圖中最優(yōu)前沿面的最優(yōu)點一定符合這樣的一個特征：靠近理想解的同時遠離厭惡解，此時最優(yōu)點的綜合評價指數(shù)也就相對較大。

圖1 TOPSIS法對進化個體的排序

3 進化個體的適應值評價

本文設(shè)計一種全新的基于ELECTRE-I法的高維多目標調(diào)和進化算法的進化個體優(yōu)劣排序規(guī)則，規(guī)則分為3層：第1層為Pareto非劣分層操作，第2層為級別高于關(guān)系的優(yōu)勢子集生成操作，第3層為雙極偏好占優(yōu)的排序操作和擁擠距離機制的優(yōu)勢子集內(nèi)進化個體排序操作。在高維問題上定義一種全新的錦標賽選擇算子ELET-Dominznce。

定義4:(ELET-Dominance)決策目標空間中任意的2個決策向量X，Y，有X個體 ELET-Dominance支配個體Y，當且僅當滿足如下條件之一：①X支配Y;②X，Y互不支配且都屬于優(yōu)勢子集Q，Xd>Yd;③X，Y互不支配且X屬于優(yōu)勢子集，Y不屬于優(yōu)勢子集;④X，Y互不支配且都不屬于優(yōu)勢子集Q，CX>CY。其中Q是ELECTRE-I生成的優(yōu)勢子集，Xd,Yd是決策向量X,Y的擁擠度，CX,CY是決策向量X,Y綜合評價指數(shù)。

該錦標賽選擇算子1遵循傳統(tǒng)的嚴格的帕累托支配策略。算子2、3和4給出了互不支配個體下的比較策略，當這兩個個體同屬一個優(yōu)勢子集下，則依據(jù)擁擠度來進一步判斷優(yōu)劣。相反，如果都不在優(yōu)勢子集中，則需要采用排隊值進行判別。

4 基于ELECTRE-I的高維多目標調(diào)和進化方法

采用一種新的調(diào)和模型和多目標群體的進化思想互相結(jié)合的方法，由于高維中出現(xiàn)進化群體的維數(shù)災難現(xiàn)象，提出一種全新的錦標賽選擇算子ELET-Dominance算子，本算子包含2個關(guān)鍵技術(shù)：ELECTRE-I生成調(diào)和集的策略與雙極偏好占優(yōu)的策略。其中ELECTRE-I法是寬松的排序技術(shù)，借助ELECTRE-I法，決策者可以發(fā)現(xiàn)若干個相對不那么差的個體集合，并且定義了這種錦標賽選擇算子下的各個進化個體的優(yōu)劣比較，最后實現(xiàn)所有進化個體的排序并且在NSGA-II方法框架下實施遺傳操作，最后逼近滿意解，具體步驟及流程如圖2所示。

5 實驗仿真及結(jié)果分析

為了驗證本文提出的基于ELECTRE-I的優(yōu)化方法，我們將該方法與4個目前比較流行的多目標進化優(yōu)化算法做比較，它們分別是NSGA-II、NSGA-III、α-NSGA-II和HV-NSGA-II。通過求解4個DTLZ的高維多目標測試集函數(shù)，來進行橫向與縱向的不同維度比較，計算機配置條件為Core i5，內(nèi)存4GB。初始群體試驗設(shè)置為100，設(shè)置迭代次數(shù)上限為250代。

圖2 本文算法流程

5.1 實驗參數(shù)及性能指標

本實驗中遺傳算子的交叉概率為0.9，變異概率為1/n。

5.2 仿真結(jié)果與分析

在進行DTLZ系列的高維測試集實驗分析前，先看基于ELECTRE-I的多目標調(diào)和進化算法在處理3目標DTLZ1和2目標ZDT3的實驗結(jié)果，如圖3、4所示。黑色實心為最終進化個體解。

圖3 DTLZ1仿真

從仿真結(jié)果可以看到，不管是2目標問題還是3目標測試問題，本文提出的方法都可以讓1組初始群體收斂到目標函數(shù)的真實Pareto前沿面，而且可以保持較好的分布性和延展度，該實驗可以驗證本文提出的方法在低維多目標上同樣具有很好的收斂性。

圖4 ZDT3仿真

由于高維多目標問題難以可視化，為了更直觀的表現(xiàn)出本算法較其它4類方法性能優(yōu)勢，圖5給出每種多目標進化方法在8目標DTLZ系列函數(shù)上的反世代距離IGD值的箱圖。從圖5的4組箱圖可以看出，本文方法和NSGA-III在8目標的DTLZ系列問題上都表現(xiàn)出了比其它3種方法更顯著的收斂和分布性能。此外，在DTLZ2系列問題上，NSGA-III的進化表現(xiàn)能力也比較突出，但是綜合幾個測試函數(shù)的最終結(jié)果來看，本文方法提出的算法較其他方法具有更強的穩(wěn)定性。

圖6給出了5類多目標進化方法處理8目標DTLZ測試問題的反世代距離值,從多目標進化代數(shù)的變化情況可以發(fā)現(xiàn)，無論在哪一個DTLZ系列的測試問題，本文提出的方法和NSGA-III法都隨著進化迭代次數(shù)的增加，可以獲得較小的IGD值，即較好的進化解和表現(xiàn)出更好的收斂性能。本文方法在DTLZ1、DTLZ3和DTLZ7上表現(xiàn)出最好的收斂性能，而NSGA-III只在DTLZ2問題上表現(xiàn)出比本文方法稍微好點的性能。此外，α-NSGA-II在DTLZ1上也表現(xiàn)出一定程度上的收斂能力，但是在其他3個測試函數(shù)上，并沒有顯示出較好的收斂能力，在DTLZ7上甚至是表現(xiàn)最差的一種方法。HV-NSGA-II在DTLZ1和DTLZ3上的IGD進化能力表現(xiàn)最差，但是在DTLZ7問題上也顯現(xiàn)出一定的進化能力，在DTLZ2問題上，HV-NSGA-II和α-NSGA-II的IGD進化能力比較接近。整體而言，本文方法獲得反世代距離的能力是最穩(wěn)定的也是最好的。

(a) DTLZ1法

(b) DTLZ2法

(c) DTLZ3法

(d) DTLZ7法圖5 8目標的DTLZ測試函數(shù)IGD箱圖

(a) DTLZ1法

(b) DTLZ2法

(c) DTLZ3法

(d) DTLZ7法圖6 8目標的DTLZ測試函數(shù)IGD折線

6 結(jié)語

針對高維多目標優(yōu)化問題中Pareto支配失效的難題，本文提出了一種基于ELECTRE-I的多目標調(diào)和進化算法。通過引入多目標決策理論中的調(diào)和模型和ELECTRE-I法，重新定義進化個體中的優(yōu)劣排序規(guī)則，在非優(yōu)勢子集中采用TOPSIS法進行同一層非劣個體的比較。在以上工作的基礎(chǔ)上，提出一種新的錦標賽選擇算子，最后在高維多目標問題DTLZ上進行進化仿真實驗，并運用性能指標反世代距離評價進化解的質(zhì)量，結(jié)果表明本文算法可以求得一組收斂性良好且延展度較大的解集。