一種混合人工免疫算法的研究

張安玲，鄧啟森

（1．長(zhǎng)治學(xué)院 數(shù)學(xué)系，山西 長(zhǎng)治046011；2．中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山西 太原030051）

0 引 言

人工免疫理論是借鑒生物免疫系統(tǒng)的機(jī)理來(lái)建立人工免疫系統(tǒng)，并用于解決現(xiàn)實(shí)問(wèn)題的理論和方法，是繼神經(jīng)網(wǎng)絡(luò)、遺傳算法后，從生物系統(tǒng)提取的又一智能化理論，是目前人工智能研究的熱點(diǎn)之一．人工免疫系統(tǒng)的應(yīng)用研究涉及控制、優(yōu)化、機(jī)器學(xué)習(xí)、故障診斷和機(jī)器人路徑規(guī)劃等多個(gè)領(lǐng)域［1－4］．

人工免疫算法為基于種群的隨機(jī)搜索算法，它具有強(qiáng)大的信息處理和問(wèn)題求解能力等優(yōu)點(diǎn)．但它在進(jìn)化中可能會(huì)出現(xiàn)退化現(xiàn)象，從而導(dǎo)致收斂速度較慢，不能以較大的概率收斂到全局最優(yōu)值，算法的收斂性和穩(wěn)定性有待進(jìn)一步分析，以及算法的執(zhí)行效率還有待提高［5］．國(guó)內(nèi)外學(xué)者為此展開(kāi)了許多研究：Gong和Jiao等人提出了一種SRCPA 算法［6］，有效地提高了算法的運(yùn)行速度．Toyoo Fukda等在文獻(xiàn)［7］中給出了一個(gè)關(guān)于信息熵的免疫算法．韓國(guó)Jang 和Chun博士等在文獻(xiàn)［8］中提出了利用高級(jí)免疫算法進(jìn)行永磁同步電機(jī)參數(shù)優(yōu)化設(shè)計(jì)．文獻(xiàn)［9］提出了DKBAIA 算法，能改善算法的收斂性．文獻(xiàn)［10］基于克隆選擇原理和免疫網(wǎng)絡(luò)理論，實(shí)現(xiàn)了一種多模態(tài)免疫優(yōu)化算法．

本文欲在提高收斂速度和收斂性能兩方面作些探討，從人工免疫算法和經(jīng)典算法的特點(diǎn)出發(fā)，設(shè)計(jì)了一種基于毆氏距離的自適應(yīng)人工免疫算法和BFGS算法相聯(lián)合的混合算法．此算法繼承了人工免疫算法的群體搜索性，具有全局優(yōu)化能力；同時(shí)在人工免疫算法中引入BFGS算法，使之能發(fā)揮傳統(tǒng)數(shù)值優(yōu)化算法在運(yùn)算速度和求解精度上的優(yōu)勢(shì)，從而有效地提高算法的局部搜索能力和運(yùn)行效率．

1 混合人工免疫算法

1．1 標(biāo)準(zhǔn)人工免疫算法

標(biāo)準(zhǔn)人工免疫算法是將生物免疫學(xué)和計(jì)算機(jī)科學(xué)相結(jié)合而形成的．該算法的具體步驟如下［11］：①抗原識(shí)別．輸入目標(biāo)函數(shù)．②初始化．隨機(jī)產(chǎn)生初始群體，生成N 個(gè)抗體．③計(jì)算抗體的適應(yīng)度．④記憶庫(kù)更新．⑤抗體的選擇（促進(jìn)和抑制）．⑥交叉和變異．⑦群體更新．⑧終止．若達(dá)到終止條件則停止迭代，否則轉(zhuǎn)到第③．

1．2 BFGS算法

BFGS算法是由Broyden，F(xiàn)letcher，Goldfarb等于1970年提出的［12］．目前BFGS算法被公認(rèn)為是最好的擬牛頓法［12］．

BFGS算法的計(jì)算步驟：

1）給出x0∈Rn，H0∈Rn×n，0≤ε＜1，k：＝0．

