基于自適應網格方法的免疫多目標進化算法

呂文鵬　許峰

摘 要：針對免疫多目標進化算法分布性欠佳的缺陷，提出一種基于自適應網格方法的免疫多目標進化算法?；舅枷胧牵簩贵w群進行免疫克隆、免疫基因和克隆選擇操作后，利用自適應網格方法提高抗體群的多樣性。仿真實驗結果和統計指標顯示，改進算法與常規免疫多目標進化算法相比較，在解的分布性方面有了較大程度的改進。

關鍵詞：多目標進化；人工免疫；自適應網格方法；分布性

中圖分類號：TP312 文獻標識碼：A

1 引言（Introduction）

20世紀70年代，Jerne最早建立了免疫網絡的數學模型。1996年12月，人工免疫系統（Artificial Immune System，AIS）概念正式提出。其后，人工免疫算法的研究進入快速發展期。鑒于人工免疫算法天然的并行性，1998年，人工免疫算法即被引入多目標優化算法，并取得了眾多成果[1]。從此以后，人工免疫多目標優化算法便一直是智能計算領域中的一個研究熱點[2-5]。

早在1991年，西安交通大學的靳蕃教授就指出“免疫系統所具有的信息處理和防衛功能具有非常深遠的意義”。2002年，莫宏偉出版了國內第一本人工免疫系統著作。西安電子科技大學焦李成教授領導的團隊系統、全面地研究了人工免疫優化算法，并出版了專著《免疫優化計算學習與識別》。近年來，國內學者在人工免疫算法特別是人工免疫多目標優化算法及應用方面取得了一系列的成果。錢淑渠[6]和劉若辰[7]等研究了動態多目標免疫優化算法；林滸[8]等研究了適應度共享多目標優化免疫克隆算法；劉楠楠[9]較為系統地研究了克隆選擇多目標優化算法；武慧虹[10]等研究了基于混沌克隆的混雜多目標免疫優化算法；王曉磊[11]研究了多目標人工免疫算法在無功優化中的應用；柴爭義[12]等研究了混沌免疫多目標算法在認知引擎參數優化問題中的應用；朱思峰[13]等研究了多目標優化量子免疫算法在基站選址問題中的應用；邢志偉[14]等研究了多目標免疫優化算法在飛機滑行軌跡中的應用。

本文提出了一種基于自適應網格方法的免疫多目標優化算法（Adaptive Grid Method Immune Multi-Objective Evolution Algorithm，AGMIMOEA）。算法的設計依據是：利用自適應網格方法進一步提多目標最優解的多樣性。根據對比仿真實驗和統計指標，對該算法進行了性能測試。

2 人工免疫算法（Artificial immune algorithm）

常見的人工免疫算法有B細胞網絡算法、免疫遺傳算法、克隆選擇算法、免疫規劃算法等，算法的流程圖如圖1所示。

3 自適應網格方法（Adaptive grid method）

衡量多目標優化算法通常有收斂性、分布性、計算復雜度三個指標。網格方法是保持多目標進化種群分布性的常用方法，在PESA、PAES、MGAMOO和DMOGA等方法中，算法的設計者均以不同方式采用網格方法保持進化種群的多樣性[15]。2003年，Knowles對網絡方法進行了改進，提出了自適應網格方法。下面簡要介紹自適應網格方法。

3.1 網絡邊界（Grid and boundary）

根據網格方法，對于有個目標的優化問題，需要設置有個邊界的網格：下界和上界。如圖2所示是一個兩目標網格，共有四個邊界：。

根據進化種群的規模和待優化問題的目標數，將一個網絡分割成若干個小區域，稱之為Hyper-Cube（HC）。將每個HC表示為，是每一維上的分割次數，通常為大于2的自然數。在圖2中，。對應于每個的邊界可以表示為

其中，為每一個小區域在第維上的寬度，，為第維上的域寬。

若將域寬設為，則有，從而得上邊界點為，下邊界點為。

3.2 個體在網格中的定位（The location of the individual

in the grid）

在網格中設置小區域的目的是判斷個體是否落在小區域內。設有個體，對區域，若且，則認為個體在區域中。

在圖2中，區域A中有三個個體，區域B中有一個個體，區域C中有兩個個體。

在某個目標上取最小的個體稱為極點。由于極點總是在端點，有利于使得進化種群具有更好的分布性，所以在選擇時，通常不能丟失極點。極點的定義為

3.3 自適應網格（Adaptive grid）

自適應網格方法對一般網格方法做了下列改進：

（1）網格的邊界是動態的，不是固定的；

（2）每次進化時，根據當前個體分布情況自適應地調整邊界；

（3）若新個體在邊界外且為非支配的，則將其入到歸檔集中。

4 基于自適應網格方法的免疫多目標優化算法

