技術(shù)報(bào)告基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)進(jìn)化算法

1、計(jì)劃類別 項(xiàng)目編號(hào) 項(xiàng)目技術(shù)報(bào)告課題名稱 項(xiàng)目主持人 承擔(dān)單位 題目：基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)進(jìn)化算法針對(duì)免疫多目標(biāo)進(jìn)化算法分布性欠佳的缺陷，提出一種基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)進(jìn)化算法。基本思想是：對(duì)抗體群進(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)格方法；分布性1 引言（Introduction）20世紀(jì)70年代，Jerne最早建立了免疫網(wǎng)絡(luò)的數(shù)學(xué)模型。1996年12月，人工免疫系統(tǒng)（Artificial I

2、mmune System，AIS）概念正式提出。其后，人工免疫算法的研究進(jìn)入快速發(fā)展期。鑒于人工免疫算法天然的并行性，1998年，人工免疫算法即被引入多目標(biāo)優(yōu)化算法，并取得了眾多成果1。從此以后，人工免疫多目標(biāo)優(yōu)化算法便一直是智能計(jì)算領(lǐng)域中的一個(gè)研究熱點(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í)與識(shí)別。近年來，國內(nèi)學(xué)者在人工免疫算法特別是人工免疫多目標(biāo)優(yōu)化算法及應(yīng)用方面取得了一

3、系列的成果。錢淑渠6和劉若辰7等研究了動(dòng)態(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)用；柴爭(zhē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

4、 Evolution Algorithm，AGMIMOEA）。算法的設(shè)計(jì)依據(jù)是：利用自適應(yīng)網(wǎng)格方法進(jìn)一步提多目標(biāo)最優(yōu)解的多樣性。根據(jù)對(duì)比仿真實(shí)驗(yàn)和統(tǒng)計(jì)指標(biāo)，對(duì)該算法進(jìn)行了性能測(cè)試。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ù)雜度三個(gè)指標(biāo)。網(wǎng)格方法是保持多目標(biāo)進(jìn)化種群分布性的常用方法，在PESA、PAES、MGAMOO和DMOGA等方法中，算法的設(shè)計(jì)者均以不

5、同方式采用網(wǎng)格方法保持進(jìn)化種群的多樣性15。2003年，Knowles對(duì)網(wǎng)絡(luò)方法進(jìn)行了改進(jìn)，提出了自適應(yīng)網(wǎng)格方法。下面簡(jiǎn)要介紹自適應(yīng)網(wǎng)格方法。3.1 網(wǎng)絡(luò)邊界（Grid and boundary）根據(jù)網(wǎng)格方法，對(duì)于有個(gè)目標(biāo)的優(yōu)化問題，需要設(shè)置有個(gè)邊界的網(wǎng)格：下界和上界。如圖2所示是一個(gè)兩目標(biāo)網(wǎng)格，共有四個(gè)邊界：。根據(jù)進(jìn)化種群的規(guī)模和待優(yōu)化問題的目標(biāo)數(shù)，將一個(gè)網(wǎng)絡(luò)分割成若干個(gè)小區(qū)域，稱之為Hyper-Cube（HC）。將每個(gè)HC表示為，是每一維上的分割次數(shù)，通常為大于2的自然數(shù)。在圖2中，。對(duì)應(yīng)于每個(gè)的邊界可以表示為其中，為每一個(gè)小區(qū)域在第維上的寬度，為第維上的域?qū)?。若將域?qū)捲O(shè)為，則有，從而得上

6、邊界點(diǎn)為，下邊界點(diǎn)為。3.2 個(gè)體在網(wǎng)格中的定位（The location of the individualin the grid）在網(wǎng)格中設(shè)置小區(qū)域的目的是判斷個(gè)體是否落在小區(qū)域內(nèi)。設(shè)有個(gè)體，對(duì)區(qū)域，若且，則認(rèn)為個(gè)體在區(qū)域中。在圖2中，區(qū)域A中有三個(gè)個(gè)體，區(qū)域B中有一個(gè)個(gè)體，區(qū)域C中有兩個(gè)個(gè)體。在某個(gè)目標(biāo)上取最小的個(gè)體稱為極點(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)格方法對(duì)一般網(wǎng)格方法做了下列改進(jìn)：（1）網(wǎng)格的邊界是動(dòng)態(tài)的，不是固定的；（2）每次進(jìn)化時(shí)，根據(jù)當(dāng)前個(gè)體分布情況

7、自適應(yīng)地調(diào)整邊界；（3）若新個(gè)體在邊界外且為非支配的，則將其入到歸檔集中。4 基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)優(yōu)化算法（Immune multi-objective evolutionary algorithmbased 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 對(duì)進(jìn)行克?。?。步驟3 對(duì)以概率進(jìn)行免疫操作：。步驟4 對(duì)進(jìn)行選擇操作：。（1）對(duì)中的每個(gè)抗體

8、，通過計(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)化算法對(duì)兩個(gè)多目標(biāo)測(cè)試函數(shù)Deb2和DTLZ7進(jìn)行仿真計(jì)算，并將計(jì)算結(jié)果與NSGAII和常規(guī)免疫多目標(biāo)進(jìn)化算法（IMOEA）的計(jì)算結(jié)果進(jìn)行了比較。為了進(jìn)一步定量地評(píng)測(cè)基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)優(yōu)化算法的分布性，圖9和圖10分別給出了NSGAII、IMOEA和A

9、GMIMOEA的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)一步研究。對(duì)算法的改進(jìn)只能依賴對(duì)比實(shí)驗(yàn)，這無疑限制和阻礙了量子遺傳算法的進(jìn)一步研究。參考文獻(xiàn)（References）1 Coello C.A.，Crue Cort N.Solving multi-objective optimiz

10、ation problem using an artificial immune systemJ.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 strategiesJ.Information Sciences，2018，430-431：46-64.3 Maria-Guad

11、alupe Martnez-Pealoza，Efren Mezura-Montes.Immune Generalized Differential Evolution for dynamic multi-objective environments：An empirical studyJ.Knowledge-Based Systems，2018，142：192-219.4 Zhuhong Zhang，Xiaoxia Wang，Jiaxuan Lu.Multi-objective immune genetic algorithm solving nonlinear interval-valued

12、 programmingJ.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 networksJ.Future Generation Computer Systems，2018，82：256-267

13、.6 錢淑渠，張著洪.動(dòng)態(tài)多目標(biāo)免疫優(yōu)化算法及性能測(cè)試研究J.智能系統(tǒng)學(xué)報(bào)，2007，2（5）：68-77.7 劉若辰，馬亞娟，張浪.基于預(yù)測(cè)策略的動(dòng)態(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 柴爭(zhēng)義，陳亮，朱思峰.混沌免疫多目標(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-