基于Ｐａｒｅｔｏ的多目標進化免疫算法

(1.上海大學 計算機工程與科學學院 上海 200072; 2.上海大學 悉尼工商學院 上海 201800)

摘 要：提出一種新的基于Pareto多目標進化免疫算法（PMEIA）。算法在每一代進化群體中選取最優非支配抗體保存到記憶細胞文檔中；同時引入Parzen 窗估計法計算記憶細胞的熵值，根據熵值對記憶細胞文檔進行動態更新，使算法向著理想Pareto最優邊界搜索。此外，算法基于點在目標空間分布情況進行克隆選擇，有利于得到分布較廣的Pareto最優邊界，且加快了收斂速度。與已有算法相比，PMEIA在收斂性、多樣性，以及解的分布性方面都得到很好的提高。

關鍵詞：進化免疫； Pareto最優解; 基于信息熵的密度估計； 克隆選擇

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

文章編號：1001-3695(2009)05-1687-04

Paretobased multiobject evolutionary immune algorithm

TAO Yuan1 WU Gengfeng1 HU Min2

(1.College of Computer Science Engineering Shanghai University Shanghai 200072，China; 2.Sydney Institute of Language Commerce Shanghai University Shanghai 201800 China)

Abstract:This paper proposed a new paretobased multiobject evolutionary immune algorithm（PMEIA）. PMEIA selected optimal nondominated antibodies which were then reserved in memory cell archive and introduced Parzen window to calculate entropy of memory cells. Updated the memory cell archive according to entropy of memory cells. This guarantees the convergence to the true Pareto front. Moreover the performance of clone selection was dependent on distribution in the objective space which was favorable for getting a widely spread Pareto front and improving convergence speed. Compared with the existed algorithmsthe obtained solutions of PMEIA have much better performance in the convergence，diversity and distribution.

Key words：evolutionary immune; Pareto optimal solution; entropybased density assessment; clone selection

近來 多目標進化算法（multiobject evolution algorithm，MEA）已成為解決多目標優化問題的主要工具，如Zitzler等人^[1]提出的SPEA和Knowles等人^[2]提出的PAES使用了精英保留策略的進化算法。采用進化算法求解多目標優化問題的優勢是：在多目標進化算法中，保留上一代非支配集，并使之參與新一代的多目標進化操作，從而使新一代的非支配集不比上一代差。這樣，一代一代進化下去，進化群體的非支配集不斷地逼近真正的最優邊界。

目前MEA 處理多目標優化問題的局限在于:a)主要是模仿生物自身的進化過程，沒有（或很少）考慮進化環境對進化的作用；b)主要針對確定的多目標優化問題而設計，而在現實世界中，許多多目標優化問題是不確定的；c）對初始種群分布有較強的依賴性，在群體分布不均時，易出現群體多樣性差的現象。因此尋求既能自我調節群體多樣性又能解決不確定性問題的MEA已成為計算智能領域研究的重要課題。

生物免疫系統面臨的環境完全是不確定的、時變的，外界入侵物（抗原）的形式幾乎是無限的，而免疫系統對已知和未知的抗原均能出色防御，被認為是已知的最精妙復雜的身體抵御外部物質的系統。人工免疫系統（AIS）作為模擬免疫學功能、原理和模型來解決復雜問題的自適應系統具有學習、記憶、自適應、自組織、分布性以及群體多樣性等特點，能很好地彌補進化算法求解多目標優化問題存在的缺陷。

AIS成功地被應用到解決各種優化問題，并且它擁有的各種免疫特性能解決進化算法的早熟問題及提高局部搜索能力。AIS采用不同的方法解決優化問題，如Cutello等人^[3]的基于克隆選擇原理，及Toma等人^[4]基于免疫網絡原理開發的AIS。但是，AIS在單目標優化問題上的成功并沒有很好地延伸到多目標優化領域，因為解決多目標優化問題的技術需要維持解集合的多樣性和均一分布。本文基于克隆選擇學說提出了一種新的基于Pareto的多目標進化免疫算法（PMEIA）。PMEIA具有更好的全局搜索能力和收斂能力，所得最優點在目標空間有更好的分散性和分布性。

