改進的免疫克隆遺傳算法研究及其在函數優化中的應用*

宮照煊，王 莉

(遼寧科技大學 電子與信息工程學院，遼寧 鞍山 114051)

對于函數優化問題，傳統的經典優化方法大都是基于梯度下降或者需要求解問題的導數。而對于多峰、多態以及求解空間比較大的復雜函數，傳統算法的求解效果很有限，甚至無法求解。遺傳算法雖然簡單易行，并以高效性、隱并行性成為求解優化問題的有效方法[1]，但其為群體中的個體提供進化機會的同時，在某種情況下退化現象也相當明顯。近年來，人們在基于生物免疫原理的基礎上提出了多種人工免疫系統模型和算法[2]，并應用到自動控制、故障診斷、優化計算等領域。免疫克隆遺傳算法是將免疫原理與遺傳算法相結合所發展的一種新算法。免疫克隆遺傳算法提供記憶細胞，使變異向提高適應值的方向發展，避免了搜索的盲目性。但對于求解一些高精度的復雜函數問題，免疫克隆遺傳算法的求解效果欠佳，主要原因是算法在進化后期的局部搜索能力有限，以及種群多樣性的快速下降而導致算法過早收斂到最優解的附近，而很難收斂到最優解。針對上述問題，本文提出了一位修正算子來解決算法進化后期存在的問題，并對免疫克隆遺傳算法的各個算子都做了相應的改進，最后用標準遺傳算法SGA(Standard Genrtic Algorithm)、免疫克隆遺傳算法IMGA(Immunity Monoclonal Genrtic Algorithm)以及本文的算法比較，并且與參考文獻[6]和參考文獻[7]的方法作了比較。實驗結果表明，本文的算法收斂速度更快、求解精度更高，并且能有效解決免疫克隆遺傳算法后期進化慢的問題。

1 改進的免疫克隆遺傳算法計算步驟

1.1 基本步驟的改進

1.1.1 編碼

改進的免疫克隆遺傳算法采用實數編碼來處理算法的編碼過程，基于實數編碼不會存在二進制編碼中的Hamming懸崖問題，并且求解精度要比二進制編碼高很多，基于實數編碼的遺傳算法能很快收斂到最優解附近。

1.1.2 初始化

不論采用離散重組算子還是算數雜交算子，搜索范圍只局限于初始群體所確定的最大矩體內。采用混沌初始化方法，利用混沌的遍歷性、隨機性和內在規律性來最大化初始種群所確定的矩體。混沌初始化在保持種群多樣性的同時，對防止算法陷入局部最優解也起到了一定作用。Logist映射：

式中μ取 4，此時的 Logisti映射為在(0，1)區間上的完全混沌狀態。產生混沌初始種群的方法：隨機初始化x0∈(0，1)，利用式(1)生成混沌序列 x0，x1，x2，…xi(i=1，2，…m)，其中 m 為種群數。 利用混沌序列 x0，x1，x2，…xi生成初始群體 p0，p1，…pi(i=1，2，…m)。

1.1.3 選擇

本算法在采用輪盤賭選擇法的基礎上引入了適應值的非單調標度變換，用來解決種群中出現個別適應值極高的個體時，可能導致這些個體在種群中迅速繁殖的現象，即讓一些適應值較小的個體也有參加進化的可能，從而增加種群多樣性。在選擇算子中采用精英保留策略，現已證明采用精英保留策略的遺傳算法能以概率1收斂到問題的最優解[3]。適應值的非單調標度變換：

其中fmax為當前適應值最大的個體，fmin為當前適應值最小的個體，eval[i]為當前各個體的適應值[4]。

1.1.4 改進的自適應變異、雜交概率

改進的自適應變異、雜交概率能提高群體中表現優良的個體交叉率和變異率，使得這些優良個體避免出現近似停滯不前的狀態，從而增加進化走出局部最優解的可能性。

式中 Pc1=0.9，Pc2=0.6，Pm1=1，Pm2=0.001

因為免疫克隆算子有記憶的功能，使得進化一直向適應值增加的方向進行，所以Pm1=1。

1.1.5 改進的免疫克隆變異雜交

本算法在免疫克隆變異、雜交的基礎上考慮了染色體各個基因位對適應值的影響程度。針對函數優化問題，考慮到在進化初期染色體的前幾位對適應值的影響相對后幾位要大，所以在進化初期算法主要對染色體的前幾位進行變異和雜交；在進化后期對染色體的后幾位進行變異和雜交，這樣做可以大大縮小搜索范圍。免疫克隆變異、雜交是將各個體克隆一定數量后進行變異、雜交操作，并且保留原個體信息。將克隆變異、雜交后的個體與原個體比較，選出適應值最高的個體來作為新個體[5]。

1.1.6 位爬山局部搜索算法

免疫克隆遺傳算法最主要的特點是能以較快的速度搜索到最優解的90%左右，全局搜索能力強，但是在進化后期的局部搜索能力相對較弱。位爬山算法是一種傳統的局部搜索算法，將位爬山算法與免疫克隆遺傳算法相結合可以取得較好的效果，本文在傳統位爬山算法的基礎上提出了一位修正算子，用來改進其在后期搜索過程中的不足，并在仿真實驗中得到了滿意的結果。

1.2 改進的位爬山算法

傳統的位爬山算法過程是[3]：

(1)對于染色體aji=(aj1，aj2，…aji)其中 i∈(1，2，…n)，j∈(1，2，…m)計算個體的適應值：f*=f(aji)，i=1，j=1；

