1、鄭金華,多目標進化算法簡介,多目標進化算法歷史,1967年Rosenberg就建議采用基于進化的搜索來處理多目標優(yōu)化問題。 1984年，David Schaffer首次在機器學習中實現(xiàn)了向量評估遺傳算法。 1989年David Goldberg在其著作Genetic algorithms for search, optimization, and machine learning中，提出了用進化算法實現(xiàn)多目標的優(yōu)化技術。 從2001年以來，每二年召開一次有關多目標進化的國際會議(EMO：evolutionary multi-criterion optimization) 國際刊物“IEEE T

2、ransactions on Evolutionary Computation”(1997年創(chuàng)刊) Evolutionary Computation (1993年創(chuàng)刊) Genetic Programming and Evolvable Machines (1999年),基本概念,進化算法(evolutionary algorithm, EA)得到了非常廣泛應用。 現(xiàn)實中，一般對多個目標同時優(yōu)化，往往優(yōu)化的多個目標之間是相互沖突。 如：企業(yè)生產中，產品質量與生產成本的關系。 為達到總目標的最優(yōu)化，對各子目標進行折衷，出現(xiàn)了多目標進化算法(multi-objective EA,MOEA)。,一般

3、描述,給定決策向量，它滿足下列約束： 設有r個優(yōu)化目標，且這r個優(yōu)化目標是相互沖突的，優(yōu)化目標可表示為： 尋求 ，使 在滿足約束(1)和(2)的同時達到最優(yōu)。,例子,決策變量x,滿足約束條件：-3x 3 設有2個優(yōu)化目標：f(x)=(f1(x),f2(x),其中 f1=x2 f2=(x-2)2 求解x*,使得f(x*)同時達到最小。,值空間分布圖,X f1f2 -3.000 9.000 25.000 -2.9008.41024.010 -2.8007.84023.040 -2.7007.29022.090 -2.6006.76021.160 -2.5006.25020.250 -2.4005.

4、76019.360 2.0004.0000.000 2.1004.4100.010 2.2004.8400.040 2.3005.2900.090 2.4005.7600.160 2.5006.2500.250 2.6006.7600.360 2.7007.2900.490 2.8007.8400.640 2.9008.4100.810 .,Pareto最優(yōu)解基本定義,多目標優(yōu)化的最優(yōu)解稱為Pareto最優(yōu)解。(1896年 Vilfredo Pareto） 定義1：給定一個多目標優(yōu)化問題 ，它的最優(yōu)解x*定義為： (3) 其中： (4) 這里為滿足式(1)和式(2)的可行解集，即： 我們稱為決

5、策變量空間(簡稱決策空間)，向量函數(shù) 將 映射到集合 ，是目標函數(shù)空間(稱目標空間)。,決策空間和目標空間,定義2：給定一個多目標優(yōu)化問題 ，稱 是最優(yōu)解(即Pareto optimal solution)， 若 ，滿足下列條件： 或者 (5) 或至少存在一個 ，I=1，2，r,使： (6) 其中滿足式(1)和式(2)的可行解集，即：,定義3：給定一個多目標優(yōu)化問題 ， 若 ，且不存在其它的 使得： 成立，且其中至少一個是嚴格不等式， 則稱X*是 的Pareto最優(yōu)解。,Pareto最優(yōu)解,X f1f2 004 0.10.013.61 0.20.043.24 0.30.092.89 0.40.

6、162.56 0.50.252.25 0.60.361.96 0.70.491.69 0.80.641.44 0.90.811.21 111 1.11.210.81 1.21.440.64 1.31.690.49 1.41.960.36 1.52.250.25 1.62.560.16 1.72.890.09 1.83.240.04 1.93.610.01 240,定義4：給定一個多目標優(yōu)化問題 ，設 如果 ，則稱 比 優(yōu)越； 如果 ，則稱 比 更優(yōu)越； 定義 ： 若X*比更優(yōu)越的 不存在，則稱X*為弱Pareto最優(yōu)解。 若X*比任何 都優(yōu)越，則稱X*為完全Pareto最優(yōu)解。 若比X*優(yōu)越的

7、 不存在，則稱X*為強Pareto最優(yōu)解。,定義5：給定一個多目標優(yōu)化問題 ，它的最優(yōu)解集定義為： 多目標進化算法的優(yōu)化過程是，針對每一代進化群體，尋找出其當前最優(yōu)個體(即當前最優(yōu)解)，稱一個進化群體的當前最優(yōu)解為非支配解(non-dominated solution)，或稱為非劣解(non-inferior solution)；所有非支配解的集合稱之為當前進化群體的非支配集(NDS：non-dominated solutions)，并使非支配集NDS不斷逼近真正的最優(yōu)解集，最終達到最優(yōu)，即使NDSet*X*，NDSet*為算法運行結束時所求得的非支配集 。,Pareto最優(yōu)邊界,定義6：給定

8、一個多目標優(yōu)化問題 和它的最優(yōu)解集X*，它的Pareto最優(yōu)邊界定義為： 區(qū)別：Pareto最優(yōu)解集，Pareto最優(yōu)邊界,實心點A、B、C、D、E、F均處在最優(yōu)邊界上，它們都是最優(yōu)解(Pareto points) ,是非支配的(non-dominated)；空心點G、H、I、J、K、L落在搜索區(qū)域內，但不在最優(yōu)邊界上，不是最優(yōu)解，是被支配的(dominated)，它們直接或間接受最優(yōu)邊界上的最優(yōu)解支配。,個體之間的支配關系,對兩個變量(個體)x和y進行比較時，可能存在三種關系：x大于y，x等于y，x小于y。在多目標情況下，由于每個個體有多個屬性，比較兩個個體之間的關系不能使用簡單的大小關系。

9、如兩個目標的個體(2, 6)和(3, 5)，在第一個目標上有2小于3，而在第二個目標上又有6大于5，這種情況下個體(2, 6)和(3, 5)之間的關系是什么呢？另一種情況，如個體(2, 6)和(3, 8)，它們之間的關系又是什么呢？當目標數(shù)大于2時，又如何比較不同個體之間的關系呢？,定義8(個體之間的支配關系) 設p和q是進化群體Pop中的任意兩個不同的個體，我們稱p支配(dominate)q，則必須滿足下列二個條件： (1)對所有的子目標，p不比q差 即 ； (2)至少存在一個子目標，使p比q好 即 ，使 。 其中r為子目標的數(shù)量。 此時稱p為非支配的(non-dominated)，q為被支

10、配的(dominated)。表示為p q，其中“ ”是支配關系(dominate relation)。,定義9(目標空間中的支配關系) 設 和 是目標空間中的兩個向量，稱U支配V(表示為 )，當且僅當： 且 ，使 。 據(jù)定義9，我們便可以得出結論：(2, 6)支配(3, 8)，(2, 6)和(3, 5)之間互相不支配。 區(qū)別：決策空間支配關系，目標空間支配關系,多目標進化算法,為了便于理解，我們這里給出一類基于Pareto的多目標進化算法的一般流程，首先產生一個初始種群P，接著選擇某個進化算法(如遺傳算法)對P執(zhí)行進化操作(如交叉、變異和選擇)，得到新的進化群體R。然后采用某種策略構造PR的非

11、支配集Nset，一般情況下在設計算法時已設置了非支配集的大小(如N)，若當前非支配集Nset的大小大于或小于N時，需要按照某種策略對Nset進行調整，調整時一方面使Nset滿足大小要求，同時也必須使Nset滿足分布性要求。之后判斷是否滿足終止條件，若滿足終止條件則結束，否則將Nset中個體復制到P中并繼續(xù)下一輪進化 。,在MOEA中，保留上一代非支配集，并使之參入新一代的多目標進化操作是非常重要的，這類似于進化算法中保留上一代的最優(yōu)個體，從而使新一代的非支配集不比上一代差，這也是算法收斂的必要條件。這樣，一代一代的進化下去，進化群體的非支配集不斷地逼近真正的最優(yōu)邊界(true pareto o

12、ptimal front)，最終得到滿意的解集(不一定是最優(yōu)解集)。,MOEA分類,按選擇機制的不同(Coello Coello et al. 2004)，可以將MOEA 分為： 聚集函數(shù)(aggregating functions) 基于群體的方法(population-based approaches) 基于Pareto的方法(pareto-based approaches),按決策方式的不同，Coello Coello等將多目標進化算法分為三大類(Coello Coello et al. 2002)： 前決策技術(priori technique) 交互決策技術(progressive

13、technique) 后決策技術(posteriori technique),進一步研究,更一般的，更通用的，更接近于自然進化的MOEA模型 基于進化環(huán)境的多目標進化模型。 MOEA在有限時間內的收斂性。 構造多目標最優(yōu)解集的最少時間復雜度。 進化過程中，個體循環(huán)地進入歸檔集問題。 MOEA在不同參數(shù)時的比較研究。 MOEA進化過程中，非支配集變化規(guī)律的研究。 MOEA運行的統(tǒng)一框架。 不確定多目標優(yōu)化問題。 ,NSGA_II,1993年 Deb提出NSGA（The Non-dominated Sorting Genetic Algorithm ） NSGA主要有三個方面的不足：一是構造Par

14、eto最優(yōu)解集的時間復雜度太高；二是沒有最優(yōu)個體(elitist)保留機制；三是共享參數(shù)大小不容易確定。 2000年，Deb等在NSGA的基礎上，提出了NSGA-II。,非支配集構造,設群體Pop的規(guī)模大小為N，將群體Pop按某種策略進行分類排序為m個子集P1、P2、Pm，且滿足下列性質： (1) (2) (3) P1 P2 Pm，即Pk+1中的個體直接受Pk中個體的支配，(k=1,2,m-1)。 對群體Pop進行分類排序的目的是為了將其劃分成若干個滿足上述三個性質的互不相交的子群體，分類排序依據(jù)個體之間的支配關系來進行。,sort(Pop) for each pPop /第一部分：計算ni和

15、si for each qPop if (p dominated q) then sp=sp q else if (q dominated p) then np=np + 1; end for q if ( np=0) then P1=P1 p end for p i=1; while (Pi) /第二部分：求P1、P2、P3、Pm H=; for each pPi for each qsp nq=nq 1; if (nq=0) then H=H q end for p i=i + 1; Pi=H; end for while end for sort,保持種群多樣性,在產生新群體時，通常將優(yōu)

16、秀的同時聚集密度比較小的個體保留并參與下一代進化。聚集密度小的個體其聚集距離反而大，一個個體的聚集距離可以通過計算與其相鄰的二個個體在每個子目標上的距離差之和來求取。 一般情況，當有r個子目標時個體i的聚集距離為：,Pidistance=(Pi+1. f1 - Pi-1. f1 )+(Pi+1. f2 - Pi-1. f2 ),crowding-distance-assignment(P) N=|P|; /N為群體大小 for each i, Pidistance=0; /初始化每個個體的聚集距離 for each objective m /針對每個子目標進行如下操作 P=sort(P, m)

17、; /對子目標m的函數(shù)值進行排序 for i=2 to (N-1) /針對邊界點之外的解 Pidistance= Pidistance+(Pi+1. m - Pi-1. m ) end for objective m P0distance= PNdistance=; /給邊界點一個最大值以確保每次它們均能入選下一代 ,Deb 的MOEA,Debs main loop of NSGA-II /初始時隨機產生一個初始群體P0，Q0make-new-pop(P0),t=0/ Rt=PtQt /將Pt和Qt并入到Rt中 F=fast-nondominated-sort(Rt) /產生所有邊界集F=(F

18、1,F2,.) Pt+1= and i=1 / Pt+1賦空集 Until (|Pt+1|+|Fi|N) /選擇個體到Pt+1中，直至填滿 Crowding-distance-assignment(Fi) /計算第i層邊界集中個體的聚集距離 Pt+1=Pt+1Fi /將第i層邊界集并入到新群體Pt+1中 i=i+1 (end of until) Sort(Fi,) /對第i層邊界集建立偏序關系 Pt+1=Pt+1Fi1: (N-|Pt+1|) /在第i層邊界集選取個體填滿Pt+1 Qt+1make-new-pop(Pt+1) /在Pt+1上執(zhí)行選擇、交叉和變異操作 t=t+1 ,種群構造示意圖

19、,SPEA,1999年 Zitzler提出SPEA(strength Pareto evolutionary algorithm) ，采用聚類方法降低非支配集大小。 產生一個初始群體Pop，同時設置一個空的非支配集NDSet(或稱歸檔集(archive set)； 將Pop中的非支配個體復制到NDSet中； 刪除NDSet中的支配個體； 如果NDSet中的個體數(shù)目超過約定值，則用聚類方法(clustering procedure)降低NDSet的大小； 計算Pop和NDSet中個體的適應度； 采用錦標賽選擇法從群體Pop和非支配集NDSet中選擇個體進入配對庫，直至配對庫滿； 對群體Pop執(zhí)行

20、進化交叉和變異操作； 若不滿足結束條件則轉，否則結束。,SPEA中個體的適應度,SPEA中個體的適應度又稱之為strength，NDSet中個體的適應度定義如下： (10) 式(10)中iNDSet，N為群體Pop的大小，ni為個體i在群體Pop中所支配的個體數(shù)： nijPop| i dominates j，iNDSet (11) 進化群體Pop中個體適應度定義如下：,用聚類方法降低非支配集大小,(1)初始化聚類集C，使 ，其中i NDSet。 (2)若 則轉(5)，否則轉(3)。 (3） ，計算C1和C2之間的距離d: 式中 為兩個個體之間的距離，這里為Euclidean距離。 (4)將C中距離最小的兩個子類C1和C2合并，即， 轉(2)。 (5)在C中，從每個子類中選出一個具有代表性的個體，組成新的非支配集。,SPEA2,N為進化群體P規(guī)模，M為歸檔集Q(archive set)大小，T為預定的進化代數(shù) (1)初始化：產生一個初始群體P0，同時使歸檔集Q0為空，t0。 (2)適應度分配：計算Pt和Qt中所有個體的適應度。 (3)環(huán)境選擇：將Pt和Qt