基于免疫的多目標優化遺傳算法
2007-01-01 00:00:00翟雨生程志紅陳光柱李柳查蔓麗
計算機應用研究 2007年3期
摘 要：提出一種基于免疫的多目標優化遺傳算法。該算法模仿生物免疫系統過程，使用克隆選擇算子和高斯變異算子提高了搜索效率和收斂性；創建了一個記憶細胞集來保存每代所產生的Pareto最優解，以便產生Pareto最優解集；提出一種有別于傳統聚類算法的鄰近排擠算法對記憶細胞集進行不斷的更新及刪除，保證了Pareto最優解集的分布均勻性。最后將該算法與SPEA算法分別進行了仿真，通過比較兩者的收斂性和分布性，得到前者優于后者的結論。
關鍵詞：多目標優化； 遺傳算法； 克隆選擇算子； 高斯變異算子
中圖分類號：TP301文獻標志碼：A
文章編號：1001—3695(2007)03—0050—03
在科學和工程實踐中，許多問題具有多目標的特性，它們需要同時滿足幾個不同的目標，而這些目標間往往是相互沖突的，這類問題被稱為多目標優化問題(Multiobjective Optimization Problems， MOP)。與單目標優化問題的本質區別在于，MOP的解不是唯一的，而是存在一個最優解集合，集合中的元素稱為Pareto最優解。常規解決MOP的方法有多目標加權法、層次優化法、ε約束法、全局準則法、目標規劃法等[1]。這些算法的特點是將多目標轉換為單目標處理，但往往只能達到一個解而非Pareto最優解集。基于群體搜索的遺傳算法(Genetic Algorithms， GAs)非常適合于求解多目標優化問題，其原理在于遺傳算法可平行搜索多個目標，以及在搜索過程中可以將最優解保存到下一代群體。多目標遺傳算法(MultiObjective Genetic Algorithms， MOGAs)的研究已有十多年，到現在為止，人們已經提出多種多目標遺傳算法，如Srinivas 的NSGA[2]、Zitzler 的SPEA[3]、Knowles 的PAES[4]以及Deb 的NSGAⅡ[5]等。這些算法各有其優點，但也均有美中不足的地方。例如，NSGA算法的計算效率相對較低，未采用精英保留策略，共享參數σshare需要預先確定；NSGAⅡ雖然克服了NSGA的缺點，但它除了需要設置共享參數外，還需要選擇一個適當的錦標賽規模，限制了該算法的實際應用效果。
1 多目標優化問題
最大化問題與最小化問題可以相互轉換，因此，僅以最小化多目標問題為例。
定義1 多目標優化問題的定義：滿足約束條件的決策變量使目標向量函數最優，即尋找決策變量X=(x1，x2，…，xn)T（通常不止一個），使向量函數f(x)最優，最優的標準一般是取函數極小化。其數學描述為
則X*為Pareto最優解（或稱非劣解、有效解），最優解往往形成一個解集，稱為最優解集，也叫Pareto前沿。
最優解是各種多目標優化算法的基礎，為了從最優解集中選出特定的解或子集，或者說為了便于決策者的決策，要求最優解集要滿足兩個條件：①最優解集個數不能太少（太少可能漏掉有些有價值的最優解）也不能太多（太多的最優解使決策者無法比較選擇）；②最優解應盡量均勻分布在Pareto前沿面上。
2 基于免疫的多目標優化遺傳算法
2.1 相關知識
在自然界中，生物的進化過程通過選擇淘汰、突然變異、基因遺傳等規律產生適應環境變化的優良物種。達爾文進化論最重要的是適者生存的原理，它認為每一物種在發展中越來越適應環境，物種每種個體的基本特征由后代所繼承，但后代又會產生一些異于父代的新變化。在環境變化時，只有那些能適應環境的個體特征方能保留下來。
遺傳算法的基本思想是基于達爾文進化論的。它充分模擬了自然界優勝劣汰的自然選擇過程，它是建立在群體遺傳學基礎上的染色體復制、交叉和突變等，具有廣泛適應性的搜索方法。其基本思想是遺傳算法把問題的解表示成染色體，在算法中即是以二進制編碼或十進制編碼的串，并且在執行遺傳算法前，給出一群染色體，也即是假設解；把這些假設解置于問題的環境中，并按適者生存的原則，從中選擇出較適應環境的染色體進行復制，再通過交叉、變異過程產生更適應環境的新一代染色體群；這樣一代一代地進化，最后就會收斂到最適應環境的一個染色體上，它就是問題的最優解。
遺傳算法自提出到現在，由于其全局概率搜索性、自適應性、隱含并行性及廣泛通用性等優點，在各種問題的求解過程中獲得了廣泛的應用，體現了其優越特點和廣泛潛力。可標準的遺傳算法搜索效率低、收斂速度慢，這都制約了其在各方面的應用。
在生物免疫系統中，當外部細菌或病毒侵入機體后，能夠識別抗原的免疫細胞根據識別的程度通過無性繁殖（克隆）達到增生的目的：與抗原具有越高的親和力，該細胞就能產生更多的后代。增生后的免疫細胞中有些成為有效細胞，另外一些成為記憶細胞。有效細胞分泌大量抗體，能與抗原結合，殺死病原體；記憶細胞在生物體內繼續生存，直到再次遇到病原，然后分化。在細胞分裂過程中，個體細胞還經歷了一個變異的過程，其結果使它們與抗原具有更高的親和力：父代細胞與抗原具有越高的親和力，則它們將經歷越小的變異。
2.2 算法描述
基于免疫的多目標優化遺傳算法的基本框架仍是遺傳算法。其具體執行步驟如下：
（1）確定編碼方案。若決策變量的取值范圍明確時，可用二進制編碼；若決策變量取值范圍不明確或精度要求高時，應采用實數編碼。
（2）確定算法的控制參數。它包括初始群體規模n、記憶細胞集閾值T、選擇比例ξ、克隆規模N和高斯變異參數β。
（3）隨機生成初始抗體種群P（抗體個數為n）和初始記憶細胞集P′（初始為空）。
（4）對初始抗體種群P利用非劣解定義（對于多目標最小優化問題采用定義2），生成初步的非劣解集Pn（成熟細胞群）。
(5)將(4)產生的非劣解集Pn拷貝到記憶細胞集P′中（刪除重復抗體）。
（6）利用非劣解定義對記憶細胞集P′作進一步篩選。
（7）如果篩選后P′中抗體數超過一定閾值T，則根據下面所述的鄰近排擠算法刪除多余抗體。
鄰近排擠算法步驟如下：
其中，x′為變異后的抗體，x為變異前的抗體；N（0，1）是均值為0、方差為1的正態分布隨機變量；α是個體的變異率； f是每個個體的適應度值；β是一個參數，用來控制指數函數倒數的大小，以使每個變量變異后仍處于其定義域之內。
(11)隨機生成抗體種群Pt，個數為n-N。
(12)更新初始抗體種群，令P=Pt+P′t。
(13)若滿足終止條件，則結束循環；否則，返回到(4)。
(14)輸出記憶細胞P′中的抗體，結束。
該算法具有以下特征：
（1）借鑒SPEA中兩次利用非劣解定義的做法，進一步去除了混在記憶細胞集中不是非劣解的個體。
（2）借鑒2.1節所述生物免疫系統過程，在標準遺傳算法中引進克隆選擇算子。克隆選擇算子是在每一代群體中選擇適應度較好的個體進行克隆，適應度越高，個體在克隆時的規模越大。克隆選擇增大優良個體的比例減少了壞個體的影響，從而避免了搜索后期由于算法的盲目性和隨機性出現的退化早熟現象。
（3）算法中克隆選擇過程中的高頻變異采用進化策略中的高斯變異算子。從高斯變異式（9）和(10)可以看出，抗體的變異程度與適應度成反比，適應度值越低，個體的變異率越高。這樣個體在可行域上能朝著適應度值最好的點搜索。該算法沒有固定個體的變異率，而是通過自適應的方式，尋找到最好解，提高了收斂速度。
（4）模仿生物免疫系統中記憶細胞的功能，創建了一個記憶細胞集來保存每代群體所產生的Pareto最優解，以便形成Pareto最優解集，并提出了一種有別于傳統聚類算法的鄰近排擠算法以不斷更新記憶細胞集中的個體。鄰近排擠算法能使Pareto最優解集中的最優解均勻分布，后面的仿真實驗證明了它比傳統的聚類算法更能使Pareto最優解分布均勻，且運行時間明顯縮短。
（5）每代都會隨機產生n-N個新個體，增強了群體多樣性。
3 計算機仿真實驗
為了驗證MOGAI的有效性，將此算法與SPEA進行計算機實驗仿真比較。在比較中，對于SPEA，參數選擇定為：初始種群個數取70，交叉概率1.0，突變概率0，外部記憶細胞的規模為30，迭代次數為100；對于本文的MOGAI，采用二進制編碼，初始抗體群體個數n=70，記憶細胞閾值T=30， ξ=50，克隆規模N=50，高斯變異算子β=1，迭代次數為100。所測試的問題ZDT1如下，盡管該問題較簡單，但其為通用的測試問題，具有一定的代表性。
問題ZDT1：
分別應用本文的MOGAI和SPEA，求問題ZDT1的Pareto最優解，可獲得如圖1和2所示的Pareto最優解分布情況圖。
遺傳算法最重要的一個性能指標是其收斂性，而對于多目標優化問題，希望得到的Pareto最優解集盡量均勻分布在Pareto前沿面上。因此，本文分別從算法的收斂性和Pareto最優解集的分布性來比較MOGAI和SPEA，算法收斂性和Pareto最優解集分布性的度量指標均采用文獻[5]中的定義，分別用γ和Δ表示。在算法中加入求解γ和Δ的程序，計算出每代記憶細胞中的γ和Δ值，然后分別計算出它們的均值和方差，如表1所示。
從表1中可以看出，MOGAI的γ和Δ的均值及方差在一定程度上都好于算法SPEA，尤其表示分布性的Δ的均值明顯好于SPEA。另外，迭代次數相同時，MOGAI的運行時間明顯短于SPEA。這些都說明了MOGAI要優于SPEA，從而證明了本文算法MOGAI的有效性。
4 結束語
本文基于生物免疫原理提出了一種新型的多目標優化免疫算法MOGAI。該算法借鑒生物免疫系統過程，使用克隆選擇算子和高斯變異算子提高了搜索效率和收斂性；創建了一個記憶細胞集來保存每代所產生的Pareto最優解，以便產生Pareto最優解集；提出一種有別于傳統聚類算法的鄰近排擠算法對記憶細胞集進行不斷的更新、刪除，保證了Pareto最優解集的分布均勻性。然而本文只將MOGAI與SPEA作了比較，以后還需與其他典型的多目標優化算法進行比較，從而進一步完善該算法。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
