免疫克隆選擇算法的改進(jìn)及其應(yīng)用

邱亞龍,張 昕,范妙炳,葉奕純,陳 婷

(華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院,廣州 510642)

?

免疫克隆選擇算法的改進(jìn)及其應(yīng)用

邱亞龍,張 昕,范妙炳,葉奕純,陳 婷

(華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院,廣州 510642)

摘 要:基于生物免疫系統(tǒng)原理,提出了改進(jìn)的免疫克隆選擇算法.引入網(wǎng)割預(yù)處理,獲得進(jìn)化終止次數(shù)并使初始抗體集的多樣性得到控制; 采取震蕩變異法提高算法的局部搜索精度; 引入記憶機(jī)制,提高二次免疫收斂速度.本文應(yīng)用此算法針對(duì)大氣污染損害率普適公式進(jìn)行參數(shù)優(yōu)化,結(jié)果顯示改進(jìn)算法在全局與局部范圍內(nèi)搜索更為細(xì)膩,提高了求解精度.

關(guān)鍵詞:免疫克隆選擇算法; 抗原預(yù)處理; 震蕩變異; 大氣污染損害率普適公式; 參數(shù)優(yōu)化

1　免疫克隆選擇算法

關(guān)于免疫克隆選擇算法(以下稱(chēng)“ICSA”)在國(guó)內(nèi)的研究,劉若辰[1]提出了多種克隆選擇改進(jìn)方法,如借助生物免疫系統(tǒng)的抗體克隆選擇機(jī)理,構(gòu)造適用于人工智能的克隆算子,并系統(tǒng)探討了基于該算子的免疫克隆策略算法的性能,借鑒免疫學(xué)克隆選擇和免疫記憶機(jī)理,提出新的人工免疫系統(tǒng)算法,稱(chēng)為免疫記憶動(dòng)態(tài)克隆策略.

ICSA主要包括選擇、克隆、變異和消亡四個(gè)步驟,強(qiáng)調(diào)基于抗體與抗原的親和度大小及比例進(jìn)行抗體選擇和克隆; 每次迭代后保留優(yōu)良抗體群; 并采取隨機(jī)方式產(chǎn)生新抗體以替代舊抗體,擴(kuò)大搜索區(qū)域,在一定程度上避免陷入局部峰值[2].

傳統(tǒng)ICSA存在局部搜索精度不高,初始抗體集多樣性不足,多峰搜索能力效果不佳等缺點(diǎn)[3].針對(duì)這些不足,諸多學(xué)者進(jìn)行了改進(jìn)研究.例如: 采取免疫記憶的動(dòng)態(tài)克隆策略方法[1]、基于克隆選擇算法的改進(jìn)[4]、基于混合免疫克隆選擇算法與差分進(jìn)化的優(yōu)化方法[5]、基于Parzen密度估計(jì)的多目標(biāo)免疫克隆聚類(lèi)方法[6]和基于克隆變異啟發(fā)的克隆選擇算法[7]等,這些改進(jìn)的算法都在一定程度上優(yōu)化了傳統(tǒng)ICSA算法的不足.

本文針對(duì)傳統(tǒng)ICSA存在的初始抗體集多樣性不確定、進(jìn)化終止次數(shù)不好控制、局部搜索能力不佳和二進(jìn)制編碼面臨的“維數(shù)災(zāi)”等不足[2],對(duì)ICSA算法進(jìn)行改進(jìn).

2　改進(jìn)的免疫克隆選擇算法

本文改進(jìn)的免疫克隆選擇算法在繼承傳統(tǒng)ICSA大體框架的基礎(chǔ)上引入網(wǎng)割預(yù)處理、震蕩變異策略以及免疫記憶機(jī)制,以下是該改進(jìn)算法核心思想.

