基于Ｐａｒｅｔｏ的快速多目標克隆選擇算法

摘要：基于免疫系統中克隆選擇原理，提出了一種多目標克隆選擇算法MCSA。該方法只對部分當前所得到的Pareto最優解進行進化操作，所求得的Pareto最優解保留在一個不斷更新的外部記憶庫中，并選用一種簡單的多樣性保存機制來保證其具有良好的分布特征。實驗結果表明，該方法能夠很快地收斂到Pareto最優前沿面，同時較好地保持解的多樣性和分布的均勻性。對于公認的多目標benchmark問題，MCSA在解集分布的均勻性、多樣性與解的精確性及算法收斂速度等方面均優于SPEA、NSGA－II等算法。

關鍵詞：克隆選擇原理； Pareto最優解； 多目標優化

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2008)05-1368-04

最優化處理是在可能的解中搜索對于某些目標來說是最優解的問題，這種問題在過去的五十年中已經得到了深入的研究。若僅考慮一個優化目標，即單目標優化問題；如果存在的目標超過一個并需要同時處理，就成為多目標優化問題[1，2]。多目標優化問題中各目標之間通過決策變量相互制約，對其中的一個目標優化必須以其他目標作為代價，而且各目標的物理意義往往又不一致，因此很難評價多目標問題解的優劣性。與單目標優化問題的本質區別在于，多目標優化問題的解不是惟一的，而是存在一個最優解集合， 集合中元素稱為Pareto 最優解或非支配解（non－dominated solutions）[3] 。所謂Pareto最優解，就是不存在比其中至少一個目標好而其他目標不劣的更好的解，也就是不可能通過優化其中部分目標而使其他目標不至劣化。因此，Pareto最優解集中的元素就所有目標而言是彼此不可比較的。

在過去的二十年中，進化算法作為多目標優化問題的新求解方法受到了相當程度的關注，這就誕生了多目標進化算法。Fonseca和Fleming對這一主題進行了綜述[4]，他們將進化多目標優化算法分為明確加權法、基于種群的非Pareto方法和基于Pareto的方法三類。其中基于Pareto的進化算法是一條求解多目標問題非劣最優解的有效途徑。在基于Pareto的方法中最具代表性的兩類是解排序遺傳算法NSGA(non－dominated sorting genetic algorithm)和基于濃度的Pareto進化算法SPEA(strength pareto evolutionary algorithm)。Zitzler和Thiele于1999年提出了SPEA[5] ，它的運行效率比較低，但由于SPEA采用聚類方法維持解群體的分布性，其解集的分布性比NSGA好。Zitzler等人于2001年又對SPEA進行了改進，提出了運行效率相對較高的SPEA2[6]。Srinivas和Deb基于個體的多層次分類提出了NSGA[7]。NSGA通過計算個體之間的聚集距離來保持群體的分布性，運行效率比SPEA高，但分布性差一些。最近，Deb等人通過引進快速非劣解排序和新的多樣性保存方法提出了第二代NSGA，簡稱NSGA－Ⅱ[8]。總的來說，NSGA－Ⅱ的運行效率比SPEA2好，其解集的分布性也不比SPEA2差，是目前研究者們比較認同的一種好算法。

上面提到的多目標進化算法基本上都是基于遺傳算法（GA）來求解多目標優化問題。本文借鑒免疫系統中的克隆選擇原理，將成功地應用于單目標優化問題的克隆選擇算法擴展到多目標優化問題中，設計出了一種新的基于Pareto的多目標優化算法。

1克隆選擇原理

在自然界中，免疫功能是指機體對外部感染具有抵抗能力而保護自身的能力，它是機體內部細胞相互作用的結果。克隆選擇原理是目前描述免疫系統作用機制的兩個主要理論之一[9，10]。

任何能夠被自適應的免疫系統識別的分子都被