（Immune multi-objective evolutionary algorithm

based on adaptive grid method）

為了進一步提高常規免疫多目標優化算法的分布性，本文將自適應網格方法引入免疫多目標優化算法，基于自適應網格方法的免疫多目標進化算法的流程如下：

步驟1 種群初始化。設定初始代數，進化代數，抗體種群大小N，克隆規模大小R；初始化抗體群：

。

步驟2 對進行克?。?。

步驟3 對以概率進行免疫操作：。

步驟4 對進行選擇操作：。

（1）對中的每個抗體，通過計算目標函數值，得到函數值矩陣。

（2）將劃分為支配抗體群和非支配抗體群。

（3）選擇非支配抗體群及相應的函數值矩陣。

步驟5 根據自適應網格方法更新，得到新的抗體群：及函數值矩陣。

步驟6 若，則輸出及；否則

，返回步驟2。

5 數值實驗結果（Numerical experiment results）

下面用基于自適應網格方法的免疫多目標優化算法對兩個多目標測試函數Deb2和DTLZ7進行仿真計算，并將計算結果與NSGAII和常規免疫多目標進化算法（IMOEA）的計算結果進行了比較。

為了進一步定量地評測基于自適應網格方法的免疫多目標優化算法的分布性，圖9和圖10分別給出了NSGAII、IMOEA和AGMIMOEA的U-measure圖。

圖3—圖10直觀表明，AGMIMOEA在解的分布性和均勻性方面均明顯優于NSGA II和IMOEA。

6 結論（Conclusion）

本文為了提高免疫多目標優化算法的分布性，引入了自適應網格方法。數值實驗表明，改進算法可在一定程度上改善算法的分布性和均勻性。

必須指出的是，人工免疫算法理論體系尚不完善，收斂性和分布性等關鍵理論問題有待進一步研究。對算法的改進只能依賴對比實驗，這無疑限制和阻礙了量子遺傳算法的進一步研究。

參考文獻（References）

[1] Coello C.A.，Crue Cort N.Solving multi-objective optimization problem using an artificial immune system[J].Genetic Programming and Evolvable Machine，2005，6：163-190.

[2] Qiuzhen Lin，Yueping Ma，Jianyong Chen.An adaptive immune-inspired multi-objective algorithm with multiple differential evolution strategies[J].Information Sciences，2018，430-431：46-64.

[3] Maria-Guadalupe Martínez-Pealoza，Efren Mezura-Montes.Immune Generalized Differential Evolution for dynamic multi-objective environments：An empirical study[J].Knowledge-Based Systems，2018，142：192-219.

[4] Zhuhong Zhang，Xiaoxia Wang，Jiaxuan Lu.Multi-objective immune genetic algorithm solving nonlinear interval-valued programming[J].Engineering Applications of Artificial Intelligence，2018，67：235-245.

[5] Bin Cao，Jianwei Zhao，Po Yang.Distributed parallel cooperative coevolutionary multi-objective large-scale immune algorithm for deployment of wireless sensor networks[J].Future Generation Computer Systems，2018，82：256-267.

[6] 錢淑渠，張著洪.動態多目標免疫優化算法及性能測試研究[J].智能系統學報，2007，2（5）：68-77.

[7] 劉若辰，馬亞娟，張浪.基于預測策略的動態多目標免疫優化算法[J].計算機學報，2015，38（5）：1544-1560.

[8] 林滸，彭勇.面向多目標優化的適應度共享免疫克隆算法[J].控制理論與應用，2011，28（2）：206-214.

[9] 劉楠楠.克隆選擇多目標優化算法及其應用研究[D].寧波大學，2013.

[10] 武慧虹，錢淑渠，王海英.基于混沌克隆的混雜多目標免疫優化算法[J].吉林師范大學學報，2014，1：40-46.

[11] 王曉磊.多目標人工免疫算法及其在無功優化中的應用[D].東北大學，2008.

[12] 柴爭義，陳亮，朱思峰.混沌免疫多目標算法求解認知引擎參數優化問題[J].物理學報，2012，61（5）：1-7.

[13] 朱思峰，陳國強，張新剛.多目標優化量子免疫算法求解基站選址問題[J].華中科技大學學報（自然科學版），2012，40（1）：

49-53.

[14] 邢志偉，宋曉鵬，羅謙.基于多目標免疫優化的飛機滑行軌跡[J].計算機工程與設計，2016，37（5）：1224-1228.

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

[16] Knowles Joshus，David W Corne.Properties of an adaptive archiving algorithm for storing nondominated vectors[J].IEEE Transaction on Evolutionary Vomputation，2003，7（2）：100-115.

作者簡介：

呂文鵬（1992-），男，碩士生.研究領域：進化算法.

許 峰（1963-），男，碩士，教授.研究領域：進化算法，數值計算.