(1)引入抗原預(yù)處理.首先在首次免疫時(shí),對(duì)抗原(即待優(yōu)化的問(wèn)題)進(jìn)行解析,創(chuàng)建抗體進(jìn)化所需環(huán)境.首先,分析問(wèn)題參數(shù)個(gè)數(shù)、參數(shù)取值范圍與精度等信息; 其次,根據(jù)相應(yīng)公式計(jì)算抗體的網(wǎng)割空間(即問(wèn)題的解空間)所需的網(wǎng)割因子(即控制網(wǎng)割空間數(shù)量的一組參數(shù))以及進(jìn)化終止次數(shù); 第三,在網(wǎng)割后各個(gè)細(xì)小空間中產(chǎn)生一定數(shù)量的初始抗體,解決初始抗體集的多樣性不確定性問(wèn)題; 并且動(dòng)態(tài)獲取進(jìn)化終止次數(shù),解決了進(jìn)化次數(shù)不好控制的問(wèn)題.

(2)自適應(yīng)變異空間.抗體的變異空間由組成抗體的基因變異半徑(即單個(gè)變量的增量范圍)確定; 基因的變異半徑由進(jìn)化次數(shù)、抗體—抗原親和度(即抗體優(yōu)良性指標(biāo))與抗原決定簇確定; 抗原決定簇的內(nèi)容由基因值可行域(即變量定義范圍)、變量精度控制組成.經(jīng)試驗(yàn),自適應(yīng)變異空間有效解決了搜索空間難以確定的問(wèn)題,提高了變異操作的效率,是震蕩變異法的基礎(chǔ).

(3)震蕩變異法.震蕩變異法先在自適應(yīng)變異空間內(nèi)產(chǎn)生一個(gè)變異增量,隨機(jī)轉(zhuǎn)化為正值或負(fù)值再與原始抗體相加得到變異抗體,據(jù)此提高抗體基因的變異效率.

2.1 網(wǎng)割預(yù)處理

網(wǎng)割預(yù)處理是指在產(chǎn)生初始抗體集前先對(duì)目標(biāo)函數(shù)的參數(shù)個(gè)數(shù)、參數(shù)精度與參數(shù)取值范圍進(jìn)行解析,從而確定進(jìn)化終止次數(shù)T和網(wǎng)割因子Gj.根據(jù)網(wǎng)割因子將目標(biāo)函數(shù)的解空間劃分為一定數(shù)量的細(xì)小空間,在網(wǎng)割空間各個(gè)范圍內(nèi)的細(xì)小空間中產(chǎn)生一定數(shù)量的抗體,所有抗體組成初始抗體集,如此便達(dá)到控制初始抗體集多樣性的目標(biāo).

終止次數(shù)T的計(jì)算公式為

網(wǎng)割因子Gj的計(jì)算公式為

其中n是變量個(gè)數(shù),ΔRj是變量j定義范圍大小的絕對(duì)值,Sj是變量j的精度,Tmax與Gmax為自定義值.

2.2 克隆

抗體克隆規(guī)模與抗體親和度成正比.通過(guò)克隆可提高優(yōu)良抗體濃度,加速提高變異后抗體群的平均親和度,從而加快算法的收斂速度; 記克隆總規(guī)模的松弛上限為W ,則第i個(gè)抗體的克隆規(guī)模為

2.3震蕩變異法

震蕩變異法是先在變異空間內(nèi)產(chǎn)生一個(gè)變異增量,接著隨機(jī)轉(zhuǎn)化為正值或者負(fù)值,再與原始基因值相加才得到變異基因值; 它是基于自適應(yīng)伸縮的變異空間以及采用雙重變異空間策略來(lái)提高變異效率的一種新型算法.

傳統(tǒng)遺傳算法有兩種變異方式: 一種是適用于二進(jìn)制編碼的0、1變異法; 另外一種是適用于十進(jìn)制編碼的現(xiàn)行搜索法.而震蕩變異法可有效地避免傳統(tǒng)遺傳算法由于這兩種變異方式造成的隨機(jī)漫游問(wèn)題.