1 多目標優化問題

多目標優化問題描述如下^[5]：

給定決策向量X=(x1，x2，…，xn)，它滿足下列約束：

gi(X)≥0，i=1，2，…，k(1)

hi(x)=0，i=1，2，…，l（2）

設有r個優化目標，且這r個優化目標是相互沖突的。優化目標可表示為

f(X)=(f1(X) f2(X)，… fr(X))（3）

尋求X=(x1，x2，…，xn)，使f(X)在滿足式（1）和（2）的同時達到最優。

多目標優化問題中的最優解通常稱為Pareto最優解，它由Vilfredo Pareto在1896年提出的，因此被命名為Pareto最優解。

定義1 給定一個多目標優化問題f(X)，其最優解X定義為

在求解多目標優化問題中的最優解通常稱為Pareto最優解。一個多目標優化問題的Pareto最優解集在其目標函數空間中的表現形式是它的Pareto最優邊界。

定義3 個體之間的支配關系。設p和q是進化群體pop中的任意兩個不同個體，稱p支配q，則必須滿足下列兩個條件：

a)對所有的子目標 p不比q差，即fk(p)≤fk(q)(k=1，2，…，r);b)至少存在一個子目標，使p比q好，即l∈{1，2，…，r}，使fl(p)＜fl(q)。其中r為子目標的數量。

此時稱p為非支配的，q為被支配的，表示為pq。其中“”是支配關系。

2 基于Pareto的多目標進化免疫算法PMEIA

多目標優化問題的基本要素如多目標優化問題、候選解、抗體抗原的匹配能力等與生物免疫系統之間的對應關系如表1所示。

2.1 PMEIA算法的流程

在PMEIA算法中 優化問題的目標函數對應于入侵抗原 免疫系統產生的抗體則代表了優化問題的解。親合力計算有兩種形式：一種反映了抗體與抗原之間的關系，即解和目標的匹配程度；另一種則反映了抗體與抗體之間的關系，從而保證了免疫算法具有抗體多樣性。算法具體流程如圖1所示。

算法具體描述如下：

a)隨機產生初始抗體群體X，并設初始記憶文檔M為空。

b)基于目標函數評價所有抗體，將非支配抗體移到記憶文檔M中，并將子目標最優解保留到記憶文檔M中。

c)更新記憶文檔。如果候選解不被記憶細胞支配，則轉為記憶細胞。并且，任何被這個解支配的記憶細胞將被降級為進化群體中的一員。當記憶文檔達到最大存儲容量時，采用本文提出的基于信息熵的密度估計方法移除最無效的記憶細胞。

d)如果滿足停止標準即達到最大進化代數，記憶文檔就是所需要的解，結束；否則設n=n+1，并執行e)。

e)克隆選擇。根據親和力由低到高進行排序，然后選取前a%的抗體。

f)動態繁殖。根據抗體在e)排序后所得序列中的位置來計算所選抗體的克隆數目。

g)變異。對得到的克隆抗體群采用以下規則變異。

h)采用以下規則清除進化群體同一和相似的抗體。

d(Abi，Abj)＜σ1，Abj∈X(7)

其中：d(x，y)表示x與y的歐氏距離，當x與y的距離小于σ1時清除y。

i)動態選擇。根據抗體的激勵度由大到小選取與進化群體個數相同的抗體組成新的進化抗體群。

2.2 算法關鍵技術的實現

2.2.1 基于信息熵的密度估計

