MATLAB遺傳算法工具箱GADS優化及應用

郭海雙，梁佳雯，張劭昀

（1.貴州師范大學 數學與計算機學院，貴州 貴陽550001；2.貴州師范大學 物理與電子科學學院，貴州 貴陽 550001）

MATLAB遺傳算法工具箱GADS優化及應用

郭海雙1，梁佳雯1，張劭昀2

（1.貴州師范大學 數學與計算機學院，貴州 貴陽550001；2.貴州師范大學 物理與電子科學學院，貴州 貴陽 550001）

為了解決復雜函數優化問題，簡要對MATLAB遺傳算法工具箱進行了介紹，并詳細闡述了遺傳算法的基本原理與方法，在此基礎之上，介紹了MATLAB遺傳算法工具箱GADS尋找最優值的工作過程，最后，結合測試函數，介紹了遺傳算法工具箱編碼方法，并驗證了MATLAB遺傳算法工具箱操作簡單方便，具有較高可靠性的優點，為解決函數優化問題提供了一種強有力的工具。

遺傳算法；優化；工具箱；MATLAB；GADS

遺傳算法是對生物系統所進行的計算機模擬研究，最早是由美國密歇根大學的Holland教授首先提出來的優化方法，它是一種建立在自然選擇和群體遺傳學基礎上的隨機、迭代、進化的全局搜索方法，GA搜索以達爾文適者生存和隨機信息交換為主旋律，根據評價函數消除適應度值低的解，利用原有解中的知識加快搜索過程，遺傳算法具有魯棒性強、效率高、多點并行搜索的優點，應用廣泛，滲透到研究與應用的各個領域，如機器學習、規劃設計、圖像處理、人工生命、自動控制等科技領域[1]，并取得了良好的效果，最近吸引人眼球的是其在人工智能和人工生命領域的研究。

遺傳算法的應用過程中需要編制大量的程序，這給無計算機編程基礎的人員帶來困難，作為使用者總希望有一個現成的程序框架，而matlab遺傳算法工具箱正好滿足這一要求,基于MATLAB的遺傳算法工具箱主要有3種，出現較早較為完備的英國謝菲爾德(Sheffield)大學開發的GATBX，美國北卡羅萊納州立大學開發的遺傳算法優化工具箱GAOT，最近影響力較大的美國MathWork公司開發的MATLAB遺傳算法與直接搜索工具箱GADS[2]，前兩個工具箱在使用過程中都需要下載安裝在matlab軟件上，GADS在MATLAB7.0版本以后不需要，它是自帶的，GADS擴展了優化工具箱和MATLAB數值計算環境的性能，應用較廣泛，這些工具箱都是由實現特定優化算法的MATLAB語句寫成的M文件，是一系列函數的集合[3]。

本文首先介紹了遺傳算法的基本原理與方法，然后對MATLAB工具箱GADS進行了研究，詳細敘述了GADS優化過程，并用二維函數證明了遺傳算法工具箱的優越性。

1 遺傳算法的基本原理與方法

遺傳算法是按照生物界自然選擇原理和自然遺傳機理形成的一種迭代式自適應搜索算法，具有簡單易懂、通用、魯棒性強、并行處理的特點，適合解決各種優化問題，遺傳算法在解決問題時將所有解看作是群體當中的一個個體或染色體，通過把每一個個體編碼進行生物上的遺傳、交叉和變異操作，模擬達爾文的生物進化過程，對群體反復進行循環操作，根據目標適應度函數評價，依據適者生存、優勝劣汰的進化規則進行篩選更新群體，同時以全局并行搜索方式來搜索優化群體中的最優個體，以求得滿足要求的最優解[4]。遺傳算法基本流程如圖1所示。

遺傳算法主要流程：

1)編 碼

是通過某種編碼機制，把對象抽象為由特定符號排成的串，確定相應的編碼方法，并產生一個確定長度的M個染色體組成的初始群體，基因值可用均勻分布的隨機數來生成，例如二進制符號串編碼[3]，其等位基因是由二值符號集{0,1}組成，串的長度取決于所求問題的精度，變量X1的區間是[a1, b1],X2的區間是[a2,b2],精度是小數點后三位，那么每個變量應該被分成至少(b1-a1)*103個部分，二進制串位數也就是染色體長度計算公式如下：

圖1 遺傳算法基本流程圖Fig.1 The basic flowchart of genetic algorithms

染色體串長度是：

從二進制串返回一個實際的值，可用下面公式來實現：

其中decimal(substring si)是求二進制串轉化的十進制值，substring si是已知的二進制串。

