基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)進(jìn)化算法

呂文鵬　許峰

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

關(guān)鍵詞：多目標(biāo)進(jìn)化；人工免疫；自適應(yīng)網(wǎng)格方法；分布性

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A

1 引言（Introduction）

20世紀(jì)70年代，Jerne最早建立了免疫網(wǎng)絡(luò)的數(shù)學(xué)模型。1996年12月，人工免疫系統(tǒng)（Artificial Immune System，AIS）概念正式提出。其后，人工免疫算法的研究進(jìn)入快速發(fā)展期。鑒于人工免疫算法天然的并行性，1998年，人工免疫算法即被引入多目標(biāo)優(yōu)化算法，并取得了眾多成果[1]。從此以后，人工免疫多目標(biāo)優(yōu)化算法便一直是智能計(jì)算領(lǐng)域中的一個研究熱點(diǎn)[2-5]。

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

本文提出了一種基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)優(yōu)化算法（Adaptive Grid Method Immune Multi-Objective Evolution Algorithm，AGMIMOEA）。算法的設(shè)計(jì)依據(jù)是：利用自適應(yīng)網(wǎng)格方法進(jìn)一步提多目標(biāo)最優(yōu)解的多樣性。根據(jù)對比仿真實(shí)驗(yàn)和統(tǒng)計(jì)指標(biāo)，對該算法進(jìn)行了性能測試。

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

常見的人工免疫算法有B細(xì)胞網(wǎng)絡(luò)算法、免疫遺傳算法、克隆選擇算法、免疫規(guī)劃算法等，算法的流程圖如圖1所示。

3 自適應(yīng)網(wǎng)格方法（Adaptive grid method）

衡量多目標(biāo)優(yōu)化算法通常有收斂性、分布性、計(jì)算復(fù)雜度三個指標(biāo)。網(wǎng)格方法是保持多目標(biāo)進(jìn)化種群分布性的常用方法，在PESA、PAES、MGAMOO和DMOGA等方法中，算法的設(shè)計(jì)者均以不同方式采用網(wǎng)格方法保持進(jìn)化種群的多樣性[15]。2003年，Knowles對網(wǎng)絡(luò)方法進(jìn)行了改進(jìn)，提出了自適應(yīng)網(wǎng)格方法。下面簡要介紹自適應(yīng)網(wǎng)格方法。

3.1 網(wǎng)絡(luò)邊界（Grid and boundary）

根據(jù)網(wǎng)格方法，對于有個目標(biāo)的優(yōu)化問題，需要設(shè)置有個邊界的網(wǎng)格：下界和上界。如圖2所示是一個兩目標(biāo)網(wǎng)格，共有四個邊界：。

根據(jù)進(jìn)化種群的規(guī)模和待優(yōu)化問題的目標(biāo)數(shù)，將一個網(wǎng)絡(luò)分割成若干個小區(qū)域，稱之為Hyper-Cube（HC）。將每個HC表示為，是每一維上的分割次數(shù)，通常為大于2的自然數(shù)。在圖2中，。對應(yīng)于每個的邊界可以表示為

其中，為每一個小區(qū)域在第維上的寬度，，為第維上的域?qū)挕?/p>

若將域?qū)捲O(shè)為，則有，從而得上邊界點(diǎn)為，下邊界點(diǎn)為。

3.2 個體在網(wǎng)格中的定位（The location of the individual

in the grid）

在網(wǎng)格中設(shè)置小區(qū)域的目的是判斷個體是否落在小區(qū)域內(nèi)。設(shè)有個體，對區(qū)域，若且，則認(rèn)為個體在區(qū)域中。

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

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

3.3 自適應(yīng)網(wǎng)格（Adaptive grid）

自適應(yīng)網(wǎng)格方法對一般網(wǎng)格方法做了下列改進(jìn)：

（1）網(wǎng)格的邊界是動態(tài)的，不是固定的；

（2）每次進(jìn)化時(shí)，根據(jù)當(dāng)前個體分布情況自適應(yīng)地調(diào)整邊界；

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

