遺傳算法原理及其應(yīng)用 第三章 遺傳算法的基本實(shí)現(xiàn)技術(shù)

遺傳算法原理及其應(yīng)用王正山wzs@第三章遺傳算法的基本實(shí)現(xiàn)技術(shù)掌握編碼方法掌握適應(yīng)度函數(shù)的設(shè)計(jì)方法掌握選擇、交叉、變異算子的設(shè)計(jì)方法了解遺傳算法的運(yùn)行參數(shù)設(shè)置掌握約束條件處理方法掌握Matlab遺傳算法工具箱3.1編碼方法編碼在遺傳算法中如何描述問(wèn)題的可行解，即把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱為編碼。設(shè)計(jì)一個(gè)完美的編碼方案是遺傳算法的應(yīng)用難點(diǎn)之一。編碼規(guī)則有意義的積木塊編碼原則：應(yīng)使用能易于產(chǎn)生與所求問(wèn)題相關(guān)的且具有低階、短定義長(zhǎng)度模式的編碼方案。最小字符集編碼原則：應(yīng)使用能使問(wèn)題得到自然表示或描述的具有最小編碼字符集的編碼方案。編碼分類二進(jìn)制編碼方法浮點(diǎn)編碼方法符號(hào)編碼方法3.1.1二進(jìn)制編碼方法二進(jìn)制編碼方法二進(jìn)制編碼方法使用的編碼符號(hào)集是由二進(jìn)制符號(hào)0和1所組成的二值符號(hào)集{0,1}，它構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼的符號(hào)串。二進(jìn)制編碼符號(hào)串的長(zhǎng)度與問(wèn)題所要求的求解精度有關(guān)。假設(shè)某一個(gè)參數(shù)的取值范圍是[Umin,Umax]，我們用長(zhǎng)度為l的二進(jìn)制編碼符號(hào)串來(lái)表示該參數(shù)，則它總共能夠產(chǎn)生2l中不同的編碼。因此，二進(jìn)制的編碼精度為。二進(jìn)制編碼的優(yōu)點(diǎn)編碼、解碼操作簡(jiǎn)單易行。交叉、變異等遺傳操作便于實(shí)現(xiàn)。符合最小字符集編碼原則。便于利用模式定理對(duì)算法進(jìn)行理論分析。假設(shè)某一參數(shù)的編碼是：則對(duì)應(yīng)的解碼公式為：3.1.2格雷碼編碼方法格雷碼編碼方法引入格雷碼的原因二進(jìn)制編碼不便于反映一些連續(xù)函數(shù)優(yōu)化問(wèn)題的特征且使得遺傳算法的局部搜索能力較差。格雷碼要求連續(xù)的兩個(gè)整數(shù)所對(duì)應(yīng)的編碼值之間僅僅只有一個(gè)碼位是不同的，其余碼位都完全相同。右表是十進(jìn)制0~15之間的二進(jìn)制碼和相應(yīng)的格雷碼。格雷碼的優(yōu)點(diǎn)便于提高遺傳算法的局部搜索能力。交叉、變異等遺傳操作便于實(shí)現(xiàn)。符合最小字符集編碼原則。便于利用模式定理對(duì)算法進(jìn)行理論分析。十進(jìn)制數(shù)二進(jìn)制碼格雷碼000000000100010001200100011300110010401000110501010111601100101701110100810001100910011101101010111111101111101211001010131101101114111010011511111000編碼和解碼過(guò)程：決策向量二進(jìn)制格雷碼3.1.3浮點(diǎn)數(shù)編碼方法浮點(diǎn)數(shù)編碼方法二進(jìn)制編碼的缺點(diǎn)二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差。二進(jìn)制編碼不便于反映所求問(wèn)題的特定知識(shí)，也不便于處理非平凡約束條件。浮點(diǎn)數(shù)編碼是指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示，個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)。例如，X=[5.80,6.90,3.50,3.80,5.00]在浮點(diǎn)數(shù)編碼方法中，必須保證基因值在給定的區(qū)間限制范圍內(nèi)。浮點(diǎn)數(shù)編碼的優(yōu)點(diǎn)適合于在遺傳算法中表示范圍較大的數(shù)。適合于精度要求較高的遺傳算法。便于較大空間的遺傳搜索。改善了遺傳算法的復(fù)雜性，提高了運(yùn)算效率。便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用。便于設(shè)計(jì)針對(duì)問(wèn)題的專門知識(shí)的知識(shí)型遺傳算子。便于處理復(fù)雜的決策變量約束條件。3.1.4無(wú)符號(hào)數(shù)編碼方法符號(hào)編碼方法指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(shù)值含義、而只有代碼含義的符號(hào)集。這個(gè)符號(hào)集可以是一個(gè)字母表，也可以是一個(gè)數(shù)字序號(hào)表。旅行商問(wèn)題:已知n個(gè)城市之間的相互距離?，F(xiàn)有一推銷員必須遍訪這n個(gè)城市，并且每個(gè)城市只能訪問(wèn)一次，最后又必須返回出發(fā)城市。如何安排他對(duì)這些城市的訪問(wèn)次序，可使其旅行路線的總長(zhǎng)度最短?