由于本文處理的是二維函數，采用二進制編碼，具有較大的Hamming距離，染色體串長，算法效率低，所以采用實數編碼，編碼長度等于變量個數，個體的基因值與某一范圍內的實數相對應，可以表示較大范圍的數，精度高，便于處理優化多變量問題[5]。

2)確定個體評價方案

對群體中的每一個染色體計算它的適應度。

適應度，根據目標函數大小評定個體優劣的標準,適應度越大，個體越好，適應度越小，個體越差，適應度值總取非負值。例如線性排序的適應度函數，適應度值只取決于排序的位序，求目標函數最小值，目標函數值最小則分配的適應度值最大，被選出的概率越大，反之則分配的適應度值最小，最小值設定為0，保證適應度函數取值非負的條件。

3)判斷是否滿足收斂準則

若滿足，則輸出搜索結果，不滿足，則繼續執行以下操作。

4)選擇

根據“適者生存”的自然選擇原理，按照某種策略從父代中挑選個體進入下一代，如比例選擇，單個個體被選中的概率等于單個個體適應度值與所有個體適應度之和的比。

5)交叉

模擬有性繁殖的基因重組操作，從種群中選擇的每一對父代，以一定的交叉概率完成部分基因的交換，得到一個有N個染色體組成的群體。

6)變異

用某一較小的概率使染色體的基因發生變異，形成新種群，繼續進行遺傳操作。

交叉和變異操作都是為了得到新個體而進行的基因重組。

遺傳算法形式上簡單明了，具有顯著的隱并行性和適應性，直接處理的對象是參數的編碼而不是問題參數本身，搜索過程既不受優化函數連續性的約束，也沒有優化函數必須可導的要求[5]。

2 GADS尋優過程

使用遺傳算法對函數進行優化，必須要編制大量的程序，如選擇、雜交、變異等過程，這些都是針對染色體進行的，染色體實質是一個向量，而MATLAB處理數值運算的強大能力使得利用MATLAB編程可以節省大量的時間和精力。

GADS具有如下特點：

1)良好的圖形用戶界面，操作簡單舒適，可以快速設置算法參數和觀測運行進程。

2)參數提供多個選項，便于解決實際問題。

3)實現模式搜索，可定義網格大小，提供完全表決的搜索方式。

4)與其他程序語言兼容，如C,C++.

5)編寫好目標文件后支持自動生成代碼，免去繁瑣的遺傳算法編程描述。

遺傳算法總是使目標函數或適應度函數最小化，如果想要求出函數f(x)的最大值，可以轉而求取函數g(x)=-f(x)的最小值，因為g(x)最小值出現的地方與函數f(x)最大值出現的地方相同[3]。求測試函數Schaffer函數最大值：

該函數是一個多峰函數，有無數個局部極大點，但只有1個全局最大點，在點(0,0)處，最大值為1，此函數的最大峰周圍有兩圈脊，它們的取值分別為0.990 284和0.962 776，因此優化過程極易陷入局部最大值點[6-7]，其幾何特性如圖2所示。

圖2 Schaffer函數幾何特性圖Fig.2 The geometry fig of Schaffer function

MATLAB遺傳算法工具箱可以輕松快速的解決這一問題，為了使用遺傳算法工具箱，首先必須編寫一個M文件，來描述想要優化的函數，并且把寫好的M文件保存在工作目錄下[3]。該M文件代碼如下所示：

運用遺傳算法GADS的圖形用戶界面GUI對函數優化。在MATLAB工作窗口輸入gatool,打開遺傳算法工具，界面如圖3所示。

圖3 遺傳算法工具圖形界面Fig.3 Genetic algorithm tool graphical interface

輸入Schaffer函數作為適應度函數，變量個數設置為2。

gatool使用參數介紹[3]：

1)Fitness function：欲求最小值的目標函數。在此輸入編寫好的M文件，格式：@fitnessfun，fitness是工作目錄下的保存文件名，本文輸入目標函數@Schaffer。

2)Number of variable：輸入適應度函數向量的長度，也就是決策變量個數。

單擊“Start”按鈕，運行遺傳算法，將在“Status and result”窗口中顯示出當前的運行結果。

在右側“Option”窗口中可以對遺傳算法參數進行設置，單擊與之相連的符號“+”可以查看窗格中所列出的各類選項。

例如Population參數選項中，Population type:編碼方式，可以選擇實數編碼，或者是二進制編碼,Population size:設置種群大小，默認是20。Creation function：創建函數。initial population:初始種群范圍。initial score：初始得分，initial range：變量多樣性初始范圍，這些都是結合自變量來設置的。