2.3.1自適應(yīng)變異空間

變異半徑是指變異前后單個(gè)基因值增量的取值范圍,兩個(gè)基因的變異半徑構(gòu)成變異平面,多個(gè)基因(3個(gè)以上)的變異半徑構(gòu)成變異空間.第i個(gè)抗體第j個(gè)基因的變異半徑為

其中ΔRj是第j個(gè)參數(shù)定義范圍大小的絕對(duì)值; Sj是第j個(gè)參數(shù)的精度要求位數(shù); t是當(dāng)前進(jìn)化代數(shù); T是終止迭代次數(shù); p是變異半徑調(diào)節(jié)因子,其值與親和度有關(guān); r是加速因子.

由正向變異半徑計(jì)算公式可知,由此構(gòu)成的變異空間具有基于抗體親和度、基因值取值范圍與進(jìn)化次數(shù)的自適應(yīng)伸縮特性; 當(dāng)基因值與親和度不變時(shí),隨著迭代次數(shù)的增加,正向變異空間的整體變化趨勢(shì)呈S型遞減.

傳統(tǒng)ICSA雖然每次迭代次數(shù)較快,但求解精度不高; 而改進(jìn)的算法在收斂后期,隨著向最優(yōu)解逐漸逼近,變異空間緩慢縮小,求解精度逐漸提高; 甚至可以通過(guò)改變最大、最小變異空間調(diào)節(jié)因子與迭代次數(shù)來(lái)調(diào)節(jié)變異空間,達(dá)到具體的精度要求.

2.3.2震蕩變異效果

當(dāng)抗體只有一個(gè)基因發(fā)生震蕩變異時(shí),該抗體會(huì)以自身為中心,在變異半徑的方向上震蕩,如圖1所示; 當(dāng)抗體有兩個(gè)基因(若有)發(fā)生震蕩變異時(shí),該抗體就以自身為中心,在變異平面上震蕩,如圖2所示;當(dāng)多個(gè)基因發(fā)生變異時(shí),抗體將會(huì)以自身為中心,在變異空間上震蕩; 若采用基于抗原—抗體親和度的選擇方式(親和度較高的抗體被選擇),隨著迭代次數(shù)的增加,震蕩變異后的抗體群就會(huì)快速向峰值靠攏,如圖3所示.

圖1 單個(gè)基因變異示意圖　

圖2 抗體變異的平面

圖3 震蕩變異三維效果圖

2.4免疫記憶機(jī)制

免疫記憶機(jī)制模仿生物免疫系統(tǒng)的記憶功能,對(duì)首次感染,初始抗體集全部以網(wǎng)割的方式隨機(jī)產(chǎn)生;而二次感染時(shí),初始抗體集部分由記憶細(xì)胞分泌產(chǎn)生,部分以網(wǎng)割方式最優(yōu)產(chǎn)生,即在網(wǎng)割隨機(jī)產(chǎn)生的抗體集中選擇親和度較高的抗體.

2.5改進(jìn)的免疫克隆選擇算法流程

改進(jìn)的免疫克隆選擇算法流程如圖4所示.

圖4 改進(jìn)的免疫克隆選擇算法流程圖

3　實(shí)際應(yīng)用

3.1 應(yīng)用背景

韓旭明、王麗敏[2]2013年根據(jù)評(píng)價(jià)大氣質(zhì)量的目標(biāo)函數(shù),采用引入疫苗接種策略和高斯變異算子的免疫克隆選擇算法(ICSA-VSLGMO)對(duì)大氣污染損害率普適公式進(jìn)行參數(shù)優(yōu)化,進(jìn)而提出基于免疫克隆選擇算法的大氣質(zhì)量評(píng)價(jià)模型和評(píng)價(jià)方法.在對(duì)吉林省某城市的大氣進(jìn)行評(píng)價(jià)時(shí),結(jié)果與該城市利用API法得到的評(píng)價(jià)結(jié)果有微小出入; 這很有可能是ICSA-VSLGMO針對(duì)大氣污染損害率公式參數(shù)優(yōu)化結(jié)果的精度不高造成的.

