摘 要: 人工免疫系統(tǒng)是基于生物免疫系統(tǒng)特性而發(fā)展的新興智能系統(tǒng)。利用免疫系統(tǒng)的克隆選擇機(jī)制,提出一種用于函數(shù)優(yōu)化的改進(jìn)免疫算法" title="免疫算法">免疫算法。其主要特點(diǎn)是采用克隆和自適應(yīng)變異" title="自適應(yīng)變異">自適應(yīng)變異等操作,提高收斂速度" title="收斂速度">收斂速度和種群的多樣性。仿真程序表明,該算法能以較快速度完成給定范圍的搜索和全局優(yōu)化任務(wù)。
關(guān)鍵詞: 克隆選擇 免疫 自適應(yīng)變異 函數(shù)優(yōu)化
在工程實(shí)際中,很多問(wèn)題都可轉(zhuǎn)化為函數(shù)優(yōu)化問(wèn)題,而對(duì)于高維、非凸、且有多個(gè)局部極值點(diǎn)的函數(shù)優(yōu)化問(wèn)題,傳統(tǒng)的基于梯度的算法通常不能求得理想解。免疫系統(tǒng)作為一種分布式自學(xué)習(xí)系統(tǒng),能自適應(yīng)地維持群體多樣性及具有自我調(diào)節(jié)功能,導(dǎo)致基于免疫機(jī)制的算法具有整體、局部搜索能力強(qiáng)的特點(diǎn),使得這類算法在函數(shù)優(yōu)化、組合優(yōu)化、模式識(shí)別、數(shù)據(jù)挖掘及機(jī)器學(xué)習(xí)等方面得到了有效應(yīng)用。
1 免疫算法原理
免疫算法的靈感來(lái)自生物獲得性免疫的克隆選擇原理[1]。根據(jù)該原理,在生物免疫系統(tǒng)中,一旦病原體侵入肌體就被分解為抗原片段,B淋巴細(xì)胞能夠?yàn)楫a(chǎn)生相應(yīng)的抗體與抗原結(jié)合,同時(shí)活化、增殖和分化,產(chǎn)生漿細(xì)胞,通過(guò)中和、溶解和調(diào)理等作用,最終使抗原從體內(nèi)清除。另有一些B 細(xì)胞變成了長(zhǎng)期存活的記憶細(xì)胞,它通過(guò)血液、淋巴和組織液循環(huán),為下一次快速、高效的消除相同或者類似抗原引起的感染奠定了基礎(chǔ)。
免疫算法采用高變異克隆的單性繁殖搜索方式,避免了遺傳算法中的交叉操作引起的模式干擾,同時(shí)具有未被激發(fā)的細(xì)胞消亡及記憶細(xì)胞的產(chǎn)生等過(guò)程又保證了抗體的多樣性。
2 算法描述
克隆選擇算法模擬生物免疫系統(tǒng)的克隆選擇原理[2],一般將待優(yōu)化的目標(biāo)函數(shù)及其約束條件視為抗原,其算法步驟如下:
(1)初始化:隨機(jī)產(chǎn)生N個(gè)二進(jìn)制編碼的抗體對(duì)應(yīng)問(wèn)題的可能解。
(2)評(píng)價(jià)和選擇1:將N個(gè)抗體分解成由m和r個(gè)抗體組成的兩部分Am,Ar,分別表示進(jìn)入記憶集的抗體和剩下的部分,其中進(jìn)入記憶集的都是親和度較高的抗體。
(3)克?。涸谟H和度最高的抗體中選擇k個(gè)進(jìn)行克隆,克隆的數(shù)量與其親和度成正比。
(4)變異:模擬生物克隆選擇中的超變異過(guò)程,對(duì)克隆后的抗體執(zhí)行變異操作,變異按某一變異概率以一定規(guī)模隨機(jī)進(jìn)行。
(5)評(píng)價(jià)和選擇2:重新計(jì)算變異后的抗體的親和度,若克隆變異后的抗體中親和度最高的抗體比父代抗體的親和度還要高,就用該抗體替換原抗體,形成新的記憶集。
(6)消亡:模擬生物克隆選擇中5%的B細(xì)胞自然消亡的過(guò)程,在Ar中選擇d個(gè)親和度最低的抗體重新初始化,以保證抗體的多樣性。
(7)檢查是否滿足終止條件,若是,則終止,否則轉(zhuǎn)到(2),進(jìn)入下一次迭代。
通過(guò)分析不難發(fā)現(xiàn),在CLONAL算法中,所有個(gè)體都是二進(jìn)制編碼,計(jì)算時(shí)需要將十進(jìn)制數(shù)轉(zhuǎn)化為二進(jìn)制數(shù),最后又必須將二進(jìn)制數(shù)再轉(zhuǎn)化為十進(jìn)制數(shù);而且對(duì)于多維函數(shù)的優(yōu)化,二進(jìn)制編碼面臨“維數(shù)災(zāi)”問(wèn)題;其次,二進(jìn)制的位數(shù)也限制了求解的精度,要求得高精度的解,勢(shì)必大幅提高二進(jìn)制編碼的位數(shù),也給計(jì)算帶來(lái)了麻煩;另外,在CLONAL算法中,變異率是一個(gè)定值[3],抗體按這個(gè)變異率產(chǎn)生一定規(guī)模的隨機(jī)變異,這樣雖擴(kuò)大了搜索空間" title="搜索空間">搜索空間,增加了抗體的多樣性,同時(shí)也可能破壞親和度高的抗體,打亂抗體的結(jié)構(gòu),降低收斂速度。文獻(xiàn)[4]提出一種改進(jìn)免疫克隆" title="免疫克隆">免疫克隆多樣性算法,采用實(shí)數(shù)編碼,但它采用變異整個(gè)抗體群的方式進(jìn)行變異,沒(méi)有保持上代中親和度高的抗體的優(yōu)勢(shì)。文獻(xiàn)[5]結(jié)合小生境技術(shù),提出一種新的免疫算法,但該算法沒(méi)有克隆操作,雖提高了收斂速度,但限制了搜索空間。
本文提出了一種改進(jìn)的克隆選擇算法,該算法采用實(shí)數(shù)編碼,并引入自適應(yīng)變異算子,根據(jù)抗體的親和度調(diào)整變異步長(zhǎng)。仿真實(shí)驗(yàn)說(shuō)明該算法收斂速度快,運(yùn)算簡(jiǎn)單、易于實(shí)現(xiàn)。
3 算法改進(jìn)
在改進(jìn)的函數(shù)優(yōu)化免疫算法中,以實(shí)數(shù)編碼的候選解作為抗體,將目標(biāo)函數(shù)和約束條件視為抗原,將親和度高的抗體按與其親和度成正比進(jìn)行克隆,并引入自適應(yīng)變異算子,與親和度成反比進(jìn)行變異,使變異程度隨著親和度的提高逐步減小,促使抗體的穩(wěn)定收斂;同時(shí)親和度低的抗體按一定比例重新初始化,以保證多樣性。算法步驟如下:
(1)隨機(jī)初始化種群,種群大小為N,抗體采用實(shí)數(shù)編碼;
(2)根據(jù)目標(biāo)函數(shù)計(jì)算所有抗體的親和度;
(3)若達(dá)到結(jié)束條件,算法終止;
(4)選出部分親和度高的進(jìn)入記憶Am,剩下的抗體記為Ar;
(5)在Am中選出親和度最高的k個(gè)抗體進(jìn)行克隆得到克隆抗體群Ab;
(6)根據(jù)抗體的親和度計(jì)算每個(gè)抗體的變異率,并按該變異率進(jìn)行變異,得到變異抗體群Ac;
(7)重新計(jì)算Ac中每個(gè)抗體的親和度,在Ac中選出親和度高的抗體,并用它們調(diào)整記憶集;
(8)在抗體的記憶集之外取得d個(gè)親和度最低的抗體運(yùn)用消亡算子予以拋棄,將其重新初始化,形成新的免疫網(wǎng)絡(luò);
(9)回到(2)。
3.1 克隆變異
算法中主要的免疫操作包括了克隆和變異。
克隆是拷貝抗體編碼模式的過(guò)程,假設(shè)父代抗體為X=[x1,x2,……xn]T,則克隆后產(chǎn)生的子代抗體為X′=Ii×X,Ii是NCi維行向量。而NCi就決定了抗體克隆的數(shù)量,在這里NCi可由下式得到:
β∈(0,1)是克隆常數(shù),N是種群規(guī)模,將要克隆的抗體按親和度排序,i是其序號(hào),其結(jié)果是親和度越高的抗體克隆的數(shù)量越多。
變異的目的是使子代抗體的編碼發(fā)生變化,以期得到優(yōu)于父代的更好的解。由于算法中的抗體采用實(shí)數(shù)編碼,因此原來(lái)的變異方法不再適用,而是采取了高斯變異的方式,并且變異并不作用到原始種群。
為了能在親和度高的抗體周圍集中搜索,同時(shí)又保證抗體的多樣性,本文引入了一種自適應(yīng)變異算子,即對(duì)每一個(gè)變異算子作用到的個(gè)體分量:
xi′=xi+Nmi*N(0,1) (2)
其中N(0,1)是一個(gè)服從標(biāo)準(zhǔn)高斯分布的隨機(jī)數(shù);而Nmi則對(duì)應(yīng)抗體的變異率,不失一般性,對(duì)求解最小值的問(wèn)題:
顯然,抗體的變異率是與其親和度成反比的,親和度越高變異率越小,抗體在每次迭代過(guò)程中根據(jù)親和度自適應(yīng)的調(diào)整變異步長(zhǎng),使得在親和度高的抗體周圍集中搜索以提高收斂速度,同時(shí)保持種群的多樣性。ρ為變異常數(shù),用來(lái)調(diào)整變異強(qiáng)度,與搜索的空間大小和種群規(guī)模相關(guān)。
3.2 調(diào)整免疫網(wǎng)絡(luò)
與遺傳算法相比,免疫算法的一大特點(diǎn)就是其具有記憶性,從新的抗體群中選出優(yōu)勢(shì)個(gè)體,排除退化個(gè)體的過(guò)程就是重新生成免疫網(wǎng)絡(luò)的過(guò)程。
經(jīng)過(guò)克隆和變異后,若存在新抗體ρ=min{f(xij)|j=1,2,……n},使得f(p)
而對(duì)于那些退化的個(gè)體,即親和度最低的一部分抗體,則通過(guò)重新初始化的方法使其消亡,以保持種群的多樣性。
4 仿真實(shí)驗(yàn)
為測(cè)試算法性能采用了以下3個(gè)典型測(cè)試函數(shù):
f3是Rosenbrock函數(shù),非凸、病態(tài)函數(shù),在xi=1時(shí)達(dá)到極小值點(diǎn)。
初始種群大小為100,維數(shù)為20,最大截止代數(shù)為400的情況下,改進(jìn)的克隆選擇算法(表1中顯示為ACLONALG)連續(xù)10次實(shí)驗(yàn)的結(jié)果與CLONALG算法比較見(jiàn)表1。
?
?
實(shí)驗(yàn)結(jié)果表明,算法在3個(gè)函數(shù)上均優(yōu)于CLONALG算法,收斂速度和精度都有明顯提高。圖1、圖2和圖3分別顯示了CLONALG和改進(jìn)的克隆選擇算法(ACLONLG)在3個(gè)函數(shù)上運(yùn)行10次的平均實(shí)驗(yàn)結(jié)果,縱坐標(biāo)取函數(shù)值的對(duì)數(shù),其中CLONALG(10)表示維數(shù)為10的CLONALG算法,其他類似。從圖中可以看出,本文提出的算法對(duì)于f1來(lái)說(shuō),在10維的情況下不及CLONALG,但在20維的情況下卻優(yōu)于CLONALG,特別在運(yùn)行后期收斂速度加快;而在f2和f3上,收斂速度和精度均高出CLONALG,顯示出明顯的優(yōu)勢(shì)。
本文介紹了免疫優(yōu)化算法的基本原理,并通過(guò)分析,提出了一種改進(jìn)的算法用于函數(shù)優(yōu)化。該算法的主要步驟包括初始化種群、親和度計(jì)算、選擇、克隆、超變異、消亡等,屬隨機(jī)優(yōu)化算法,具有顯示的并行性。通過(guò)3個(gè)典型測(cè)試函數(shù)對(duì)算法進(jìn)行了仿真實(shí)驗(yàn),與CLONALG的結(jié)果進(jìn)行了比較。結(jié)果表明,本文所提算法收斂速度和精度均有提高,解的多樣性增加,在高維情況下優(yōu)勢(shì)明顯。
參考文獻(xiàn)
1 Burnet F M.The Clonal Selection Theory of Acquired Immunity.London:Cambridge University Press,1959
2 Castro L N,Zuben F J.Learning and OptimizationUsing the Clonal Selection Principle IEEE Transactions on Evolution-aryComputation,Special Issue on Artificial Immune Systems,2002;(6)239-251
3 Castro L N,Matlab code for CLONALG is on his webpage.2001.http://www.dca.fee.unicamp.br/~lnunes
4 莫宏偉,金鴻章.用于函數(shù)優(yōu)化的改進(jìn)免疫克隆多樣性算法.哈爾濱工程大學(xué)學(xué)報(bào),2004;25(1)
5 張著洪,黃席樾.一種新的免疫算法及其在多模態(tài)函數(shù)優(yōu)化中的應(yīng)用.控制理論與應(yīng)用,2004;21(1)