人工免疫思維進化算法設計

1、人工免疫思維進化算法的設計摘要：文中提出一種人工免疫思維進化算法，此算法在免疫系統(tǒng)優(yōu)化機理的基礎上吸取了思維進化算法中的優(yōu)點，提出了趨同半徑和異化半徑的概念，實現(xiàn)了免疫算法中抗體的局部和全局尋優(yōu)，并且給出了一種基于矢量距的概率選擇方法。同時，本文描述了算法的具體實現(xiàn)步驟，證明了算法的收斂性，給出了仿真實驗。實驗結果表明，新算法有機地結合了人工免疫算法和思維進化算法的優(yōu)點，具有不易陷入局部極值，解的精度高，收斂速度快等特性。關鍵詞：人工免疫算法 思維進化算法 趨同 異化 矢量距中圖分類號：tp18文獻標識碼：a文章編號：1007-9416(2012)02-0127-03the design of

2、 artificial immune mind evolution algorithmli xiao-min(engineering school of shanxi datong university, datong 037003, shanxi province)abstract:a kind of artificial immune mind evolution algorithm is proposed in this paper, which combines the advantage of mind evolution algorithm with the optimizatio

3、n mechanism of immune system; the concept of similartaxis radius and dissimilation radius is defined; to realize the local optimization and global optimization of antibody, and probability choice based on vector distance was given. meanwhile, algorithm description was given in detail in this paper;

4、the convergence of algorithm was proved, and simulation experiment was carried out. the experiment result has shown that the new algorithm has good performance with the merit of artificial immune algorithm and mind evolution algorithm, such as avoiding local optima, high precision solution, and quic

5、k convergence.key words:artificial immune algorithm mind evolution algorithm similartaxis; dissimilation；vector distance1、引言生命現(xiàn)象和生物的智能行為一直為人工智能研究者所關注。而自然免疫系統(tǒng)正是人工智能方法靈感的重要源泉之一。免疫系統(tǒng)在顯示學習、適應性、記憶機制等應用于不同計算任務的方法方面可以給人們提供豐富的靈感和啟示。從人體免疫系統(tǒng)發(fā)展出的計算方法已經(jīng)引起許多不同領域廣泛的研究興趣。受人類自然免疫系統(tǒng)的啟發(fā)，現(xiàn)在已經(jīng)提出了各種人工免疫算法。人工免疫算法是模擬自然免疫系

6、統(tǒng)功能的一種智能方法，它實現(xiàn)一種受生物免疫系統(tǒng)啟發(fā)，通過學習外界物質(zhì)的自然防御機理的學習技術，提供噪聲忍耐、無師學習、自組織、記憶等進化學習機理，結合了分類器、神經(jīng)網(wǎng)絡和機器推理等系統(tǒng)的一些優(yōu)點，因此具有提供新穎的解決問題的方法的潛力1。它已經(jīng)成為繼神經(jīng)網(wǎng)絡、模糊邏輯推理和進化計算后人工智能的又一研究熱點2。思維進化算法3,4是模擬人類思維進化過程的一種新型進化算法，其中的趨同與異化的概念對于目前正在大量廣泛研究的人工免疫算法有著重要的啟示。根據(jù)人工免疫和思維進化的特點，本文提出了人工免疫思維進化算法。該算法借鑒了思維進化中的上述特點，引入了趨同半徑和異化半徑的概念，這樣抗體根據(jù)克隆擴增和受體

7、編輯的原理分別進行局部競爭和全局競爭，實現(xiàn)了兩層搜索機制。另外，算法中強調(diào)了免疫記憶的優(yōu)良抗體保持作用。2、人工免疫思維進化算法的生物學機理5,6,7與達爾文生物進化原理相似，生物免疫系統(tǒng)中也存在著進化現(xiàn)象。當抗原侵入肌體時，b細胞群體通過如下進化過程產(chǎn)生抗體以消滅抗原：(1)與抗原親合力高的b細胞被選出。(2)在輔助t細胞的作用下，該b細胞分裂增生，產(chǎn)生大量b細胞，稱為克隆擴增（clonal expansion）。b細胞通過克隆擴增在形狀空間中的小范圍內(nèi)產(chǎn)生大量子b細胞以在局部范圍內(nèi)搜索親合性更高的b細胞。(3)一些親合力低的子b細胞刪除其受體并生成新受體，即受體編輯（receptor ed