而采用本文改進(jìn)的免疫克隆選擇算法優(yōu)化參數(shù)后得到了精度更高、收斂更穩(wěn)定的結(jié)果,從而得到了更準(zhǔn)確的大氣質(zhì)量評(píng)價(jià)模型.

3.2 算法實(shí)現(xiàn)

3.2.1 大氣污染損害率普適公式

錢(qián)蓮文[8]等在L.D.詹姆斯、李祚泳等前人研究成果基礎(chǔ)上,引入一個(gè)與污染物特性無(wú)關(guān)的普適參數(shù)c ,將原有公式進(jìn)行改寫(xiě),得到對(duì)多種大氣污染物均適用的、具有更強(qiáng)普適性的大氣污染損害率計(jì)算公式:

3.2.2構(gòu)造目標(biāo)函數(shù)

國(guó)家公布的《環(huán)境空氣質(zhì)量標(biāo)準(zhǔn)(GB3095—1996)》中列出了7種污染物的各項(xiàng)指標(biāo),見(jiàn)表1.

表1 國(guó)家《環(huán)境空氣質(zhì)量標(biāo)準(zhǔn)(GB3095—1996)》

根據(jù)5個(gè)級(jí)別的標(biāo)準(zhǔn)濃度與基準(zhǔn)濃度值,大氣污染的實(shí)際情況以及文[8],建立目標(biāo)函數(shù):

其中m為污染物種類(lèi)數(shù)目; K為大氣污染程度的分級(jí)數(shù); Rik為i污染物k級(jí)污染損害率; Rke為k級(jí)標(biāo)準(zhǔn)的污染損害率的目標(biāo)值.

3.2.3親和度公式

根據(jù)目標(biāo)函數(shù)可得第i個(gè)抗體—抗原親和度公式:

其中fi∈(0,1); w、λ是靈敏度調(diào)節(jié)參數(shù); fi(x)是第i個(gè)抗體的目標(biāo)函數(shù)值.

3.2.4 編碼

采用實(shí)數(shù)制編碼.經(jīng)多次實(shí)驗(yàn),取待優(yōu)化的參數(shù)a、b、c區(qū)間范圍分別為(0,100),(0,1),(0,1),再加上目標(biāo)函數(shù)值與親和度,每個(gè)抗體的數(shù)據(jù)結(jié)構(gòu)是一個(gè)1× 5的矩陣,如圖5所示.

由此得相關(guān)抗體集的數(shù)據(jù)結(jié)構(gòu),見(jiàn)表2.

圖5 抗體數(shù)據(jù)結(jié)構(gòu)

表2 各抗體集數(shù)據(jù)結(jié)構(gòu)

3.2.5算法具體步驟

步驟1 抗原預(yù)處理.將待優(yōu)化參數(shù)a、b、c的取值范圍分別劃分為5個(gè)等長(zhǎng)的小區(qū)間,然后進(jìn)行全排列得到125個(gè)網(wǎng)割空間;

步驟2 抗原識(shí)別.檢測(cè)記憶細(xì)胞M是否存在且完整(即檢測(cè)存放抗體集的文件是否存在,以及文件內(nèi)容是否完整),若存在轉(zhuǎn)至步驟4,否則轉(zhuǎn)至步驟3;

步驟3 首次感染.在步驟1中得到的每個(gè)網(wǎng)割空間內(nèi)均產(chǎn)生一個(gè)抗體,組成初始抗體集iP ,并計(jì)算親和度,在親和度公式(8)中,令參數(shù)w =15 ,λ=0.06 ,轉(zhuǎn)至步驟5;

步驟4 二次感染.初始候選解集iP中,30%的抗體集由記憶細(xì)胞M分泌產(chǎn)生,其余抗體由網(wǎng)割最優(yōu)產(chǎn)生,分泌過(guò)程由克隆與變異操作組成;