本文采用基于信息熵的密度估計方法來維持非支配解的均一分布和對記憶文檔的動態更新，引入Parzen 窗估計法來計算熵值。并且，在目標空間而不是在決策空間進行密度估計。熵值量化每一個細胞對記憶文檔的信息分布貢獻，具有的熵值越大，記憶細胞沿著Pareto最優邊界分布越均勻。

定義記憶文檔M包含｜M｜個記憶細胞或非支配抗體，定義記憶細胞的概率 pmi為

pmi=p(mi∈M)(8)

則細胞的熵值E(mi)為

E(mi)=-pmi log pmi(9)

Parzen窗估計法是一種具有堅實理論基礎和優秀性能的非參數函數估計方法 它能夠較好地描述多維數據的分布狀態 其基本思想就是利用一定范圍內各點密度的平均值對總體密度函數進行估計。Parzen 窗定義如下

細胞的概率密度估計為

(X)=1/｜X｜∑｜X｜i=1 1/σm K((X-xi)/σ)（10）

一般可以選擇的窗函數有方窗、正態窗等?；谙铝性?本文選擇正態窗作為核函數:

a)正態函數的平滑性將使得估計函數變化平滑。

b)如果選擇完全對稱的正態函數 估計函數中只有一個參量變化。

K(X)=1/(2π)m/2 ｜σ｜m exp (-XT X/2)(11)

這里設記憶文檔的容量有限。因為隨著時間及外界環境的變化，之前保存的記憶細胞可能變得無效。當記憶文檔達到最大存儲量時，根據熵值移去熵值最小、最無效的記憶細胞。這樣，通過對有限記憶文檔的動態更新，既節省資源，也可清楚地記憶文檔中的冗余及無效記憶細胞，充分考慮了進化環境對進化的作用。此外，任何被清除出記憶文檔的記憶細胞將降級為當前進化群體中的一員，這既確保了記憶文檔的動態更新，也盡量避免丟失信息。

2.2.2 克隆選擇

依據抗體與抗原的親和力進行克隆選擇，根據親和力選取前a%的抗體參與下一步的動態繁殖。定義抗體親和力：

aff(Ab)=exp (-〈F(Ab)，F(Ab)〉)(13)

其中：〈，〉表示內積。在目標空間而不是在決策空間計算親和力，綜合考慮了在目標空間點的分布情況。此外，選取的比例 a隨著進化群體的平均濃度動態調控。

α=｜X｜/(1+exp(δc))（14）

其中：0＜δ＜1；｜X｜為X中抗體的個數；c為X中所有抗體的平均濃度。其既確保了本代中好的抗體進化下一代，也充分考慮了抗體的濃度，避免搜索局限于局部空間。

2.2.3 動態繁殖

根據親和力由高到低排序后的抗體在序列中的位置計算其克隆數目NiC。

NiC=「(Pi[npop×b-(n pop-1)]+(npop-1))/npop(15)

其中:Pi=affi/ ∑npopk=1affk（16）

npop是抗體種群大?。华玝是定義的最好抗體的最大克隆數。

從式（14）可見，所選取細胞的克隆數目與其親和力值成正比，且1≤NiC≤b。以下給出式（14）的證明。

證明 因為0≤Pi≤1，當Pi=1（取最大值時）

NiC=「([npop×b-(npop-1)]+(npop-1))/npop

所以NiC=b（最大克隆數），當Pi=0（取最小值時），NiC= 「(npop-1)/npop。故NiC=1 （最小克隆數）。

2.3.4 動態選擇 

根據抗體的激勵度^[6]選取新的進化群體，對抗體親和力及細胞濃度進行綜合考抗體濃度：

c(Abi)=｜{x∈A｜d(x，Abi)＜σ2}｜/｜X｜（17）

其中:0＜σ2＜1；d(x，y)表示x與y的歐氏距離。

抗體的激勵度：

act(Abi)=aff(Abi)exp(-βc(Abi))（18）

其中：0＜β＜1。抗體的激勵度越高，它的全局響應能力越強。

3 性能評價指標

