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

.最新發(fā)布的MATLAB 7.0 Release 14已經(jīng)包含了一個專門設(shè)計的遺傳算法與直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox，GADS）。使用遺傳算法與直接搜索工具箱，可以擴展MATLAB及其優(yōu)化工具箱在處理優(yōu)化問題方面的能力，可以處理傳統(tǒng)的優(yōu)化技術(shù)難以解決的問題，包括那些難以定義或不便于數(shù)學建模的問題，可以解決目標函數(shù)較復(fù)雜的問題，比如目標函數(shù)不連續(xù)、或具有高度非線性、隨機性以及目標函數(shù)沒有導(dǎo)數(shù)的情況。本章8.1節(jié)首先介紹這個遺傳算法與直接搜索工具箱，其余各節(jié)分別介紹該工具箱中的遺傳算法工具及其使用方法。8.1 遺傳算法與直接搜索工具箱概述本節(jié)介紹MATLAB的GADS（遺傳算法與直接搜索）工具箱的特點、圖形用戶界面及運行要求，解釋如何編寫待優(yōu)化函數(shù)的M文件，且通過舉例加以闡明。8.1.1 工具箱的特點GADS工具箱是一系列函數(shù)的集合，它們擴展了優(yōu)化工具箱和MATLAB數(shù)值計算環(huán)境的性能。遺傳算法與直接搜索工具箱包含了要使用遺傳算法和直接搜索算法來求解優(yōu)化問題的一些例程。這些算法使我們能夠求解那些標準優(yōu)化工具箱范圍之外的各種優(yōu)化問題。所有工具箱函數(shù)都是MATLAB的M文件，這些文件由實現(xiàn)特定優(yōu)化算法的MATLAB語句所寫成。使用語句type function_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)建、適應(yīng)度計算、選擇、交叉和變異。(3) 直接搜索工具實現(xiàn)了一種模式搜索方法，其選項可用于定義網(wǎng)格尺寸、表決方法和搜索方法。(4) 遺傳算法與直接搜索工具箱函數(shù)可與MATLAB的優(yōu)化工具箱或其他的MATLAB程序結(jié)合使用。(5) 支持自動的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ù)值、適應(yīng)度值和函數(shù)估計。適用于直接搜索算法的函數(shù)包括函數(shù)值、分值直方圖、系譜、適應(yīng)度值、網(wǎng)格尺寸和函數(shù)估計。這些函數(shù)可以將多個繪圖一并顯示，可直觀方便地選取最優(yōu)曲線。另外，用戶也可以添加自己的繪圖函數(shù)。使用輸出函數(shù)可以將結(jié)果寫入文件，產(chǎn)生用戶自己的終止準則，也可以寫入用戶自己的圖形界面來運行工具箱求解器。除此之外，還可以將問題的算法選項導(dǎo)出，以便日后再將它們導(dǎo)入到圖形界面中去。 所需的產(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)計工具箱應(yīng)用統(tǒng)計算法和概率模式。(2) 神經(jīng)網(wǎng)絡(luò)工具箱設(shè)計和仿真神經(jīng)網(wǎng)絡(luò)。(3) 模糊邏輯工具箱設(shè)計和仿真基于模糊邏輯的系統(tǒng)。(4) 金融工具箱分析金融數(shù)據(jù)和開發(fā)金融算法。 所需的系統(tǒng)及平臺遺傳算法和直接搜索工具箱對于對于運行環(huán)境、支持平臺和系統(tǒng)的需求，可隨時通過訪問網(wǎng)站/products/gads了解最新發(fā)布的信息。這里介紹的MATLAB 7.0 Release 14所需的最低配置是：Windows系列操作系統(tǒng)，Pentium III 500 CPU、64MB RAM，空閑硬盤空間600MB以上。8.1.2 編寫待優(yōu)化函數(shù)的M文件為了使用遺傳算法和直接搜索工具箱，首先必須編寫一個M文件，來確定想要優(yōu)化的函數(shù)。這個M文件應(yīng)該接受一個行向量，并且返回一個標量。行向量的長度就是目標函數(shù)中獨立變量的個數(shù)。本節(jié)將通過實例解釋如何編寫這種M文件。 編寫M文件舉例下面的例子展示了如何為一個想要優(yōu)化的函數(shù)編寫M文件。假定我們想要計算下面函數(shù)的最小值：M文件確定這個函數(shù)必須接受一個長度為2的行向量X，分別與變量x1和x2相對應(yīng)，并且返回一個標量X，其值等于該函數(shù)的值。為了編寫這個M文件，執(zhí)行如下步驟：(1) 在MATLAB的File菜單中選擇New菜單項。(2) 選擇M-File，將在編輯器中打開一個新的M文件。(3) 在該M文件中，輸入下面兩行代碼：function z = my_fun(x)z = x(1)2 - 2*x(1)*x(2) + 6*x(1) + x(2)2 - 6*x(2);(4) 在MATLAB路徑指定的目錄中保存該M文件。為了查看該M文件是否返回正確的值，可鍵入my_fun(2 3)ans = -5注意：在運行遺傳算法工具或模式搜索工具時，不要使用編輯器或調(diào)試器來調(diào)試目標函數(shù)的M文件，否則會導(dǎo)致在命令窗口出現(xiàn)Java異常消息，并且使調(diào)試更加困難。 最大化與最小化遺傳算法和直接搜索工具箱中的優(yōu)化函數(shù)總是使目標函數(shù)或適應(yīng)度函數(shù)最小化。也就是說，它們求解如下形式的問題：如果我們想要求出函數(shù)f(x)的最大值，可以轉(zhuǎn)而求取函數(shù)g(x)=f(x)的最小值，因為函數(shù)g(x)最小值出現(xiàn)的地方與函數(shù)f(x)最大值出現(xiàn)的地方相同。例如，假定想要求前面所描述的函數(shù)的最大值，這時，我們應(yīng)當編寫一個M文件來計算，求函數(shù)的最小值。 自動代碼生成遺傳算法與直接搜索工具箱提供了自動代碼生成特性，可以自動生成求解優(yōu)化問題所需要的M文件。例如，圖8.1所示的就是使用遺傳算法工具的自動代碼生成特性所產(chǎn)生的M文件。另外，圖形用戶界面所輸出的優(yōu)化結(jié)果可以作為對來自命令行調(diào)用代碼的一種解釋，這些代碼還用于使例程和保護工作自動化。圖8.1 遺傳算法M文件代碼的自動生成8.2 使用遺傳算法工具初步遺傳算法與直接搜索工具箱包含遺傳算法工具和直接搜索工具。從本節(jié)至章末，將主要介紹其中的遺傳算法工具及其使用方法。本節(jié)主要介紹遺傳算法工具使用的初步知識，內(nèi)容包括：遺傳算法使用規(guī)則，遺傳算法工具的使用方式，舉例說明如何使用遺傳算法來求解一個優(yōu)化問題，解釋遺傳算法的一些基本術(shù)語，最后闡述遺傳算法的工作原理與工作過程。8.2.1 遺傳算法使用規(guī)則遺傳算法是一種基于自然選擇、生物進化過程來求解問題的方法。遺傳算法反復(fù)修改對于個體解決方案的種群。在每一步，遺傳算法隨機地從當前種群中選擇若干個體作為父輩，并且使用它們產(chǎn)生下一代的子種群。在連續(xù)若干代之后，種群朝著優(yōu)化解的方向進化。我們可以用遺傳算法來求解各種不適宜于用標準優(yōu)化算法求解的優(yōu)化問題，包括目標函數(shù)不連續(xù)、不可微、隨機或高度非線性的問題。遺傳算法在每一步使用下列三類規(guī)則從當前種群來創(chuàng)建下一代：(1) 選擇規(guī)則（Selection rules），選擇對下一代種群有貢獻的個體，稱為父輩。(2) 交叉規(guī)則（Crossover rules），將兩個父輩結(jié)合起來構(gòu)成下一代的子輩種群。(3) 變異規(guī)則（Mutation rules），施加隨機變化給父輩個體來構(gòu)成子輩。遺傳算法與標準優(yōu)化算法主要在兩個方面有所不同，它們的比較情況歸納于表8.1中。表8.1 遺傳算法與標準優(yōu)化算法比較標準算法遺傳算法每次迭代產(chǎn)生一個單點，點的序列逼近一個優(yōu)化解每次迭代產(chǎn)生一個種群，種群逼近一個優(yōu)化解通過確定性的計算在該序列中選擇下一個點通過隨機進化選擇計算來選擇下一代種群8.2.2 遺傳算法使用方式遺傳算法工具有兩種使用方式：(1) 以命令行方式調(diào)用遺傳算法函數(shù)ga。(2) 使用遺傳算法工具，從圖形用戶界面到遺傳算法。本節(jié)對這些方式做一個簡要的介紹。 在命令行調(diào)用函數(shù)ga 對于在命令行使用遺傳算法，可以用下列語法調(diào)用遺傳算法函數(shù)ga：x fval = ga(fitnessfun, nvars, options) 其中：fitnessfun 是適應(yīng)度函數(shù)句柄；nvars 是適應(yīng)度函數(shù)的獨立變量的個數(shù)；options 是一個包含遺傳算法選項參數(shù)的結(jié)構(gòu)。如果不傳遞選項參數(shù)，則ga使用它本身的缺省選項值。函數(shù)所給出的結(jié)果：fval適應(yīng)度函數(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打開的遺傳算法工具圖形用戶界面如圖8.2所示。 輸入適應(yīng)度函數(shù)輸入適應(yīng)度函數(shù) 的變量數(shù)目開始遺傳算法 顯示結(jié)果顯示參數(shù)描述圖8.2 遺傳算法工具為了使用遺傳算法工具，首先必須輸入下列信息：(1) Fitness function（適應(yīng)度函數(shù)）欲求最小值的目標函數(shù)。輸入適應(yīng)度函數(shù)的形式為fitnessfun，其中fitnessfun.m是計算適應(yīng)度函數(shù)的M文件。在前面“編寫待優(yōu)化函數(shù)的M文件”一節(jié)里已經(jīng)解釋了如何編寫這種M文件。符號產(chǎn)生一個對于函數(shù)fitnessfun的函數(shù)句柄。(2) Number of variables（變量個數(shù)）適應(yīng)度函數(shù)輸入向量的長度。對于“編寫待優(yōu)化函數(shù)的M文件”一節(jié)所描述的函數(shù)My_fun，這個參數(shù)是2。點擊Start按鈕，運行遺傳算法，將在Status and Results（狀態(tài)與結(jié)果）窗格中顯示出相應(yīng)的運行結(jié)果。在Options窗格中可以改變遺傳算法的選項。為了查看窗格中所列出的各類選項，可單擊與之相連的符號“+”。8.2.3 舉例：Rastrigin函數(shù)本節(jié)介紹一個例子，講述如何尋找Rastrigin函數(shù)的最小值和顯示繪制的圖形。Rastrigin函數(shù)是最常用來測試遺傳算法的一個典型函數(shù)。Rastrigin函數(shù)的可視化圖形顯示，它具有多個局部最小值和一個全局最小值，遺傳算法可以幫助我們確定這種具有多個局部最小值函數(shù)的最優(yōu)解。 Rastrigin函數(shù)具有兩個獨立變量的Rastrigin函數(shù)定義為Rastrigin函數(shù)的圖形如圖8.3所示。工具箱包含一個M文件，即rastriginsfcn.m，是用來計算Rastrigin函數(shù)值的。全局最小點0，0圖8.3 Rastrigin函數(shù)圖形如圖8.3所示，Rastrigin函數(shù)有許多局部最小值在圖上顯示為“谷底（valleys）”。然而，該函數(shù)只有一個全局最小值，出現(xiàn)在x-y 平面上的點0，0處，正如圖中豎直線指示的那樣，函數(shù)的值在那里是0。在任何不同于0，0的局部最小點處，Rastrigin函數(shù)的值均大于0。局部最小處距原點越遠，該點處Rastrigin函數(shù)的值越大。Rastrigin函數(shù)之所以最常用來測試遺傳算法，是因為它有許多局部最小點，使得用標準的、基于梯度的查找全局最小的方法十分困難。圖8.4所示是Rastrigin函數(shù)的輪廓線，它顯示出最大最小交替變化的情形。全局最小點0，0局部最小點局部最小點圖8.4 Rastrigin函數(shù)的輪廓線 尋找Rastrigin函數(shù)的最小值本節(jié)解釋如何使用遺傳算法來尋找Rastrigin函數(shù)的最小值。注意：因為遺傳算法使用隨機數(shù)據(jù)來進行它的搜索，所以該算法每一次運行時所返回的結(jié)果會稍微有些不同。為了查找最小值，進行下列步驟：(1) 在命令行鍵入gatool，打開遺傳算法工具。(2) 在遺傳算法工具的相應(yīng)欄目，輸入適應(yīng)度函數(shù)和變量個數(shù)。在“Fitness function（適應(yīng)度函數(shù)）”文本框中，輸入rastriginsfcn；在“Number of variables（變量個數(shù)）”文本框中，輸入2，這就是Rastrigin函數(shù)獨立變量的個數(shù)。這一步操作如圖8.5所示。圖8.5 輸入適應(yīng)度函數(shù)與變量個數(shù)(3) 在“Run solver（運行求解器）”窗格中，單擊Start按鈕，如圖8.6所示。圖8.6 單擊運行求解器Start按鈕在算法運行的同時，“Current generation（當前代數(shù)）”文本框中顯示出當前的代數(shù)。通過點擊“暫停（Pause）”按鈕，可以使算法臨時暫停一下。當這樣做的時候，該按鈕的名字變?yōu)椤癛esume（恢復(fù)）”。為了從暫停處恢復(fù)算法的運行，可單擊這個“Resume”按鈕。當算法完成時，“Status and results”窗格出現(xiàn)如圖8.7所示的情形。最終點的適應(yīng)度函數(shù)值最終點圖8.7 狀態(tài)與結(jié)果顯示“Status and results”窗格顯示下列信息：(1) 算法終止時適應(yīng)度函數(shù)的最終值：Fitness function value: 0.0067749206244585025注意：所顯示的值非常接近于Rastrigin函數(shù)的實際最小值0?！斑z傳算法舉例”一節(jié)描述了一些方法，可以用來得到更接近實際最小值的結(jié)果。(2) 算法終止的原因：Optimization terminated:maximum number of generations exceeded.即退出的原因是：超過最大代數(shù)而導(dǎo)致優(yōu)化終止。在本例中，算法在100代后結(jié)束，這是 “Generations（代數(shù)）” 選項的缺省值，此選項規(guī)定了算法計算的最大代數(shù)。(3) 最終點，在本例中是0.00274 -0.00516。 從命令行查找最小值為了從命令行查找Rastrigin函數(shù)的最小值，可鍵入x fval reason = ga(rastriginsfcn, 2)這將返回x = 0.0027 -0.0052fval = 0.0068reason =Optimization terminated: maximum number of generations exceeded. 其中：x是算法返回的最終點；fval是該最終點處適應(yīng)度函數(shù)的值；reason是算法結(jié)束的原因。 顯示繪制圖形“Plots（繪圖）”窗格可以顯示遺傳算法運行時所提供的有關(guān)信息的各種圖形。這些信息可以幫助我們改變算法的選項，改進算法的性能。例如，為了繪制每一代適應(yīng)度函數(shù)的最佳值和平均值，選中復(fù)選框“Best fitness（最佳適應(yīng)度）”，如圖8.8所示。圖8.8 繪圖對話框當點擊Start按鈕時，遺傳算法工具顯示每一代適應(yīng)度函數(shù)的最佳值和平均值的繪制圖形。當算法停止時，所出現(xiàn)的圖形如圖8.9所示。最佳值 0.0067796 平均值 0.014788圖8.9 各代適應(yīng)度函數(shù)的最佳值和平均值在每一代中，圖的底部的點表示最佳適應(yīng)度值，而其上的點表示平均適應(yīng)度值。圖的頂部還顯示出當前一代的最佳值0.0067796和平均值0.014788。為了得到最佳適應(yīng)度值減少到多少為更好的直觀圖形，我們可以將圖中y軸的刻度改變?yōu)閷?shù)刻度。為此，需進行如下操作：(1) 從繪圖窗格的Edit（編輯）菜單中選擇“Axes Properties（坐標軸屬性）”，打開屬性編輯器，如圖8.10所示。選擇對數(shù)刻度單擊Y表項 圖8.10 繪圖屬性編輯器(2) 點擊Y表項。(3) 在“Scale（刻度）”窗格，選擇“Log (對數(shù))”。繪制的圖形如圖8.11所示。最佳值0.0067796 平均值0.014788圖8.11 每一代適應(yīng)度函數(shù)最佳值和平均值的對數(shù)圖形典型情況下，在早期各代中，當個體離理想值較遠時，最佳值會迅速得到改進。在后來各代中，種群越接近最佳點，最佳值改進得越慢。8.2.4 遺傳算法的一些術(shù)語本節(jié)解釋遺傳算法的一些基本術(shù)語，主要包括： 適應(yīng)度函數(shù)（Fitness Functions）。 個體（Individuals）。 種群（Populations）和代（Generations）。 適應(yīng)度值（Fitness Values）和最佳適應(yīng)度值（Best Fitness Values）； 父輩和子輩（Parents and Children）。 適應(yīng)度函數(shù)所謂適應(yīng)度函數(shù)就是想要優(yōu)化的函數(shù)。對于標準優(yōu)化算法而言，這個函數(shù)稱為目標函數(shù)。該工具箱總是試圖尋找適應(yīng)度函數(shù)的最小值。我們可以將適應(yīng)度函數(shù)編寫為一個M文件，作為輸入?yún)?shù)傳遞給遺傳算法函數(shù)。 個體一個個體是可以施加適應(yīng)度函數(shù)的任意一點。一個個體的適應(yīng)度函數(shù)值就是它的得分或評價。例如，如果適應(yīng)度函數(shù)是則向量（2, -3, 1）就是一個個體，向量的長度就是問題中變量的個數(shù)。個體（2, -3, 1）的得分是f(2, -3, 1) = 51。個體有時又稱為基因組或染色體組（genome），個體的向量項稱為基因（genes）。 種群與代所謂種群是指由個體組成的一個數(shù)組或矩陣。例如，如果個體的長度是100，適應(yīng)度函數(shù)中變量的個數(shù)為3，我們就可以將這個種群表示為一個1003的矩陣。相同的個體在種群中可以出現(xiàn)不止一次。例如，個體(2, -3, 1)就可以在數(shù)組的行中出現(xiàn)多次。每一次迭代，遺傳算法都對當前種群執(zhí)行一系列的計算，產(chǎn)生一個新的種群。每一個后繼的種群稱為新的一代。 多樣性多樣性或差異（Diversity）涉及一個種群的各個個體之間的平均距離。若平均距離大，則種群具有高的多樣性；否則，其多樣性低。在圖8.12中，左面的種群具有高的多樣性，亦即差異大；而右面的種群多樣性低，亦即差異小。圖8.12 種群多樣性比較多樣性是遺傳算法必不可少的本質(zhì)屬性，這是因為它能使遺傳算法搜索一個比較大的解的空間區(qū)域。 適應(yīng)度值和最佳適應(yīng)度值個體的適應(yīng)度值就是該個體的適應(yīng)度函數(shù)的值。由于該工具箱總是查找適應(yīng)度函數(shù)的最小值，所以一個種群的最佳適應(yīng)度值就是該種群中任何個體的最小適應(yīng)度值。 父輩和子輩為了生成下一代，遺傳算法在當前種群中選擇某些個體，稱為父輩，并且使用它們來生成下一代中的個體，稱為子輩。典型情況下，該算法更可能選擇那些具有較佳適應(yīng)度值的父輩。8.2.5 遺傳算法如何工作本節(jié)簡要介紹遺傳算法的工作原理或工作過程，內(nèi)容包括：算法要點；初始種群；生成下一代；后一代的繪圖；算法的停止條件。 算法要點下面的要點總結(jié)了遺傳算法是如何工作的：(1) 首先，算法創(chuàng)建一個隨機種群。(2) 接著，算法生成一個新的種群序列，即新的一代。在每一步，該算法都使用當前一代中的個體來生成下一代。為了生成新一代，算法執(zhí)行下列步驟：(a) 通過計算其適應(yīng)度值，給當前種群的每一個成員打分。(b) 確定原來的適應(yīng)度值的比例尺度，將其轉(zhuǎn)換為更便于使用的范圍內(nèi)的值。(c) 根據(jù)它們的適應(yīng)度選擇父輩。(d) 由父輩產(chǎn)生子輩。子輩的產(chǎn)生可以通過隨機改變一個單個父輩，亦即變異（mutation）來進行，也可以通過組合一對父輩的向量項，亦即交叉（crossover）來進行。(e) 用子輩替換當前種群，形成下一代。(3) 最后，若停止準則之一得到滿足，則該算法停止。關(guān)于停止準則，可參見“ 算法的停止條件”一節(jié)。 初始種群遺傳算法總是以產(chǎn)生一個隨機的初始種群開始，如圖8.13所示。圖8.13 初始種群在本例中，初始種群包含20個個體，這恰好是“Population（種群）”選項中的“Population size（種群尺度）”的缺省值。注意：初始種群中的所有個體均處于圖上右上角的那個象限，也就是說，它們的坐標處于0和1之間，這是因為“Population”選項中的“Initial range（初始范圍）”的缺省值是0; 1。如果已知函數(shù)的最小點大約位于何處，就可以設(shè)置一個適當?shù)摹癐nitial range”，以便使該點處于那個范圍的中間附近。例如，如果確信Rastrigin函數(shù)的最小值在點0，0附近，那么就可以直接設(shè)置“Initial range”為-1;1。然而，正如本例所顯示的那樣，即使沒有給“Initial range”設(shè)置一個理想的值，遺傳算法也還是能夠找到那個最小值。 產(chǎn)生下一代在每一步，遺傳算法使用當前種群來產(chǎn)生子輩，即獲得下一代。算法在當前種群中選擇一組個體，稱為父輩，這些個父輩將其genes亦即其向量中的項貢獻給它們的子輩。遺傳算法通常選擇那些具有較好適應(yīng)度值的個體作為父輩。我們可以在“Selection（選擇）”選項的“Selection function（選擇函數(shù)）”文本框中指定遺傳算法用來選擇父輩的函數(shù)。遺傳算法對于下一代產(chǎn)生三類子輩： 優(yōu)良子輩（Elite children），是在當前代中具有最佳適應(yīng)度值的那些個體。這些個體子輩存活到下一代。 交叉子輩（Crossover children），是由一對父輩向量組合產(chǎn)生的。 變異子輩（Mutation children），是對一個單個父輩引入隨機改變即變異產(chǎn)生的。圖8.14表示了這三個類型的子輩。優(yōu)良子輩交叉子輩變異子輩圖8.14 三類子輩在“變異與交叉”一節(jié)解釋如何指定遺傳算法產(chǎn)生的每一類子輩的數(shù)目，以及用來執(zhí)行完成交叉和變異的函數(shù)。 交叉子輩算法通過組合當前種群中的父輩對（Pair）來產(chǎn)生交叉子輩。在子輩向量的每一個相同位置處，缺省的交叉函數(shù)在兩個父輩之一的相同位置處隨機選擇一項，即基因，并將它指派給其子輩。 變異子輩算法通過隨機改變個體父輩中的基因而產(chǎn)生變異子輩。按照缺省，算法給父輩增加一個高斯分布的隨機向量。圖8.15表示出初始種群的子輩，也即第二代種群，并且指出它們是否為優(yōu)良子輩、交叉子輩或變異子輩。圖8.15 初始種群的子輩 后代圖形繪制圖8.16展示出在迭代60次, 80次, 95次, 100次時的種群的圖形。圖8.16 在迭代60, 80, 95, 100次時的種群隨著代數(shù)的增加，種群中的個體靠近在一起，且逼近最小值點0，0。 算法的停止條件遺傳算法使用下列5個條件來確定何時停止： Generations（代數(shù)）當產(chǎn)生的代的數(shù)目達到規(guī)定的代數(shù)的值時，算法停止。 Time limit（時限）在運行時間的秒數(shù)等于時限時，算法停止。 Fitness limit（適應(yīng)度限）當適應(yīng)度函數(shù)的值對于當前種群的最佳點小于或等于適應(yīng)度限時，算法停止。 Stall generations（停滯代數(shù)）在連續(xù)繁殖的時間序列中，若長時間不繁殖新代，亦即目標函數(shù)無改進，到達停滯代數(shù)規(guī)定的代數(shù)時，則算法停止。 Stall time limit（停滯時限）在秒數(shù)等于停滯時限的時間間隔期間，若目標函數(shù)無改進，則算法停止。若這5個條件中任何一個條件一旦滿足，則該算法停止。我們可以在遺傳算法工具的“Stopping criteria（停止標準）”選項中指定這些標準的值。它們的缺省值如圖8.17所示。圖8.17 停止標準的缺省值當運行遺傳算法時，“Status（狀態(tài)）”面板顯示這些導(dǎo)致算法停止的標準。“Time limit（時限）”選項與“Stall time limit”選項可以用來防止算法運行過長的時間。如果算法由于這兩個條件之一而停止，則可以通過相應(yīng)增加“Time limit”或“Stall time limit”的值來改善運行的結(jié)果。 8.3 使用遺傳算法工具求解問題本節(jié)首先概括使用遺傳算法工具GUI的一般步驟，然后介紹如何從命令行使用遺傳算法工具，最后通過例子，詳細說明如何使用遺傳算法工具來求解優(yōu)化問題。8.3.1 使用遺傳算法GUI在前面一章，已經(jīng)介紹了使用遺傳算法工具的初步知識。本節(jié)將簡要歸納使用遺傳算法工具GUI來求解優(yōu)化問題的一般步驟，內(nèi)容包括：打開遺傳算法工具；在遺傳算法工具中定義問題；運行遺傳算法；暫停和停止運算；圖形顯示；創(chuàng)建用戶圖形函數(shù)；復(fù)現(xiàn)運行結(jié)果；設(shè)置選項參數(shù)；輸入輸出參數(shù)及問題；從最后種群繼續(xù)運行遺傳算法。 打開遺傳算法工具 在MATLAB窗口中輸入gatool，打開、進入遺傳算法工具，初啟時的界面顯示如圖8.18所示。圖8.18 遺傳算法工具初啟時的界面 在遺傳算法工具中定義問題在下列兩個文本框中定義所要解決的問題：(1) 適應(yīng)度函數(shù)求解的問題是求目標函數(shù)的最小值。輸入一個計算適應(yīng)度函數(shù)的M文件函數(shù)的句柄。(2) 變量個數(shù)適應(yīng)度函數(shù)的獨立變量個數(shù)。注意：當運行遺傳算法工具時不要用“Editor/Debugger（編輯/調(diào)試）”功能來調(diào)試目標函數(shù)的M文件，而要從命令行直接調(diào)用目標函數(shù)或把M文件輸入到遺傳算法函數(shù)ga。為了方便調(diào)試，可以在遺傳算法工具中把問題輸出到MATLAB工作窗中。如圖8.19所示，輸入前面章節(jié)所介紹的Rastrigin函數(shù)或my_fun函數(shù)作為適配度函數(shù)，它們的變量個數(shù)為2。圖8.19 輸入適應(yīng)度函數(shù)與變量個數(shù) 運行遺傳算法要運行遺傳算法，在“ Run solver（運行求解器）”中單擊Start按紐，如圖8.20所示。圖8.20 單擊Start按鈕這時，在“Current generation（當前代）”文本框中顯示當前代的數(shù)目，在Status and results”窗格顯示“GA running”等信息，如圖8.23所示。圖8.21 當前代數(shù)和狀態(tài)與結(jié)果窗格當遺傳算法停止時，“Status and results”窗格顯示： “GA terminated（GA終止）”信息。 最后一代最佳個體的適應(yīng)度函數(shù)值。 算法停止的原因。 最終點的坐標。圖8.22顯示當運行例子“Rastrigin 函數(shù)”遺傳算法停止時的信息。圖8.22 Rastrigin函數(shù)的遺傳算法運行結(jié)果在遺傳算法工具中，當遺傳算法運行時可以更改多個參數(shù)設(shè)置。所做的改變將被應(yīng)用到下一代，即在下一代將按照新設(shè)置的參數(shù)運行。在下一代開始但尚未應(yīng)用改變的參數(shù)之前，在“Status and results”窗格顯示信息“Changes pending”。而在下一代開始且應(yīng)用了改變的參數(shù)時，在“Status and results”窗格顯示信息“Changes applied”。這樣在遺傳算法運行時更改了參數(shù)設(shè)置產(chǎn)生的輸出信息如圖8.23所示。圖8.23 遺傳算法運行時更改了參數(shù)設(shè)置 暫停和停止運算遺傳算法的暫停和停止運行，可以通過下面操作繼續(xù)運行： 單擊按鈕“Pause（暫停）”，算法暫停運行。該按鈕上的文字變?yōu)椤癛esume（恢復(fù)）”。單擊這個“Resume” 按鈕，即恢復(fù)遺傳算法繼續(xù)運行。 單擊按鈕“Stop”，算法停止運行?！癝tatus and results”窗口顯示停止運行時當前代最佳點的適應(yīng)度函數(shù)值。注意：如果單擊按鈕“Stop”，然后通過單擊按鈕“Start”再次運行時，遺傳算法將以新的隨機初始種群或在“Initial population（初始種群）”文本框中專門指定的種群運行。如果需要在算法停止后能再次恢復(fù)運行，則可以通過交替地單擊按鈕“Pause”和“Resume”來控制算法暫?；蚶^續(xù)運行。遺傳算法的停止運行常常是通過設(shè)置算法停止準則來進行控制的。使用停止準則，設(shè)置停止準則參數(shù)，可以解決遺傳算法在何時停止運行的控制問題。這樣，也就不用通過單擊“Stop” 按鈕來人為地控制算法運行的停止。遺傳算法有五個停止準則或條件，其中任何一個條件滿足，算法即停止運行。這些停止準則是： 代數(shù)算法運行到規(guī)定的代數(shù)。 時限算法運行到規(guī)定的時間。 適應(yīng)度限當前代的最佳適應(yīng)度值小于或等于規(guī)定的值。 停滯代數(shù)適應(yīng)度函數(shù)值在運行規(guī)定的代數(shù)后沒有改進。 停滯時限適應(yīng)度函數(shù)值在運行規(guī)定時間后沒有改進。如果想使算法一直運行到按下按鈕“Pause”或“Stop”時才停下來，可以改變這些停止準則的參數(shù)值： 設(shè)置“Generations（代數(shù)）”為 Inf。 設(shè)置“Time”為 Inf。 設(shè)置“Fitness limit”為 Inf。 設(shè)置“Stall generations”為 Inf。 設(shè)置“Stall time limit”為 Inf。圖8.24顯示了這些更改后的設(shè)置。圖8.24 改變停止準則參數(shù)注意：在命令行中調(diào)用遺傳算法函數(shù)ga時，并不使用這些參數(shù)設(shè)置，就好像是不按下 “Ctrl + C”鍵，函數(shù)就會永遠運行而不會停止。其實相反，可以設(shè)置“Generations”或者“Time”做為限值來控制算法停止運行。 圖形顯示圖8.25為“Plots（繪圖）”窗格，可以用來控制顯示遺傳算法運行結(jié)果變化的圖形。圖8.25 在繪圖窗格選擇輸出項選擇所要顯示的圖形參數(shù)的復(fù)選框。例如，如果選擇“Best Fitness（最佳適應(yīng)度）”和“Best individual（最佳個體）”，運行例子“Rastrigin 函數(shù)”，其顯示輸出如圖8.26所示。圖8.26 Rastrigin函數(shù)最佳適應(yīng)度與最佳個體圖8.28上部離散點為每一代的最佳適應(yīng)度值和平均適應(yīng)度值，下部柱型圖表示當前代最佳適應(yīng)度值對應(yīng)的點的坐標。注意：當要想顯示兩個以上參數(shù)項的圖形時，可選擇相應(yīng)參數(shù)項的復(fù)選框，單獨打開一個較大的圖形窗口即可。 舉例創(chuàng)建用戶繪圖函數(shù)如果工具箱中沒有符合想要輸出圖形的繪圖函數(shù)，用戶可以編寫自己的繪圖函數(shù)。遺傳算法在每次運行時調(diào)用這個函數(shù)，畫出圖形。這里舉例說明怎樣創(chuàng)建一個用戶繪圖函數(shù)來顯示從前一代到當前代最佳適應(yīng)度值的變化情形，內(nèi)容包括：創(chuàng)建繪圖函數(shù)，使用繪圖函數(shù)，繪圖函數(shù)如何作用。（1）創(chuàng)建繪圖函數(shù)為了創(chuàng)建繪圖函數(shù)，在MATLAB編輯器中復(fù)制、粘貼下列代碼到一個新的M文件。Function state = gaplotchange(options, state, flag)% GAPLOTCHANGE Plots the change in the best score from the% previous generation.persistent last_best % Best score in the previous generationif (strcmp(flag,init) % Set up the plotset(gca,xlim,1, options.Generations,Yscale，log); hold on; xlabel Generationtitle(Change in Best Fitness Value)endbest = min(state.Score)； % Best score in the current generationif state.Generation = 0 % Set last_best to best。last_best = best；elsechange = last_best - best；% Change in best scorelast_best = best；plot(state.Generation,change,.r)；title(Change in Best Fitness Value)end然后在MATLAB 路徑下將其存為M文件gaplotchange.m。（2）使用繪圖函數(shù)為了使用用戶繪圖函數(shù)，在”繪圖（Plots）”窗格中選擇“Custom function（定制函數(shù)）”，并且在其右邊的文本框中輸入函數(shù)名gaplotchange。為了對用戶繪圖函數(shù)輸出的最佳適應(yīng)度值圖形進行比較，在這里也選擇“Best Fitness”。現(xiàn)在，如果運行例子函數(shù)Rastrigin，顯示出來的圖形如圖8.27所示。最佳適應(yīng)度值的變化最佳值 0.0021904 平均值 0.49832圖8.27 用戶繪圖函數(shù)輸出的Rastrigin函數(shù)運行結(jié)果注意：因為圖中下半部的y-軸為對數(shù)刻度，所以圖形中的離散點僅僅顯示大于零的點。對數(shù)刻度能顯示適應(yīng)度函數(shù)的微小變化，而上面的圖形則不能顯示出微小變化。（3）繪圖函數(shù)如何作用繪圖函數(shù)使用包含在下面結(jié)構(gòu)體中的信息，它們由遺傳算法傳遞給繪圖函數(shù)作為輸入?yún)?shù)： options（參數(shù)） 當前參數(shù)設(shè)置。 state（狀態(tài)） 關(guān)于當前代的信息。 flag（曲線標志） 曲線表示為對數(shù)等的當前狀態(tài)。繪圖函數(shù)的主要作用可以描述如下：persistent last_best生成永久變量last_best 即前一代的最佳值。永久變量保存著多種圖形函數(shù)調(diào)用類型。set(gca, xlim，1，options.Generations, Yscale, log)；在遺傳算法運行前建立圖形。options.Generation為代數(shù)的最大值。best = min(state.Score)state.Score包含當前代中所有個體的得分值，變量best是其中最小的得分值。結(jié)構(gòu)體狀態(tài)文本框的完整描述可參見“ 圖形參數(shù)”一節(jié)。change = last_best - best變量change是前一代的最佳值減去當前代的最佳值。plot(state.Generation，change，.r)畫出當前代的變化曲線，變量維數(shù)包含在state.Generation中。函數(shù)gaplotchange的代碼包含了函數(shù)gaplotbestf代碼中許多相同成分，函數(shù)gaplotbestf生成最佳適應(yīng)度圖形。 復(fù)現(xiàn)運行結(jié)果為了復(fù)現(xiàn)遺傳算法前一次的運行結(jié)果，選擇“Use random states from previous run（使用前一次運行的隨機狀態(tài)）”復(fù)選框。這樣就把遺傳算法所用的隨機數(shù)發(fā)生器的狀態(tài)重新設(shè)置為前一次的值。如果沒有改變遺傳算法工具中的所有設(shè)置，那么遺傳算法下一次運行時返回的結(jié)果與前一次運行的結(jié)果一致。正常情況下，不要選擇“Use random states from previous run”這個復(fù)選框，可以充分利用遺傳算法隨機搜索的優(yōu)點。如果想要分析特定的運行結(jié)果或者顯示相對個體的精確結(jié)果，可以選擇“Use random states from previous run”復(fù)選框。 設(shè)置選項參數(shù)設(shè)置遺傳算法工具使用時的選項參數(shù)有兩種方法：一種是在遺傳算法工具GUI的“Options”窗格中直接進行設(shè)置，另一種是在MATLAB工作窗口中通過命令行方式進行設(shè)置。在參數(shù)“Options”窗格中設(shè)置遺傳算法的各種運行參數(shù)，如圖8.28所示。每一類參數(shù)對應(yīng)有一個窗格，單擊該類參數(shù)時，對應(yīng)窗格展開。例如，點擊“Population”參數(shù)選項，種群窗格展開來，可以逐一設(shè)置其中的參數(shù)項，如Population type（種群類型）、Population size（種群尺度）、Creation function（創(chuàng)建函數(shù)）、Initial population、Initial score（初始得分）、Initial range（初始范圍）等。此外，其他選項參數(shù)類還有：Fitness scaling（適應(yīng)度測量）、selection、Reproduction、Mutation、Crossover、Migration（遷移）、Hybrid function（混合函數(shù)）、Stopping criteria、Output function（輸出函數(shù)）、Display to command window（顯示到命令窗口）、Vectorize（向量化）等。這些參數(shù)類各自對應(yīng)一個參數(shù)窗格，點擊后相應(yīng)窗格隨即展開，可以進行參數(shù)項的設(shè)置。所有變量參數(shù)的含義及詳細描述可參見“8.4.1 遺傳算法參數(shù)”一節(jié)。圖8.28 選項參數(shù)窗口在MATLAB工作窗口中，可以將遺傳算法的運行參數(shù)設(shè)置為變量。對于數(shù)值參數(shù)的設(shè)置，可以直接在相應(yīng)編輯框中輸入該參數(shù)的值，或者在包含該參數(shù)值的MATLAB工作窗口中輸入相應(yīng)變量的名字，就可以完成設(shè)置。例如，可以利用下面兩種方法之一設(shè)置“Initial point（初始點）”為2.1 1.7： 在“Initial point”文本框輸入2.1 1.7。 在MATLAB工作區(qū)輸入變量x0 = 2.1 1.7，然后在“Initial point” 文本框輸入變量的名字x0。因為選項參數(shù)是比較大的矩陣或向量，所以在MATLAB工作窗口中把參數(shù)的值定義為變量一般是比較方便的，也就是說，如果需要，很容易改變矩陣或向量的項。 輸入輸出參數(shù)及問題參數(shù)和問題結(jié)構(gòu)可以從遺傳算法工具被輸出到MATLAB的工作窗口，也可以在以后的某個時間再反過來把它們從MATLAB的工作窗口輸入給遺傳算法工具。這樣就可以保存對問題的當前設(shè)置，并可以在以后恢復(fù)這些設(shè)置。參數(shù)結(jié)構(gòu)也可以被輸出到MATLAB工作窗口，并且可以再把它們用于命令行方式的遺傳算法函數(shù)ga。輸入和輸出信息通常包含下列各項： 問題定義，包括“Fitness function”和“Number of variables（變量個數(shù)）”。 當前指定的選項參數(shù)。 算法運行的結(jié)果。下面解釋如何輸入和輸出這些信息。（1）輸出參數(shù)和問題參數(shù)和問題可以被輸出到MATLAB工作空間，以便以后在遺傳算法工具中應(yīng)用它們。也可以以命令行方式，在函數(shù)ga中應(yīng)用這些參數(shù)和問題。為了輸出參數(shù)和問題，單擊“Export to Workspace（輸出到工作空間）”按鈕或從File菜單中選擇“Export to Workspace”菜單項，這將打開如圖8.29所示的對話框。圖8.29 輸出對話框?qū)υ捒蛱峁┫铝袇?shù)： 為了保存問題的定義和當前參數(shù)的設(shè)置，選擇“Export problem and options to a MATLAB structure named（輸出問題與參數(shù)到已命名的MATLAB結(jié)構(gòu)）”，并為這個結(jié)構(gòu)體輸入一個名字。單擊OK按鈕，即把這個信息保存到MATLAB工作空間的一個結(jié)構(gòu)體。如果以后要把這個結(jié)構(gòu)體輸入到遺傳算法工具，那么當輸出這個結(jié)構(gòu)時，所設(shè)置的“Fitness function”和“Number of variables”，以及所有的參數(shù)設(shè)置都被恢復(fù)到原來值。注意：輸出問題之前，如果在“Run solver（運行求解器）” 窗格選中“Use random states from previous run（使用前一次運行的隨機狀態(tài)）”選項，則遺傳算法工具將保存上一次運行開始時隨機數(shù)產(chǎn)生函數(shù)rand和randn的狀態(tài)。然后，在選擇了“Use random states from previous run”選項的情況下，輸入問題且運行遺傳算法，那么輸出問題之前的運行結(jié)果就被準確地復(fù)現(xiàn)了。 如果想要遺傳算法在輸出問題之前從上一次運行的最后種群恢復(fù)運行，可選擇“Include information needed to resume this run（包括所需信息以恢復(fù)本次運行）”。然后，當輸入問題結(jié)構(gòu)體并單擊Start按鈕，算法就從前次運行的最后種群繼續(xù)運行。為了恢復(fù)遺傳算法產(chǎn)生隨機初始種群的缺省行為，可刪除在“Init