遺傳算法的原理及MATLAB程序?qū)崿F(xiàn)

1、1 遺傳算法的原理1.1 遺傳算法的基本思想遺傳算法（genetic algorithms，GA）是一種基于自然選擇和基因遺傳學(xué)原理，借鑒了生物進(jìn)化優(yōu)勝劣汰的自然選擇機(jī)理和生物界繁衍進(jìn)化的基因重組、突變的遺傳機(jī)制的全局自適應(yīng)概率搜索算法。遺傳算法是從一組隨機(jī)產(chǎn)生的初始解（種群）開始，這個(gè)種群由經(jīng)過基因編碼的一定數(shù)量的個(gè)體組成，每個(gè)個(gè)體實(shí)際上是染色體帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的外部表現(xiàn)。因此，從一開始就需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射，即編碼工作。初始種群產(chǎn)生后，按照優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解。在每一代，根據(jù)

2、問題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣，后代種群比前代更加適應(yīng)環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼，可以作為問題近似最優(yōu)解。計(jì)算開始時(shí)，將實(shí)際問題的變量進(jìn)行編碼形成染色體，隨機(jī)產(chǎn)生一定數(shù)目的個(gè)體，即種群，并計(jì)算每個(gè)個(gè)體的適應(yīng)度值，然后通過終止條件判斷該初始解是否是最優(yōu)解，若是則停止計(jì)算輸出結(jié)果，若不是則通過遺傳算子操作產(chǎn)生新的一代種群，回到計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度值的部分，然后轉(zhuǎn)到終止條件判斷。這一過程循環(huán)執(zhí)行，直到滿足優(yōu)化準(zhǔn)則，最終產(chǎn)生問題的最優(yōu)解。圖1-1給出了遺傳算法的基本過程。1.2

3、遺傳算法的特點(diǎn)1.2.1 遺傳算法的優(yōu)點(diǎn)遺傳算法具有十分強(qiáng)的魯棒性，比起傳統(tǒng)優(yōu)化方法，遺傳算法有如下優(yōu)點(diǎn)：1. 遺傳算法以控制變量的編碼作為運(yùn)算對象。傳統(tǒng)的優(yōu)化算法往往直接利用控制變量的實(shí)際值的本身來進(jìn)行優(yōu)化運(yùn)算，但遺傳算法不是直接以控制變量的值，而是以控制變量的特定形式的編碼為運(yùn)算對象。這種對控制變量的編碼處理方式，可以模仿自然界中生物的遺傳和進(jìn)化等機(jī)理，也使得我們可以方便地處理各種變量和應(yīng)用遺傳操作算子。2. 遺傳算法具有內(nèi)在的本質(zhì)并行性。它的并行性表現(xiàn)在兩個(gè)方面，一是遺傳圖1-1 簡單遺傳算法的基本過程算法的外在并行性，最簡單的方式是讓多臺計(jì)算機(jī)各自進(jìn)行獨(dú)立種群的演化計(jì)算，最后選擇最優(yōu)個(gè)

4、體。可以說，遺傳算法適合在目前所有的并行機(jī)或分布式系統(tǒng)上進(jìn)行并行計(jì)算處理。二是遺傳算法的內(nèi)在并行性，由于遺傳算法采用種群的方式組織搜索，因而可同時(shí)搜索解空間內(nèi)的多個(gè)區(qū)域，并相互交流信息。這樣就使得搜索效率更高，也避免了使搜索過程陷于局部最優(yōu)解。3. 遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息。在簡單遺傳算法中，基本上不用搜索空間的知識和其它輔助信息，而僅用目標(biāo)函數(shù)即適應(yīng)度函數(shù)來評估個(gè)體解的優(yōu)劣，且適應(yīng)度函數(shù)不受連續(xù)可微的約束，對該函數(shù)和控制變量的約束極少。對適應(yīng)度函數(shù)唯一的要求就是對于輸入能夠計(jì)算出可比較的輸出。4. 遺傳算法是采用概率的變遷規(guī)則來指導(dǎo)它的搜索方向，其搜索過程朝著搜索空間的更優(yōu)化的解