8、iting）。受體編輯使得子b細胞在形狀空間中可能突變?yōu)殡x其較遠的點，以在全局范圍內(nèi)搜索親合性更高的b細胞。另一些親合力低的子b細胞死亡，同時骨髓產(chǎn)生一部分新b細胞以增加群體的多樣性。(4)經(jīng)過若干世代的選擇、克隆擴增、受體編輯、骨髓產(chǎn)生新b細胞過程，最終產(chǎn)生了親合力很高的b細胞以消滅抗原。3、算法中的幾個概念3.1 趨同半徑與異化半徑趨同和異化3,4是思維進化算法中的兩個重要概念，將趨同與異化的思想分別與克隆擴增和受體編輯相對應。為此分別定義趨同半徑和異化半徑：群體中的任一抗體的局部范圍構造為：其中為歐幾里德范數(shù)，為解空間，是由與的歐氏距離不大于常數(shù)的所有可行解構成，解空間是以為中心，為半徑

9、的局部球形區(qū)域，定義為趨同半徑。群體中的任一抗體的全局范圍構造為：其中是以為中心，為半徑的全局球形區(qū)域，定義為異化半徑。3.2 基于矢量距的選擇方法8在常見的算法中，通常選取與種群中個體適應度成正比的方法作為選擇概率，這樣很容易使種群中相似適應度的個體迅速增加，使算法未成熟收斂。為此，提出基于矢量距的選擇方法。將抗原、b細胞和抗體分別對應于優(yōu)化問題的目標函數(shù)、優(yōu)化解，解的適應度函數(shù)，n個抗體構成了一個非空免疫系統(tǒng)集合x。規(guī)定抗體在集合x上的距離為：這就是抗體矢量距的定義式。于是抗體的濃度可由如下公式表示：由此可推導出基于抗體濃度的概率選擇公式：由此可知，集合x中與抗體i基因相似的抗體越多，抗體

10、i被選中的概率越小。反之亦然。這使得親合力低的抗體也能得到繁殖機會，增加了抗體的多樣性。4、人工免疫思維進化算法的步驟算法的操作步驟如下：4.1 抗原識別輸入目標函數(shù)和各種約束條件作為免疫算法的抗原。4.2 產(chǎn)生初始抗體群產(chǎn)生n個實數(shù)編碼的抗體作為初始群體a，在第一次迭代時，抗體通常在解空間中用隨機的方法產(chǎn)生。4.3 抗體選擇操作計算群體a中每個抗體的親合力值，并且計算抗體的濃度，基于抗體濃度的概率公式選擇其中m個抗體組成群體b（其中m<n），并將群體a中m1個親合力最高的抗體作為免疫記憶抗體保留（m1<m）?；诳贵w濃度的選擇方法是：計算累積概率，其中，并且令。在區(qū)間上產(chǎn)生一個均

11、勻分布的隨機數(shù)w，若，則抗體被選中，產(chǎn)生m個這樣的隨機數(shù)，則有m個抗體被選中到群體b中。4.4 抗體在趨同半徑內(nèi)進行擴增操作群體b中m抗體在趨同半徑局部范圍內(nèi)進行擴增操作，產(chǎn)生n個抗體組成群體c。擴增方法是將群體b中的抗體和隨機兩兩配對，按一個指定概率pc進行交叉操作。抗體在趨同范圍內(nèi)進行擴增操作相當于在解空間的局部范圍內(nèi)進行小范圍搜索。4.5 抗體在異化半徑內(nèi)進行突變操作群體c中nm個抗體在異化半徑全局范圍內(nèi)進行突變操作，保持群c的規(guī)模不變并組成群體d。突變操作是對每個抗體，按一定概率pm進行變異操作。這相當于在解空間的全局范圍內(nèi)進行大范圍搜索。4.6 抗體更新群體d中親合力最低的m1個抗體

12、替換成步驟3中的免疫記憶抗體，組成新一代群體a。4.7 終止條件如果新一代群體a中有滿足要求的抗體，則輸出最優(yōu)抗體，算法結束；否則轉到第3步重復執(zhí)行。算法的流程圖如圖1所示。5、算法的收斂性分析定義1設是時刻k時群體中的最優(yōu)抗體，是待求問題的抗原，當且僅當成立，稱人工免疫思維進化算法是全局收斂的。定義29 a是一個的方陣。(1)若對所有的i，j，記為，稱a為非負的（nonnegative）；(2)若a是非負的，且對所有的i，則a是隨機的（stochastic）；(3)若a是非負的，且對a中的行和列經(jīng)過置換能得到形式（c，t是方陣），則a是可約的（reducible）。定理110 設p是一個可約

