一種用于求解多目標組合優化的混合遺傳算法

收稿日期：2007-11-07；修回日期：2008-01-15

基金項目：國家自然科學基金資助項目（70572098）

作者簡介：楊開兵（1967-），女，遼寧大連人，博士研究生，主要研究方向為智能計算、計算機集成制造系統（kaibingy@126.com）；劉曉冰（1956-），男，吉林長春人，教授，博導，主要研究方向為計算機集成制造系統、企業信息化*

（1.大連理工大學 CIMS中心，遼寧 大連 116024；2.大連工業大學 信息科學與工程學院，遼寧 大連 116034）

摘 要：為高效求解多目標組合優化問題，提出一種進化計算與局部搜索結合的多目標算法。此算法基于個體排序數和密度值進行適應度賦值，采用非劣解并行局部搜索策略，在解的適應度賦值和局部搜索過程中使用Pareto支配的概念。實驗結果表明，新算法不僅提高了優化搜索的效率，且能夠找到更多的近似Pareto最優解。

關鍵詞：多目標組合優化；混合遺傳算法；適應度賦值；局部搜索

中圖分類號：TP301

文獻標志碼：A

文章編號：1001-3695(2008)10-2956-03

Hybrid genetic algorithm for multi-objective combinatorial optimization

YANG Kai-bing¹，2，LIU Xiao-bing¹

(1.CIMS Center， Dalian University of Technology， DalianLiaoning 116024 ，China; 2. College of Information Science Engineering ， Dalian Polytechnic University， Dalian Liaoning 116034，China)

Abstract:To efficiently solve multi-objective combinatorial optimization problems， combining evolutionary computation with local search， this paper proposed a hybrid genetic algorithm. It evaluatd the indivi-dual fitness based on the rank of the individual and its density value， used a Pareto parallel local search strategy. Used the concept of Pareto dominance to assign fitness to the solutions and in the local search procedure. The experimental results show that the proposed algorithm can improve search efficiency of optimization and find more approximate Pareto optimal solutions.

Key words：multi-objective combinatorial optimization; hybrid genetic algorithm; fitness assignment; local search

多目標組合優化是現實世界廣泛存在的NP難問題。由于目標間的沖突性以及計算的復雜性，使得多目標組合優化問題的求解尤為困難。隨著多目標進化算法的興起，并成功地應用于多目標優化領域，為求解多目標組合優化問題提供了一條有效的途徑。近年來，將進化計算與局部搜索結合，用于求解多目標組合優化問題，受到了許多研究者的關注[1~5]。Ishibuchi和Murata[1]建立了基于隨機加權和的多目標遺傳局部搜索算法（multi-objective genetic local search algorithm，MOGLS），其主要思想是每代隨機地產生一組權重，用于進化過程中雙親的選擇和局部搜索過程中搜索方向的確定，局部搜索作用于當前群體的每一個個體上。此算法應用到流水車間調度問題中，其結果顯示出好于Schaffer提出的基于向量評估的遺傳算法（VEGA）。Jaszkiewicz[3]也建立了一個多目標遺傳局部搜索算法（J-MOGLS），主要做法是根據隨機權重確定的標量化函數，從當前群體中選擇一定數目的不同個體，構成臨時群體，從中選擇兩個個體重組，得到的新個體進行局部搜索。此算法在求解多目標對稱旅行商問題上取得了較好的效果。上述兩種算法的共同特征是解的適應度評價都是基于多個目標的加權標量化函數，局部搜索都是對進化產生的每一個個體實施的。

為更有效地產生Pareto前沿的近似，本文提出了一種不同的混合算法MOHGA（multi-objective hybrid genetic algorithm）。該算法將Elaoud等人[6]提出的Pareto適應度遺傳算法PFGA（Pareto fitness genetic algorithm）與局部搜索相結合，在改善算法收斂性的同時，保持了群體的多樣性。通過對一組多目標流水車間問題的求解，與MOGLS[1]、J-MOGLS[3]、PFGA[6]算法進行比較，實驗結果表明，MOHGA有更快的收斂速度和更好的優化效果。

1 問題描述

一般地，多目標組合優化問題可描述如下[7]：

minimize z=f(x)=(f1(x)=z1，…， fr(x)=zr)

subject to x∈Ω（1）

其中:f(x)為具有r個分量的目標向量；x是離散的決策向量；Ω是可行解的集合；點z=f(x)是解x∈Ω在目標空間中的像。

如果對任意的j∈{1，2，…，r}，有zj=fj(x)≤z′j=fj(x′)，并且至少存在一個j，有zj＜zj′，則稱點z=(z1，…，zr)支配點z′=(z1′，…，zr′)。如果解x的像支配解x′的像，則稱解x支配解x′。