例如，對(duì)于旅行商問(wèn)題，假設(shè)有n個(gè)城市分別記為C1,C2,…,Cn，將各個(gè)城市的代號(hào)按其被訪問(wèn)的順序連接在一起就可構(gòu)成一個(gè)表示旅行路線的個(gè)體。例如，X:[C1,C2,…,Cn]。若將各個(gè)城市按其代號(hào)的下標(biāo)進(jìn)行編號(hào)，則這個(gè)個(gè)體也可表示為：X:[1,2,…,n]

。符號(hào)編碼的優(yōu)點(diǎn)符合有意義積木塊的編碼原則。便于在遺傳算法中利用所求解問(wèn)題的專門知識(shí)。便于遺傳算法與相關(guān)近似算法之間的混合使用。3.1.5多參數(shù)級(jí)聯(lián)編碼方法多參數(shù)級(jí)聯(lián)編碼對(duì)含有多個(gè)變量的個(gè)體進(jìn)行編碼的方法就稱為多參數(shù)編碼方法。將各個(gè)參數(shù)分別以某種編碼方法進(jìn)行編碼，然后再將它們的編碼按一定順序聯(lián)接在一起就組成了表示全部參數(shù)的個(gè)體編碼。這種編碼方法稱為多參數(shù)級(jí)聯(lián)編碼方法。在進(jìn)行多參數(shù)級(jí)聯(lián)編碼時(shí)，每個(gè)參數(shù)的編碼方式可以是二進(jìn)制編碼、格雷碼、浮點(diǎn)數(shù)編碼或符號(hào)編碼等編碼方式中的一種，每個(gè)參數(shù)可以真有不同的上下界，也可以有不同的編碼長(zhǎng)度或編碼精度。3.1.6多參數(shù)交叉編碼方法多參數(shù)交叉編碼方法基本思想將各個(gè)參數(shù)中起主要作用的碼位集中在一起。具體方法在進(jìn)行多參數(shù)交叉編碼時(shí)，可先對(duì)各個(gè)參數(shù)進(jìn)行分組編碼(假設(shè)共有n個(gè)參數(shù)，每個(gè)參數(shù)都用長(zhǎng)度為m的地二進(jìn)制串表示)；然后取各個(gè)參數(shù)編碼串中的最高位聯(lián)接在一起，以它們作為個(gè)體編碼串的前n位編碼；再取各個(gè)參數(shù)編碼串中的次高位聯(lián)接在一起，…。這樣所組成的長(zhǎng)度為mn位的編碼串就是多參數(shù)的一個(gè)交叉編碼串。思考題：多參數(shù)級(jí)聯(lián)編碼與多參數(shù)交叉編碼方法的適用范圍？3.2適應(yīng)度函數(shù)目標(biāo)函數(shù)與適應(yīng)度函數(shù)目標(biāo)函數(shù)是指所關(guān)心的目標(biāo)(某一變量y)與相關(guān)的因素(某些變量xi)的函數(shù)關(guān)系。適應(yīng)度函數(shù)度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。評(píng)價(jià)個(gè)體適應(yīng)度的一般過(guò)程對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體的表現(xiàn)型。由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。根據(jù)最優(yōu)化問(wèn)題的類型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度。第二章中給出的是基本遺傳算法的目標(biāo)函數(shù)到適應(yīng)度函數(shù)的變換方法。F(X)=f(X)+Cmin