4 基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)優(yōu)化算法

（Immune multi-objective evolutionary algorithm

based on adaptive grid method）

為了進(jìn)一步提高常規(guī)免疫多目標(biāo)優(yōu)化算法的分布性，本文將自適應(yīng)網(wǎng)格方法引入免疫多目標(biāo)優(yōu)化算法，基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)進(jìn)化算法的流程如下：

步驟1 種群初始化。設(shè)定初始代數(shù)，進(jìn)化代數(shù)，抗體種群大小N，克隆規(guī)模大小R；初始化抗體群：

。

步驟2 對進(jìn)行克?。骸?/p>

步驟3 對以概率進(jìn)行免疫操作：。

步驟4 對進(jìn)行選擇操作：。

（1）對中的每個抗體，通過計(jì)算目標(biāo)函數(shù)值，得到函數(shù)值矩陣。

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

（3）選擇非支配抗體群及相應(yīng)的函數(shù)值矩陣。

步驟5 根據(jù)自適應(yīng)網(wǎng)格方法更新，得到新的抗體群：及函數(shù)值矩陣。

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

，返回步驟2。

5 數(shù)值實(shí)驗(yàn)結(jié)果（Numerical experiment results）

下面用基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)優(yōu)化算法對兩個多目標(biāo)測試函數(shù)Deb2和DTLZ7進(jìn)行仿真計(jì)算，并將計(jì)算結(jié)果與NSGAII和常規(guī)免疫多目標(biāo)進(jìn)化算法（IMOEA）的計(jì)算結(jié)果進(jìn)行了比較。

為了進(jìn)一步定量地評測基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)優(yōu)化算法的分布性，圖9和圖10分別給出了NSGAII、IMOEA和AGMIMOEA的U-measure圖。

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

6 結(jié)論（Conclusion）

本文為了提高免疫多目標(biāo)優(yōu)化算法的分布性，引入了自適應(yīng)網(wǎng)格方法。數(shù)值實(shí)驗(yàn)表明，改進(jìn)算法可在一定程度上改善算法的分布性和均勻性。

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

參考文獻(xiàn)（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] 錢淑渠，張著洪.動態(tài)多目標(biāo)免疫優(yōu)化算法及性能測試研究[J].智能系統(tǒng)學(xué)報(bào)，2007，2（5）：68-77.

[7] 劉若辰，馬亞娟，張浪.基于預(yù)測策略的動態(tài)多目標(biāo)免疫優(yōu)化算法[J].計(jì)算機(jī)學(xué)報(bào)，2015，38（5）：1544-1560.

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

[9] 劉楠楠.克隆選擇多目標(biāo)優(yōu)化算法及其應(yīng)用研究[D].寧波大學(xué)，2013.

[10] 武慧虹，錢淑渠，王海英.基于混沌克隆的混雜多目標(biāo)免疫優(yōu)化算法[J].吉林師范大學(xué)學(xué)報(bào)，2014，1：40-46.

[11] 王曉磊.多目標(biāo)人工免疫算法及其在無功優(yōu)化中的應(yīng)用[D].東北大學(xué)，2008.

[12] 柴爭義，陳亮，朱思峰.混沌免疫多目標(biāo)算法求解認(rèn)知引擎參數(shù)優(yōu)化問題[J].物理學(xué)報(bào)，2012，61（5）：1-7.

[13] 朱思峰，陳國強(qiáng)，張新剛.多目標(biāo)優(yōu)化量子免疫算法求解基站選址問題[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，40（1）：

49-53.

[14] 邢志偉，宋曉鵬，羅謙.基于多目標(biāo)免疫優(yōu)化的飛機(jī)滑行軌跡[J].計(jì)算機(jī)工程與設(shè)計(jì)，2016，37（5）：1224-1228.

[15] 鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，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-），男，碩士生.研究領(lǐng)域：進(jìn)化算法.

許 峰（1963-），男，碩士，教授.研究領(lǐng)域：進(jìn)化算法，數(shù)值計(jì)算.