如果不存在x∈Ω使得z=f(x)支配z*=f(x*)，則稱解x*∈Ω是Pareto最優解（或非劣解）。Pareto最優解組成的集合稱為Pareto最優集。Pareto最優集在目標空間的像稱為Pareto前沿（或非劣前沿）。

2 多目標混合遺傳算法（MOHGA）

本文提出的算法具有如下特征：

a)雙重精英策略。一是從外部群體中選擇一定數目的個體進入進化群體中；二是在進化選擇中淘汰掉個別最差個體，提高算法收斂性。

b)采用基于Pareto支配關系的雙倍排序策略以及自適應密度評估技術，賦予個體以適當的適應度值，保持群體多樣性。

c)基于Pareto支配概念，進行并行多目標局部搜索，加強不同區域的搜索。

21 雙重精英策略

MOHGA使用兩個群體：進化群體和外部群體。外部群體用來保存進化過程中產生的所有非劣解。在每次迭代中，從外部群體NDt中選擇Nelite個精英解，組成精英解集Et，加入到當前群體MPt中，形成聯合群體MPt∪Et。讓目前所發現的所有非劣解都有機會參與局部搜索。在進化過程中，規模為Npop+Nelite的進化群體選擇Npop個優秀個體，淘汰掉Nelite個最差個體，使大部分較優個體參與進化。同時采用上述兩種方式的精英策略，以更好地提高算法的收斂性。

22 適應度賦值

多目標進化算法中，適應度賦值是關鍵技術之一，有基于Pareto支配概念和不基于Pareto支配概念兩大類技術。MOGLS和J-MOGLS是不基于Pareto支配概念的目標加權和法。 基于Pareto支配概念的適應度賦值將多目標解按Pareto支配關系進行排序，可消除目標尺度的無公度性帶來的影響。PFGA[6]基于Pareto支配關系，采取雙倍排序策略和自適應密度評估方法，對群體中的個體進行適應度賦值。它不僅考慮了個體間的Pareto最優性，還考慮了其在整個搜索空間的分布，能夠更好地防止遺傳漂移（群體收斂到一個最優解上），保持群體多樣性。本文基于PFGA，提出了個體適應度賦值的方法，先根據Pareto支配關系計算每一個體的排序數，再根據個體周圍的擁擠狀況計算個體的密度值；最后綜合確定個體的適應度值。具體方法如下：

a)計算當前群體P中每個個體i的偽排序數：

R′(i)=|{j/j∈P，j  i}|，i∈P

其中：符號“”表示Pareto支配關系，即R′(i)表示當前群體P中支配個體i的個體數。

b)計算個體i的排序數：

R(i)=R′(i)+∑j∈P，ijR′(j)，i∈P

即個體i的排序數R(i)等于個體i的偽排序數與支配個體i的所有個體的偽排序數之和。

c)將目標空間根據群體規模Npop劃分成nc×nc×…×nc個網格區域，nc表示每維目標空間的網格數，第i維目標空間的網格寬度為

Wdi=[max fi(x)-min fi(x)]/nc；j=1，2，…，k

其中:k表示目標數;max fi(x)和min fi(x)分別是第i維目標空間的上邊界和下邊界。

nc的確定：設kNpop的整數部分為a，小數部分為r，則當r=0時，nc=a，r≠0時，nc=a+1。每一個體都位于一個網格區域內，將每個個體所在的網格區域內的個體數作為該個體的密度值。

d)個體的適應度為

fitness(i)=1/[exp(R(i))×D(i)]

其中:R(i)表示個體i的排序數;D(i)表示個體i的密度值。

個體的適應度既與它的排序數有關，又與它周圍擁擠狀況有關。當個體的排序數相同時，其適應度將只依賴于它的密度值，位于稀疏區域的個體將有較大的適應度。當一個非劣解不與其他任何個體同處于一個網格區域時，其適應度最大。這種適應度賦值方式，既保證了群體朝著Pareto前沿逼近，又能在一定程度上保持群體多樣性。

為進一步提高群體多樣性，本文在上述適應度賦值的基礎上采取將群體中的極端個體賦予最大的適應度，以增加被選擇的機會，避免Pareto前沿過于狹窄，使產生的非劣前沿分布范圍更廣。

23 多目標局部搜索

MOGLS和J-MOGLS對進化產生的每一個個體進行局部搜索，但是當個體質量較差時，搜索效率并不高。此外，MOGLS和J-MOGLS對個體進行局部搜索時，是基于各目標加權和的標量化函數來判斷個體的優劣，而且，只在新個體和目標個體這兩個個體間比較后就決定是否接受新個體。這種方式有時會丟棄一些支配其他個體的非劣解。

