基于遺傳的免疫算法在函數優化中的應用

摘要:通過對傳統免疫算法的研究，在此算法的基礎上提出了一種改進的免疫算法—基于遺傳的免疫算法，該算法把遺傳算法的思想引入到免疫算法中，通過把遺傳算法和免疫算法的思想結合起來，既保證了抗體的多樣性又保留了群體中較優抗體，避免了免疫算法搜索速度慢和遺傳算法易出現未成熟收斂、限于局部最優解的缺點，得到了全局最優解。并且將提出的基于遺傳的免疫算法應用到函數優化中。

關鍵詞:免疫算法;遺傳算法;函數優化

中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2009)25-7217-02

Application of Immune Algorithm Based on Genetic in Function Optimization

ZHAO Lian-di， MA Yong-qiang

(School of Information Science and Technology， Southwest JiaoTong University， Chengdu 610031， China)

Abstract: Through the research of traditional immune algorithm， an improved effective immune genetic algorithm is proposed based on this algorithm. The algorithm put the thought of genetic algorithm into immune algorithm， by combining idea of genetic algorithm and immune algorithm， It not only ensure the diversity of the antibody but also retain the better antibodies in group， and avoid the disadvantage of immune algorithm’s slow search speed and genetic algorithm prone to premature convergence and limit to local optimal solution， finally get the global optimal solution. And the proposed immune algorithm based on genetic applied to function optimization.

Key words: immune algorithm; genetic algorithm; function optimization

免疫算法近幾年來得到了迅速發展，在眾多工程和科學領域中得到了廣泛應用，其中在工程應用中有許多復雜的組合優化問題和函數優化問題 ，這些問題大都是非線性的，有些甚至不連續，若不對其進行簡化處理，用常規的數學優化方法一般都無法進行有效求解。免疫算法[1-2]作為一種借鑒生物免疫系統獨有的計算機制，模擬生物免疫系統自適應調節過程的全局優化算法，具有搜索速度相對較快，群體多樣性，容易獲得全局最優解等特點。由于免疫算法有著其他算法無法比擬的優點，因此，人們廣泛的應用免疫算法來解決各種實際問題，然而在實際應用中還有許多問題有待進一步研究討論。免疫算法具有搜索全局最優解的優點，但是它的搜索速度還有待于改進，我們利用遺傳算法[3-4]的搜索局部最優解的優點來調節免疫算法，使它既能避免遺傳算法的“早熟”現象，又能使免疫算法的尋優速度和尋優質量有所提高。因此，研究免疫優化理論以及遺傳算法[5-8]設計新的有效優化算法對優化問題具有重要的意義。

1 基本免疫算法

基本免疫算法基于生物免疫系統基本機制，模仿了人體的免疫系統?；久庖咚惴◤捏w細胞理論和網絡理論得到啟發，實現了類似于生物免疫系統的抗原識別、細胞分化、記憶和自我調節的功能 。如果將免疫算法與求解優化問題的一般搜索方法相比較，那么抗原、抗體、抗原和抗體之間的親和性分別對應于優化問題的目標函數、優化解、解與目標函數的匹配程度。

基本免疫算法在優化領域中的應用非常廣泛，但其存在以下缺點[7]:

1)抗體評價主要靠抗體和抗原的親和度;

2)促進高親和度抗體和抑制低親和度抗體往往容易導致陷入局部最優;

3)記憶庫往往只在產生初始群體時被使用，在之后的過程中只是更新記憶庫，未再利用它，這沒起到加速收斂的效果。

2 基于遺傳的免疫算法

免疫系統對于一個優化問題而言，抗原對應問題的是目標函數，而抗體對應問題的最優解[9]。由于免疫算法和遺傳算法各有優缺點[1，8]，所以把二者結合起來，既能避免二者的缺點，又能更好的發揮優點。

如圖1所示，基于遺傳的免疫算法的主要步驟包括:

1)抗原輸入:輸入目標函數和各種約束，作為基于遺傳的免疫算法的抗原。

2)產生初始群體:對初始應答，初始抗體隨機產生，面對再次應答，部分或全部由上一代的進化群體而得，其余的隨機產生，這樣既保留了具有較高親和力的解，又保證了抗體的多樣性，因此，可提高收斂速度和全局搜索能力。

3)計算抗體的適應度:在當前群體中計算所有抗體的適應度。抗體的適應度函數通常是采用帶優化問題目標函數的某一變換。這里采用下面的公式:

D=1-abs(y'-y)

其中y為實際值，y'為用基于遺傳的免疫算法求得的最大值。

4)記憶細胞的更新:將與抗原的親和度高的抗體放到記憶細胞中。由于記憶細胞的數量有限，所以在每次更新時，用新加入的記憶細胞取代原有的記憶細胞中親和度較低的部分。

5)抗體生成的促進和抑制:當一種抗體和抗原相遇時，如果適應度越高則越接近最優解，反之，則越遠離最優解。在尋優過程中，采用在每一代記憶細胞中隨機產生部分新的抗體而取代適應度較低的抗體來調節記憶細胞，以防尋優陷入局部最優解。

6)群體更新:

