一種用于函數(shù)優(yōu)化的免疫算法

1、    一種用于函數(shù)優(yōu)化的免疫算法    一種用于函數(shù)優(yōu)化的免疫算法    類別：嵌入式系統(tǒng)                              &nbsp來源：電子技術(shù)應用

2、作者：劉麗玨 唐璉 蔡自興        &nbsp摘要：人工免疫系統(tǒng)是基于生物免疫系統(tǒng)特性而發(fā)展的新興智能系統(tǒng)。利用免疫系統(tǒng)的克隆選擇機制，提出一種用于函數(shù)優(yōu)化的改進免疫算法。其主要特點是采用克隆和自適應變異等操作，提高收斂速度和種群的多樣性。仿真程序表明，該算法能以較快速度完成給定范圍的搜索和全局優(yōu)化任務。        &nbsp關鍵詞：克隆選擇免疫自適應變異函數(shù)優(yōu)化       &#

3、160; &nbsp在工程實際中，很多問題都可轉(zhuǎn)化為函數(shù)優(yōu)化問題，而對于高維、非凸、且有多個局部極值點的函數(shù)優(yōu)化問題，傳統(tǒng)的基于梯度的算法通常不能求得理想解。免疫系統(tǒng)作為一種分布式自學習系統(tǒng)，能自適應地維持群體多樣性及具有自我調(diào)節(jié)功能，導致基于免疫機制的算法具有整體、局部搜索能力強的特點，使得這類算法在函數(shù)優(yōu)化、組合優(yōu)化、模式識別、數(shù)據(jù)挖掘及機器學習等方面得到了有效應用。        &nbsp1 免疫算法原理   &nbsp免疫算法的靈感來自生物獲得性免疫的

4、克隆選擇原理。根據(jù)該原理，在生物免疫系統(tǒng)中，一旦病原體侵入肌體就被分解為抗原片段，B淋巴細胞能夠為產(chǎn)生相應的抗體與抗原結(jié)合，同時活化、增殖和分化，產(chǎn)生漿細胞，通過中和、溶解和調(diào)理等作用，最終使抗原從體內(nèi)清除。另有一些B細胞變成了長期存活的記憶細胞，它通過血液、淋巴和組織液循環(huán)，為下一次快速、高效的消除相同或者類似抗原引起的感染奠定了基礎。   &nbsp免疫算法采用高變異克隆的單性繁殖搜索方式，避免了遺傳算法中的交叉操作引起的模式干擾，同時具有未被激發(fā)的細胞消亡及記憶細胞的產(chǎn)生等過程又保證了抗體的多樣性。    &#

5、160;  &nbsp2 算法描述   &nbsp克隆選擇算法模擬生物免疫系統(tǒng)的克隆選擇原理，一般將待優(yōu)化的目標函數(shù)及其約束條件視為抗原，其算法步驟如下：    (1)初始化：隨機產(chǎn)生N個二進制編碼的抗體對應問題的可能解。    (2)評價和選擇1：將N個抗體分解成由m和r個抗體組成的兩部分Am，Ar，分別表示進入記憶集的抗體和剩下的部分，其中進入記憶集的都是親和度較高的抗體。    (3)克?。涸谟H和度最高的

6、抗體中選擇k個進行克隆，克隆的數(shù)量與其親和度成正比。    (4)變異：模擬生物克隆選擇中的超變異過程，對克隆后的抗體執(zhí)行變異操作，變異按某一變異概率以一定規(guī)模隨機進行。    (5)評價和選擇2：重新計算變異后的抗體的親和度，若克隆變異后的抗體中親和度最高的抗體比父代抗體的親和度還要高，就用該抗體替換原抗體，形成薪的記憶集。    (6)消亡：模擬生物克隆選擇中5的B細胞自然消亡的過程，在Ar中選擇d個親和度最低的抗體重新初始化，以保證抗體的多樣性。  

7、  (7)檢查是否滿足終止條件，若是，則終止，否則轉(zhuǎn)到(2)，進入下一次迭代。   &nbsp通過分析不難發(fā)現(xiàn)，在CLONAL算法中，所有個體都是二進制編碼，計算時需要將十進制數(shù)轉(zhuǎn)化為二進制數(shù)，最后又必須將二進制數(shù)再轉(zhuǎn)化為十進制數(shù)；而且對于多維函數(shù)的優(yōu)化，二進制編碼面臨“維數(shù)災”問題；其次，二進制的位數(shù)也限制了求解的精度，要求得高精度的解，勢必大幅提高二進制編碼的位數(shù)，也給計算帶栗了麻煩；另外，在CLDNAL算法中，變異率是一個定值，抗體按這個變異率產(chǎn)生一定規(guī)模的隨機變異，這樣雖擴大了搜索空間，增加了抗體的多樣性，同時也可能破壞親和度高

8、的抗體，打亂抗體的結(jié)構(gòu)，降低收斂速度。文獻提出一種改進免疫克隆多樣性算法，采用實數(shù)編碼，但它采用變異整個抗體群的方式進行變異，沒有保持上代中親和度高的抗體的優(yōu)勢。文獻結(jié)合小生境技術(shù)，提出一種新的免疫算法，但該算法沒有克隆操作，雖提高了收斂速度，但限制了搜索空間。   &nbsp本文提出了一種改進的克隆選擇算法，該算法采用實數(shù)編碼，并引入自適應變異算子，根據(jù)抗體的親和度調(diào)整變異步長。仿真實驗說明該算法收斂速度快運算簡單、易于實現(xiàn)。       &nbsp3 算法改進 &#