5、區(qū)域移動，它的方向性使得它的效率遠(yuǎn)遠(yuǎn)高于一般的隨機(jī)算法。遺傳算法在解空間內(nèi)進(jìn)行充分的搜索，但不是盲目的窮舉或試探，因?yàn)檫x擇操作以適應(yīng)度為依據(jù)，因此它的搜索性能往往優(yōu)于其它優(yōu)化算法。5. 原理簡單，操作方便，占用內(nèi)存少，適用于計(jì)算機(jī)進(jìn)行大規(guī)模計(jì)算，尤其適合處理傳統(tǒng)搜索方法難以解決的大規(guī)模、非線性組合復(fù)雜優(yōu)化問題。6. 由于遺傳基因串碼的不連續(xù)性，所以遺傳算法處理非連續(xù)混合整數(shù)規(guī)劃時(shí)有其獨(dú)特的優(yōu)越性，而且使得遺傳算法對某些病態(tài)結(jié)構(gòu)問題具有很好的處理能力。7. 遺傳算法同其他算法有較好的兼容性。如可以用其他的算法求初始解；在每一代種群，可以用其他的方法求解下一代新種群。1.2.2 遺傳算法的缺點(diǎn)但是

6、，遺傳算法也存在一些缺點(diǎn)。1. 遺傳算法是一類隨機(jī)搜索型算法，而非確定性迭代過程描述，這種方式必然會較低的計(jì)算效率。2. 對簡單遺傳算法的數(shù)值試驗(yàn)表明，算法經(jīng)常出現(xiàn)過早收斂現(xiàn)象。3. 遺傳和變異的完全隨機(jī)性雖然保證了進(jìn)化的搜索功能，但是這種隨機(jī)變化也使得好的優(yōu)良個(gè)體的性態(tài)被過早破壞，降低了各代的平均適應(yīng)值。2. 遺傳算法的實(shí)現(xiàn)2.1 初始參數(shù)種群規(guī)模：種群數(shù)目影響遺傳算法的有效性。種群數(shù)目太小，不能提供足夠的采樣點(diǎn)；種群規(guī)模太大，會增加計(jì)算量，使收斂時(shí)間增長。一般種群數(shù)目在20到160之間比較合適。交叉概率：控制著交換操作的頻率，太大，會使高適應(yīng)值的結(jié)構(gòu)很快被破壞掉，太小會使搜索停滯不前，一般

7、取0.51.0。變異概率：是增大種群多樣性的第二個(gè)因素，太小，不會產(chǎn)生新的基因塊，太大，會使遺傳算法變成隨機(jī)搜索，一般取0.0010.1。進(jìn)化代數(shù)：表示遺傳算法運(yùn)行結(jié)束的一個(gè)條件。一般的取值范圍1001000。當(dāng)個(gè)體編碼較長時(shí)，進(jìn)化代數(shù)要取小一些，否則會影響算法的運(yùn)行效率。進(jìn)化代數(shù)的選取，還可以采用某種判定準(zhǔn)則，準(zhǔn)則成立時(shí)，即停止。2.2 染色體編碼利用遺傳算法進(jìn)行問題求解時(shí)，必須在目標(biāo)問題實(shí)際表示與染色體位串結(jié)構(gòu)之間建立一個(gè)聯(lián)系。對于給定的優(yōu)化問題，由種群個(gè)體的表現(xiàn)型集合所組成的空間稱為問題空間，由種群基因型個(gè)體所組成的空間稱為編碼空間。由問題空間向編碼空間的映射稱作編碼，而由編碼空間向問題

8、空間的映射成為解碼。按照遺傳算法的模式定理，De Jong進(jìn)一步提出了較為客觀明確的編碼評估準(zhǔn)則，稱之為編碼原理。具體可以概括為兩條規(guī)則：(1)有意義積木塊編碼規(guī)則：編碼應(yīng)當(dāng)易于生成與所求問題相關(guān)的且具有低階、短定義長度模式的編碼方案。(2)最小字符集編碼規(guī)則：編碼應(yīng)使用能使問題得到自然表示或描述的具有最小編碼字符集的編碼方案。常用的編碼方式有兩種：二進(jìn)制編碼和浮點(diǎn)數(shù)（實(shí)數(shù)）編碼。二進(jìn)制編碼方法是遺傳算法中最常用的一種編碼方法，它將問題空間的參數(shù)用字符集構(gòu)成染色體位串，符合最小字符集原則，便于用模式定理分析，但存在映射誤差。采用二進(jìn)制編碼，將決策變量編碼為二進(jìn)制，編碼串長取決于需要的精度。例如