步驟5 選擇.從初始抗體集iP中選出親和度較高的30個(gè)抗體組成臨時(shí)記憶集tP ;

步驟6 克隆.克隆規(guī)模參數(shù)W設(shè)置為50,基于親和度,將臨時(shí)記憶集tP進(jìn)行克隆,得到規(guī)模為50的克隆抗體集cP ;

步驟7 變異.對(duì)克隆抗體集Pc進(jìn)行變異操作,得到變異抗體集Pm,其中加速因子r =0.168 ;

步驟8 消亡.在變異抗體集Pm中選擇40%的親和度較低的抗體重新初始化;

步驟9 再選擇.從臨時(shí)記憶集tP和變異抗體集Pm中選擇較優(yōu)的共30個(gè)抗體并更新臨時(shí)記憶集tP ;

步驟10 判斷是否達(dá)到迭代終止次數(shù)或平均親和度是否達(dá)到理想值,是則轉(zhuǎn)步驟11,否則轉(zhuǎn)步驟5;

步驟11 向記憶細(xì)胞分化.①若首次感染則從臨時(shí)記憶集tP中選擇較優(yōu)的20個(gè)抗體組成記憶細(xì)胞M ;②若為二次感染,則檢測(cè)是否得到比上次感染更優(yōu)的抗體,若得到更優(yōu)的抗體就更新記憶細(xì)胞M ,否則不更新記憶細(xì)胞.完成分化后即轉(zhuǎn)至步驟12;

步驟12 輸出最終解.輸出臨時(shí)記憶集tP中親和度較優(yōu)的20個(gè)抗體;

3.3 試驗(yàn)結(jié)果比較

關(guān)于大氣污染損害率公式參數(shù)優(yōu)化問(wèn)題,在4種已有的算法: 傳統(tǒng)的ICSA,引入疫苗接種策略的免疫克隆選擇算法(ICSA-VS),引入局部高斯變異算子的免疫克隆選擇算法(ICSA-LGMO)以及引入疫苗接種策略和高斯變異算子的免疫克隆選擇算法(ICSA-VSLGMO)之中,ICSA-VSLGMO算法的參數(shù)優(yōu)化結(jié)果最佳,見(jiàn)表3[2]; 表4是采用本文改進(jìn)的免疫克隆選擇算法得到的優(yōu)化結(jié)果; 圖6～9是這兩種算法針對(duì)大氣普適公式的三個(gè)參數(shù)優(yōu)化結(jié)果的對(duì)比.

表3 ICSA-VSLGMO 算法得到的目標(biāo)值及參數(shù)a、b、c的值　

表4 本文改進(jìn)的免疫克隆選擇算法得到的目標(biāo)值及參數(shù)a、b、c的值

圖6 前20個(gè)抗體參數(shù)a的值 　

圖7 前20個(gè)抗體參數(shù)b的值

圖8 前20個(gè)抗體參數(shù)c的值 　

圖9 兩種算法前20個(gè)抗體目標(biāo)值

比較結(jié)果可知,本文改進(jìn)的免疫克隆選擇算法在全局和局部范圍內(nèi)搜索更為細(xì)膩,求解精度進(jìn)一步提高,并且更為穩(wěn)定; 而且本算法引入免疫記憶機(jī)制,在二次運(yùn)行算法時(shí),收斂速度更快(迭代次數(shù)在20次以?xún)?nèi))、更穩(wěn)定,精度更高(達(dá)到小數(shù)點(diǎn)后8位).

4　結(jié)束語(yǔ)