9、160; &nbsp在改進的函數(shù)優(yōu)化免疫算法中，以實數(shù)編碼的候選解作為抗體，將目標函數(shù)和約束條件視為抗原，將親和度高的抗體按與其親和度成正比進行克隆，并引入自適應變異算子，與親和度成反比進行變異，使變異程度隨著親和度的提高逐步減小，促使抗體的穩(wěn)定收斂；同時親和度低的抗體按一定比例重新初始化，以保證多樣性。算祛步驟如下：    (1)隨機初始化種群，種群大小為N，抗體采用實數(shù)編碼；    (2)根據(jù)目標函數(shù)計算所有抗體的親和度；    (3)若達到結(jié)束條件，算

10、法終止；    (4)選出部分親和度高的進入記憶Am，剩下的抗體記為Ar；    (5)在Am中選出親和度最高的k個抗體進行克隆得到克隆抗體群Ab；    (6)根據(jù)抗體的親和度計算每個抗體的變異率，并按該變異率進行變異，得到變異抗體群Ac；    (7)重新計算Ac中每個抗體的親和度，在Ac中選出親和度高的抗體，并用它們調(diào)整記憶集；    (8)在抗體的記憶集之外取得d個親和度最低的抗體運用消亡

11、算子予以拋棄，將其重新初始化，形成新的免疫網(wǎng)絡；    (9)回到(2)。       &nbsp31 克隆變異   &nbsp算法中主要的免疫操作包括了克隆和變異。   &nbsp克隆是拷貝抗體編碼模式的過程，假設父代抗體為X=x1，x2，xnT，則克隆后產(chǎn)生的子代抗體為X=Ii×   &nbspX，Ii是NCi維行向量。而NCi就決定了抗體克隆的數(shù)量，

12、在這里NCi可由下式得到：        &nbsp(0，1)是克隆常數(shù)，N是種群規(guī)模，將要克隆的抗體按親和度排序，i是其序號。其結(jié)果是親和度越高的抗體克隆的數(shù)量越多。   &nbsp變異的目的是使子代抗體的編碼發(fā)生變化，以期得到優(yōu)于父代的更好的解。由于算法中的抗體采用實數(shù)編碼，因此原來的變異方法不再適用，而是采取了高斯變異的方式，并且變異并不作用到原始種群。   &nbsp為了能在親和度高的抗體周圍集中搜索，同時又保證抗體的多樣性，本文引入

13、了一種自適應變異算子，即對每一個變異算子作用到的個體分量：   &nbsp其中N(0，1)是一個服從標準高斯分布的隨機數(shù)；而Nmi則對應抗體的變異率，不失一般性，對求解最小值的問題：        &nbsp顯然，抗體的變異率是與其親和度成反比的，親和度越高變異率越小，抗體在每次迭代過程中根據(jù)親和度自適應的調(diào)整變異步長，使得在親和度高的抗體周圍集中搜索以提高收斂速度，同時保持種群的多樣性。為變異常數(shù)，用來調(diào)整變異強度，與搜索的空間大小和種群規(guī)模相關。  

14、60;    &nbsp32 調(diào)整免疫網(wǎng)絡   &nbsp與遺傳算法相比，免疫算法的一大特點就是其具有記憶性，從新的抗體群中選出優(yōu)勢個體，排除退化個體的過程就是重新生成免疫網(wǎng)絡的過程。   &nbsp經(jīng)過克隆和變異后，若存在新抗體=minf(xij)|j=1，2，n，使得f(p)<f(xi)則用p取代其父抗體xi，更新抗體群。   &nbsp而對于那些退化的個體，即親和度最低的一部分抗體，則通過重新初始化的方法使其消亡，以保持種

15、群的多樣性。        &nbsp4 仿真實驗   &nbsp為測試算法性能采用了以下3個典型測試函數(shù)：        &nbsp初始種群大小為100，維數(shù)為20，最大截止代數(shù)為400的情況下，改進的克隆選擇算法(表1中顯示為ACLONALG)連續(xù)lO次實驗的結(jié)果與CLONALG算法比較見表l。             &nbsp實驗結(jié)果表明，算法在3個函數(shù)上均優(yōu)于CLONALG算法，收斂速度和精度都有明顯提高。圖1、圖2和圖3分別顯示了CLONALG和改進的克隆選擇算法(ACLONLG)在3個函數(shù)上運行10次的平均實驗結(jié)果，縱坐標取函數(shù)值的對數(shù)，其中cLONALG(10)表示維數(shù)為10的CLONALG算法，其他類似。從圖中可以看出，本文提出的算法對于f1來說，在lO維的情況下不及CLONALG，但在20維的情況下卻優(yōu)于CLONALG，特別在運行后期收斂速度加快；而在f2和f3上，收斂速度和精度均高出CLONALC，顯示出明顯的優(yōu)