9、，的值域?yàn)?，而需要的精度是小?shù)點(diǎn)后5位，這要求將得值域至少分為份。設(shè)所需要的字串長為，則有： (2.1)那么二進(jìn)制編碼的編碼精度為，將由二進(jìn)制轉(zhuǎn)為十進(jìn)制可按下式計(jì)算： (2.2)其中， 表示變量的子串的十進(jìn)制值。染色體編碼的總串長。若沒有規(guī)定計(jì)算精度，那么可采用定長二進(jìn)制編碼，即可以自己確定。二進(jìn)制編碼方式的編碼、解碼簡單易行，使得遺傳算法的交叉、變異等操作實(shí)現(xiàn)方便。但是，當(dāng)連續(xù)函數(shù)離散化時(shí)，它存在映射誤差。再者，當(dāng)優(yōu)化問題所求的精度越高，如果必須保證解的精度，則使得個(gè)體的二進(jìn)制編碼串很長，從而導(dǎo)致搜索空間急劇擴(kuò)大，計(jì)算量也會增加，計(jì)算時(shí)間也相應(yīng)的延長。浮點(diǎn)數(shù)（實(shí)數(shù)）編碼方法能夠解決二進(jìn)制編碼

10、的這些缺點(diǎn)。該方法中個(gè)體的每個(gè)基因都要用參數(shù)所給定區(qū)間范圍內(nèi)的某一浮點(diǎn)數(shù)來表示，而個(gè)體的編碼長度則等于其決策變量的總數(shù)。遺傳算法中交叉、變異等操作所產(chǎn)生的新個(gè)體的基因值也必須保證在參數(shù)指定區(qū)間范圍內(nèi)。當(dāng)個(gè)體的基因值是由多個(gè)基因組成時(shí)，交叉操作必須在兩個(gè)基因之間的分界字節(jié)處進(jìn)行，而不是在某一基因內(nèi)的中間字節(jié)分隔處進(jìn)行。2.3 適應(yīng)度函數(shù)適應(yīng)度函數(shù)是用來衡量個(gè)體優(yōu)劣，度量個(gè)體適應(yīng)度的函數(shù)。適應(yīng)度函數(shù)值越大的個(gè)體越好，反之，適應(yīng)值越小的個(gè)體越差。在遺傳算法中根據(jù)適應(yīng)值對個(gè)體進(jìn)行選擇，以保證適應(yīng)性能好的個(gè)體有更多的機(jī)會繁殖后代，使優(yōu)良特性得以遺傳。一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的。由于在遺傳

11、算法中根據(jù)適應(yīng)度排序的情況來計(jì)算選擇概率，這就要求適應(yīng)度函數(shù)計(jì)算出的函數(shù)值(適應(yīng)度)不能小于零。因此，在某些情況下，將目標(biāo)函數(shù)轉(zhuǎn)換成最大化問題形式而且函數(shù)值非負(fù)的適應(yīng)度函數(shù)是必要的，并且在任何情況下總是希望越大越好，但是許多實(shí)際問題中，目標(biāo)函數(shù)有正有負(fù)，所以經(jīng)常用到從目標(biāo)函數(shù)到適應(yīng)度函數(shù)的變換?？紤]如下一般的數(shù)學(xué)規(guī)劃問題：變換方法一：(1)對于最小化問題，建立適應(yīng)度函數(shù)和目標(biāo)函數(shù)的映射關(guān)系： (2.3)式中，既可以是特定的輸入值，也可以選取到目前為止所得到的目標(biāo)函數(shù)的最大值。(2)對于最大化問題，一般采用下述方法： (2.4)式中，既可以是特定的輸入值，也可以選取到目前為止所得到的目標(biāo)函數(shù)的最