本文改進(jìn)的免疫克隆選擇算法基于解析抗原決定簇,采用基于自適應(yīng)伸縮變異空間的震蕩變異法,有效地解決了傳統(tǒng)ICSA存在的搜索精度不高、初始抗體集多樣性不足和多峰搜索能力效果不佳等缺陷;并且引入免疫記憶機(jī)制,在二次感染時(shí)提高收斂速度和求解精度,從而豐富了傳統(tǒng)免疫算法的內(nèi)容.將改進(jìn)算法針對(duì)大氣污染損害率普適公式進(jìn)行參數(shù)優(yōu)化,實(shí)驗(yàn)結(jié)果表明,與當(dāng)前韓旭明,王麗敏改進(jìn)的ICSA-VSLGMO算法相比,本文改進(jìn)的算法在全局和局部搜索能力上更細(xì)膩,求解精度更高,從而提高了大氣質(zhì)量評(píng)價(jià)模型的準(zhǔn)確性.

參考文獻(xiàn)

[1] 劉若辰.免疫克隆策略算法及其應(yīng)用研究[D].西安: 西安電子科技大學(xué)智能信息研究所博士學(xué)位論文,2005

[2] 韓旭明,王麗敏.人工免疫算法改進(jìn)及其應(yīng)用[M].北京: 電子工業(yè)出版社,2013

[3] 徐 銳.人工免疫算法優(yōu)化及其用研究[D].上海: 上海大學(xué)電子生物技術(shù)研究中心博士學(xué)位論文,2009

[4] 陳 林,姚宏亮.免疫克隆遺傳算法在物流配送中的應(yīng)用[J].河南科技學(xué)院學(xué)報(bào),2012,40(5): 70～74

[5] 葉洪濤,羅文廣,吳 艷.一種基于差分進(jìn)化和免疫克隆選擇算法的混合優(yōu)化方法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(4): 2～3

[6] 秦 亮,張文廣,史賢俊,等.基于免疫克隆算法的多目標(biāo)聚類(lèi)方法[J].信息與控制,2013,42(1)8～12

[7] 胡江強(qiáng),郭 晨,李鐵山.啟發(fā)式自適應(yīng)免疫克隆算法[J].哈爾濱工程大學(xué)學(xué)報(bào),2007,28(1): 1～5

[8] 錢(qián)蓮文,吳承禎,宏 偉,等.大氣質(zhì)量評(píng)價(jià)的污染危害指數(shù)的改進(jìn)[J].福建林學(xué)院報(bào),2003,23(3): 249～252

Application and Improvement of Immune Clonally Selection Algorithm

QIU Ya-long,ZHANG Xin,FAN Miao-bing,YE Yi-chun,CHEN Ting
(College of Mathematics and Information,South China Agricultural University,Guangzhou 510642,China)

Abstract:Based on the principle of biological immune system,an improved immune clonally selection algorithm(ICSA)was proposed.The algorithm introduced the analysis of antigenic determinant,calculated the network cut factor of antibody space and the end times of antibodies evolution,and created environment required to produce antibodies; shock variation method was adopted to make antibodies mutated; Innovative space adaptive mutation was proposed creatively; The improved ICSA was applied to analyze the parameters optimization problem of the atmospheric pollution harm rate universal formulaThe results show that the algorithm within the scope of the global and local search is more exquisite.Solution accuracy is significantly increased.

Key words:immune clonally selection algorithm,antigen pretreatment,concussion variation,damage rate universal formula of air pollution,parameter optimization

通訊作者:張 昕(1968?),男,湖南邵陽(yáng)人,華南農(nóng)業(yè)大學(xué)數(shù)學(xué)與信息學(xué)院副教授.主要研究方向: 數(shù)值計(jì)算

作者簡(jiǎn)介:邱亞龍(1988?),男,廣東陽(yáng)江人,華南農(nóng)業(yè)大學(xué)數(shù)學(xué)與信息學(xué)院碩士研究生.主要研究方向: 智能計(jì)算

基金項(xiàng)目:廣東省大學(xué)生創(chuàng)新創(chuàng)業(yè)項(xiàng)目(201410564201)

收稿日期:2016-01-05

中圖分類(lèi)號(hào):TP301.6

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1672-5298(2016)01-0027-06