本文采用如下三個量化標準來評價算法性能。它們分別由Deb、Veldhuizen和Zitzler等人提出，并被廣泛用于評價和比較多目標優化算法的性能。

a）GD用于評價非支配解集和Pareto最優解集在目標向量空間上的距離：GD=(1/n ∑

MS指標越大表示所得非支配解集分散性越好。

在上述評價式中，n是優化方法所得到的非支配解的個數；Di為第i個解到Pareto最優解集在目標空間上的最短距離；di是第i個解到其他解在目標空間上的最短距離；d為di的平均值；M是給定的優化目標個數。

4 仿真實驗與結果分析

4.1 測試問題與算法比較

為了測試算法的性能，選取了ZDT6與FON兩個基準測試問題進行測試，并將本文的PMEIA與經典的IMOEA^[7]、SPEA2^[8]和PAES進行比較。

F1 測試問題ZDT6描述如下：

對于每一個測試函數，四種算法初始種群均為50，記憶文檔大小定義為300。圖2和3中各子圖中的點為各算法搜索到的最優解。表2和3為評價結果。

從圖2可知，PMEIA所搜索到的最優解與其他三種算法相比數量更多，分布更均勻。并且從表2的數值結果可知，PMEIA與其他三種算法相比，具有較好的收斂性，且所得最優點在目標空間具有更好的分散性和分布性。

從圖3可知，IMOEA、SPEA2和PAES只能找到部分最優邊界，且其中所找到的部分最優解并非為真正的最優解，而PMEIA能找到整個最優邊界。從表3的數值結果可知，算法PMEIA與其他三種算法相比，具有較好的收斂性，且所得最優點在目標空間具有更好的分散性和分布性。

5 結束語

本文提出一種新的用于求解多目標優化問題的算法PMEIA。算法與以往的多目標優化算法相比具有三個特點：a)引入Parzen窗估計法來計算熵值，根據熵值對記憶細胞文檔進行動態更新，清除最無效的記憶細胞，充分考慮了進化環境對進化的作用；b)基于點在目標空間分布情況進行克隆選擇，確保了進化群體的多樣性；c)通過對抗體親和力及細胞濃度進行綜合考慮來選取新的進化群體，這樣不僅使具有較強全局響應能力的抗體參與下一輪進化，也開拓了進化群體的搜索領域。

仿真實驗表明PMEIA具有很強的全局搜索能力、較強的收斂性以及很好的解的分布性。下一步工作的重點是設計更加有效的算法來解決有強約束更高維的多目標優化問題。

參考文獻：

［1］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.

[2]KNOWLES J D CORNE D W. Approximating the nondominated front using the Pareto archived evolution strategy[J]. Evolutionary Computation 2000，8(2):149-172.

[3]CUTELLO V NICOSIA G PARVONE M. Exploring the capability of immune algorithms: a characterization of hypermutation operators[C]//Proc of the 3nd International Conference on Artificial Immune Systems.Berlin: SpringerVerlag 2004:263-276.

[4]TOMA N ENDO S YAMADA K et al. Evolutionary optimization algorithm using MHC and immune network[C]//Proc of the 26th IEEE Annual Conference. Nagoya: Industrial Electronics Society，2000:2849-2854.

[5]鄭金華．多目標進化算法及其應應用[M]. 北京：科學出版社，2007:1-10.

[6]黃席樾，張著洪，何傳江，等. 現代智能算法理論及應用[M]. 北京：科學出版社，2004:138-141.

[7]TAN K C LEE T H KHOR E F. Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization[J]. IEEE Trans on Evolutionary Computation 2001，5(6):565-588.

[8]ZITZLER E LAUMANNS M THIELE L. SPEA2: improving the strength Pareto evolutionary algorithm，technical report 103[R]. Zurich:Computer Engineering and Networks Laboratory (TIK) Swiss Federal Institute of Technology (ETH) 2001.