12、小值。變換方法二：(1)對于最小化問題，建立適應(yīng)度函數(shù)和目標(biāo)函數(shù)的映射關(guān)系： (2.5)(2)對于最大化問題，一般采用下述方法： (2.6)式中，為目標(biāo)函數(shù)界限的保守估計(jì)值。2.4 約束條件的處理 在遺傳算法中必須對約束條件進(jìn)行處理，但目前尚無處理各種約束條件的一般方法，根據(jù)具體問題可選擇下列三種方法，其罰函數(shù)法、搜索空間限定法和可行解變換法。2.4.1 罰函數(shù)法罰函數(shù)的基本思想是對在解空間中無對應(yīng)可行解的個(gè)體計(jì)劃其適應(yīng)度時(shí)，處以一個(gè)罰函數(shù)，從而降低該個(gè)體的適應(yīng)度，使該個(gè)體被選遺傳到下一代群體中的概率減小?？梢杂孟率綄€(gè)體的適應(yīng)度進(jìn)行調(diào)整： （2.7）其中，為原適應(yīng)度函數(shù)，為調(diào)整后的新的適應(yīng)度

13、函數(shù)，為罰函數(shù)，為約束條件組成的集合。如何確定合理的罰函數(shù)是這種處理方法難點(diǎn)之所在，在考慮罰函數(shù)時(shí)，既要度量解對約束條件不滿足的程度，由要考慮計(jì)算效率。2.4.2 搜索空間限定法搜索空間限定法的基本思想是對遺傳算法的搜索空間的大小加以限制，使得搜索空間中表示一個(gè)個(gè)體的點(diǎn)與解空間中的表示一個(gè)可行解的點(diǎn)有一一對應(yīng)的關(guān)系。對一些比較簡單的約束條件通過適當(dāng)編碼使搜索空間與解空間一一對應(yīng)，限定搜索空間能夠提高遺傳算法的效率。在使用搜索空間限定法時(shí)必須保證交叉、變異之后的解個(gè)體在解空間中有對應(yīng)解。2.4.3 可行解變換法 可行解變換法的基本思想：在由個(gè)體基因型到個(gè)體表現(xiàn)型的變換中，增加使其滿足約束條件的處

14、理過程，其尋找個(gè)體基因型與個(gè)體表現(xiàn)型的多對一變換關(guān)系，擴(kuò)大了搜索空間，使進(jìn)化過程中所產(chǎn)生的個(gè)體總能通過這個(gè)變換而轉(zhuǎn)化成解空間中滿足約束條件的一個(gè)可行解。可行解變換法對個(gè)體的編碼方式、交叉運(yùn)算、變異運(yùn)算等無特殊要求，但運(yùn)行效果下降。2.5 遺傳算子遺傳算法中包含了3個(gè)模擬生物基因遺傳操作的遺傳算子：選擇（復(fù)制）、交叉（重組）和變異（突變）。遺傳算法利用遺傳算子產(chǎn)生新一代群體來實(shí)現(xiàn)群體進(jìn)化，算子的設(shè)計(jì)是遺傳策略的主要組成部分，也是調(diào)整和控制進(jìn)化過程的基本工具。2.5.1 選擇操作 遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算。遺傳算法使用選

15、擇（復(fù)制）算子來對群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度較高的個(gè)體被遺傳到下一代群體中的概率較大；適應(yīng)度較低的個(gè)體被遺傳到下一代群體中的概率較小。選擇操作建立在對個(gè)體適應(yīng)度進(jìn)行評價(jià)的基礎(chǔ)之上。選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計(jì)算效率。常用的選擇方法有轉(zhuǎn)輪法、排序選擇法、兩兩競爭法。1) 輪盤賭法。簡單的選擇方法為輪盤賭法：通常以第個(gè)個(gè)體入選種群的概率以及群體規(guī)模的上限來確定其生存與淘汰，這種方法稱為輪盤賭法。輪盤賭法是一種正比選擇策略，能夠根據(jù)與適應(yīng)函數(shù)值成正比的概率選出新的種群。輪盤賭法由以下五步構(gòu)成：1. 計(jì)算各染色體適應(yīng)值；2. 計(jì)算種群中所有染色體的適應(yīng)值的和； （