iff(X)+Cmin>00

iff(X)+Cmin

≤03.2適應(yīng)度函數(shù)…適應(yīng)度函數(shù)尺度變化的原因在遺傳算法運(yùn)行早期群體中可能會(huì)有少數(shù)幾個(gè)個(gè)體的適應(yīng)度相對(duì)其他個(gè)體來(lái)說(shuō)非常高。若按照常用的比例選擇算子來(lái)確定個(gè)體的遺傳數(shù)量時(shí)，則這幾個(gè)相對(duì)較好的個(gè)體將在下一代群體中占有很高的比例，在極端情況下或當(dāng)群體現(xiàn)模較小時(shí)，新的群體甚至完全由這樣的少數(shù)幾個(gè)個(gè)體所組成。這時(shí)產(chǎn)生新個(gè)體作用較大的交叉算子就起不了什么作用，因?yàn)橄嗤膬蓚€(gè)個(gè)體不論在何處進(jìn)行交叉操作都永遠(yuǎn)不會(huì)產(chǎn)生出新的個(gè)體。在遺傳算法運(yùn)行的后期階段群體中所有個(gè)體的平均適應(yīng)度可能會(huì)接近于群體中最佳個(gè)體的適應(yīng)度。也就是說(shuō)，大部分個(gè)體的適應(yīng)度和最佳個(gè)體的適應(yīng)度差異不大，它們之間無(wú)競(jìng)爭(zhēng)力，都會(huì)有以相接近的概率被遺傳到下一代的可能性，從而使得進(jìn)化過(guò)程無(wú)競(jìng)爭(zhēng)性可言，只是一種隨機(jī)的選擇過(guò)程。3.2適應(yīng)度函數(shù)…適應(yīng)度尺度變換方法線性尺度變換（圖示見(jiàn)下頁(yè)）乘冪尺度變換指數(shù)尺度變換3.2適應(yīng)度函數(shù)…線性比例尺度變換的正常情況示意圖滿足兩個(gè)條件尺度變換后全部個(gè)體的新適應(yīng)度的平均值要等于其原始適應(yīng)度的平均適應(yīng)值。尺度變換后群體中新的最大適應(yīng)度要等于其原平均適應(yīng)度的指定倍數(shù)。使用適應(yīng)度尺度變換時(shí)，群體中少數(shù)幾個(gè)優(yōu)良個(gè)體的適應(yīng)度按比例縮小，同時(shí)幾個(gè)較差個(gè)體的適應(yīng)度也按比例擴(kuò)大。種群規(guī)模大小為50~100時(shí)，C的取值是1.2~2。3.2適應(yīng)度函數(shù)…線性比例尺度變換的非正常情況示意圖原因：在遺傳算法搜索過(guò)程的后期階段，隨著個(gè)體適應(yīng)度從總體上的不斷改進(jìn)，群體中個(gè)體的最大適應(yīng)度和全部個(gè)體的平均適應(yīng)度較接近，而少數(shù)幾個(gè)較差的個(gè)體的適應(yīng)度卻遠(yuǎn)遠(yuǎn)低于最大適應(yīng)度，這時(shí)要想維持C的值不變，將有可能會(huì)使較差個(gè)體的適應(yīng)度為負(fù)數(shù)。解決方法：把原最小適應(yīng)度Fmin映射為F’min，使得F’min值為0，并且保持原平均適應(yīng)度Favg與新的平均適應(yīng)度F’avg相等。3.3選擇算子比例選擇各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。設(shè)群體大小為M，個(gè)體i的適應(yīng)度為Fi，則個(gè)體i被選中的概率pis為：最優(yōu)保存策略迄今為止的適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，而是用它來(lái)替換掉本代群體中經(jīng)過(guò)交叉、變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個(gè)體。具體操作過(guò)程找出當(dāng)前群體中適應(yīng)度最高的個(gè)體和適應(yīng)度最低的個(gè)體。若當(dāng)前群體中最佳個(gè)體的適應(yīng)度比總的迄今為止的最好個(gè)體的適應(yīng)度還要高，則以當(dāng)前種群中的最佳個(gè)體作為新的迄今為止的最好個(gè)體。用迄今為止的最好個(gè)體替換掉當(dāng)前群體中的最差個(gè)體。最優(yōu)保存策略可視為選擇操作的一部分。當(dāng)前種群的最佳個(gè)體當(dāng)前種群的最差個(gè)體迄今為止的最好個(gè)體3.3.3確定式采樣選擇確定式采樣選擇基本思想按照一種確定的方式來(lái)進(jìn)行選擇操作。操作過(guò)程計(jì)算群體中各個(gè)個(gè)體在下一代群體中的期望生存數(shù)目Ni=(Fi

/sum(Fi))xM。用Ni的整數(shù)部分確定各個(gè)對(duì)應(yīng)個(gè)體在下一代群體中的生存數(shù)目。按照Ni的小數(shù)部分對(duì)個(gè)體進(jìn)行降序排序，順序取前苦干個(gè)個(gè)體使得下一代群體中的個(gè)體數(shù)目達(dá)到M-sum(Ni)個(gè)。3.3.4無(wú)回放隨機(jī)選擇無(wú)回放隨機(jī)選擇基本思想根據(jù)每個(gè)個(gè)體在下一代群體中的生存期望值來(lái)進(jìn)行隨機(jī)運(yùn)算。操作過(guò)程計(jì)算群體中每個(gè)個(gè)體在下一代群體中的生存期望數(shù)目Ni。若某一個(gè)個(gè)體被選中參與交叉運(yùn)算，則它在下一代中的生存期望數(shù)目減去0.5；若某一個(gè)個(gè)體沒(méi)有被選中參與交叉運(yùn)算，則它在下一代中的生存期望數(shù)目減去1.0。隨著選擇過(guò)程的進(jìn)行，若某一個(gè)個(gè)體的生存期望數(shù)目小于0，則該個(gè)體就不再有機(jī)會(huì)被選中。3.3.5無(wú)回放余數(shù)隨機(jī)選擇無(wú)回放余數(shù)隨機(jī)選擇操作過(guò)程計(jì)算群體中每一個(gè)個(gè)體在下一代群體中的生存期望數(shù)目Ni。取Ni的整數(shù)部分為對(duì)應(yīng)個(gè)體在一下代群體中的生存數(shù)目。這樣共可確定出下一代群體中的個(gè)個(gè)體。以為各個(gè)個(gè)體的新的適應(yīng)度，用比例選擇方法來(lái)隨機(jī)確定下一代群體中還沒(méi)有確定的個(gè)體。3.3.6排序選擇排序選擇基本思想對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率。具體過(guò)程對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行降序排序。根據(jù)具體求解問(wèn)題，設(shè)計(jì)一個(gè)概率分配表，將各個(gè)概率值按上述排列次序分配給各個(gè)個(gè)體。以各個(gè)個(gè)體所分配到的概率值作為其能夠被遺傳到下一代的概率，基于這些概率值用比例選擇的方法來(lái)產(chǎn)生下一代群體。關(guān)鍵問(wèn)題必須根據(jù)對(duì)所研究問(wèn)題的分析和理解情況預(yù)先設(shè)計(jì)一個(gè)概率分配表。3.3.7隨機(jī)聯(lián)賽選擇隨機(jī)聯(lián)賽選擇基本思想每次選取幾個(gè)個(gè)體之中適應(yīng)值最高的一個(gè)個(gè)體遺傳到下一代群體中。具體過(guò)程從群體中隨機(jī)選取N個(gè)個(gè)體進(jìn)行適應(yīng)度大小的比較，將其中適應(yīng)度最高的上體遺傳到下一代群體中。將上述過(guò)程復(fù)復(fù)M次，就可得到下一代群體中的M個(gè)個(gè)體。N的值通常情況下，聯(lián)賽規(guī)模N的取值是2。3.4交叉算子交叉算子是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法產(chǎn)生新個(gè)體的主要方法，它決定了遺傳算法的全局搜索能力。配對(duì)策略隨機(jī)配對(duì)，即將群體中的M個(gè)個(gè)體以隨機(jī)的方式組成M/2對(duì)配對(duì)個(gè)體組。研究?jī)?nèi)容如何確定交叉點(diǎn)的位置？如何進(jìn)行部分基因交換？3.4交叉算子…單點(diǎn)交叉指在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)的部分染色體。雙點(diǎn)交叉指在個(gè)體編碼串中隨機(jī)設(shè)置二個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因交換。操作過(guò)程在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)。交換兩個(gè)個(gè)體在所設(shè)定的兩個(gè)交叉點(diǎn)之間的部分染色體。3.4.3均勻交叉均勻交叉均勻交叉是指兩個(gè)配對(duì)個(gè)體的每一個(gè)基因座上的基因都以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體。操作過(guò)程隨機(jī)產(chǎn)生一個(gè)與個(gè)體編碼串長(zhǎng)度等長(zhǎng)的屏蔽字W。由下述規(guī)則從A和B兩個(gè)父代個(gè)體中產(chǎn)生出兩個(gè)新的子代個(gè)體A’和B’。若wi

