使用MATLAB遺傳算法工具實例(詳細)

使用MATLAB遺傳算法工具實例（詳細）最新發(fā)布的MATLABRelease14已經(jīng)包含了一個專門設(shè)計的遺傳算法與直接搜索工具箱（GeneticAlgorithmandDirectSearchToolbox，GADS）。使用遺傳算法與直接搜索工具箱，可以擴展MATLAB及其優(yōu)化工具箱在處理優(yōu)化問題方面的能力，可以處理傳統(tǒng)的優(yōu)化技術(shù)難以解決的問題，包括那些難以定義或不便于數(shù)學建模的問題，可以解決目標函數(shù)較復雜的問題，比如目標函數(shù)不連續(xù)、或具有高度非線性、隨機性以及目標函數(shù)沒有導數(shù)的情況。本章節(jié)首先介紹這個遺傳算法與直接搜索工具箱，其余各節(jié)分別介紹該工具箱中的遺傳算法工具及其使用方法。遺傳算法與直接搜索工具箱概述本節(jié)介紹MATLAB的GADS（遺傳算法與直接搜索）工具箱的特點、圖形用戶界面及運行要求，解釋如何編寫待優(yōu)化函數(shù)的M文件，且通過舉例加以闡明。工具箱的特點GADS工具箱是一系列函數(shù)的集合，它們擴展了優(yōu)化工具箱和MATLAB數(shù)值計算環(huán)境的性能。遺傳算法與直接搜索工具箱包含了要使用遺傳算法和直接搜索算法來求解優(yōu)化問題的一些例程。這些算法使我們能夠求解那些標準優(yōu)化工具箱范圍之外的各種優(yōu)化問題。所有工具箱函數(shù)都是MATLAB的M文件，這些文件由實現(xiàn)特定優(yōu)化算法的MATLAB語句所寫成。使用語句typefunction_name就可以看到這些函數(shù)的MATLAB代碼。我們也可以通過編寫自己的M文件來實現(xiàn)來擴展遺傳算法和直接搜索工具箱的性能，也可以將該工具箱與MATLAB的其他工具箱或Simulink結(jié)合使用，來求解優(yōu)化問題。工具箱函數(shù)可以通過圖形界面或MATLAB命令行來訪問，它們是用MATLAB語言編寫的，對用戶開放，因此可以查看算法、修改源代碼或生成用戶函數(shù)。遺傳算法與直接搜索工具箱可以幫助我們求解那些不易用傳統(tǒng)方法解決的問題，譬如表查找問題等。遺傳算法與直接搜索工具箱有一個精心設(shè)計的圖形用戶界面，可以幫助我們直觀、方便、快速地求解最優(yōu)化問題。功能特點遺傳算法與直接搜索工具箱的功能特點如下：(1)圖形用戶界面和命令行函數(shù)可用來快速地描述問題、設(shè)置算法選項以及監(jiān)控進程。(2)具有多個選項的遺傳算法工具可用于問題創(chuàng)建、適應度計算、選擇、交叉和變異。(3)直接搜索工具實現(xiàn)了一種模式搜索方法，其選項可用于定義網(wǎng)格尺寸、表決方法和搜索方法。⑷遺傳算法與直接搜索工具箱函數(shù)可與MATLAB的優(yōu)化工具箱或其他的MATLAB程序結(jié)合使用。⑸支持自動的M代碼生成。圖形用戶界面和命令行函數(shù)遺傳算法工具函數(shù)可以通過命令行和圖形用戶界面來使用遺傳算法。直接搜索工具函數(shù)也可以通過命令行和圖形用戶界面來進行訪問。圖形用戶界面可用來快速地定義問題、設(shè)置算法選項、對優(yōu)化問題進行詳細定義。遺傳算法與直接搜索工具箱還同時提供了用于優(yōu)化管理、性能監(jiān)控及終止準則定義的工具，同時還提供大量標準算法選項。在優(yōu)化運行的過程中，可以通過修改選項來細化最優(yōu)解，更新性能結(jié)果。用戶也可以提供自己的算法選項來定制工具箱。使用其他函數(shù)和求解器遺傳算法與直接搜索工具箱與MATLAB及優(yōu)化工具箱是緊密結(jié)合在一起的。用戶可以用遺傳算法或直接搜索算法來尋找最佳起始點，然后利用優(yōu)化工具箱或用MATLAB程序來進一步尋找最優(yōu)解。通過結(jié)合不同的算法，可以充分地發(fā)揮MATLAB和工具箱的功能以提高求解的質(zhì)量。對于某些特定問題，使用這種方法還可以得到全局（最優(yōu)）解。顯示、監(jiān)控和輸出結(jié)果遺傳算法與直接搜索工具箱還包括一系列繪圖函數(shù)用來可視化優(yōu)化結(jié)果。這些可視化功能直觀地顯示了優(yōu)化的過程，并且允許在執(zhí)行過程中進行修改。工具箱還包括一系列繪圖函數(shù)用來可視化優(yōu)化結(jié)果。這些可視化功能直觀地顯示了優(yōu)化的過程，并且允許在執(zhí)行過程中進行修改。該工具箱還提供了一些特殊繪圖函數(shù)，它們不僅適用于遺傳算法，還適用于直接搜索算法。適用于遺傳算法的函數(shù)包括函數(shù)值、適應度值和函數(shù)估計。適用于直接搜索算法的函數(shù)包括函數(shù)值、分值直方圖、系譜、適應度值、網(wǎng)格尺寸和函數(shù)估計。這些函數(shù)可以將多個繪圖一并顯示，可直觀方便地選取最優(yōu)曲線。另外，用戶也可以添加自己的繪圖函數(shù)。使用輸出函數(shù)可以將結(jié)果寫入文件，產(chǎn)生用戶自己的終止準則，也可以寫入用戶自己的圖形界面來運行工具箱求解器。除此之外，還可以將問題的算法選項導出，以便日后再將它們導入到圖形界面中去。所需的產(chǎn)品支持遺傳算法與直接搜索工具箱作為其他優(yōu)化方法的補充，可以用來尋找最佳起始點，然后可以再通過使用傳統(tǒng)的優(yōu)化技術(shù)來進步尋找最優(yōu)解。工具箱需要如下產(chǎn)品支持：（1）MATLAB。（2）優(yōu)化工具箱。相關(guān)產(chǎn)品與遺傳算法與直接搜索工具箱相關(guān)的產(chǎn)品有：（1）統(tǒng)計工具箱——應用統(tǒng)計算法和概率模式。⑵神經(jīng)網(wǎng)絡(luò)工具箱——設(shè)計和仿真神經(jīng)網(wǎng)絡(luò)。⑶模糊邏輯工具箱——設(shè)計和仿真基于模糊邏輯的系統(tǒng)。⑷金融工具箱——分析金融數(shù)據(jù)和開發(fā)金融算法。所需的系統(tǒng)及平臺遺傳算法和直接搜索工具箱對于對于運行環(huán)境、支持平臺和系統(tǒng)的需求，可隨時通過訪問網(wǎng)站了解最新發(fā)布的信息。這里介紹的MATLABRelease14所需的最低配置是：Window系列操作系統(tǒng)，PentiumIII500CPU、64MB口人乂，空閑硬盤空間600MB以上。編寫待優(yōu)化函數(shù)的M文件為了使用遺傳算法和直接搜索工具箱，首先必須編寫一個M文件，來確定想要優(yōu)化的函數(shù)。這個M文件應該接受一個行向量，并且返回一個標量。行向量的長度就是目標函數(shù)中獨立變量的個數(shù)。本節(jié)將通過實例解釋如何編寫這種M文件。編寫M文件舉例下面的例子展示了如何為一個想要優(yōu)化的函數(shù)編寫M文件。假定我們想要計算下面函數(shù)的最小值：__-__22(,)266fxxxxxxxx=-++-M文件確定這個函數(shù)必須接受一個長度為2的行向量X,分別與變量x1和x2相對應，并且返回一個標量X，其值等于該函數(shù)的值。為了編寫這個M文件，執(zhí)行如下步驟：(1)在MATLAB的File菜單中選擇New菜單項。(2)選擇M-File，將在編輯器中打開一個新的M文件。在該M文件中，輸入下面兩行代碼：functionz=my_fun(x)z=x(1)八2-2__(1)__(2)+6__(1)+x(2)八2-6__(2);(4)在MATLAB路徑指定的目錄中保存該M文件。為了查看該M文件是否返回正確的值，可鍵入my_fun([23])ans=-5注意：在運行遺傳算法工具或模式搜索工具時，不要使用編輯器或調(diào)試器來調(diào)試目標函數(shù)的M文件，否則會導致在命令窗口出現(xiàn)Java異常消息，并且使調(diào)試更加困難。最大化與最小化遺傳算法和直接搜索工具箱中的優(yōu)化函數(shù)總是使目標函數(shù)或適應度函數(shù)最小化。也就是說，它們求解如下形式的問題：minimize()xfx如果我們想要求出函數(shù)f(x)的最大值，可以轉(zhuǎn)而求取函數(shù)g(x)=-f(x)的最小值，因為函數(shù)g(x)最小值出現(xiàn)的地方與函數(shù)f(x)最大值出現(xiàn)的地方相同。例如，假定想要求前面所描述的函數(shù)__-__22(,)266fxxxxxxxx=-++-的最大值，這時，我們應當編寫一個M文件來計算，求函數(shù)__-__22()(,)(266)gxfxxxxxxxx=-=--++-的最小值。自動代碼生成遺傳算法與直接搜索工具箱提供了自動代碼生成特性，可以自動生成求解優(yōu)化問題所需要的M文件。例如，圖所示的就是使用遺傳算法工具的自動代碼生成特性所產(chǎn)生的M文件。另外，圖形用戶界面所輸出的優(yōu)化結(jié)果可以作為對來自命令行調(diào)用代碼的一種解釋，這些代碼還用于使例程和保護工作自動化。圖遺傳算法M文件代碼的自動生成使用遺傳算法工具初步遺傳算法與直接搜索工具箱包含遺傳算法工具和直接搜索工具。從本節(jié)至章末，將主要介紹其中的遺傳算法工具及其使用方法。本節(jié)主要介紹遺傳算法工具使用的初步知識，內(nèi)容包括：遺傳算法使用規(guī)則，遺傳算法工具的使用方式，舉例說明如何使用遺傳算法來求解一個優(yōu)化問題，解釋遺傳算法的一些基本術(shù)語，最后闡述遺傳算法的工作原理與工作過程。遺傳算法使用規(guī)則遺傳算法是一種基于自然選擇、生物進化過程來求解問題的方法。遺傳算法反復修改對于個體解決方案的種群。在每一步，遺傳算法隨機地從當前種群中選擇若干個體作為父輩，并且使用它們產(chǎn)生下一代的子種群。在連續(xù)若干代之后，種群朝著優(yōu)化解的方向進化。我們可以用遺傳算法來求解各種不適宜于用標準優(yōu)化算法求解的優(yōu)化問題，包括目標函數(shù)不連續(xù)、不可微、隨機或高度非線性的問題。遺傳算法在每一步使用下列三類規(guī)則從當前種群來創(chuàng)建下一代：⑴選擇規(guī)則(Selectionrules),選擇對下一代種群有貢獻的個體，稱為父輩。(2)交叉規(guī)則(Crossoverrules),將兩個父輩結(jié)合起來構(gòu)成下一代的子輩種群。⑶變異規(guī)則(Mutationrules),施加隨機變化給父輩個體來構(gòu)成子輩。遺傳算法與標準優(yōu)化算法主要在兩個方面有所不同,它們的比較情況歸納于表中。表遺傳算法與標準優(yōu)化算法比較遺傳算法使用方式遺傳算法工具有兩種使用方式：⑴以命令行方式調(diào)用遺傳算法函數(shù)ga。(2)使用遺傳算法工具，從圖形用戶界面到遺傳算法。本節(jié)對這些方式做一個簡要的介紹。在命令行調(diào)用函數(shù)ga對于在命令行使用遺傳算法，可以用下列語法調(diào)用遺傳算法函數(shù)ga：[xfval]=ga(@fitnessfun,nvars,options)其中：@fitnessfun是適應度函數(shù)句柄；nvars是適應度函數(shù)的獨立變量的個數(shù)；options是一個包含遺傳算法選項參數(shù)的結(jié)構(gòu)。如果不傳遞選項參數(shù)，則ga使用它本身的缺省選項值。函數(shù)所給出的結(jié)果：fval——適應度函數(shù)的最終值；x——最終值到達的點。我們可以十分方便地把遺傳算法工具輸出的結(jié)果直接返回到MATLAB的workspace(工作空間)，或以不同的選項從M文件多次調(diào)用函數(shù)ga來運行遺傳算法。調(diào)用函數(shù)ga時，需要提供一個選項結(jié)構(gòu)options。后面的有關(guān)章節(jié)對于在命令行使用函數(shù)ga和創(chuàng)建選項結(jié)構(gòu)options提供了詳細的描述。通過GUI使用遺傳算法遺傳算法工具有一個圖形用戶界面GUI,它使我們可以使用遺傳算法而不用工作在命令行方式。為了打開遺傳算法工具，可鍵入gatool打開的遺傳算法工具圖形用戶界面如圖所示。顯示參數(shù)描述輸入適應度函數(shù)輸入適應度函數(shù)開始遺傳算法顯示結(jié)果圖遺傳算法工具為了使用遺傳算法工具，首先必須輸入下列信息：(1)Fitnessfunction(適應度函數(shù)) 欲求最小值的目標函數(shù)。輸入適應度函數(shù)的形式為@體門巳55句5其中是計算適應度函數(shù)的M文件。在前面“編寫待優(yōu)化函數(shù)的M文件”一節(jié)里已經(jīng)解釋了如何編寫這種M文件。符號@產(chǎn)生一個對于函數(shù)fitnessfun的函數(shù)句柄。(2)Numberofvariables(變量個數(shù)) 適應度函數(shù)輸入向量的長度。對于“編寫待優(yōu)化函數(shù)的M文件”一節(jié)所描述的函數(shù)My_fun,這個參數(shù)是2。點擊Start按鈕，運行遺傳算法，將在StatusandResults（狀態(tài)與結(jié)果）窗格中顯示出相應的運行結(jié)果。在Options窗格中可以改變遺傳算法的選項。為了查看窗格中所列出的各類選項，可單擊與之相連的符號“+”。舉例：Rastrigin函數(shù)本節(jié)介紹一個例子，講述如何尋找Rastrigin函數(shù)的最小值和顯示繪制的圖形。Rastrigin函數(shù)是最常用來測試遺傳算法的一個典型函數(shù)。Rastrigin函數(shù)的可視化圖形顯示，它具有多個局部最小值和一個全局最小值，遺傳算法可以幫助我們確定這種具有多個局部最小值函數(shù)的最優(yōu)解。Rastrigin函數(shù)具有兩個獨立變量的Rastrigin函數(shù)定義為__（）2022年?0$2cos2）Rasxxxxxnn=++-+Rastrigin函數(shù)的圖形如圖所示。工具箱包含一個M文件，即，是用來計算Rastrigin函數(shù)值的。圖Rastrigin函數(shù)圖形如圖所示，Rastrigin函數(shù)有許多局部最小值一一在圖上顯示為“谷底（valleys）”。然而，該函數(shù)只有一個全局最小值，出現(xiàn)在x-y平面上的點［0,0］處，正如圖中豎直線指示的那樣，函數(shù)的值在那里是0。在任何不同于［0,0］的局部最小點處，Rastrigin函數(shù)的值均大于0。局部最小處距原點越遠，該點處Rastrigin函數(shù)的值越大。全局最小點［0,0］Rastrigin函數(shù)之所以最常用來測試遺傳算法，是因為它有許多局部最小點,使得用標準的、基于梯度的查找全局最小的方法十分困難。圖所示是Rastrigin函數(shù)的輪廓線，它顯示出最大最小交替變化的情形。局部最小點局部最小點全局最小點［0,0］圖Rastrigin函數(shù)的輪廓線尋找Rastrigin函數(shù)的最小值本節(jié)解釋如何使用遺傳算法來尋找Rastrigin函數(shù)的最小值。注意：因為遺傳算法使用隨機數(shù)據(jù)來進行它的搜索,所以該算法每一次運行時所返回的結(jié)果會稍微有些不同。為了查找最小值,進行下列步驟：(1)在命令行鍵入92801，打開遺傳算法工具。(2)在遺傳算法工具的相應欄目,輸入適應度函數(shù)和變量個數(shù)。ft“Fitnessfunction（適應度函數(shù)）”文本框中，輸入@rastriginsfcn；在“Numberofvariables（變量個數(shù)）”文本框中，輸入2，這就是Rastrigin函數(shù)獨立變量的個數(shù)。這一步操作如圖所示。圖輸入適應度函數(shù)與變量個數(shù)（3）在“Runsolver（運行求解器）”窗格中，單擊Start按鈕，如圖所示。圖單擊運行求解器Start按鈕在算法運行的同時，“Currentgeneration（當前代數(shù)）”文本框中顯示出當前的代數(shù)。通過點擊“暫停（Pause）”按鈕，可以使算法臨時暫停一下。當這樣做的時候，該按鈕的名字變?yōu)椤癛esume（恢復）”。為了從暫停處恢復算法的運行，可單擊這個“Resume”按鈕。當算法完成時，“Statusandresults”窗格出現(xiàn)如圖所示的情形。圖狀態(tài)與結(jié)果顯示“Statusandresults”窗格顯示下列信息：算法終止時適應度函數(shù)的最終值：Fitnessfunctionvalue:注意：所顯示的值非常接近于Rastrigin函數(shù)的實際最小值0?！斑z傳算法舉例”一節(jié)描述了一些方法，可以用來得到更接近實際最小值的結(jié)果。算法終止的原因：Optimizationterminated:maximumnumberofgenerationsexceeded.即退出的原因是：超過最大代數(shù)而導致優(yōu)化終止。在本例中，算法在100代后結(jié)束，這是“Generations(代數(shù))”選項的缺省值，此選項規(guī)定了算法計算的最大代數(shù)。(3)最終點，在本例中是[]。從命令行查找最小值為了從命令行查找Rastrigin函數(shù)的最小值，可鍵入[xfvalreason]=ga(@rastriginsfcn,2)這將返回x=fval=reason=Optimizationterminated:maximumnumberofgenerationsexceeded.其中：x是算法返回的最終點；fval是該最終點處適應度函數(shù)的值；reason是算法結(jié)束的原因。顯示繪制圖形“Plots(繪圖)”窗格可以顯示遺傳算法運行時所提供的有關(guān)信息的各種圖形。這些信息可以幫助我們改變算法的選項，改進算法的性能。例如，為了繪制每一代適應度函數(shù)的最佳值和平均值，選中復選框“Bestfitness（最佳適應度）”，如圖所示。圖繪圖對話框當點擊Start按鈕時，遺傳算法工具顯示每一代適應度函數(shù)的最佳值和平均值的繪制圖形。當算法停止時，所出現(xiàn)的圖形如圖所示。最佳值平均值圖各代適應度函數(shù)的最佳值和平均值在每一代中，圖的底部的點表示最佳適應度值，而其上的點表示平均適應度值。圖的頂部還顯示出當前一代的最佳值和平均值。為了得到最佳適應度值減少到多少為更好的直觀圖形，我們可以將圖中y軸的刻度改變?yōu)閷?shù)刻度。為此，需進行如下操作:（1）從繪圖窗格的Edit（編輯）菜單中選擇“AxesProperties（坐標軸屬性）”，打開屬性編輯器，如圖所示。圖繪圖屬性編輯器⑵點擊Y表項。（3）在“Scale（刻度）”窗格，選擇“Log（對數(shù)）”。繪制的圖形如圖所示。最佳值平均值圖每一代適應度函數(shù)最佳值和平均值的對數(shù)圖形典型情況下，在早期各代中，當個體離理想值較遠時，最佳值會迅速得到改進。在后來各代中，種群越接近最佳點，最佳值改進得越慢。遺傳算法的一些術(shù)語本節(jié)解釋遺傳算法的一些基本術(shù)語，主要包括：⑴適應度函數(shù)(FitnessFunctions)。(2)個體(Individuals)。(3)種群(Populations)和代(Generations)。⑷適應度值(FitnessValues)和最佳適應度值(BestFitnessValues)；(5)父輩和子輩(ParentsandChildren)。適應度函數(shù)所謂適應度函數(shù)就是想要優(yōu)化的函數(shù)。對于標準優(yōu)化算法而言，這個函數(shù)稱為目標函數(shù)。該工具箱總是試圖尋找適應度函數(shù)的最小值。我們可以將適應度函數(shù)編寫為一個M文件，作為輸入?yún)?shù)傳遞給遺傳算法函數(shù)。個體一個個體是可以施加適應度函數(shù)的任意一點。一個個體的適應度函數(shù)值就是它的得分或評價。例如，如果適應度函數(shù)是__-__3(,,)(21)(34)(2)fxxxxxx=++++-則向量(2,-3,1)就是一個個體，向量的長度就是問題中變量的個數(shù)。個體(2,-3,1)的得分是f(2,-3,1)=51。個體有時又稱為基因組或染色體組(genome),個體的向量項稱為基因(genes)。種群與代所謂種群是指由個體組成的一個數(shù)組或矩陣。例如，如果個體的長度是100，適應度函數(shù)中變量的個數(shù)為3，我們就可以將這個種群表示為一個100x3的矩陣。相同的個體在種群中可以出現(xiàn)不止一次。例如，個體(2,-3,1)就可以在數(shù)組的行中出現(xiàn)多次。每一次迭代，遺傳算法都對當前種群執(zhí)行一系列的計算，產(chǎn)生一個新的種群。每一個后繼的種群稱為新的一代。多樣性多樣性或差異(Diversity)涉及一個種群的各個個體之間的平均距離。若平均距離大，則種群具有高的多樣性；否則，其多樣性低。在圖中，左面的種群具有高的多樣性，亦即差異大；而右面的種群多樣性低，亦即差異小。圖種群多樣性比較多樣性是遺傳算法必不可少的本質(zhì)屬性，這是因為它能使遺傳算法搜索一個比較大的解的空間區(qū)域。適應度值和最佳適應度值個體的適應度值就是該個體的適應度函數(shù)的值。由于該工具箱總是查找適應度函數(shù)的最小值，所以一個種群的最佳適應度值就是該種群中任何個體的最小適應度值。父輩和子輩為了生成下一代，遺傳算法在當前種群中選擇某些個體，稱為父輩，并且使用它們來生成下一代中的個體，稱為子輩。典型情況下，該算法更可能選擇那些具有較佳適應度值的父輩。遺傳算法如何工作本節(jié)簡要介紹遺傳算法的工作原理或工作過程，內(nèi)容包括：算法要點；初始種群；生成下一代；后一代的繪圖；算法的停止條件。算法要點下面的要點總結(jié)了遺傳算法是如何工作的：首先，算法創(chuàng)建一個隨機種群。接著，算法生成一個新的種群序列，即新的一代。在每一步，該算法都使用當前一代中的個體來生成下一代。為了生成新一代，算法執(zhí)行下列步驟：通過計算其適應度值，給當前種群的每一個成員打分。確定原來的適應度值的比例尺度，將其轉(zhuǎn)換為更便于使用的范圍內(nèi)的值。根據(jù)它們的適應度選擇父輩。由父輩產(chǎn)生子輩。子輩的產(chǎn)生可以通過隨機改變一個單個父輩，亦即變異（mutation）來進行，也可以通過組合一對父輩的向量項，亦即交叉（crossover）來進行。用子輩替換當前種群，形成下一代。（3）最后，若停止準則之一得到滿足，則該算法停止。關(guān)于停止準則，可參見“8.2.5.7算法的停止條件”一節(jié)。初始種群遺傳算法總是以產(chǎn)生一個隨機的初始種群開始，如圖所示。圖初始種群在本例中，初始種群包含20個個體，這