稱為抗原（Ag）。當機體首次接觸某種抗原時，其骨髓產生的B 細胞的某個子部分會作出反應，產生抗體（Ab）。它們的作用就是識別并綁定特定的抗原， 特定類型的抗體是針對一類相對特定的抗原的。克隆選擇原理如圖1所示，其基本思想是只有那些能夠識別抗原的細胞才進行擴增，只有這些細胞才能被選擇并保留下來；那些不能識別抗原的細胞則不選擇，也不進行擴增。骨髓中微小的“休眠”的B細胞每一個都載有一個不同的抗體類型，這些細胞載有對于抗原特異的受體，擴增分化成漿細胞和記憶細胞 。

與達爾文的生物進化原理相似，免疫系統中也存在著進化現象。 免疫系統中每個B細胞受體的形狀可用一個n維實向量描述， 因此可表示為n維歐幾里得空間中的一點，稱此空間為歐幾里得形狀空間。 兩個B細胞的受體形狀越相似， 它們在形狀空間中的距離越近。當抗原侵入機體時，B細胞受體與抗原形狀互補程度越大，二者間的親和力越高， 從而更易結合。B細胞群體通過如下進化過程產生抗體:

a)選出與入侵抗原親和力高的B細胞。

b)該B細胞分裂為若干子B細胞， 稱為克隆擴增。 子B細胞受體形狀在母細胞的基礎上發生微小變異， 即超突變。B 細胞通過克隆擴增和高頻變異在形態空間中的小鄰域內產生若干子B細胞， 以在局部范圍內搜索親和力更高的B細胞。

c)在克隆擴增生成親和力更高的子B細胞的同時， 也產生了親和力低的子B細胞。 一些親和力低的子B細胞刪除其受體并生成新受體， 稱為受體編輯。受體編輯使得子B細胞可能突變為形狀空間中離原B細胞較遠的點， 以避免在尋求親和力更高的B細胞的過程中陷入局部最優。

d)一些親和力低的子B細胞死亡， 同時骨髓產生一些新的B細胞加入群體， 以保持群體的多樣性。經過若干世代的選擇、克隆擴增、受體編輯和骨髓產生新B細胞的過程， 最終產生了親和力很高的B細胞。 這些B細胞分化為記憶細胞或漿細胞， 產生與受體形狀相同的抗體以消滅抗原， 發生適應性免疫應答。

本文主要用到的克隆選擇原理的特征是：a）只有那些能夠識別抗原的細胞才進行擴增，而那些不能識別抗原的細胞則不選擇，也不進行擴增。b）B細胞通過克隆擴增和高頻變異在形態空間中的小鄰域內產生若干子B細胞，以在局部范圍內搜索親和力更高的B細胞。c）一些具有高親和力的B細胞能夠分化成為生命期較長的B記憶細胞被選入記憶細胞池中。

2多目標克隆選擇算法

本文提出的多目標克隆選擇算法（multi－objective clonal selection algorithm，MCSA）與其他的基于Pareto算法的最大區別在于，它在進化過程中丟掉所有被支配解的信息而只選取算法當前所得到的部分Pareto解進行進化操作。在算法運行過程中，每代所得到的Pareto解的個數可能不同。當Pareto解的個數較小時，對其全部進行克隆擴增和高頻變異操作；當所得到的Pareto的個數很多時，如果對其均進行克隆擴增和高頻變異操作的話，算法的運算量將變得很大。為此，本文設定一個上限值nmax1來限制參加下一次進化操作的Pareto解的個數。當某一代所得Pareto解的個數超過上限值時，選用NSGA－Ⅱ中的個體局部擁擠距離的定義方法對當前所得到的Pareto解進行排序，選取局部擁擠距離較大的Pareto解進行下一次進化操作，從而形成一種多樣性保持機制。此外，本文借鑒免疫系統中記憶細胞池的概念，設立一個獨立的外部記憶庫來保留算法所求得的部分Pareto解。記憶庫中存儲的Pareto解在每代進化結束后更新。設定記憶庫中保留的Pareto最優解的最大個數為nmax2，當所得Pareto解的個數超過上限值時，按照同樣的方法選取nmax2個Pareto解加以保留。最終算法停止后，外部記憶庫中的Pareto解即算法所求得的所有Pareto解。