2）如果‖gk‖ ≤ε，則停止；否則，計(jì)算dk＝－Hkgk．

3）沿方向dk作線性搜索求αk＞0，令xk＋1＝xk＋αkdk．

4）利用

求Hk＋1，使得擬牛頓條件Hk＋1yk＝sk成立．

5）若k：＝k＋1，則轉(zhuǎn)第2）．

BFGS算法不僅計(jì)算精度高，而且具有很好的數(shù)值穩(wěn)定性．

1．3 混合免疫算法

1．3．1 參數(shù)設(shè)置

1）編碼方式本文采用的均是二進(jìn)制編碼．

2）交叉率pc和變異率pm［13］

式中：0≤ki≤1，i＝1，2，3，4；f（x）表示適應(yīng)度；表示平均適應(yīng)度；fmax（x）表示最大適應(yīng)度．

3）抗體濃度和抗體期望繁殖率

定義1 在特定的抗體群中，給定抗體v，其與抗體群中任一抗體w 的毆氏距離記為d（v，w）＝‖v－w‖［14］．

定義2 抗體v，w 的適應(yīng)度記為Fv和Fw，對(duì)應(yīng)所求解的問(wèn)題給定適當(dāng)?shù)某?shù)r＞0，m＞0，若有

成立，則稱抗體w 與抗體v相似；與抗體v相似的抗體（包括v）的個(gè)數(shù)稱為抗體v 的濃度，記為Cv［14］．

定義3 對(duì)于特定的規(guī)模為N 的抗體群，抗體v的期望繁殖率可用式（3）算出

式中：Fv為抗體v 的適應(yīng)度；Cv為抗體v 的濃度［14］．

1．3．2 混合人工免疫算法

標(biāo)準(zhǔn)人工免疫算法是一種全局性概率搜索算法，但它的收斂性、穩(wěn)定性以及算法的執(zhí)行效率還有待進(jìn)一步提高．為此，對(duì)標(biāo)準(zhǔn)人工免疫算法進(jìn)行了改進(jìn)，以提高算法的收斂性和運(yùn)行速度．

1）抗原識(shí)別．

2）初始化．隨機(jī)產(chǎn)生初始群體，生成N 個(gè)抗體．

3）抗體適應(yīng)度的計(jì)算．

4）記憶庫(kù)更新．用最大適應(yīng)度值對(duì)應(yīng)的抗體替換記憶庫(kù)中比其適應(yīng)度值低的任一抗體．記n（n＜N）為記憶庫(kù)中抗體的規(guī)模．

5）抗體的選擇（促進(jìn)和抑制）．利用式（3）所得的抗體v的期望繁殖率進(jìn)行選擇．

6）交叉和變異．分別采用1）和2）自適應(yīng)變化的交叉率和變異率對(duì)抗體進(jìn)行單點(diǎn)交叉和變異．

7）BFGS算法運(yùn)算．對(duì)群體中每個(gè)抗體以概率ps進(jìn)行一次BFGS 算法運(yùn)算，將子代取代父代；對(duì)記憶庫(kù)中的每個(gè)抗體進(jìn)行一次BFGS算法運(yùn)算，將子代取代父代．

8）計(jì)算抗體的適應(yīng)度．

9）群體更新．用記憶庫(kù)中的抗體代替群體中適應(yīng)度值比其低的抗體．

10）終止．若達(dá)到終止條件則停止迭代，且輸出記憶庫(kù)中的最好抗體作為最優(yōu)解；否則轉(zhuǎn)到第4）．

注1 在此混合算法中，每個(gè)抗體是以概率ps進(jìn)行BFGS算法運(yùn)算，這樣提高了算法的運(yùn)算效率．

注2 用記憶庫(kù)中的抗體替換群體中比其適應(yīng)度值小的抗體，增強(qiáng)了記憶庫(kù)中抗體的功能，避免了迭代過(guò)程中因隨機(jī)性而使最好抗體丟失，從而提高了全局收斂性．

2 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證本文算法的有效性，給出以下測(cè)試函數(shù)．