13、隨機矩陣，其中c是正的m階隨機矩陣，則。定理2 人工免疫思維進化算法是依概率1收斂的。證明：算法中的交叉操作是以概率pc對選擇的一對抗體上的兩個基因位進行交叉。變異操作是對抗體的每個基因位以概率pm相互獨立的進行變異。則算法步驟（15）的n步狀態(tài)轉移可用狀態(tài)轉移陣表示，且，。根據(jù)定義1和2，狀態(tài)轉移矩陣p是隨機的。通過置換將轉移矩陣p的各狀態(tài)排列如下：第一個狀態(tài)為全局最優(yōu)解；第二個狀態(tài)為全局次優(yōu)解；依此類推，第n個狀態(tài)為全局最差解。則算法步驟（6）中的更新操作可視為：對任意狀態(tài)i，依 和，對轉移矩陣更新，生成新的轉移陣。這里， ，r，是一階正的隨機矩陣，根據(jù)定義，狀態(tài)轉移陣p是可約的。根據(jù)定理

14、1，。的第一狀態(tài)的極限概率為1，即，由定義1可知人工免疫思維進化算法是全局收斂的。6、仿真實驗與結論以求極小值為例，選取以下4個函數(shù)作為測試函數(shù)：以上函數(shù)的最優(yōu)值分別為：25、0.397887、0、4.687，其中函數(shù)有3個極小值點。設置人工免疫思維進化算法中的參數(shù)n=20，m=10，m1=5，并且使算法循環(huán)迭代100次，于是將該算法與基本思維進化算法進行函數(shù)優(yōu)化比較，優(yōu)化結果如表1所示。為了表示方便，以aimea代表人工免疫思維進化算法，以mea代表思維進化算法。從上面的實驗中我們可以看到，在此類階梯函數(shù)的優(yōu)化中，aimea在100代的時候已經(jīng)能夠找到最優(yōu)解25，但是mea卻只能得到20。由

15、此可知，aimea在多變量求解方面較mea要好，而且其優(yōu)化結果與收斂速度，都優(yōu)于mea。在和此類多峰函數(shù)的優(yōu)化中，雖然函數(shù)有許多局部極小值，但是aimea仍能較快地找出全局最優(yōu)解，可見其有效地避免了“早熟”現(xiàn)象，不容易陷入局部極值，其收斂速度也要優(yōu)于mea。而在此類函數(shù)的優(yōu)化中，雖然兩種算法都是有效的，都能夠找到最優(yōu)解。但是從收斂速度來看，aimea明顯比mea快。而且其尋優(yōu)結果也要比mea精確。8、結語綜上所述，算法能在群體中優(yōu)秀抗體的局部范圍和全局范圍內(nèi)同時搜索親合力更高的抗體。突變操作在異化半徑內(nèi)進行大范圍搜索，以在全局搜索親合力高的區(qū)域，是粗搜索，當粗搜索找到親合力較高的區(qū)域后，擴增操

16、作通過趨同半徑進行局部細搜索以尋求高精度的解。算法通過粗和細的兩層搜索，以保證其全局尋優(yōu)和局部求精度的性能。由此可見，人工免疫思維進化算法不易陷入局部極值，并且在收斂速度與精確性等方面還是有一定的優(yōu)勢的。參考文獻1丁永生,任立紅.人工免疫系統(tǒng)：理論與應用j.模式識別與人工智能,2000,13(1):5259.2jon timmis,mark neal,john hunt.an artificial immune system for data analysisj.biosystem,2000(55):143-150.3keming xie, changhua mou, gang xie. th

17、e multi-parameter combination mind-evolutionary-based machine learning and its applicationa. 2000 ieee international conference on system, man, and cybernetics(smc2000). music city sheraton, nashville, tennessee, usa, 2000. 183187.4keming xie, changhua mou, gang xie. a new mebml-based algorithm for

18、adjusting parameters on-linea. 2000 5th international conference on signal processing proceedings(icsp2000, wcc2000). beijing, china, 2000.17141717.5左興權,李士勇,黃金杰.一種新的免疫進化算法及其性能分析j.系統(tǒng)仿真學報,2003,15(11):16071609.6de castro l n,von zuben f j.learning and optimization using the clonal selection principlej.ieee transactions on evolutionary computation,2000,6(3):239-251.7ada g l,nossal g.the clonal selection theoryj.scientific ameri