人工免疫優(yōu)化與分類算法及其應(yīng)用研究.pdf

1、人工免疫系統(tǒng)(AIS:Artificial Immune System)是一類基于生物免疫系統(tǒng)的功能、原理、基本特征以及相關(guān)理論免疫學(xué)說(shuō)而建立的用于解決各種復(fù)雜問(wèn)題的計(jì)算系統(tǒng),是繼人工神經(jīng)網(wǎng)絡(luò)、進(jìn)化計(jì)算之后新的計(jì)算智能研究方向。本論文旨在深入探索和研究生物免疫系統(tǒng)中蘊(yùn)含的進(jìn)化學(xué)習(xí)機(jī)制,設(shè)計(jì)高效的人工免疫算法,并用其解決工業(yè)中的組合優(yōu)化問(wèn)題以及數(shù)據(jù)挖掘中的分類問(wèn)題。本論文的主要研究工作包括以下幾個(gè)方面:
　　 1.一般克隆選擇算法

2、(CSA)求解函數(shù)優(yōu)化問(wèn)題時(shí),雖然表現(xiàn)出了比遺傳算法更好的全局尋優(yōu)能力,能有效克服遺傳算法早熟現(xiàn)象。但是,在解決諸如背包問(wèn)題等組合優(yōu)化問(wèn)題時(shí)收斂速度緩慢,解波動(dòng)較大且難搜到最優(yōu)解。為此,對(duì)一般克隆選擇算法進(jìn)行了改進(jìn),提出了帶受體編輯的克隆選擇算法(RECSA)。該算法受生物免疫系統(tǒng)機(jī)理的啟發(fā),不僅通過(guò)體細(xì)胞高頻變異還引入了受體編輯操作實(shí)現(xiàn)親和力的成熟,使抗體達(dá)到與抗原的高度匹配,同時(shí)增加一個(gè)歷史至當(dāng)前代最佳個(gè)體記憶單元防止種群退化。針對(duì)

3、背包問(wèn)題,采用貪婪策略和寬限邊界值相結(jié)合的方式,對(duì)每代抗體群進(jìn)行受體編輯操作。在對(duì)背包問(wèn)題的兩個(gè)算例求解中表明:與一般CSA算法和遺傳算法相比,RECSA算法能提高種群質(zhì)量和算法的收斂速度,在隨機(jī)搜索期望最優(yōu)值方面能力更強(qiáng),而且算法更加穩(wěn)定可靠,魯棒性更好。
　　 2.針對(duì)組合優(yōu)化問(wèn)題,建立了一般CSA和RECSA算法的有限時(shí)齊馬爾可夫鏈模型,定義了種群狀態(tài)并構(gòu)造了馬爾可夫鏈的狀態(tài)轉(zhuǎn)移矩陣,然后采用馬爾可夫鏈理論對(duì)兩算法的收斂性

4、進(jìn)行了證明。理論推導(dǎo)表明,當(dāng)?shù)螖?shù)趨于無(wú)窮大時(shí),馬爾可夫鏈中的任意種群初始態(tài)是以概率1收斂到最優(yōu)態(tài),即至少有一個(gè)最優(yōu)解能被尋到。最后,采用馬爾可夫鏈平均吸收時(shí)間定理,證明了RECSA算法的平均收斂代數(shù)小于一般的CSA的平均收斂代數(shù),從理論上說(shuō)明了RECSA算法的收斂速度更快。
　　 3.為了說(shuō)明RECSA算法解決組合優(yōu)化問(wèn)題的普遍有效性,我們將其用于組播路由問(wèn)題當(dāng)中。針對(duì)時(shí)延受限的組播路由,根據(jù)代價(jià)最小化原則和延時(shí)要求對(duì)個(gè)體的

5、基因片段進(jìn)行兩次受體編輯,采用RECSA算法對(duì)其進(jìn)行求解表明,在無(wú)需先求解備選路徑的情況下能快速找到最優(yōu)解,算法復(fù)雜度低且穩(wěn)定可靠。本文還將RECSA算法用于解決組播路由的QoS問(wèn)題,在首先滿足延時(shí)約束的條件下,再綜合考慮延時(shí)、帶寬、代價(jià)這三個(gè)性能指標(biāo),引入了一個(gè)參數(shù)Q來(lái)衡量組播路由綜合性能,使算法在這三者之間進(jìn)行權(quán)衡約束,克服了目前傳統(tǒng)的組播路由算法的一種性能參數(shù)的改善是以另一種或幾種性能參數(shù)的退化作為代價(jià),過(guò)于厚此薄彼的作法。仿真實(shí)

6、驗(yàn)表明:該算法收斂速度快,能從整體上把握組播路由的綜合性能,大大改善了組播路由的服務(wù)質(zhì)量。將該算法用于長(zhǎng)沙移動(dòng)網(wǎng)的LAC優(yōu)化中,實(shí)現(xiàn)了在不增減LAC區(qū)的情況下盡量減小LAC區(qū)邊界處位置更新次數(shù)。
　　 4.從免疫進(jìn)化網(wǎng)絡(luò)理論著手,在研究了aiNET聚類模型和AIRS、AINMC等分類算法基礎(chǔ)上,提出了基于免疫進(jìn)化網(wǎng)絡(luò)理論的分類器(IENC)。該算法主要采用記憶細(xì)胞池間與記憶細(xì)胞池內(nèi)的兩次網(wǎng)絡(luò)抑制操作來(lái)改善網(wǎng)絡(luò)結(jié)構(gòu),使記憶細(xì)胞在特

7、異性與“通用性”之間得到平衡,從而提高分類準(zhǔn)確率。對(duì)UCI中的Iris、Ionospere、Sonar和Pima的四個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集的測(cè)試表明, IENC分類器比AIRS和AINMC更好,分類準(zhǔn)確率更高。
　　 5.最后,將IENC分類器用于。DNA序列和電能質(zhì)量擾動(dòng)分類中同樣得到了比較滿意的分類準(zhǔn)確率。以上測(cè)試中,分類器的親和力度量均采用常用的歐式距離。而在DNA序列的分類中發(fā)現(xiàn),DNA序列的特征提取和親和力度量方法對(duì)分類性能有較