在這里有必要說明的是，從嚴格意義上講在MCSA中使用的術語Pareto解與傳統方式的含義有所不同。本算法中，每代都需要確定Pareto解，然而，由于每代種群中僅包含原始問題的部分解，Pareto解僅表示關于所有當前獲得的解的非支配點的含義。某一代中的非支配解可能被以后產生的新解支配。此外，在具體算法中忽略抗體和B細胞在概念上的差別，將其統稱為B細胞。

設多目標優化問題表述為

3仿真分析

為了驗證MCSA解決多目標優化問題的快速性、有效性以及Pareto解的分布性能，將該算法與目前世界上公認的比較好的NSGA－Ⅱ、SPEA和PAES算法進行比較。

本文選取專為測試多目標優化算法性能而設計的五個benchmark問題：ZDT1、ZDT2、ZDT3、ZDT4和ZDT6作為測試函數，其特點如表1所示。ZDT1和ZDT2分別有凸和凹的Pareto前沿； ZDT3的Pareto前沿由幾段不連續的凸線組成；ZDT4包含219個局部Pareto前沿，這個函數可以測試算法解決多峰問題的能力。由于搜索空間的不連續性使得求解ZDT6的Pareto前沿有兩個困難，即非劣解在Pareto前沿上分布不連續；越靠近Pareto前沿解的密度越低，反之越高。

表2給出了采用四種不同的優化方法，各計算30次，每次運行250代所得到的γ指標的平均值和方差。從表2可以看出，在所有五個問題的求解中，本算法與NSGA－Ⅱ、SPEA和PAES相比， MCSA能夠更快并且很好地收斂到多目標優化問題的Pareto 最優前沿面。

表3給出了采用四種不同的優化方法，各計算30次，每次運行250代所得到的Δ指標的平均值和方差。從表3可以看出，在ZDT1、ZDT2、ZDT4和ZDT6的求解中，MCSA所求的Pareto解的分布都明顯好于其他幾種算法。在ZDT3的求解中，MCSA所求解仍然具有較好的分布特征。

4結束語

本文基于克隆選擇原理提出了一種多目標優化克隆選擇算法MCSA，此算法的關鍵在于采用了Pareto最優解的選擇操作、高斯變異操作及外部最優保留策略。該算法充分體現了Pareto最優解的概念，具有并行搜索、群體規模動態調整及Pareto最優個體保存于群體外并不斷更新等特點。實驗結果表明，該算法具有參數少、結構簡單、適應性強、解的質量高、收斂速度快等優點。

參考文獻：

[1]DEV K. Optimization for engineering design: algorithms and examples[M]. New Delhi: Prentice－Hall， 1995.

[2]STEUER R E. Multiple criteria optimization: theory computation， and application[M]. New York: Wiley， 1986.

[3]PARETO V.Cours d’economie politique，volumeⅠand Ⅱ[M]. Lausanne: F. Rouge， 1896.

[4]FONSECA C M， FLEMING P J. An overview of evolutionary algorithms in multi－objective optimization[J]. Evolutionary Computation， 1995，3(1):1-16.

[5]ZITZLER E， THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE Trans on Evolutionary Computation， 1999，3(4):257-271.

[6]ZITZLER E， LAUMANNS M， THIELE L. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization[C]//Proc of Evolutionary Methods for Design， Optimization and Control with Applications to Industrial Problems. 2002:95－100.

[7]SRINIVAS N， DEB K. Multiobjective optimization using nondomina-ted sorting in genetic algorithms[J]. Evolutionary Computation， 1994，2(3):221-248.

[8]DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm: NSGA－Ⅱ [J]. IEEE Trans on Evolutio-nary Computation， 2002，6(2):182-197.

[9]De CASTRO L N， ZUBEN F J von. Learning and optimization using the clonal selection principle[J]. IEEE Trans on Evolutionary Computation， 2002，6(3):239-251.

[10]De CASTRO L N ， ZUBEN F J von. Artificial immune systems， part Ⅰ: basic theory and applications [EB/OL].(1999).http://www.dca.fee.unicamp.br/~lnunes/immune.htm.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”