利用Matlab對(duì)以上4個(gè)函數(shù)分別運(yùn)算30次，與各測(cè)試函數(shù)真實(shí)最優(yōu)解的方差及平均收斂時(shí)間如表1 所示．

表1 方差與平均收斂時(shí)間Tab．1 Variance and average convergence time

從表1 可以看出，本文算法計(jì)算出的函數(shù)最優(yōu)解與真實(shí)最優(yōu)解的方差較小，說(shuō)明本文搜索到的平均最優(yōu)解與真實(shí)最優(yōu)解偏離程度較小，數(shù)據(jù)波動(dòng)小，求解精度高，穩(wěn)定性好．從平均收斂時(shí)間可知，算法收斂速度較快．

為了體現(xiàn)出本文算法對(duì)函數(shù)的進(jìn)化過(guò)程，對(duì)4個(gè)測(cè)試函數(shù)的函數(shù)值進(jìn)化曲線分別從30次的運(yùn)算中隨機(jī)選取1次與文獻(xiàn)［15］進(jìn)行比較，具體的對(duì)比結(jié)果如圖1～圖4 所示．搜索能力和BFGS算法的局部超線性收斂性．

圖1 函數(shù)f1 進(jìn)化曲線Fig．1 Function f1evolution curve

圖2 函數(shù)f2 進(jìn)化曲線Fig．2 Function f2evolution curve

圖3 函數(shù)f3 進(jìn)化曲線Fig．3 Function f3evolution curve

圖4 函數(shù)f4 進(jìn)化曲線Fig．4 Function f4evolution curve

從以上4個(gè)函數(shù)的進(jìn)化曲線可以看出，本文算法對(duì)函數(shù)f1，f2，f3能很快找到最優(yōu)解，迭代次數(shù)非常少；而文獻(xiàn)［15］分別得運(yùn)行400，100，150，300次左右才能找到解．針對(duì)很難極小化的函數(shù)f4，本文算法也比文獻(xiàn)［15］的迭代次數(shù)少．對(duì)這些多極值、難以極小化的函數(shù)該算法都能以較少的進(jìn)化代數(shù)搜索到全局最優(yōu)解，表明它的收斂速度快，穩(wěn)定性好，從而體現(xiàn)出BFGS 算法嵌入到人工免疫算法中，局部收斂性得到了很大的改善．

利用本文算法和文獻(xiàn)［15］算法分別對(duì)以上測(cè)試函數(shù)針對(duì)算法的成功率進(jìn)行了比較，比較結(jié)果如表2 所示．

從表1 數(shù)據(jù)可以看出，本文算法收斂到最優(yōu)解的次數(shù)明顯多于文獻(xiàn)［15］，這說(shuō)明本文算法的收斂性、穩(wěn)定性較好，從而表明在算法中嵌入BFGS算法提高了人工免疫算法的收斂速度和收斂性能．該算法充分發(fā)揮了人工免疫算法的全局

表2 本文算法與文獻(xiàn)［15］算法的比較結(jié)果Tab．2 Comparison between algorithm of this paper and algorithm of the literature［15］

3 結(jié) 論

本文針對(duì)人工免疫算法局部收斂性較弱的缺陷，提出了一種基于經(jīng)典優(yōu)化算法——BFGS 算法的改進(jìn)人工免疫算法．該算法在保持人工免疫算法的全局搜索能力的基礎(chǔ)上，在局部嵌入了BFGS算法，從而加強(qiáng)了人工免疫算法的局部搜索能力，整體上提高了人工免疫算法的執(zhí)行效率．典型函數(shù)的實(shí)驗(yàn)數(shù)據(jù)表明：該算法在成功率、收斂速度和求解精度上都有了提高，并且具有很強(qiáng)的魯棒性，為函數(shù)優(yōu)化提供了一種方法．該算法還可以應(yīng)用到求解非線性方程、方程組等具體問(wèn)題中．本文算法是加強(qiáng)了人工免疫算法的局部搜索能力，而如何進(jìn)一步提高人工免疫算法的后期搜索能力，是下一步的研究工作．

