張安玲，鄧啟森

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

0 引 言

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

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

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

1 混合人工免疫算法

1．1 標準人工免疫算法

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

1．2 BFGS算法

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

BFGS算法的計算步驟：

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

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

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

4）利用

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

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

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

1．3 混合免疫算法

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

1）編碼方式本文采用的均是二進制編碼．

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

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

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

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

定義2 抗體v，w 的適應度記為Fv和Fw，對應所求解的問題給定適當?shù)某?shù)r＞0，m＞0，若有

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

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

式中：Fv為抗體v 的適應度；Cv為抗體v 的濃度［14］．

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

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

1）抗原識別．

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

3）抗體適應度的計算．

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

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

6）交叉和變異．分別采用1）和2）自適應變化的交叉率和變異率對抗體進行單點交叉和變異．

7）BFGS算法運算．對群體中每個抗體以概率ps進行一次BFGS 算法運算，將子代取代父代；對記憶庫中的每個抗體進行一次BFGS算法運算，將子代取代父代．

8）計算抗體的適應度．

9）群體更新．用記憶庫中的抗體代替群體中適應度值比其低的抗體．

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

注1 在此混合算法中，每個抗體是以概率ps進行BFGS算法運算，這樣提高了算法的運算效率．

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

2 數(shù)值實驗

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

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

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

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

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

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

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

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

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

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

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

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

表2 本文算法與文獻［15］算法的比較結果Tab．2 Comparison between algorithm of this paper and algorithm of the literature［15］

3 結 論

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

［1］柴爭義，王獻榮，王亮．用于異常檢測的實值否定選擇算法［J］．吉林大學學報，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］王磊，肖人彬．基于免疫記憶的人工免疫算法模型及其應用［J］．模式識別與人工智能，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］．南昌大學學報（工科版），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 的人工免疫算法及應用研究［D］．杭州：浙江大學，2013．

［12］陳寶林．最優(yōu)化理論與算法［M］．北京：清華大學出版社，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］．計算機工程與應用，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è)大學學報，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）