16、2.6）3. 計(jì)算各染色體的選擇概率； (2.7)4. 計(jì)算各染色體的累計(jì)概率； (2.8)5. 在區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)，若，則選擇第一個(gè)染色體；否則，選擇第個(gè)染色體，使得成立。2) 排序選擇法。排序選擇法的主要思想是：對群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來分配各個(gè)個(gè)體被選中的概率。排序選擇方法的具體操作過程是：1. 對群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行降序排序。2. 根據(jù)具體求解問題，設(shè)計(jì)一個(gè)概率分配表，將各個(gè)概率值按上述排列次序分配給各個(gè)個(gè)體。3. 以各個(gè)個(gè)體所分配到的概率值作為其能夠被遺傳到下一代的概率，基于這些概率值用輪盤賭法來產(chǎn)生下一代群體。3) 兩兩競

17、爭法。錦標(biāo)賽選擇法的基本做法是：在選擇時(shí)先隨機(jī)的在種群中選擇個(gè)個(gè)體進(jìn)行錦標(biāo)賽式的比較，從中選出適應(yīng)值最好的個(gè)體進(jìn)入下一代，復(fù)用這種方法進(jìn)行直到下一代個(gè)體數(shù)為種群規(guī)模時(shí)為止。這種方法也使得適應(yīng)值好的個(gè)體在下一代具有較大的“生存”機(jī)會，同時(shí)它只能使用適應(yīng)值的相對值作為選擇的標(biāo)準(zhǔn)，而與適應(yīng)值的數(shù)值大小不成直接比例，所以，它能較好的避免超級個(gè)體的影響，一定程度的避免過早收斂現(xiàn)象和停滯現(xiàn)象。2.5.2 交叉操作在遺傳算法中，交叉操作是起核心作用的遺傳操作，它是生成新個(gè)體的主要方式。交叉操作的基本思想是通過對兩個(gè)個(gè)體之間進(jìn)行某部分基因的互換來實(shí)現(xiàn)產(chǎn)生新個(gè)體的目的。常用交叉算子有：單點(diǎn)交叉算子、兩點(diǎn)交叉算子

18、和多點(diǎn)交叉算子、均勻交叉算子和算術(shù)交叉算子等等。1) 單點(diǎn)交叉算子交叉過程分兩個(gè)步驟：首先對配對庫中的個(gè)體進(jìn)行隨機(jī)配對；其次，在配對個(gè)體中隨機(jī)設(shè)定交叉位置，配對個(gè)體彼此交換部分信息。圖2-1 單點(diǎn)交叉示意2) 兩點(diǎn)交叉算子具體操作是隨機(jī)設(shè)定兩個(gè)交叉點(diǎn)，互換兩個(gè)父代在這兩點(diǎn)間的基因串，分別生成兩個(gè)新個(gè)體。3) 多點(diǎn)交叉算子多點(diǎn)交叉的思想源于控制個(gè)體特定行為的染色體表示信息的部分無須包含于鄰近的子串中，多點(diǎn)交叉的破壞性可以促進(jìn)解空間的搜索，而不是促進(jìn)過早的收斂。4) 均勻交叉算子均勻交叉式指通過設(shè)定屏蔽字來決定新個(gè)體的基因繼承兩個(gè)個(gè)體中那個(gè)個(gè)體的對應(yīng)基因，當(dāng)屏蔽字中的位為0時(shí)，新個(gè)體繼承舊個(gè)體中對

19、應(yīng)的基因，當(dāng)屏蔽字位為1時(shí)，新個(gè)體繼承舊個(gè)體中對應(yīng)的基因，由此可生成一個(gè)完整的新個(gè)體，同理可生成新個(gè)體。圖2-2 均與交叉示意圖2.5.3 變異操作變異操作是指將個(gè)體染色體編碼串中的某些基因座的基因值用該基因座的其他等位基因來替代，從而形成一個(gè)新的個(gè)體。變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它和選擇、交叉算子結(jié)合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機(jī)搜索能力，提高遺傳算法的搜索效率；同時(shí)使遺傳算法保持種群的多樣性，以防止出現(xiàn)早熟收斂。在變異操作中，為了保證個(gè)體變異后不會與其父體產(chǎn)生太大的差異，保證種群發(fā)展的穩(wěn)定性，變異率不能取太大，如果變異率大于0.5，遺傳算法就變?yōu)殡S機(jī)搜索，遺傳