仿真結果：

運行截止代數90時的仿真結果如圖4所示。

圖4 Schaffer函數最佳適應度與最佳個體的流程圖Fig.4 Flow chart of the best fitness and individual

運行截止代數100時的仿真結果如圖5所示。

圖5 Schaffer函數最佳適應度與最佳個體的流程圖Fig.5 Flow chart of the best fitness and individual

根據反復試驗，當種群初始規模設置為20，最大遺傳代數為100，停滯代數為100，交叉概率為0.8，高斯變異，其他參數使用缺省值時，Schaffer函數優化結果最好。

圖4圖5上半部分圖中底部的點代表最佳適應度值，而其上的點代表平均適應度值，頂部顯示的是當前代的最佳值和平均值[7]。平均適應度值在遺傳代數為90時達到收斂，收斂較緩慢，并且出現擺動，圖中所示結果是多次仿真后的最佳結果。下圖表示當前代最佳適應度值對應的點坐標變量，圖4中X坐標是(0.003 16,-0.001 18)，圖5中X坐標是(0.000 22,0.002 18)，非常接近于理論值（0,0）運行到最后一代的最優解是f(x) =-1,種群平均值是：-0.999 58。Schafer函數取了相反數，所以所求Schaffer函數最大值是1。

3 結論

主要介紹了MATLAB遺傳算法工具箱GADS圖形用戶界面GUI尋找最優值的工作過程，采用基本遺傳算法，遺傳進化操作簡單，容易理解，最大特點是只需編寫目標函數的M文件，免去編程麻煩，把編程過程用圖形界面體現出來，給編程能力不好的工作人員提供一種快速解決函數優化問題的新思路[7]。測試結果顯示，在解決低維函數時，MATLAB遺傳算法工具箱具有很強的處理能力，在處理高維函數優化問題時，快要接近最優解時收斂較慢，可以和其智能算法相結合，以使遺傳算法工具箱收斂性能更佳[8]。

[1]李延梅.一種改進的遺傳算法及應用[D].廣東:華南理工大學,2012.

[2]羅述全.傳統優化算法與遺傳算法的比較[J].湖北工業大學學報,2007(6):32-35.LUO Shu-quan.Comparision between readitional optimized algorithm and heredity algotithm[J].Hubei University of Technology Journal,2007(6):32-35.

[3]雷英杰，張尚文，李續武等.MATLAB遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，2005.

[4]金芬.MATLAB遺傳算法工具箱在函數優化中的應用[J].福建電腦,2009(7):23-25.JIN Fen.MATLAB genetic algorithm toolbox in function optimization[J].Fujian Computer,2009(7):23-25.

[5]陳廣洲，解華明，魯祥友，等.Matlab遺傳算法工具箱在非線性優化中的應用[J].計算機技術與發展，2008(3):247-248.CHEN Guang-zhou,XIE Hua-ming,LU Xiang-you,et al.Nonlinear optimization based on genetic algorithm toolbox of matlab[J].Computer Technology and Development,2008(3): 247-248.

[6]金芬.遺傳算法在函數優化中的應用研究[D].蘇州：蘇州大學,2008.

[7]石麗娟.遺傳算法求解函數優化問題的Matlab實現[J].福建電腦,2010(6):72-74.SHI Li-juan.Matlab achieve for genetic algorithm function optimization[J].Fujian Computer,2010(6):72-74.

[8]陳超.精通Matlab2008應用程序接口編程技術[M].北京:電子工業出版社,2009.

Optimization and examples in M atlab GA Toolbox GADS

GUO Hai-shuang1,LIANG Jia-wen1,ZHANG Shao-yun2
（1.College of Computer Science&Mathematics,Guizhou Nomal University,Guiyang 550001,China; 2.College of Physics and Electronics Science,Guizhou Nomal University,Guiyang 550001,China）

In order to solve the complex function optimization problem，the Genetic Algorithm Toolbox for MATLAB were briefly introduced,and the basic principles and methods of genetic algorithms were also elaborated，on this basis,introduced the work process of MATLAB genetic algorithm toolbox GADS to find the optimal value,at last,tested and verified the MATLAB genetic algorithm toolbox easy,high reliability advantages with combine application examples.

genetic algorithm;optimization;toolbox;MATLAB;GADS

TN911.1

A

1674－6236（2015）10-0027-03

2014-09-21 稿件編號：201409179

郭海雙(1989—)，男，河北遷安人，碩士研究生。研究方向：軟件工程學的應用。