為避免上述問題，本文采取基于Pareto支配關系的并行搜索策略，只對非劣解進行局部搜索。基本思想是：對當前群體的非劣解集S中的每一個解x產生一個鄰域N(x)，對該鄰域內的解y，只要y不比S中的解差，即y不受S中的解支配，則接受y作為新解。將搜索過程中產生的所有新解組成集合S′。用S′修正S，即將S′的解添加到S中，同時刪除S中被支配的解，這樣會得到改善的非劣解集S；再將S作為初始集合，重復上述搜索過程。這種從S出發，并行地搜索解空間的幾個區域，能夠加強不同區域的搜索，提高搜索效率。具體步驟如下：

a)初始化局部搜索的非劣解集合S，并將S加入到NDI中，令迭代次數t=1。

b)置S′為空集。對S中每一個解xk產生xk的鄰域N(xk)，對y∈N(xk)判斷y是否處于受集合NDI支配的區域。若y不被NDI中的任何解支配，且yNDI，則將y加入到S′中。

c)用S′修正NDI，即將S′的解添加到NDI中，剔除其中受支配的解。

d)如果t小于最大迭代數，則置S=NDI，t=t+1，返回步驟b)。

24 MOHGA的實現步驟

a)算法參數設定：群體規模Npop，交叉概率Pc，變異概率Pm，最大精英數Nelite，局部搜索的最大迭代數Niter。

b)初始化：隨機產生規模為Npop的初始群體，計算每個個體的目標值。初始化外部群體NDI=，初始化精英解集E1=。

c)求非劣解：求出當前群體Pt中的所有非劣解。

d)修正外部群體NDt：將非劣解加入到NDt中，再從NDt中刪去被支配的個體。

e)適應度賦值：按2.2節的方法計算所有個體的適應度。

f)選擇、交叉和變異：將Pt中的個體按適應度由大到小排序，選擇前Npop個個體進入交配池，從交配池中選擇兩個不同的個體，依概率Pc進行交叉，得到的子代依概率Pm進行變異，共產生Npop個個體，形成中間群體MPt。

g)精英策略：隨機從集合NDt中選出Nelite個個體，存放于集合Et中。

h)局部搜索：應用2.3節的方法對MPt∪Et的非劣解集S進行局部搜索，得到改善的非劣解集NDI。用NDI修正MPt∪Et，得到下一代群體Pt+1。

用NDI修正MPt∪Et，方法如下：

(a)|NDI|=|S|，則用NDI替代S。

(b)|NDI|＞|S|，從MPt∪Et中刪去S和隨機選擇的|NDI|-|S|個解，再加進NDI。

(c)|NDI|＜|S|，隨機從S中選擇|S|-|NDI|個解，連同NDI一起加入到MPt∪Et中，再從MPt∪Et中刪去S。其中：|NDI|為集合NDI中的元素個數;|S|為集合S中的元素個數。

i)停止準則：若停止條件滿足，則輸出外部群體；否則Pt=Pt+1，返回步驟c)。

MOHGA的基本流程如圖1所示。

3 實驗測試

31 測試問題

Flow shop問題是一種典型的組合優化問題，置換flow shop調度可以描述為n個工件按照同一加工順序在m臺機器上依次進行處理，要求確定使預定目標函數最小的工件加工順序。這意味著問題的解為工件的一個全排列，其搜索空間的規模是n!。本文按照文獻[2]的方法，產生六個規模不同的調度實例，包括機器數m為10和20，工件數n為20、40、60和80，每一問題表示成n×m。優化目標是使最大完成時間f1（make span）和最大拖后時間f2（maximum tardiness）達到最小。

32 性能指標

多目標優化的目的有兩個：一是收斂到Pareto前沿;二是維持Pareto最優集內解的多樣性。本文采用Knowles 和Corne[8]提出的基于與參考集（Pareto最優集或近似Pareto最優集）的距離指標D1R來評價解的質量。D1R可同時考察解集的收斂性和多樣性。設S*是參考解集，Sj是評價的解集，則D1R定義如下：D1R(Sj)=1/|S*|∑y∈S*min{dxy|x∈Sj}（2）其中：dxy是解x和參考解y在N維標準化目標空間的距離。dxy=∑Ni=1(f*i(y)-f*i(x))²（3）其中：f*i(·)是使用參考集進行標準化的第i個目標值。D1R(Sj)越小，解集Sj越好。

此外，本文還采用Fieldsend等人[9]提出的指標來比較兩個集合的收斂速度。設A、B是兩個待比較的集合，C的定義為C(A，B)=|{b∈B;a∈A，ab}|/|B|（4）其中：C∈[0，1]，表示B的非劣解被A的非劣解支配的個數占B的非劣解總數的比率。當B中任何點都被A中某些點支配時，C(A，B)=1；當B中所有點都不被A中任何點支配時，C(A，B)=0。一般C(A，B)≠C(B，A)。

33 計算結果和比較