20、算法的一些重要的數(shù)學(xué)特性和搜索能力也就不存在了。變異算子的設(shè)計(jì)包括確定變異點(diǎn)的位置和進(jìn)行基因值替換。變異操作的方法有基本位變異、均勻變異、邊界變異、非均勻變異等。1) 基本位變異基本位變異操作是指對個(gè)體編碼串中以變異概率隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算，所以其發(fā)揮的作用比較慢，作用的效果也不明顯?；疚蛔儺愃阕拥木唧w執(zhí)行過程是：1. 對個(gè)體的每一個(gè)基因座，依變異概率指定其為變異點(diǎn)。2. 對每一個(gè)指定的變異點(diǎn)，對其基因值做取反運(yùn)算或用其他等位基因值來代替，從而產(chǎn)生出一個(gè)新個(gè)體。2) 均勻變異均勻變異操作是指分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來替換個(gè)體編碼串中各個(gè)基因座上

21、的原有基因值。均勻變異的具體操作過程是：1. 依次指定個(gè)體編碼串中的每個(gè)基因座為變異點(diǎn)。2. 對每一個(gè)變異點(diǎn)，以變異概率從對應(yīng)基因的取值范圍內(nèi)取一隨機(jī)數(shù)來替代原有基因值。假設(shè)有一個(gè)個(gè)體為，若為變異點(diǎn)，其取值范圍為，在該點(diǎn)對個(gè)體進(jìn)行均勻變異操作后，可得到一個(gè)新的個(gè)體：，其中變異點(diǎn)的新基因值是 (2.9)式中，為范圍內(nèi)符合均勻概率分布的一個(gè)隨機(jī)數(shù)。均勻變異操作特別適合應(yīng)用于遺傳算法的初期運(yùn)行階段，它使得搜索點(diǎn)可以在整個(gè)搜索空間內(nèi)自由地移動，從而可以增加群體的多樣性。2.5.4 倒位操作所謂倒位操作是指顛倒個(gè)體編碼串中隨機(jī)指定的二個(gè)基因座之間的基因排列順序，從而形成一個(gè)新的染色體。倒位操作的具體過程

22、是：1. 在個(gè)體編碼串中隨機(jī)指定二個(gè)基因座作為倒位點(diǎn)；2. 以倒位概率顛倒這二個(gè)倒位點(diǎn)之間的基因排列順序。2.6 搜索終止條件遺傳算法的終止條件有以下兩個(gè)，滿足任何一個(gè)條件搜索就結(jié)束。1)遺傳操作中連續(xù)多次前后兩代群體中最優(yōu)個(gè)體的適應(yīng)度相差在某個(gè)任意小的正數(shù)所確定的范圍內(nèi)，即滿足： (2.10)式中，為新產(chǎn)生的群體中最優(yōu)個(gè)體的適應(yīng)度；為前代群體中最優(yōu)個(gè)體的適應(yīng)度。2) 達(dá)到遺傳操作的最大進(jìn)化代數(shù)。3 具體數(shù)學(xué)規(guī)劃問題的遺傳算法實(shí)現(xiàn)利用遺傳算法求解下列數(shù)學(xué)規(guī)劃問題： (3.1)3.1 初始化針對上述問題利用MATLAB編寫遺傳算法程序求解，程序的主函數(shù)是GA.m。首先，確定程序初始化中所需要的參

23、數(shù)和對應(yīng)的值。其中求解精度是指決策變量的求解精度，由于題目中沒有給出，所以這是我自己設(shè)定的參數(shù)。程序中涉及到得參數(shù)名稱、符號和相應(yīng)的值如下表所示。表3-1 遺傳算法初始化參數(shù)參數(shù)名稱符號值最大進(jìn)化代數(shù)100種群規(guī)模n100交叉概率0.8變異概率0.1求解精度變量上限值10變量下限值03.2 染色體編碼本程序采用二進(jìn)制編碼，將決策變量編碼為二進(jìn)制，其串長取決于問題要求的求解精度，但本題并沒有給出精度要求，只是限定了為整數(shù)，不妨假設(shè)求解精度為，兩個(gè)變量均采用二進(jìn)制編碼，為整數(shù)這個(gè)限制條件在可在計(jì)算出小數(shù)值后作四舍五入取整處理，因此可按照假設(shè)的求解精度將決策變量的值域分成份，則有： (3.2)由于所

