MATLAB遺傳算法工具箱GADS優(yōu)化及應(yīng)用

郭海雙，梁佳雯，張劭昀

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

MATLAB遺傳算法工具箱GADS優(yōu)化及應(yīng)用

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

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

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

遺傳算法；優(yōu)化；工具箱；MATLAB；GADS

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

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

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

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

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

遺傳算法主要流程：

1)編 碼

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

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

染色體串長度是：

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

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

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

2)確定個體評價方案

對群體中的每一個染色體計算它的適應(yīng)度。

適應(yīng)度，根據(jù)目標(biāo)函數(shù)大小評定個體優(yōu)劣的標(biāo)準(zhǔn),適應(yīng)度越大，個體越好，適應(yīng)度越小，個體越差，適應(yīng)度值總?cè)》秦?fù)值。例如線性排序的適應(yīng)度函數(shù)，適應(yīng)度值只取決于排序的位序，求目標(biāo)函數(shù)最小值，目標(biāo)函數(shù)值最小則分配的適應(yīng)度值最大，被選出的概率越大，反之則分配的適應(yīng)度值最小，最小值設(shè)定為0，保證適應(yīng)度函數(shù)取值非負(fù)的條件。

3)判斷是否滿足收斂準(zhǔn)則

若滿足，則輸出搜索結(jié)果，不滿足，則繼續(xù)執(zhí)行以下操作。

4)選擇

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

5)交叉

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

6)變異

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

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

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

2 GADS尋優(yōu)過程

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

GADS具有如下特點：

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

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

3)實現(xiàn)模式搜索，可定義網(wǎng)格大小，提供完全表決的搜索方式。

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

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

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

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

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

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

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

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

輸入Schaffer函數(shù)作為適應(yīng)度函數(shù)，變量個數(shù)設(shè)置為2。

gatool使用參數(shù)介紹[3]：

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

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

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

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

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

仿真結(jié)果：

運行截止代數(shù)90時的仿真結(jié)果如圖4所示。

圖4 Schaffer函數(shù)最佳適應(yīng)度與最佳個體的流程圖Fig.4 Flow chart of the best fitness and individual

運行截止代數(shù)100時的仿真結(jié)果如圖5所示。

圖5 Schaffer函數(shù)最佳適應(yīng)度與最佳個體的流程圖Fig.5 Flow chart of the best fitness and individual

根據(jù)反復(fù)試驗，當(dāng)種群初始規(guī)模設(shè)置為20，最大遺傳代數(shù)為100，停滯代數(shù)為100，交叉概率為0.8，高斯變異，其他參數(shù)使用缺省值時，Schaffer函數(shù)優(yōu)化結(jié)果最好。

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

3 結(jié)論

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

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

[2]羅述全.傳統(tǒng)優(yōu)化算法與遺傳算法的比較[J].湖北工業(yè)大學(xué)學(xué)報,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]雷英杰，張尚文，李續(xù)武等.MATLAB遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2005.

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

[5]陳廣洲，解華明，魯祥友，等.Matlab遺傳算法工具箱在非線性優(yōu)化中的應(yīng)用[J].計算機技術(shù)與發(fā)展，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]金芬.遺傳算法在函數(shù)優(yōu)化中的應(yīng)用研究[D].蘇州：蘇州大學(xué),2008.

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

[8]陳超.精通Matlab2008應(yīng)用程序接口編程技術(shù)[M].北京:電子工業(yè)出版社,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—)，男，河北遷安人，碩士研究生。研究方向：軟件工程學(xué)的應(yīng)用。