采用MOGLS[1]、J-MOGLS[3]以及PFGA[6]作為參考算法，檢驗本文MOHGA的優化性能。采用基于工件加工順序的自然數編碼，統一設定參數：群體規模Npop=30，交叉概率Pc=0.9，變異概率Pm=0.3，精英解的數目Nelite=3。對于J-MOGLS，群體的最大規模為Nmax=100，臨時集合規模為6；對于MOHGA，局部搜索的最大迭代數Niter=3。所有算法使用相同的遺傳操作和鄰域結構：兩點交叉，插入變異，對換鄰域且搜索步長為2。計算終止條件均設定為評價100 000個解。每種算法在相同的初始條件下獨立運行20次，合并各次非劣解集并剔除其中的劣解后，獲得各問題的最終非劣解集作為參考集（非劣解前沿）。表1給出了評價指標D1R的計算結果。從中可以看出，MOHGA的指標D1R均優于其他三種算法，說明MOHGA能有效地產生更接近非劣解前沿的近似集。

表1 指標D1R的比較問題MOHGAMOGLSJ-MOGLSPFGA20×100.013 10.040 40.025 90.116 940×100.005 00.139 00.138 70.388 440×200.019 70.065 40.115 10.297 760×100.000 00.357 30.377 80.532 560×200.007 00.146 20.171 81.543 580×200.019 50.216 50.134 21.087 7

表2給出了每種算法產生的非劣解數量。表3是C指標的統計結果。由表2和3可知，MOHGA均獲得了多于其他三種驗證算法獲得的非劣解數量，且具有更快的收斂速度。

圖2（a）（b）是以問題40×20和60×10為例，描述了不同算法得到的非劣解集的比較。從圖中可以看出，在相同的算法終止條件下，本文MOHGA得到較多且較廣泛的非劣解前沿的近似。

表2 非劣解數目的比較問題MOHGAMOGLSJ-MOGLSPFGA20×102419281940×103416112240×203215251560×1012137360×202615111980×2031142017表3 C指標的統計結果問題C(A，B)C(A，C)C(A，D)C(B，A)C(C，A)C(D，A)20×100.263 20.678 610.250.166 7040×100.562 50.818 210.205 90.058 9040×200.866 7110.03130060×1011100060×200.933 30.818 2100.115 4080×2010.75100.322 60

注：C指標評價中，A表示MOHGA所得的非劣解集；B表示MOGLS所得的非劣解集；C表示J-MOGLS所得的非劣解集；D表示PFGA所得的非劣解集。

4 結束語

本文提出了一種新的多目標混合遺傳算法MOHGA。MOHGA采用雙倍排序策略以及自適應密度評估進行適應度賦值，以保持群體多樣性，基于Pareto支配關系對非劣解進行并行局部搜索，以提高搜索效率。在進化選擇中通過淘汰掉個別最差個體以及引入外部群體中的精英個體，進一步加快解的收斂速度。實驗證明，MOHGA在求解多目標組合優化問題時能有效地產生數量較多、分布較廣的非劣解的近似集。

參考文獻：

[1]ISHIBUCHI H ， MURATA T. A multi-objective genetic local search algorithm and its application to flowshop scheduling[J]. IEEE Trans on Systems， Man and Cybernetics， 1998， 28 (3): 392-403.

[2]ISHIBUCHI H， YOSHIDA T， MURATA T. Balance between genetic search and local search inmemetic algorithms for multiobjective permutation flowshop scheduling[J]. IEEE Trans on Evolutionary Computation， 2003， 7(2): 204-223.

[3]JASZKIEWICZ A .Genetic local search for multi-objective combinatorial optimization[J]. European Journal of Operational Research， 2002， 137(1) : 50-71.

[4]KNOWLES J D， CORNE D W. A memetic algorithm for multiobjective optimization[C]// Proc of the Congress on Evolutionary Computation. Piscataway: IEEE Service Center， 2000: 325-332.

[5]JASZKIEWICZ A. On the performance of multiple-objective genetic local search on the 0/1 knapsack problem: a comparative experiment [J]. IEEE Trans on Evolutionary Computation， 2002，6 (4) : 402-412.

[6]ELAOUD S， LOUKIL T， TEGHEM J. The Pareto fitness genetic algorithm : test function study[J]. European Journal of Operational Research， 2007， 177 (3):1703-1719.

[7]ARROYO J E C， ARMENTANO V A. Genetic local search for multi-objective flowshop scheduling problems[J]. European Journal of Operational Research， 2005， 167(3):717-738.

[8]KNOWLES J D， CORNE D W. On metrics for comparing nondominated sets[C]// Proc of the Congress on Evolutionary Computation. Piscataway : IEEE ServiceCenter ， 2002 : 711-716.

[9]FIELDSEND J E， EVERSON R M， SINGH S. Using unconstrained elite archives for multiobjective optimization[J]. IEEE Trans on Evolutionary Computation， 2003， 7(3):305-323.