遺傳算法及其工具箱在函數優化問題中的應用

摘要:函數優化是遺傳算法的經典應用領域，也是對遺傳算法進行性能評價的常用算例。由此，該文首先對遺傳算法的基本原理和定義，以及其工具箱作了簡介，最后結合實例，簡述了遺傳算法及其工具箱在函數優化問題中的應用。

關鍵詞:遺傳算法;遺傳算法工具箱;函數優化

中圖分類號:TP18文獻標識碼:A文章編號:1009-3044(2009)26-7487-02

The Application of Genetic Algorithms and Toolbox on Function Optimization

WAN Hou-lun， WEN Yuan-quan

(Dongguan University of Technology， Dongguan， Dongguan 523808， China)

Abstract: Function optimization is not only the classic application of Genetic Algorithm， but also a common example used to evaluate the performance of Genetic Algorithm. Therefore， this thesis first introduces the basic principle and definition ofGenetic Algorithm， then introduce the toolbox of Genetic Algorithm. Last， Simply describe the function of the Genetic Algorithm and it's toolbox on Function optimization combine with some examples.

Key words: genetic algorithm; genetic algorithms toolbox; function optimization

遺傳算法(GA)是模擬自然界“優勝劣汰”的生物進化過程與機制求解極值問題的一類自組織、自適應人工智能技術，并逐漸發展成為一種疊代自適應啟發式概率性搜索算法。[1]近年來，以遺傳算法為代表的進化算法倍受重視，得到迅速發展，在各種問題的求解與應用中展現了其特點和魅力，特別是在對函數優化問題中， 結合Matlab遺傳算法工具箱，使其優勢充分的發揮出來，并得到了廣泛的運用。

目前，函數優化是遺傳算法的經典應用領域，也是對遺傳算法進行性能評價的常用算例。[2]對于函數優化中求解實數型變量的問題，一般采用動態編碼和實數編碼的方法來提高其搜索效率，這也是求解各類函數優化問題比較適合的算法。

1 遺傳算法的基本原理和定義

遺傳算法是一種模擬達爾文的生物自然選擇學說和生物進化過程的自適應全局概率搜索算法。它采用模擬自然界基因演化的循環過程(如圖1示，遺傳算法示意圖)，因其是一種全局優化策略，故能避免陷入局部最優，在解決實際問題時，首先大致確定問題的潛在解的集合，即初始種群，一般由計算機隨機生成一定的數目，接下來是對個體適應度進行評估，如果個體的適應度符合優化準則，則輸出最佳個體及其代表的最優解，并結束計算。否則就依據適應度選擇再生個體，接著按照一定的交叉概率和交叉方法、變異概率和變異方法生成新的個體，最后由交叉和變異產生新一代的種群。為了產生下一代種群，再從個體適應度進行評估開始到產生新的種群，不斷循環，通過快速隨機搜索，直至找到問題的近似最優解或次優解。

基本遺傳算法 (Simple Genetic Algorithm，SGA)可定義為一個八元組:

SGA=(C，E，P0，M，Ф，Г，Ψ，T)

其中，C:個體的編碼方法，SGA使用固定長度二進制符號串的編碼方法;

E:個體的適應度評價函數;

P0:初始群體;

M:群體大小，一般取20-100;

Ф:選擇算子，SGA使用比例選擇算子;

Г:交叉算子， SGA使用單點交叉算子;

Ψ:變異算子，SGA使用基本位變異算子;

T:遺傳運算終止條件，一般終止進化代數為100-500。

2 遺傳算法工具箱簡介

遺傳算法工具函數可以通過命令行和圖形界面兩種不同方式來實現。采用圖形界面，只需要設置相對應窗格中的參數就可以了，設置后Matlab程序會自動調用遺傳算法工具箱函數，使用比較方便。其參數主要有:[3]

1)圖形參數，可以得到圖形的數據。包括bestfitness最佳函數值;best individual，最佳適應度個體向量值;distance平局距離;Genealogy個體譜系;Range適應度函數值范圍;Score diversity多樣性值;Score個體得分;Selection選擇;Stopping停止條件等。

2)種群參數，包括Population Type適應度函數類型;population Size個體數;Initial population初始種群;Initial Score初始種群的初始值;Initial range初始種群向量范圍等。

3)適應度比例參數，是把適應度函數值轉換為適合選擇函數的范圍值。可供選擇參數有:Ranking排列;Proportional比率;Top最佳比例;Shift linear線性轉換等。

4)選擇參數，說明怎樣為下一代挑選雙親，有Stochastic nuiform隨機均勻分布等方式。

5)再生參數，說明怎樣為下一代創建子個體。

6)變異參數，有Gaussian高斯;Uniform均勻;Custom自定義等。

7)交叉參數，有Scattered、singel point、Intermediate等。

8)遷移參數，指明個體在子群中怎樣移動。

9)混合函數參數，是運行在遺傳算法終止后的另一個最小化函數。

10)停止條件參數，算法終止條件，有Generation、Fitnesslimit等。

此外，還有輸出函數參數、向量參數等。

3 通過GUI使用遺傳算法工具箱

在Matlab7.0或以上版本工作窗口鍵入>>gatool命令，彈出遺傳算法工具箱圖形界面(如圖3示，遺傳算法工具箱界面示意圖)只需要在相對應的窗格中選擇與其相對應的選項便可以進行遺傳算法的仿真實驗。其中，fitnessfun為適應度函數，可填寫@fitnessfun，Number of variable窗格為變量個數。其它窗格參數根據實際情況填寫，然后單擊start按鈕來查看其仿真結果。

4 應用實例

以優化Rosenbrock函數為例，來說明其優化問題，并采用Matlab7.0或以上版本自帶的遺傳算法工具箱來仿真。

個體評價方法采用對應的目標函數:F(X)=f(x1，x2)，SGA使用比例選擇算子、單點交叉算子和基本位變異算子。

使用Matlab7.0或以上版本的遺傳算法工具箱來優化Rosenbrock函數，并取群體大小:M=80，終止代數:T=150，交叉概率:Pc=0.2，變異概率:Pm=0.008，得到其前六代的數據測試結果(如圖2示)，從數據可以看出，從世代的不斷疊加中，逐漸靠近函數優化值，不斷的疊加搜索，最終可搜索到問題的最優解或近似解。

圖3(如圖3示)為Rosenbrock函數的幾何特征圖，從圖中可以看出，它有兩個局部極大點，分別是:F(2.048，-2.048)=3897.7342和f(-2.048， -2.048)=3905.9262。

由此可見，Rosenbrock函數的全局最大值為3905.9262。

5 結束語

遺傳算法是以自然選擇和遺傳理論為基礎，將生物進化過程中適者生存規則與群體內部染色體的隨機信息交換機制相結合的高效全局尋優搜索算法。Matlab遺傳算法工具箱有效地進行仿真實驗，其精度也很高，是解決復雜問題的好幫手。并且遺傳算法及其工具箱還有具有簡單易行、高效性和普遍適用性等優點，隨著遺傳算法的不斷深人研究，它將在函數優化問題中展現其獨特的魅力。

參考文獻:

[1] 陳本慶.遺傳算法研究及其在排課問題中的應用[D].西安交通大學，2003.

[2] 王小平，曹立明.遺傳算法[M].西安:西安交通大學出版社，2002.

[3] 雷英杰.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社，2005.

[4] 周明，孫樹棟.遺傳算法原理及應用[M].北京:國防工業出版社，1999.