① 免疫群體更新:通過選擇、克隆和變異操作，產生進入下一代的抗體。u為激活閥值，當適應度大于激活閥值時，就被選擇進行克隆，適應度越高，被克隆的數量越多，反之，越少?？寺的繛?l=round(10×(B(m)-u))，其中round為四舍五入取整，B(m)為第m個抗體的適應度，u為激活閥值。變異是對抗體進行小幅度的擾動，在它附近搜索最優解，本文中使用b=a+(2×rand()/10-0.1000)×a，其中a為原始抗體，rand()為隨機產生的0-1之間的數。

② 遺傳群體的更新:在父代中隨機的選擇更適應的個體，產生后代以構成下一代，在一代中好的個體可能被選幾次，而較差的個體可能沒有機會被選到。當選出兩個父代個體后，它們被重組，這里C(n)=A(s)+(2×rand()/10-0.1000) ×A(t)，C(n+1)= A(t)+(2×rand()/10-0.1000) ×A(s)，其中C(n)、C(n+1)為A(t)、A(s)交叉變異后的兩個個體。

7)終止條件判斷:若滿足終止條件，輸出最優解，否則，轉3)。

3 基于遺傳的免疫算法在函數優化中的應用

函數優化通常是極大或極小某個多變量的函數并滿足一些等式或不等式的約束。函數優化分為無約束優化和約束優化兩類。雖然絕大多數實際優化問題都有必須滿足的約束，但是無約束優化問題的研究是約束優化問題的基礎。現有的函數優化研究大都是面向單峰函數優化問題的，但在現實生活中，很多數學工程問題都是多峰函數優化問題。對這種問題，當然可以采用多次優化計算直至發現所有峰值，但這不僅浪費時間，還不能保證各次計算收斂到多個不同的峰上。免疫遺傳算法以其獨特的種群策略和內在的并行性成為很多學者用來求解多峰函數優化問題的最佳選擇。為了驗證本文所提出的免疫遺傳算法在函數優化中的應用，我們采用下列函數進行優化計算，如圖2:

我們采用上述免疫遺傳算法進行函數優化，用于檢驗該算法的有效性。本文對免疫算法和免疫遺傳算法各做了200次試驗，免疫遺傳算法尋找到最優解的平均迭代次數為31.16次，而免疫算法的平均迭代次數為34.61次，試驗結果如圖3所示，其中橫坐標表示搜索到最優解所需要的迭代次數，縱坐標表示在200次試驗中搜索到最優解的試驗次數。從圖3中我們可以看出，本文所提出的把免疫算法和遺傳算法結合起來的方法由于對抗體一半進行免疫搜索一半進行遺傳搜索，之后進行交換抗體，循環迭代，充分利用了免疫算法和遺傳算法的優點，有效的避免了兩者的不足，所以更容易收斂到最優解。

顯然，由圖4可以看出免疫遺傳算法在200次試驗中，迭代次數小于10的試驗有52次，而免疫算法有45次;免疫遺傳算法迭代次數大多數集中在50以內，在200次試驗中免疫遺傳算法有173次，免疫算法有155次，免疫遺傳算法明顯多于免疫算法;迭代次數在50次以上的試驗次數明顯少于免疫算法，而且迭代次數超過100次的，免疫遺傳算法是6次，免疫算法是13次，明顯優于免疫算法?？傮w而言，本文提出的免疫遺傳算法在大部分情況下確實有一定的優勢，可以更快的搜索到全局最優解。

4 結論

介紹了基本免疫算法及其存在的缺點，針對其存在的缺點，提出把人工免疫算法與遺傳算法相結合，在每一代操作中，把抗體分為兩部分，一部分使用免疫算法的思想進行操作，另一部分使用遺傳算法的思想進行操作，在本代執行完后，把兩部分進行交換，很好的保證了抗體的多樣性和群體中的最優抗體，避免了免疫算法搜索速度慢和遺傳算法易出現未成熟收斂、限于局部最優解的缺點。將所提出的算法應用到函數優化問題中，在求解過程中，我們把抗原作為對應問題的目標函數和約束條件，把抗體作為對應問題的最優解。仿真實驗證明，本文所提出的算法具有較好的優化效果，有較強的脫離局部最優值的能力，能快速穩定收斂。

參考文獻:

[1] 李濤.計算機免疫學[M].北京:電子工業出版社，2004:67-68.

[2] 蘇彩紅，朱學鋒，毛宗源.一類免疫優化算法及其應用[J].西南交通大學學報，2002，37(6):677-680.

[3] 王凌.智能優化算法及其應用[M].北京:清華大學出版社，2001.

[4] 玄光男，程潤偉，于歆杰，等.遺傳算法與工程優化[M].北京:清華大學出版社，2004.

[5] 高巖，位耀光，付冬梅，等.免疫遺傳算法的研究及其在函數優化中的應用[J].微計算機信息，2007，23(2):183-184.

[6] 位耀光，鄭德玲，付冬梅.基于生物免疫系統克隆選擇機理和免疫網絡理論的免疫算法[J].北京科技大學學報，2005(2)245-249.

[7] 關靜.免疫遺傳算法在函數優化中的應用[J].軟件導刊，2007(2):91-92.

[8] 張建萍，劉希玉，譚業武.改進免疫遺傳算法及其應用研究[J].計算機技術與發展，2008，18(10):166-169.

[9] 桂超，汪波.基于遺傳算法的最短路徑路由優化算法[J].計算機信息，2005，21(12):193-195.