一種用于函數優(yōu)化的免疫算法
人工免疫系統是基于生物免疫系統特性而發(fā)展的新興智能系統。利用免疫系統的克隆選擇機制,提出一種用于函數優(yōu)化的改進(jìn)免疫算法。其主要特點(diǎn)是采用克隆和自適應變異等操作,提高收斂速度和種群的多樣性。仿真程序表明,該算法能以較快速度完成給定范圍的搜索和全局優(yōu)化任務(wù)。
本文引用地址:http://dyxdggzs.com/article/83867.htm在工程實(shí)際中,很多問(wèn)題都可轉化為函數優(yōu)化問(wèn)題,而對于高維、非凸、且有多個(gè)局部極值點(diǎn)的函數優(yōu)化問(wèn)題,傳統的基于梯度的算法通常不能求得理想解。免疫系統作為一種分布式自學(xué)習系統,能自適應地維持群體多樣性及具有自我調節功能,導致基于免疫機制的算法具有整體、局部搜索能力強的特點(diǎn),使得這類(lèi)算法在函數優(yōu)化、組合優(yōu)化、模式識別、數據挖掘及機器學(xué)習等方面得到了有效應用。
1 免疫算法原理
免疫算法的靈感來(lái)自生物獲得性免疫的克隆選擇原理。根據該原理,在生物免疫系統中,一旦病原體侵入肌體就被分解為抗原片段,B淋巴細胞能夠為產(chǎn)生相應的抗體與抗原結合,同時(shí)活化、增殖和分化,產(chǎn)生漿細胞,通過(guò)中和、溶解和調理等作用,最終使抗原從體內清除。另有一些B細胞變成了長(cháng)期存活的記憶細胞,它通過(guò)血液、淋巴和組織液循環(huán),為下一次快速、高效的消除相同或者類(lèi)似抗原引起的感染奠定了基礎。
免疫算法采用高變異克隆的單性繁殖搜索方式,避免了遺傳算法中的交叉操作引起的模式干擾,同時(shí)具有未被激發(fā)的細胞消亡及記憶細胞的產(chǎn)生等過(guò)程又保證了抗體的多樣性。
2 算法描述
克隆選擇算法模擬生物免疫系統的克隆選擇原理,一般將待優(yōu)化的目標函數及其約束條件視為抗原,其算法步驟如下:
(1)初始化:隨機產(chǎn)生N個(gè)二進(jìn)制編碼的抗體對應問(wèn)題的可能解。
(2)評價(jià)和選擇1:將N個(gè)抗體分解成由m和r個(gè)抗體組成的兩部分Am,Ar,分別表示進(jìn)入記憶集的抗體和剩下的部分,其中進(jìn)入記憶集的都是親和度較高的抗體。
(3)克?。涸谟H和度最高的抗體中選擇k個(gè)進(jìn)行克隆,克隆的數量與其親和度成正比。
(4)變異:模擬生物克隆選擇中的超變異過(guò)程,對克隆后的抗體執行變異操作,變異按某一變異概率以一定規模隨機進(jìn)行。
(5)評價(jià)和選擇2:重新計算變異后的抗體的親和度,若克隆變異后的抗體中親和度最高的抗體比父代抗體的親和度還要高,就用該抗體替換原抗體,形成薪的記憶集。
(6)消亡:模擬生物克隆選擇中5%的B細胞自然消亡的過(guò)程,在A(yíng)r中選擇d個(gè)親和度最低的抗體重新初始化,以保證抗體的多樣性。
(7)檢查是否滿(mǎn)足終止條件,若是,則終止,否則轉到(2),進(jìn)入下一次迭代。
通過(guò)分析不難發(fā)現,在CLONAL算法中,所有個(gè)體都是二進(jìn)制編碼,計算時(shí)需要將十進(jìn)制數轉化為二進(jìn)制數,最后又必須將二進(jìn)制數再轉化為十進(jìn)制數;而且對于多維函數的優(yōu)化,二進(jìn)制編碼面臨“維數災”問(wèn)題;其次,二進(jìn)制的位數也限制了求解的精度,要求得高精度的解,勢必大幅提高二進(jìn)制編碼的位數,也給計算帶栗了麻煩;另外,在CLDNAL算法中,變異率是一個(gè)定值,抗體按這個(gè)變異率產(chǎn)生一定規模的隨機變異,這樣雖擴大了搜索空間,增加了抗體的多樣性,同時(shí)也可能破壞親和度高的抗體,打亂抗體的結構,降低收斂速度。文獻提出一種改進(jìn)免疫克隆多樣性算法,采用實(shí)數編碼,但它采用變異整個(gè)抗體群的方式進(jìn)行變異,沒(méi)有保持上代中親和度高的抗體的優(yōu)勢。文獻結合小生境技術(shù),提出一種新的免疫算法,但該算法沒(méi)有克隆操作,雖提高了收斂速度,但限制了搜索空間。
本文提出了一種改進(jìn)的克隆選擇算法,該算法采用實(shí)數編碼,并引入自適應變異算子,根據抗體的親和度調整變異步長(cháng)。仿真實(shí)驗說(shuō)明該算法收斂速度快.運算簡(jiǎn)單、易于實(shí)現。
3 算法改進(jìn)
在改進(jìn)的函數優(yōu)化免疫算法中,以實(shí)數編碼的候選解作為抗體,將目標函數和約束條件視為抗原,將親和度高的抗體按與其親和度成正比進(jìn)行克隆,并引入自適應變異算子,與親和度成反比進(jìn)行變異,使變異程度隨著(zhù)親和度的提高逐步減小,促使抗體的穩定收斂;同時(shí)親和度低的抗體按一定比例重新初始化,以保證多樣性。算祛步驟如下:
(1)隨機初始化種群,種群大小為N,抗體采用實(shí)數編碼;
(2)根據目標函數計算所有抗體的親和度;
(3)若達到結束條件,算法終止;
(4)選出部分親和度高的進(jìn)入記憶Am,剩下的抗體記為Ar;
(5)在A(yíng)m中選出親和度最高的k個(gè)抗體進(jìn)行克隆得到克隆抗體群Ab;
(6)根據抗體的親和度計算每個(gè)抗體的變異率,并按該變異率進(jìn)行變異,得到變異抗體群Ac;
(7)重新計算Ac中每個(gè)抗體的親和度,在A(yíng)c中選出親和度高的抗體,并用它們調整記憶集;
(8)在抗體的記憶集之外取得d個(gè)親和度最低的抗體運用消亡算子予以?huà)仐?,將其重新初始化,形成新的免疫網(wǎng)絡(luò );
(9)回到(2)。
評論