=0，則A’在第i個(gè)基因座上的基因值繼承A的對(duì)應(yīng)基因值，B’在第i個(gè)基因座上的基因值繼承B的對(duì)應(yīng)基因值。若wi=1，則A’在第i個(gè)基因座上的基因值繼承B的對(duì)應(yīng)基因值，B’在第i個(gè)基因座上的基因值繼承A的對(duì)應(yīng)基因值。3.4.4算術(shù)交叉算子算術(shù)交叉算術(shù)交叉是指由兩個(gè)個(gè)體的線性組合而產(chǎn)生出兩個(gè)新的個(gè)體。算術(shù)交叉一般采用浮點(diǎn)數(shù)編碼。假設(shè)有兩個(gè)個(gè)體XA和XB之間進(jìn)行算術(shù)交叉，則交叉運(yùn)算后所產(chǎn)生的兩個(gè)新個(gè)體是：如果α(0<α<1)是一個(gè)常數(shù)，則稱為均勻算術(shù)交叉；如果α是一個(gè)由進(jìn)化代數(shù)所決定的變量，則稱為非均勻算術(shù)交叉。3.5變異算子變異算子是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其它等位基因來(lái)替換，從而形成一個(gè)新的個(gè)體。變異運(yùn)算是遺傳算法產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力。作用改善遺傳算法的局部搜索能力。維持種群的多樣性，防止出現(xiàn)“早熟”現(xiàn)象。研究?jī)?nèi)容如何確定變異點(diǎn)？如何進(jìn)行基因值替換？3.5變異算子…基本位變異指對(duì)個(gè)體編碼串中以變異概率pc隨機(jī)指定的某一位或某幾位基因座上的基因值作變異運(yùn)算。均勻變異指分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來(lái)替換個(gè)體編碼串中各個(gè)基因座上的原有基因值。假設(shè)有一個(gè)個(gè)體為X=x1x2…xk…xl，若xk為變異點(diǎn)，其取值范圍為[Ukmin,Ukmax]，在該點(diǎn)對(duì)個(gè)體X進(jìn)行均勻變異操作后，可得到一個(gè)新的個(gè)體X’=x1x2…x’k…xl，其變異的新基因值是：其中，r為[0,1]范圍內(nèi)符合均勻分布的一個(gè)隨機(jī)數(shù)。3.5.3邊界變異邊界變異邊界變異操作是均勻變異操作的一個(gè)變形。在進(jìn)行邊界變異操作時(shí)，隨機(jī)地取基因座的二個(gè)對(duì)應(yīng)邊界基因值之一去替代原有基因值。在進(jìn)行由X=x1x2…xk…xl向X’=x1x2…x’k…xl的邊界變異操作時(shí)，若變異點(diǎn)xk的基因取值范圍為[Ukmin,Ukmax]，則新的x’k由下式確定：3.5.4非均勻變異非均勻變異不是取均勻分布的隨機(jī)數(shù)去替換原有的基因值，而是對(duì)原有基因作一隨機(jī)擾動(dòng)，以擾動(dòng)后的結(jié)果作為變異后的新基因值。非均勻變異的具體操作過(guò)程與均勻變異相類似，但是它重點(diǎn)搜索原個(gè)體附近的微小區(qū)域。在進(jìn)行由X=x1x2…xk…xl向X’=x1x2…x’k…xl的非均勻變異操作時(shí)，若變異點(diǎn)xk的基因取值范圍為[Ukmin,Ukmax]，則新的x’k由下式確定：