24、有變量的求解精度一樣，那么，決策變量的串長、，于是染色體的總長，求解二進(jìn)制編碼串長的程序時(shí)len.m。那么，二進(jìn)制編碼精度為 (3.3)根據(jù)二進(jìn)制編碼的串長以及種群規(guī)?？缮沙跏挤N群，為計(jì)算種群中的各個(gè)個(gè)體的適應(yīng)值，應(yīng)先將基因型轉(zhuǎn)換成表現(xiàn)型，其程序?yàn)閏oding.m。首先，將二進(jìn)制值轉(zhuǎn)換為十進(jìn)制值，其公式為 (3.4)那么，對應(yīng)的變量值為 (3.5)3.3 計(jì)算適應(yīng)值首先確定適應(yīng)度函數(shù)。根據(jù)目標(biāo)函數(shù)和約束條件可選擇適應(yīng)度函數(shù)的變換方式。由于目標(biāo)函數(shù)，為了避免出現(xiàn)適應(yīng)值大于1的情況，于是根據(jù)目標(biāo)函數(shù)的特點(diǎn)在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)，在分母上加上2，分子上剩以4，如式(3.1)所示；又根據(jù)優(yōu)化問題的約束條

25、件，利用約束條件處理方法中的罰函數(shù)法設(shè)計(jì)了相應(yīng)的罰函數(shù)，那么適應(yīng)度函數(shù)為 (3.6)其中，。按照上述方法計(jì)算種群中各個(gè)個(gè)體的適應(yīng)值，如果適應(yīng)值趨近于1，那么對應(yīng)的個(gè)體即為最佳個(gè)體，計(jì)算適應(yīng)值的程序是fitness.m。3.4 遺傳算子3.4.1 選擇操作本程序選擇輪盤賭法來實(shí)現(xiàn)選擇操作。根據(jù)之前計(jì)算的各個(gè)個(gè)體的適應(yīng)值，利用式(2.6)計(jì)算種群中所有個(gè)體的適應(yīng)值的和；然后按照如式(2.7)、(2.8)計(jì)算每個(gè)個(gè)體的選擇概率p和累計(jì)概率q。旋轉(zhuǎn)輪盤100次（種群規(guī)模），每次生成一個(gè)0到1的隨機(jī)數(shù)r，用這個(gè)隨機(jī)數(shù)與種群中的個(gè)體的累積概率q作比較，如果這個(gè)隨機(jī)數(shù)落在了這個(gè)概率區(qū)間，那么就保留該個(gè)體，這

26、就完全模擬了輪盤賭的思想，若個(gè)體的選擇概率大，那么它被選到遺傳到下一代的概率也就大一些。選擇操作的程序是selec.m。3.4.2 交叉操作 對經(jīng)過選擇操作產(chǎn)生的群體作交叉操作。本程序采用均勻交叉的方式，首先打亂種群中所有個(gè)體的原有排列順序，這樣體現(xiàn)了隨機(jī)抽取的概念，然后把種群分成兩部分new_genA和new_genB；分別從這兩個(gè)部分選擇一個(gè)個(gè)體配成對進(jìn)行均勻交叉，其程序?yàn)閏ross.m。3.4.3 變異操作 對經(jīng)過交叉操作產(chǎn)生的群體作變異操作。本程序采用基本位變異方法實(shí)現(xiàn)變異操作，依據(jù)變異概率對新種群中的個(gè)體實(shí)施基本位變異，具體程序?yàn)閙ut.m。在最初編寫的程序中還包含倒位操作，具體程序是inverse.m，原理類似于基本位變異，只是具體操作上有差異。在調(diào)試時(shí)，我比較了有倒位操作和沒有倒位操作作用于程序?qū)τ?jì)算結(jié)果的影響，在有倒位操作時(shí)并沒有改善算法在搜索到最優(yōu)解方面的性能，于是我在最終的程序中取掉了這一操作。3.5 搜索終止判斷本程序采用了達(dá)到最大進(jìn)化代數(shù)時(shí)停止搜索的方法，由于本問題比較簡單，所以采用此法是可行的。但是，對于復(fù)雜的問題，也許要求更加有效的判斷手段，所以這是需要改進(jìn)的地方。3.6 運(yùn)行調(diào)試調(diào)試階段解決了兩個(gè)問題：第一，最佳個(gè)體的適應(yīng)值很快就