(2)變異各位基因值 ：a′ji=1-aji；

(3)計算新個體適應值：f(a′ji)；

(4)比較新個體適應值：if f(a′ji)＞f*then f*=f(a′ji)

a′ji=(aj1，aj2，…a′ji，aji+1，…ajn)；

(5)循環 i=i+1，返回(2)；

(6)若 i=n，j=j+1 返回(1)；

(7)若 j=m，終止。

位爬山算法存在以下問題：(1)局部最大：某個節點比周圍任何一個鄰居都高，但是卻不是整個問題的最高點。(2)高地(也稱為平頂)：搜索一旦到達高地，就無法確定搜索最佳方向，會產生隨機走動，使得搜索效率降低。(3)山脊：搜索可能會在山脊的兩面來回振蕩，前進步伐很小。

對于函數優化問題來說，最優解的每一位數的取值都受其后幾位的影響，所以傳統的位爬山算法很可能指導算法向偏離最優解的方向搜索。

針對上述問題，本文提出了一位修正算子來改進位爬山算法的不足。具體過程如下：

(1)設aij是利用位爬山算法搜索到的第i個個體中變異第j位基因所得到的最優變異個體。

(2)對于該最優變異個體，在其他位不變的情況下，搜索aij與aij-1的全部組合所得到的個體適應值為evalk，k=0，1，2，…，99aij，aij-1∈(0，9)。

改進的位爬山算法可以以較大的概率避免算法向遠離最優解的方向搜索，在進化后期采用改進的位爬山算法搜索到最優解的能力也大大提高了。實驗表明，改進的位爬山算法能以較大的概率克服傳統位爬山算法的不足，并且能較快收斂到最優解。

2 仿真實驗

本文選取了4個具有相當復雜度的測試函數：

F1函數在自變量取值區間內有多個極值點，精確到10-12的最優解為 2.850 273 766 768。

表1 4種函數50次獨立實驗的統計結果

F2函數有6個局部極小點，其中有 2個點(-0.898，0.712 6)和(0.898，-0.712 6)為全局最小點，最小值為-1.031 628。

F3函數有760個局部極小點，其中有18個全局最小點，最小值為186.73，此函數極易陷入局部極小值185.25。

F4 函數(大海撈針函數)，α∈{0.1，0.01，0.001}隨著α的取值不同，此函數形成不同嚴重程度的模式欺騙問題。當α=0.001時，此函數有無限個局部極大點，其中只有1個點(0，0)為全局最大值點，最大值為1。此函數最大值周圍有1個圈脊，取值均為0.990 283，因此此函數非常容易停滯在此局部極大點。本文α取0.001。

對SGA、IMGA以及本文的算法進行了比較，參數選取如下：F1種群數 50，最大進化代數 50；F2種群數100，最大進化代數 50；F3種群數 50，最大進化代數 50；F4種群數100，最大進化代數50。4種函數的50次獨立實驗結果如表1所示：

從表1中可以看到，由于函數本身的復雜性，SGA的結果是不如人意的。IMGA對于前3個函數能較快收斂到最優解，但由于F4函數具有嚴重的模式欺騙問題，使得IMGA只能搜索到局部最優。而本文算法在求解精度和求得全局最優解的次數上都遠優于SGA和IMGA。

[6]使用一種基于種群劃分和雜交的免疫遺傳算法對F1函數作了測試，表2為參考文獻[6]中的算法與本文算法在獨立測試100次后的比較結果：

從表2可以看出，在種群數一樣的前提下本文算法與參考文獻[6]中的算法都能收斂到最優解，但本文算法利用一位修正算子大大提高了進化后期的收斂速度，因此所需的平均進化代數要比參考文獻[6]中的算法少得多。

表2 參考文獻[6]算法與本文算法在F1函數上的性能比較

參考文獻[7]對遺傳算法的各個算子都做了改進，并對F2函數和F4函數作了測試，表3為參考文獻[7]算法與本文算法的比較結果。

表3 參考文獻[7]算法與本文算法在F2與F4函數上的性能比較

從表3可以看出對于F2函數與F4函數，當進化20代后，本文算法得到的最優解都要優于參考文獻 [7]中的算法，在進化到40代時，本文算法都收斂到了最優解。

本文在免疫克隆遺傳算法的基礎上對各個算子都做了一些改進，并且提出了一種一位修正算子來克服免疫克隆遺傳算法在后期搜索方面的不足。實驗結果表明本文的算法在收斂速度和收斂精度上遠遠優于SGA和IMGA，并且通過與參考文獻[6]和參考文獻[7]中的算法的比較，體現出本文算法在進化代數上的優勢。

參考文獻

[1]王小平，曹立明.遺傳算法理論應用與軟件實現[M].西安：西安交通大學出版社：2002.

[2]DU H， JIAO L， WANG S.Clonal Operator and antibody clone algorithms[C].Proceedings of the First International Conferrence on Machine Learning and Cybernetics， Beijing，2002.

[3]張文修.遺傳算法的數學基礎[M].西安：西安交通大學出版社，2000.

[4]李敏強，林丹，李書全.遺傳算法的基本理論與應用[M].北京：科學出版社，2002.

[5]焦李成，劉芳，緱水平.智能數據挖掘與知識發現[M].西安：西安電子科技大學出版社，2006.

[6]武研，李儒耘.一種基于種群劃分及雜交的免疫遺傳算法[J].計算機工程，2008，2(3)：220-222.

[7]王慶明，宋玉梅.基于改進遺傳算法的函數優化及其性能分析.機械設計與制造[J].2007，2(2)：52-54.