［1］柴爭(zhēng)義，王獻(xiàn)榮，王亮．用于異常檢測(cè)的實(shí)值否定選擇算法［J］．吉林大學(xué)學(xué)報(bào)，2012，42（1）：176－181．Chai Zhengyi，Wang Xianrong，Wang Liang．Real－value negative selection algorithm for anomaly detection［J］．Journal of Jilin University，2012，42（1）：176－181．（in Chinese）

［2］Biswal B，Biswal M K，Dash P K，et al．Power quality event characterization using support vector machine and optimization using advanced immune algorithm［J］．Neurocomputing，2013，103：75－86．

［3］Nicholas W，Pradeep R，Greg S，et al．Artificial immune systems for the detection of credit card fraud：an architecture，prototype and preliminary results［J］．Information Systems Journal，2012，22（1）：53－76．

［4］Chen J，Lin Q，Ji Z．A hybrid immune multiobjective optimization algorithm［J］，European Journal of Operational Research，2010，204（2）：294－302．

［5］王磊，肖人彬．基于免疫記憶的人工免疫算法模型及其應(yīng)用［J］．模式識(shí)別與人工智能，2002，15（4）：385－390．Wang Lei，Xiao Renbin．An algorithmic model of artificial immune system based on immunological memory［J］．Pattern Recognition and Artificial Intelligence，2002，15（4）：385－390．（in Chinese）

［6］Gong M G，Jiao L C，Zhang L N，et al．Immune secondary response and clonal selection inspired optimizers［J］．Progress in Natural Science，2009，19（2）：237－253．

［7］Dasgupta D．Artificial Immune Systems and Their Applications［M］．Bedin Heidelberg：Springer－Verlang，1999．

［8］Jang S，Chun M K K，Hyun－Kyo J．Shape optimization of electromagnetic devices using immune algorithm［J］．IEEE Transactions on Magnetics，1997，33（2）：1876－1879．

［9］鄭日榮，毛宗源，羅欣賢．基于歐氏距離和精英交叉的免疫算法研究［J］．控制與決策，2005，20（2）：161－169．Zheng Rirong，Mao Zongyuan，Luo Xinxian．Research on euclidean distance and King－crossover－based immune algorithms［J］．Control and Decision，2005，20（2）：161－169．（in Chinese）

［10］何珍梅，徐雪松．一種多模態(tài)函數(shù)優(yōu)化的免疫算法［J］．南昌大學(xué)學(xué)報(bào)（工科版），2008，30（1）：83－86．He Zhenmei，Xu Xuesong．A immune algorithm for multi－modal function optimization［J］．Journal of Nanchang University（Engineering ＆ Technology Edition），2008，30（1）：83－86．（in Chinese）

［11］李翠云．基于DNA 的人工免疫算法及應(yīng)用研究［D］．杭州：浙江大學(xué)，2013．

［12］陳寶林．最優(yōu)化理論與算法［M］．北京：清華大學(xué)出版社，2005．

［13］Srinivas M．A daptive probability of crossover and mutation in genetic algorithms［J］．IEEE Trans．Syst．Man．Cybern．，1994，24（4）：655－667．

［14］鄭日榮，毛宗源，羅欣賢．改進(jìn)人工免疫算法的分析研究［J］．計(jì)算機(jī)工程與應(yīng)用，2003，39（34）：35－37．Zheng Rirong，Wao Zongyuan，Luo Xinxian．A study on modified artificial immune algorithms［J］．Computer Engineering and Applications，2003，39（34）：35－37．（in Chinese）

［15］趙偉，劉雪英．基于最速下降法的人工免疫算法［J］．內(nèi)蒙古工業(yè)大學(xué)學(xué)報(bào)，2009，28（2）：94－97．Zhao Wei，Liu Xueying．The artificial immune algorithm based on the steepest descent method［J］．Journal of Inner Mongolia University of Technology，2009，28（2）：94－97．（in Chinese）