一種快速構造多目標Ｐａｒｅｔｏ 非支配集的方法：選舉法則
2009-01-01 00:00:00楊平鄭金華李密青羅彪
計算機應用研究 2009年2期
(湘潭大學 信息工程學院， 湖南 湘潭 411105)
摘 要：基于Pareto的多目標優化問題是進化算法的一個重要研究方向，而如何構造Pareto非支配集則是提高算法效率的關鍵所在。通過對選舉現象的觀察，同時針對多目標個體之間的特性，提出了一種快速求解多目標Pareto非支配集的方法: 選舉法則(election principle，EP)，分析了其時間復雜度為O(rmN)，并對其進行了正確性證明。因為種群中實際的非支配個體數m比進化群體規模N小，所以與同類方法相比，EP有更高的效率，并通過了實驗驗證。
關鍵詞：多目標優化問題; 進化算法; 選舉現象; Pareto非支配集; 選舉法則
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)02048804
Fast method of constructing multiobjective Pareto nondominated set:election principle
YANG Ping，ZHENG Jinhua，LI Miqing，LUO Biao
(Institute of Information Engineering， Xiangtan University， Xiangtan Hunan 411105， China)
Abstract:The multiobjective optimization problem based on pareto is a important research direction of the evolutionary algorithm， and how to improve the efficiency of constructing the Pareto nondominated set is a key to the algorithm.This paper proposed a quick method of constructing multiobjective pareto nondominated set through observing the election phenomenon and understanding the mutual character of multiobjective individual， namely the election principle (EP)， analyzed that its computational complexity was O(rmN)，proved the EP works correctly. Because the number m of actual nondominated individual is smaller than the population size N，compared with familiar methods the EP has a high efficiency and proves it through experiment finally.
Key words:multiobjective optimization problem; evolutionary algorithm; election phenomenon; Pareto nondominated set; election principle(EP)
0 引言
在實際生活中，存在著很多多目標優化問題(MOP)，進化算法因具有解決高度復雜的非線性問題的能力，引起了專家學者們的極大興趣。基于Pareto的多目標優化是進化算法的一個重要研究方向。該方法最先由Goldberg提出[1]，其基本思想是利用基于Pareto的適應度分配策略，從當前進化群體中找出所有的非支配個體，在進化過程中通過構造當前進化群體的Pareto非支配集，使其逐漸逼近真實的Pareto前沿，但因其每一代的進化都需找出所有非支配個體，因此構造Pareto非支配集的效率則直接影響到整個進化算法的運行效率。目前構造Pareto非支配集的最典型方法主要有：鄭金華等人[2]的擂臺賽法則；Deb等人[3]提出的構造非支配集的方法，其時間復雜度為O(rN2)，其中r為目標數，N為群體規模；Jensen[4]提出的一種采用遞歸構造非支配集的方法，其時間復雜度為O(N log(r-1)N)，但是當目標數目r很大時，其復雜度呈指數增加。
本文提出的選舉法則(election principle，EP)是一種新的構造Pareto非支配集的方法，其思想來源于選舉現象。西方國家存在多個政黨，包括執政黨和在野黨。因此每當舉行換屆選舉時，多個政黨之間會發生激烈的競爭，一般情況下，只有兩個實力較強且最為接近的政黨之間產生激烈的爭奪，如美國的民主黨和共和黨，英國的工黨和保守黨，日本的自民黨和民主黨等。當競選時每個政黨都需要產生一位候選競選人，這個競選人要有足夠的實力，否則會就被競爭對手打敗，由對手替代自己充當新的候選人。可以將此思想用到多目標優化中個體之間的支配性分析上，抉擇產生最終的所有非支配個體。通過分析發現，EP的時間復雜度僅為O(rmN)，而0 1 相關概念 定義1 多目標優化問題(MOP)。一般一個MOP包括n個決策變量，r個目標函數，k個約束條件。給定一個決策變量x=(x1，x2，…，xn)。其中x∈X，滿足以下約束條件： gi(x)≤0；i=1，2，…，k(1) X={x1，x2，…，xn)|li≤xi≤ui}(2) l=(l1，l2，…，ln)(3) u=(u1，u2，…，un)(4) 其中：X為決策空間；l和u分別為上界和下界。假設有r個優化目標，且優化目標之間是相互沖突的，優化問題可表示為 min f-(x)=(f1(x)，f2(x)，…，fr(x))(5) 尋求x*=(x*1，x*2，…，x*n)，使f-(x*)在滿足以上約束條件的同時達到最優。 定義2 可行解。可行解是決策向量的集合，滿足 xf={x∈X|gi(x)≤0}(6) 定義3 Pareto最優解。給出min f-(x)，稱x*為Pareto最優解，若x∈xf，滿足下列條件 ∧i∈I(fi(x)=fi(x*)) (7) 或者至少存在一個j∈I，使 fj(x)＞fj(x*)(8) 其中I={1，2，…，r}，xf是可行解。 定義4 設p和q是兩個解個體，稱p支配q，則必須滿足 k，fk(p)≤fk(q)；k∈{1，2，…，r}(9) l，fl(p)＜fl(q)；l∈{1，2，…，r}(10) 記為pq，其中為支配關系。 定義5 不相關。若個體x與y之間不存在支配關系，則稱x與y不相關或者無關。 定義6 對于給定個體x∈Pop，Pop為所有個體的集合，若不存在y∈Pop，使yx，則稱x為集合Pop的非支配個體。Pop的所有非支配個體組成的集合，稱之為Pop的非支配集。 定義7 設Nds是Pop的非支配集，則NdsPop，x∈Pop，若x是Pop的非支配個體，必有x∈Nds，則稱Nds是Pop的最大非支配集。 定義8 任意兩個個體p和q，若它們不相關，則定義它們的簇cluster(p，q)={x|not(px)not(qx)，x，p，q∈Pop}，即集合Pop中不被p和q支配的所有個體集合。 定義9 若cluster(p，q)為個體p和q的簇，則稱p和q為簇長。 定理1 支配關系具有傳遞性。 證明 x，y，z∈Pop，若有xy，yz，即證xz。 因為xy，由定義4有fk(x)≤fk(y)(k=1，2，…，r)，且l，fl(x)＜fl(y)，l∈{1，2，…，r}；而yz，同樣由定義4有fk(y)≤fk(z)(k=1，2，…，r)，且l，fl(y)＜fl(z)，l∈{1，2，…，r}。綜合以上兩步，則有fk(x)≤fk(z)，(k=1，2，…，r)，且l，fl(x)＜fl(z)，l∈{1，2，…，r}，再由定義4得出x z，證畢。 2 用選舉法則構造多目標進化群體的Pareto非支配集復雜 采用選舉法則(EP)構造非支配的基本思路是：每一輪比較時先從構造集中選出兩個個體擔任候選競選個體，保證兩個候選競選個體互不相關；再依次從構造集中選取一個個體與兩個候選競選個體進行比較，敗者被淘汰出局，勝者成為新的候選競選個體，若競選個體發生替換，則還要再次比較這兩個候選競選個體，淘汰弱者，以保證它們互不相關，并繼續該輪比較；一輪比較后，兩個候選競選個體即為非支配個體。按照此方法進行下一輪比較，直至構造集為空。 2.1 用選舉法則構造非支配集的方法 設Pop為r個目標的進化群體，Cs為構造集，令Cs＝Pop，Nds為非支配集，初始時置為空。設Bs為一個緩沖集，用來存儲與當前競選個體不相關但不能確定最終相關性的個體。Xs和Ys分別為兩個競選據點，用來存儲競選個體，Xf和Yf分別用來表示當前Xs和Ys據點是否有競選個體。當且僅當據點Xs（或Ys）內有個體時，Xf（或Yf）置為真，否則為假。首先從構造集Cs中任取一個個體p作為競選個體，填充據點Xs，同時置Xf為真，置Bs為空，依次與Cs中所有其他個體q進行比較，如果p支配q，則將個體q從Cs中清除；如果q支配p，則用q代替p(即替換產生了新的競選個體)；如果p和q不相關，判斷Yf，當Yf為假時，則將q填充據點Ys；當Yf為真，則考慮Ys和q的相關性，不相關時，則Bs＝Bs∪{q}，并繼續進行剩余個體的比較。一輪比較后，將p和q并入非支配集Nds中，刪除Bs中被簇長q和p支配的個體，再將Bs并入Cs中，重復以上步驟。依此下去，直至Cs為空。構造非支配集的具體過程如算法1所示。 算法1 用選舉法則構造非支配集。 a)初始化：Nds＝，令Cs＝Pop。 b)從構造集Cs中任選一個個體p，令Xs＝p，Xf＝1，Yf＝0，Cs＝Cs-{p}，Bs＝。 c)判斷Cs是否為空，為空則轉i)；否則進行下一步操作。 d)依次從構造集Cs中取出一個個體q，Cs＝Cs-{q}，判斷Xs與q的支配關系，若Xsq或者有Yf＝1且Ysq，則轉c)；否則進行下一步操作。 e)如果q與Xs不相關，轉f)；否則令Xs＝q，若Yf＝1 qYs，則Yf＝0，轉c)。 f)判斷Yf，若Yf＝1，轉g)；否則Ys＝q，Yf＝1，轉c)。 g)判斷Ys與q的相關性，如果Ys與q無關，則令Bs＝Bs∪{q}，轉c)；否則進行下一步。 h)如果qYs，則令Ys＝q，轉c)。 i)如果Xf＝1，Nds＝Nds∪{Xs}。 j)如果Yf＝1，Nds＝Nds∪{Ys}。 k)令Cs＝Cs∪{w|w∈Bs not (Xsw)not (Ysw)}，即把集合Bs中所有不被最后勝出競選個體Xs和Ys所支配的個體并入集合Cs中。 l)判斷Cs是否為空，若Cs＝，則轉m)；否則轉b)。 m)保存集合Nds，即非支配集，結束。 以上是用選舉法則構造非支配集的基本步驟。第一步初始化非支配集和構造集，接下來進行每一輪的比較，找出兩個優秀的候選競選個體。因為在每一輪比較過程中，會發生候選競選個體被實力更強的個體打敗的現象，即出現了替換操作。而將要被替換的那個候選競選個體通過在前面的比較過程中積累了很多有用信息。此時，就需要記錄下替換操作發生時的有用信息，如與候選競選個體不相關的個體的集合。這是因為，在替換操作之前被保留下來的個體有可能是被最新的實力更強的候選競選個體所支配，對于其中一些個體只被當前這個最新候選競選個體所支配而不被此前的任何其他候選競選個體所支配的情況，這個最新的候選競選個體必須返回去找出相同的被它所支配的個體并清除之。否則，只被某個新的候選競選個體所支配的個體就會被保留下來，并被當成是非支配個體，所以要采取必要的措施排除這種情況的發生。 為此，在本算法中設置了一個緩沖集Bs，用它來存儲目前那些不相關個體，在每一輪的比較前，初始化Bs為空，在競選比較過程中Bs積累了所有到目前為止判定為不相關的個體信息，而在這一輪的最后再用最終的優秀候選競選個體對Bs中被它所支配的個體進行刪除。一般情況下，設在構造非支配集的某一輪的比較中，兩個競選據點Xs和Ys分別出現了m和n個新的候選競選個體，Xs據點的替換過程為XmXm-1X2X1，Ys據點的替換過程為YnYn-1Y2Y1。其中：X1表示據點Xs的第一個候選競選個體；Xi表示第i次出現的新的候選競選個體；Y1表示據點Ys的第一個候選競選個體；Yj表示據點Ys的第j個候選競選個體。Bsk表示據點Xs(或Ys)第k＋1次出現新候選競選個體Xk+1(或Yk+1)時，沒有被此前的舊候選競選個體Xk和Yh(假設此時Ys據點的個體為Yh)在比較時所清除的所有個體的集合。這樣一來，當第k＋1個新的候選競選個體出現時，Xk+1(或Yk+1)需要返回進行比較的個體的集合為Bsk。因為由定理1，即支配關系的傳遞性可知，任何被Xk＋1(或Yk+1)所支配的個體q∈Bsk，1≤k＜m(或1≤k＜n)，也必然被Xm或者Yn(即最終的競選個體)所支配。從而可知，當多次出現新舊競選個體的更替時，只需將最后的競選個體與其前被保留下來的所有個體進行比較，并清除被它支配的所有個體即可。 2.2 構造方法的時間復雜性分析 現對算法1進行時間復雜度分析，設進化群體集合Pop的大小為N，Pop中共有m個非支配個體，則算法總共需要執行了m/2輪比較操作，每一輪產生兩個非支配個體。產生第一輪非支配個體時最多需要做2×(N-2)次比較操作，假設清除了k1個Pop中的支配個體。其中k1≥0。產生第二輪非支配個體時最多要做2×(N-k1-4)次比較操作，設清除了k2個Pop中的支配個體。其中k2≥0。依此類推，產生第m/2輪非支配個體時做了2×(N-k1-k2-…-km/2-1-m)次比較操作，設清除了km/2個Pop的支配個體。其中km/2≥0。由于m個非支配個體全部產生后，所有的支配個體都已經被清除，(k1+k2+…+km/2)=N-m。由以上分析可知算法1在最壞情況下的時間復雜度為 T(EP)=2×(N-2)+2×(N-k1-4)+…+2×(N-k1-k2-…-km/2-1-m)=2×[(N-2)+(N-4)+…+(N-m)]-2×[k1+(k1+k2)+ …+ (k1+k2+…+km/2-1)]<(N-1)+(N-2) +…+(N-m)-[k1+(k1+k2)+ …+(k1+k2+…+km/2-1)]<(2N-m-1)m/2 即算法在最壞情況下的時間復雜度為O(r m N)。其中：r為MOP中目標的數目，m為實際的非支配的個體數目，N為進化種群大小。由于在一般情況下有m＜N，EP在0 3 選舉法則的正確性證明 下面討論用選舉法則(EP)構造Pareto非支配集的正確性，這里從兩個方面進行分析：a)證明算法1的合理性，即采用EP所構造的Nds就是Pop的非支配集；b)證明算法1的完備性，即算法1結束時的Nds就是進化群體Pop的最大非支配集。 定理2選舉法則構造非支配集(即算法1)是合理的。 證明 假設算法執行了n輪循環，令xi和yi表示第i輪產生的非支配個體，Pi表示第i輪的所有個體集合，Di表示該輪中被xi或者yi所支配的所有個體集合，Csi表示在個體集Pi中由簇長xi和yi所對應的簇cluster(xi，yi)，則n輪對應下列n個關系式： P1=x1+y1+Cs1+D1 P2=x2+y2+Cs2+D2 Pn=xn+yn+Csn+Dn (11) 其中：p1=Pop，pi=Csi-1；i=2，…，n，Csn=。 下面用歸納法進行證明： a)首先證明第一輪進入Nds的個體是Pop的非支配個體。 設第一輪進入Nds的個體為x1和y1，易知它們不相關，否則由構造方法可知會發生替換，從據點中被消除，不會進入非支配集。由構造方法可知，z∈Pop， 使zx1或者zy1，即x1和y1不被Pop中任一個體所支配，否則會發生替換或者從據點中被清除；同時由簇的定義8知：m∈Cs1， x1m，y1m，即x1和y1不支配Cs1中任一個體，故可知x1和y1與Cs1中個體不相關。又Di中全是被個體xi或者yi所支配的個體的集合，故x1和y1不被P1中任一個體所支配，亦即第一輪進入Nds的個體是Pop的非支配個體。 b)假設前面s(1≤s≤n-1)輪進入Nds中的個體是Pop的非支配個體，現證明第s＋1輪進入Nds的個體是Pop的非支配個體。 設xs+1和ys+1是第s+1輪產生的兩個個體，由構造方法可知，xs+1和ys+1不相關，否則發生替換，從據點中被清除，由簇的定義知，xs+1和ys+1與Css+1中任何一個個體無關，又Ds+1中為xs+1或ys+1所支配的個體集合，故知xs+1和ys+1不被Ps+1中任一個體所支配，是Ps+1中的非支配個體，而Ps+1=Css，由歸納假設可知是xs和ys是Pop中的非支配個體，而xs和ys與Css中任何一個個體無關且集合Ds中所有個體都被xs或ys所支配，故Css中非支配個體就是Pop中的非支配個體，即xs+1和ys+1是Pop中的非支配個體，也就是說第s+1輪進入Nds的個體也是Pop的非支配個體。 綜合a)和b)，采用EP所構造的Nds就是Pop的非支配集，即選舉法則構造非支配集是合理的，故得證！ 定理3 選舉法則構造的非支配集(即算法1)是完備的。 證明 即求證Nds是Pop的最大非支配集。根據最大非支配集的定義，這里采用反證法進行證明。 若x∈Nds，但不是Pop的非支配個體，則必y∈Nds，使yx。則由算法構造過程知，或者在y并入Nds之前，x被y從構造集Cs中清除，故不會被并入Nds中；或者在y并入Nds之后，x被簇長y從簇中清除并進入下一輪的比較，這種情況下x也不可能被并入Nds中，這與x∈Nds發生矛盾。反之，若x∈Pop-Nds，且是Pop的非支配個體，則y∈Pop，使yx，因此Pop中任一個體都不能將x清除，故x必定被并入Nds中，這與x∈Pop-Nds發生矛盾。由此可知，按算法1所構造的非支配集Nds是P的最大非支配集，即選舉法則構造的非支配集是完備的，故得證！ 4 實驗結果 這里做了兩部分實驗:a)基于標準測試函數，采用NSGAⅡ[3]測試進化過程中非支配個體在種群中所占的比例；b)在標準測試函數下，求解算法關鍵操作次數的比較實驗。實驗環境為：Intel(R) Celeron(R) CPU 2.40 GHz，256 MB的內存。 4.1 基于標準測試函數非支配個體比例的測試實驗 為統計多目標進化算法在求解標準測試函數問題時，進化過程中實際的非支配個體比例變化情況，本文選用NSGAⅡ求解DTLZ系列標準測試函數[5]，并記錄下每代種群的非支配個體比例。在文獻[6]中給出了建議的歸檔集大小，對每個函數，分別取目標數r=2，3，5，8進行測試，結果如圖1所示，發現進化時實際的非支配個體數m是動態變化的，初始時比較小，隨進化而不斷增大，進化到一定程度時趨于穩定。 對于這些標準測試問題，當目標數較少時（r=2，3），群體中非支配個體比例在50%左右；在目標數較多的情況下（r=5，8），群體中非支配個體的比例會有所上升，但是一般在65%左右，以此驗證了實際的非支配個體數目m比種群N確實小，即0 4.2 基于標準測試函數的算法關鍵操作次數的比較實驗 在這一節，再基于算法的關鍵操作次數來比較算法的效率，該算法關鍵操作次數就是個體的支配性比較次數。這里采用關鍵操作次數的比較而不采用時間的比較是因為它更能反映出算法的效率。將EP集成到NSGAⅡ中，代替其中構造非支配集部分的算法，然后比較(EP+NSGAⅡ)與DEB的NSGAⅡ在標準測試函數上的關鍵操作次數，如圖2所示。標準測試函數采用上一節使用的DTLZ1~6，進化參數設置如表1所示。 表1 進化參數設置 number of objectives2358 population size200200300500 generation200250400600 從圖2可以看出，通過對DTLZ 系列標準測試函數的實驗，無論是在低維還是在高維問題上，(EP+NSGAⅡ)比Deb的NSGAⅡ的關鍵操作次數都要少，即個體的比較次數要少，所以算法EP的效率更高。 從前面兩部分的實驗可以得出：EP受非支配個體比例的影響，而實際測試問題中每代的非支配個體比例不會達到100%，這由第一部分實驗進行了驗證。由此可知，EP要比Deb的算法要好，而第二部分的實驗正是驗證了這一點。 5 結束語 因為基于Pareto的多目標優化是通過在每一代進化過程中構造進化群體的非支配集，并使之不斷逼近真實Pareto前沿來實現的。因此，構造非支配集的方法，直接影響MOEA的運行效率。本文提出了一種新的快速構造Pareto非支配集的方法——選舉法則，給出并討論了用選舉法則構造多目標進化群體的Pareto非支配集的方法，同時進行了時間復雜度的分析，論證了構造方法的正確性。實驗分為兩部分，因為分析表明選舉法則受非支配個體比例（即m/N）的影響，所以實驗第一部分是進行非支配個體比例的測試實驗，驗證了0 參考文獻： ［1］ GOLDBERG D E.Genetic algorithms in search， optimization， and machine learning， reading[M].Massachusetts:AddisonWesley，1989. [2]鄭金華，蔣浩，鄺達，等.擂臺賽法則構造多目標Pareto最優解集的方法研究[J].軟件學報，2007，18(6): 12871297. [3]DEB K，PRATAP A，AGRAWAL S，et al.A fast and elitist multiobjective genetic algorithm: NSGAⅡ[J].IEEE Trans on Evolutio-nary Computation，2002，6(2): 182197. [4]JENSEN M T.Reducing the runtime complexity of multiobjective EAs:the NSGAⅡ and other algorithms[J].IEEE Trans on Evolutionary Computation，2003，7(5):503515. [5]DEB K，THIELE L，LAUMANNS M，et al.Scalable evolutionary multiobjective optimization test problems[C]//Proc ofCongress on Evolutionary Computation.New Jersey: IEEE Service Center， 2002. [6]KNOWLES J D，CORNE D W，FLEISCHER M.Bounded archiving using the lebesgue measure [C]//Proc ofCongress on Evolutionary Computation.Piscataway， NJ: IEEE Press， 2003.