Δ(t,y)表示[0,y]范圍內(nèi)符合非均勻分布的一個(gè)隨機(jī)數(shù)，要求隨著進(jìn)化代數(shù)t的增加，Δ(t,y)接近于0的概率也逐漸增加。例如，Δ(t,y)可按下式定義：其中，r為[0,1]范圍內(nèi)符合均勻分布的一個(gè)隨機(jī)數(shù)，T是最大進(jìn)化代數(shù)，b是一個(gè)系統(tǒng)參數(shù)。3.5.5高斯變異高斯變異高期變異是改進(jìn)遺傳算法對(duì)重點(diǎn)搜索區(qū)域的局部搜索性能的另一種變異操作方法。高斯變異是指進(jìn)行變異操作時(shí)，用符合均值為μ、方差為σ2的正態(tài)分布的一個(gè)隨機(jī)數(shù)來(lái)替換原有基因值。具體實(shí)現(xiàn)高斯變異時(shí)，符合正態(tài)分布的隨機(jī)數(shù)Q可由一些符合均勻分布的隨機(jī)數(shù)利用公式來(lái)近似產(chǎn)生。假定有12個(gè)在[0,1]范圍內(nèi)均勻分布的隨機(jī)數(shù)ri(i=1,2,..,12)，則符合N(μ,σ2)正態(tài)分布的一個(gè)隨機(jī)數(shù)Q可由下式求得：3.6遺傳算法的運(yùn)行參數(shù)編碼串的長(zhǎng)度l群體大小M交叉概率pc變異概率pm終止代數(shù)T規(guī)定最大迭代次數(shù)T規(guī)定最小的偏差觀察適應(yīng)度的變化趨勢(shì)代溝G表示每一代群體中被替換掉的個(gè)體在全部個(gè)體中所占的百分比。G=1.0表示群體中的全部個(gè)體都是新產(chǎn)生的。3.7約束條件的處理方法搜索空間限定法基本思想對(duì)遺傳算法的搜索空間的大小加以限制，使得搜索空間中表示一個(gè)個(gè)體的點(diǎn)與解空間中表示一個(gè)可行解的點(diǎn)有一一對(duì)應(yīng)的關(guān)系。評(píng)價(jià)用這種處理方法能夠在遺傳算法中設(shè)置最小的搜索空間。但是，除了在編碼方法上想辦法之外，還必須保證經(jīng)過(guò)交叉、變異等遺傳操作作用之后所產(chǎn)生的新個(gè)體在解空間中也要有確定的對(duì)應(yīng)解，而不會(huì)產(chǎn)生無(wú)效解。實(shí)現(xiàn)方法用編碼方法來(lái)保證總是能夠產(chǎn)生出在解空間中有對(duì)應(yīng)可行解的染色體。用程序來(lái)保證直到產(chǎn)生出在解空間中有對(duì)應(yīng)可行解的染色體之前，一直進(jìn)行交叉運(yùn)算和變異運(yùn)算。3.7約束條件的處理方法…可行解變換法基本思想在由個(gè)體基因型到個(gè)體表現(xiàn)型的變換中，增加使其滿足約束條件的處理過(guò)程。即尋找出一種個(gè)體基因型和個(gè)體表現(xiàn)型之間的多對(duì)一的變換關(guān)系，使進(jìn)化過(guò)程中所產(chǎn)生的個(gè)體總能夠通過(guò)這個(gè)變換而轉(zhuǎn)化成解空間中滿足約束條件的一個(gè)可行解。評(píng)價(jià)這種處理方法雖然對(duì)個(gè)體的編碼方法、交叉運(yùn)算等沒(méi)有附加要求，但它卻是以擴(kuò)大搜索空間為代價(jià)的。3.7約束條件的處理方法…罰函數(shù)法基本思想對(duì)在解空間中無(wú)對(duì)應(yīng)的可行解的個(gè)體，計(jì)算其適應(yīng)度時(shí)，處以一個(gè)罰函數(shù)，從而降低個(gè)體適應(yīng)度，使該個(gè)體被遺傳到下一代群體中的機(jī)會(huì)減少。即用下式來(lái)對(duì)個(gè)體的適應(yīng)度進(jìn)行調(diào)整：其中F(X)為原適應(yīng)度，F(xiàn)’(X)為考慮了罰函數(shù)之后的新適應(yīng)度，P(X)為罰函數(shù)。評(píng)價(jià)如何確定合理的罰函數(shù)是這種處理方法的難點(diǎn)所在，因?yàn)檫@時(shí)既要考慮如何度量解對(duì)約束條件不滿足的程度，又要考慮遺傳算法在計(jì)算效率上的要求。圖形界面方式打開圖形界面的命令gatool輸入下列信息FitnessfunctionNumberofvariables單擊start按鈕運(yùn)行遺傳算法在Statusandresults的窗格中顯示出相應(yīng)的運(yùn)行結(jié)果在Plots空格中可以需要顯示的圖形在Options窗格中可以改變遺傳算法的選項(xiàng)。Matlab遺傳算法工具箱…Matlab遺傳算法工具箱…舉例：Rastrigin函數(shù)Rastrigin函數(shù)Rastrigin函數(shù)圖像尋找Rastrigin函數(shù)的最小值在命令行鍵入gatool輸入適應(yīng)度函數(shù)和變量個(gè)數(shù)單擊start按鈕(Stop,Pause,Resume)查看運(yùn)行結(jié)果顯示繪制圖形復(fù)現(xiàn)運(yùn)行結(jié)果設(shè)置選項(xiàng)參數(shù)輸出問(wèn)題和選項(xiàng)參數(shù)輸入問(wèn)題和選項(xiàng)參數(shù)生成M文件Matlab遺傳算法工具箱只求最小值Matlab遺傳算法工具箱命令行方式[x,fval,exitFlag,output,population,scores]=ga(@fitnessfun,nvars,options)@fitness：適應(yīng)度函數(shù)的句柄。nvars：適應(yīng)度函數(shù)的獨(dú)立變量的個(gè)數(shù)。options是一個(gè)包含遺傳算法選項(xiàng)參數(shù)的結(jié)構(gòu)。如果不傳遞選項(xiàng)參數(shù)，則ga使用它本身的缺省選項(xiàng)值。x：最終值到達(dá)的點(diǎn)。fval：適應(yīng)度函數(shù)的最終值。exitFlag:算法停止的原因。output:randstate,randnstate,generations,funcount,message。population:最后種群。scores:最后種群的得分值。從命令行查找最小值[x,fval

resean]=ga(@rastriginsfcn,2)Matlab701\toolbox\gads\gadsdemosMatlab遺傳算法工具箱…設(shè)置選項(xiàng)參數(shù)options=gaoptimsetoptions=gaoptimset(“PopulationSize’,100)options=gaoptimset(“PopulationSize’,100,’Plotfcns’,@plotbestf)newoptions=gaoptimset(oldoptions,“PopulationSize’,100)復(fù)現(xiàn)運(yùn)行結(jié)果[x,fval,reason,output,population,scores]=ga(@fitnessfcn,nvars)rand(‘state’,output.randstate)randn(‘state’,output.randnstate)以上一次的最后種群為初始種群運(yùn)行遺傳算法[x,fval,reason,output,finalpop]=ga(@fitnessfcn,nvars);options=gaoptimset(“InitialPop”,finalpop);Matlab遺傳算法工具箱…從M文件運(yùn)行g(shù)aoptions=gaoptimset('Generations',300);rand('state',71);%Thesetwocommandsareonlyincludedtorandn('state',59);%maketheresultsreproducible.record=[];forn=0:.05:1options=gaoptimset(options,'CrossoverFraction',n);[xfval]=ga(@rastriginsfcn,2,options);record=[record;fval];endplot(0:.05:1,record);xlabel('CrossoverFraction');ylabel('fval')Matlab遺傳算法工具箱…遺傳算法參數(shù)圖形參數(shù)Functionstate=plotfun(options,state,flag)flag:init,iter,done種群參數(shù)Functionpopulation=createfun(genlength,fitnessfcn,options)適應(yīng)度縮放參數(shù)Functionexpection=scalefun(scores,nparents)選擇參數(shù)Functionparents=selctfun(expectation,nparents,options)再生參數(shù)EliteCount2；交叉概率0.8；變異概率0.2交叉參數(shù)FunctionXoverkids=crossfun(parents,options,nvars,…,fitnessfcn,thispopulation)變異參數(shù)FunctionChildren=mutationfun(parents,options,nvars,…,fitnessfcn,state,thisscore,thispopulation)PopulationEliteCrossoverMutationMatlab遺傳算法工具箱…遺傳算法參數(shù)遷移參數(shù)涉及到多個(gè)子種群混合函數(shù)參數(shù)涉及到對(duì)遺傳算法的結(jié)果進(jìn)行再次直接搜索停止條件參數(shù)Generations,Timelimit,Fitnesslimit,Stallgenerations,Stalltime輸出函數(shù)參數(shù)Historytonewwindow,Custom顯示到命令窗口參數(shù)Levelofdisplay:off,iterative,diagnose,final向量參數(shù)off,onMatlab遺傳算法工具箱…TSP問(wèn)題的遺傳算法load('usborder.mat','x','y','xx','yy');plot(x,y,'Color','red');holdon;cities=40;locations=zeros(cities,2);n=1;while(n<=cities)

xp=rand*1.5;

yp=rand;ifinpolygon(xp,yp,xx,yy)locations(n,1)=xp;locations(n,2)=yp;n=n+1;endendplot(locations(:,1),locations(:,2),'bo');