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

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

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

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

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

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

6、可以用其他的算法求初始解； 在 每一代種群，可以用其他的方法求解下一代新種群。1.2.2 遺傳算法的缺點但是，遺傳算法也存在一些缺點。1. 遺傳算法是一類隨機搜索型算法，而非確定性迭代過程描述，這種方式 必然會較低的計算效率。2. 對簡單遺傳算法的數(shù)值試驗表明，算法經(jīng)常出現(xiàn)過早收斂現(xiàn)象。3. 遺傳和變異的完全隨機性雖然保證了進(jìn)化的搜索功能，但是這種隨機變化也使得好的優(yōu)良個體的性態(tài)被過早破壞，降低了各代的平均適應(yīng)值。2. 遺傳算法的實現(xiàn)2.1 初始參數(shù)種群規(guī)模 n ：種群數(shù)目影響遺傳算法的有效性。種群數(shù)目太小，不能提供足夠的采樣點；種群規(guī)模太大，會增加計算量，使收斂時間增長。一般種群數(shù)目在20

7、到 160之間比較合適。交叉概率Pc： Pc控制著交換操作的頻率，Pc太大，會使高適應(yīng)值的結(jié)構(gòu)很快被破壞掉，Pc太小會使搜索停滯不前，一般 Pc取0.51.0。變異概率Pm： Pm是增大種群多樣性的第二個因素，Pm太小，不會產(chǎn)生新的基因塊，Pm太大，會使遺傳算法變成隨機搜索，一般 PmM0.0010.1o進(jìn)化彳t數(shù)t ：表示遺傳算法運行結(jié)束的一個條件。一般的取值范圍100100a 當(dāng)個體編碼較長時，進(jìn)化代數(shù)要取小一些，否則會影響算法的運行效率。 進(jìn)化代 數(shù)的選取，還可以采用某種判定準(zhǔn)則，準(zhǔn)則成立時，即停止。2.2 染色體編碼利用遺傳算法進(jìn)行問題求解時，必須在目標(biāo)問題實際表示與染色體位用結(jié)構(gòu) 之

8、間建立一個聯(lián)系。對于給定的優(yōu)化問題，由種群個體的表現(xiàn)型集合所組成的空 間稱為問題空間，由種群基因型個體所組成的空間稱為編碼空間。由問題空間向編碼空I可的映射稱作編碼，而由編碼空間向問題空間的映射成為解碼。按照遺傳算法的模式定理，De Jong進(jìn)一步提出了較為客觀明確的編碼評估 準(zhǔn)則，稱之為編碼原理。具體可以概括為兩條規(guī)則：(1)有意義積木塊編碼規(guī)則：編碼應(yīng)當(dāng)易于生成與所求問題相關(guān)的且具有低 階、短定義長度模式的編碼方案。(2)最小字符集編碼規(guī)則：編碼應(yīng)使用能使問題得到自然表示或描述的具有 最小編碼字符集的編碼方案。常用的編碼方式有兩種：二進(jìn)制編碼和浮點數(shù)(實數(shù))編碼。二進(jìn)制編碼方法是遺傳算法中

9、最常用的一種編碼方法，它將問題空間的參數(shù) 用字符集10構(gòu)成染色體位用，符合最小字符集原則，便于用模式定理分析， 但存在映射誤差。采用二進(jìn)制編碼，將決策變量編碼為二進(jìn)制，編碼用長 m取決于需要的精 度。例如，x的值域為瓦由,而需要的精度是小數(shù)點后5位，這要求將x得值 域至少分為(b -ai不106份。設(shè)Xi所需要的字用長為m,則有：2f 二 bi -ai1 0 ：二 m2(2.1)那么二進(jìn)制編碼的編碼精度為b二2亙，將X由二進(jìn)制轉(zhuǎn)為十進(jìn)制可按下 2mi -1式計算：xi -ai decimal(substringi) 、(2.2)其中，decimal(substring)表示變量x的子用subs

10、tringi的十進(jìn)制值。染色體編碼N的總串長m = E mi o若沒有規(guī)定計算精度，那么可采用定長二進(jìn)制編碼，即 m可以自己確定。二進(jìn)制編碼方式的編碼、解碼簡單易行，使得遺傳算法的交叉、變異等操作 實現(xiàn)方便。但是，當(dāng)連續(xù)函數(shù)離散化時，它存在映射誤差。冉者，當(dāng)優(yōu)化問題所 求的精度越高，如果必須保證解的精度，則使得個體的二進(jìn)制編碼用很長，從而 導(dǎo)致搜索空間急劇擴大，計算量也會增加，計算時間也相應(yīng)的延長。浮點數(shù)(實數(shù))編碼方法能夠解決二進(jìn)制編碼的這些缺點。該方法中個體的 每個基因都要用參數(shù)所給定區(qū)間范圍內(nèi)的某一浮點數(shù)來表示，而個體的編碼長度則等于其決策變量的總數(shù)。遺傳算法中交叉、變異等操作所產(chǎn)生的新

11、個體的基因 值也必須保證在參數(shù)指定區(qū)間范圍內(nèi)。 當(dāng)個體的基因值是由多個基因組成時， 交 叉操作必須在兩個基因之間的分界字節(jié)處進(jìn)行， 而不是在某一基因內(nèi)的中間字節(jié) 分隔處進(jìn)行。2.3 適應(yīng)度函數(shù)適應(yīng)度函數(shù)是用來衡量個體優(yōu)劣，度量個體適應(yīng)度的函數(shù)。適應(yīng)度函數(shù)值越 大的個體越好，反之，適應(yīng)值越小的個體越差。在遺傳算法中根據(jù)適應(yīng)值對個體 進(jìn)行選擇，以保證適應(yīng)性能好的個體有更多的機會繁殖后代， 使優(yōu)良特性得以遺 傳。一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的。 由于在遺傳算法中根據(jù)適 應(yīng)度排序的情況來計算選擇概率，這就要求適應(yīng)度函數(shù)計算出的函數(shù)值(適應(yīng)度)不能小于零。因此，在某些情況下，將目標(biāo)函數(shù)轉(zhuǎn)換成

12、最大化問題形式而且函數(shù) 值非負(fù)的適應(yīng)度函數(shù)是必要的，并且在任何情況下總是希望越大越好， 但是許多 實際問題中，目標(biāo)函數(shù)有正有負(fù)，所以經(jīng)常用到從目標(biāo)函數(shù)到適應(yīng)度函數(shù)的變換。考慮如下一般的數(shù)學(xué)規(guī)劃問題：min f (x)s.t. g(x)=0h min-h( X ) Mh max變換方法(1)對于最小化問題，建立適應(yīng)度函數(shù)F (x)和目標(biāo)函數(shù)f (x)的映射關(guān)系:C max F( x)=-f( x)0f( x) Cmax f( x) - Cmax(2.3)式中，Cmax既可以是特定的輸入值，也可以選取到目前為止所得到的目標(biāo)函數(shù)f (x)的最大值。(2)對于最大化問題，一般采用下述方法:(2.4)F

13、( x)= f( -f( x) Cmin0f(x) Cmin式中，Cmin既可以是特定的輸入值，也可以選取到目前為止所得到的目標(biāo)函數(shù)f( X )的最小值。變換方法二：(1)對于最小化問題，建立適應(yīng)度函數(shù) f (X)和目標(biāo)函數(shù)f(x)的映射關(guān)系:F( x)=c_0,c f(x) ,0(2.5)(2)對于最大化問題，一般采用下述方法:(2.6)1.F(x) = c_0,c-f(x)_01 c - f (x)式中，c為目標(biāo)函數(shù)界限的保守估計值。2.4 約束條件的處理在遺傳算法中必須對約束條件進(jìn)行處理，但目前尚無處理各種約束條件的一 股方法，根據(jù)具體問題可選擇下列三種方法，其罰函數(shù)法、搜索空間限定法和

14、可 行解變換法。2.4.1 罰函數(shù)法罰函數(shù)的基本思想是對在解空間中無對應(yīng)可行解的個體計劃其適應(yīng)度時，處以一個罰函數(shù)，從而降低該個體的適應(yīng)度，使該個體被選遺傳到下一代群體中的 概率減小?？梢杂孟率綄€體的適應(yīng)度進(jìn)行調(diào)整：(2.7)F( x)x UF (x)=F(x) -P( x) x U其中，F(xiàn)(x)為原適應(yīng)度函數(shù)，F(xiàn)(x)為調(diào)整后的新的適應(yīng)度函數(shù)，P(x)為罰函數(shù)，U為約束條件組成的集合。如何確定合理的罰函數(shù)是這種處理方法難點之所在，在考慮罰函數(shù)時，既要度量解對約束條件不滿足的程度，由要考慮計算效率。2.4.2 搜索空間限定法搜索空間限定法的基本思想是對遺傳算法的搜索空間的大小加以限制，使得搜

15、索空間中表示一個個體的點與解空間中的表示一個可行解的點有一一對應(yīng)的關(guān)系。對一些比較簡單的約束條件通過適當(dāng)編碼使搜索空間與解空間一一對應(yīng)，限定搜索空間能夠提高遺傳算法的效率。在使用搜索空間限定法時必須保證交叉、變異之后的解個體在解空間中有對應(yīng)解。2.4.3 可行解變換法可行解變換法的基本思想： 在由個體基因型到個體表現(xiàn)型的變換中， 增加使其滿足約束條件的處理過程，其尋找個體基因型與個體表現(xiàn)型的多對一變換關(guān)系， 擴大了搜索空間， 使進(jìn)化過程中所產(chǎn)生的個體總能通過這個變換而轉(zhuǎn)化成解空間中滿足約束條件的一個可行解。 可行解變換法對個體的編碼方式、 交叉運算、變異運算等無特殊要求，但運行效果下降。2.5

16、 遺傳算子遺傳算法中包含了 3 個模擬生物基因遺傳操作的遺傳算子：選擇（復(fù)制） 、交叉（重組）和變異（突變） 。遺傳算法利用遺傳算子產(chǎn)生新一代群體來實現(xiàn)群體進(jìn)化， 算子的設(shè)計是遺傳策略的主要組成部分， 也是調(diào)整和控制進(jìn)化過程的基本工具。2.5.1 選擇操作遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個體遺傳到下一代群體中的一種遺傳運算。 遺傳算法使用選擇 （復(fù)制） 算子來對群體中的個體進(jìn)行優(yōu)勝劣汰操作： 適應(yīng)度較高的個體被遺傳到下一代群體中的概率較大； 適應(yīng)度較低的個體被遺傳到下一代群體中的概率較小。 選擇操作建立在對個體適應(yīng)度進(jìn)行評價的基礎(chǔ)之上。選擇操作的主要目的是為了

17、避免基因缺失、提高全局收斂性和計算效率。常用的選擇方法有轉(zhuǎn)輪法、排序選擇法、兩兩競爭法。1） 輪盤賭法。簡單的選擇方法為輪盤賭法：通常以第 i 個個體入選種群的概率以及群體規(guī)模的上限來確定其生存與淘汰， 這種方法稱為輪盤賭法。 輪盤賭法是一種正比選擇策略， 能夠根據(jù)與適應(yīng)函數(shù)值成正比的概率選出新的種群。 輪盤賭法由以下五步構(gòu)成：1 . 計算各染色體vk 適應(yīng)值F（vk） ；2 . 計算種群中所有染色體的適應(yīng)值的和；nFall = F(Vk)(2.6)kJ3 .計算各染色體Vk的選擇概率Pk;Pk 二答，k=12Un(2.7)Fall4 .計算各染色體Vk的累計概率a ；kqk 八 Pj,k =

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

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

20、和多點交叉 算子、均勻交叉算子和算術(shù)交叉算子等等。1)單點交叉算子交叉過程分兩個步驟：首先對配對庫中的個體進(jìn)行隨機配對；其次，在配對個體中隨機設(shè)定交叉位置，配對個體彼此交換部分信息。個體力1001 111 1001000 新個體月個體8 0011 000 0011111新個體交叉點 I圖2-1單點交叉示意2）兩點交叉算子具體操作是隨機設(shè)定兩個交叉點，互換兩個父代在這兩點間的基因申， 分別 生成兩個新個體。3）多點交叉算子多點交叉的思想源于控制個體特定行為的染色體表示信息的部分無須包含 于鄰近的子用中，多點交叉的破壞性可以促進(jìn)解空間的搜索，而不是促進(jìn)過早的收斂。4）均勻交叉算子均勻交叉式指通過設(shè)

21、定屏蔽字來決定新個體的基因繼承兩個個體中那個個體的對應(yīng)基因，當(dāng)屏蔽字中的位為 0時，新個體A繼承舊個體A中對應(yīng)的基因， 當(dāng)屏蔽字位為1時，新個體A，繼承舊個體B中對應(yīng)的基因，由此可生成一個完整 的新個體A、同理可生成新個體B舊個體4001111舊個體111100屏蔽字 010L01新個體noinio新個體8,101101圖2-2均與交叉示意圖2.5.3 變異操作變異操作是指將個體染色體編碼用中的某些基因座的基因值用該基因座的 其他等位基因來替代，從而形成一個新的個體。變異運算是產(chǎn)生新個體的輔助方 法，它和選擇、交叉算子結(jié)合在一起，保證了遺傳算法的有效性，使遺傳算法具 有局部的隨機搜索能力，提高

22、遺傳算法的搜索效率；同時使遺傳算法保持種群的 多樣性，以防止出現(xiàn)早熟收斂。在變異操作中，為了保證個體變異后不會與其父體產(chǎn)生太大的差異，保證種群發(fā)展的穩(wěn)定性，變異率不能取太大，如果變異率大 于0.5,遺傳算法就變?yōu)殡S機搜索，遺傳算法的一些重要的數(shù)學(xué)特性和搜索能力 也就不存在了。變異算子的設(shè)計包括確定變異點的位置和進(jìn)行基因值替換。變異操作的方法有基本位變異、均勻變異、邊界變異、非均勻變異等。1)基本位變異基本位變異操作是指對個體編碼用中以變異概率Pm隨機指定的某一位或某幾位基因作變異運算，所以其發(fā)揮的作用比較慢，作用的效果也不明顯。基本位 變異算子的具體執(zhí)行過程是：1 .對個體的每一個基因座，依變

23、異概率 Pm指定其為變異點。2 .對每一個指定的變異點，對其基因值做取反運算或用其他等位基因值來 代替，從而產(chǎn)生出一個新個體。2)均勻變異均勻變異操作是指分別用符合某一范圍內(nèi)均勻分布的隨機數(shù)， 以某一較小的 概率來替換個體編碼用中各個基因座上的原有基因值。 均勻變異的具體操作過程 是：1 .依次指定個體編碼用中的每個基因座為變異點。2 .對每一個變異點，以變異概率Pm從對應(yīng)基因的取值范圍內(nèi)取一隨機數(shù)來 替代原有基因值。假設(shè)有一個個體為 v k =v2川VkllNm,若Vk為變異點，其取值范圍為 Vk,min,Vk,max,在該點對個體V k進(jìn)行均勻變異操作后，可得到一個新的個體： . , .

24、Vk =VlV2 IllVklllVm,其中變異點的新基因值是 vk - vk, m i n r (vk , m avk ) , m i n(2.9)式中，r為0,1范圍內(nèi)符合均勻概率分布的一個隨機數(shù)。均勻變異操作特別適合 應(yīng)用于遺傳算法的初期運行階段，它使得搜索點可以在整個搜索空間內(nèi)自由地移 動，從而可以增加群體的多樣性。2.5.4倒位操作所謂倒位操作是指顛倒個體編碼用中隨機指定的二個基因座之間的基因排 列順序，從而形成一個新的染色體。倒位操作的具體過程是：1 .在個體編碼用中隨機指定二個基因座作為倒位點；2 .以倒位概率顛倒這二個倒位點之間的基因排列順序。2.6搜索終止條件遺傳算法的終止條

25、件有以下兩個，滿足任何一個條件搜索就結(jié)束1）遺傳操作中連續(xù)多次前后兩代群體中最優(yōu)個體的適應(yīng)度相差在某個任意小 的正數(shù)6所確定的范圍內(nèi)，即滿足：r：d ；(2.10)式中，F(xiàn)new為新產(chǎn)生的群體中最優(yōu)個體的適應(yīng)度；Fold為前代群體中最優(yōu)個體的適應(yīng)度。2）達(dá)到遺傳操作的最大進(jìn)化代數(shù)t。3具體數(shù)學(xué)規(guī)劃問題的遺傳算法實現(xiàn)利用遺傳算法求解下列數(shù)學(xué)規(guī)劃問題:r22min f (x1, x2) = x1 - 3 x2 -2尸 ,、22 廣(3.1)g1(x1,x2) =x +x2 5s.tKi(Xi,X2)=Xi +2x2 =40Xi,X2 10,Xi w N3.1初始化針對上述問題利用 MATLAB編寫

26、遺傳算法程序求解，程序的主函數(shù)是GA.m o首先，確定程序初始化中所需要的參數(shù)和對應(yīng)的值。 其中求解精度是指決策 變量的求解精度，由于題目中沒有給出，所以這是我自己設(shè)定的參數(shù)。程序中涉 及到得參數(shù)名稱、符號和相應(yīng)的值如下表所示。表3-1遺傳算法初始化參數(shù)參數(shù)名稱符號值最大進(jìn)化代數(shù)tmax100種群規(guī)模n100交叉概率Pc0.8變異概率Pm0.1求解精度dec10變量上限值xmax10變量下限值xmin03.2染色體編碼本程序采用二進(jìn)制編碼，將決策變量編碼為二進(jìn)制，其用長取決于問題要求 的求解精度，但本題并沒有給出精度要求，只是限定了 xi為整數(shù)，不妨假設(shè)求解 精度為10工，兩個變量均采用二進(jìn)制

27、編碼，Xi為整數(shù)這個限制條件在可在計算出 小數(shù)值后作四舍五入取整處理，因此可按照假設(shè)的求解精度將決策變量的值域分 成105份，則有：mi 15mix=xmin +5xx 2(xmaxxmin)父 10 2(3.2)由于所有變量的求解精度一樣，那么，決策變量的用長 mi = 20、m2 =20, 于是染色體的總長m =m1 +m2 =40,求解二進(jìn)制編碼用長的程序時len.m。那么, 二進(jìn)制編碼精度為1 0- 06c. = 00= 9.5368 10-(3.3)mi(hWI回)2 - b2i=xi 1(3.4)(3.5)根據(jù)二進(jìn)制編碼的用長以及種群規(guī)模可生成初始種群， 為計算種群中的各個 個體的

28、適應(yīng)值，應(yīng)先將基因型轉(zhuǎn)換成表現(xiàn)型，其程序為 coding.m。首先，將二進(jìn) 制值轉(zhuǎn)換為十進(jìn)制值，其公式為那么，對應(yīng)的變量值為x = xni n .、 x3.3 計算適應(yīng)值首先確定適應(yīng)度函數(shù)。根據(jù)目標(biāo)函數(shù)和約束條件可選擇適應(yīng)度函數(shù)的變換方 式。由于目標(biāo)函數(shù)f (x )之0,為了避免出現(xiàn)適應(yīng)值大于1的情況，于是根據(jù)目標(biāo) 函數(shù)的特點在設(shè)計適應(yīng)度函數(shù)時，在分母上加上2,分子上剩以4,如式(3.1)所示；又根據(jù)優(yōu)化問題的約束條件，利用約束條件處理方法中的罰函數(shù)法設(shè)計了相 應(yīng)的罰函數(shù)c,那么適應(yīng)度函數(shù)為F( x)=4f (x) c 2(3.6)其中，c = Hmax0,g1(x1,x2) 5 + RMma

29、x0,| 兀(4乂2)4| , 4=2=10000。按照上述方法計算種群中各個個體的適應(yīng)值，如果適應(yīng)值趨近于1,那么對應(yīng)的個體即為最佳個體，計算適應(yīng)值的程序是 fitness.mo3.4 遺傳算子3.4.1 選擇操作本程序選擇輪盤賭法來實現(xiàn)選擇操作。根據(jù)之前計算的各個個體的適應(yīng)值，利用式(2.6)計算種群中所有個體的適應(yīng)值的和Fall ；然后按照如式(2.7) 、 (2.8)計算每個個體的選擇概率p和累計概率q。旋轉(zhuǎn)輪盤100次(種群規(guī)模)，每次生 成一個0至IJ 1的隨機數(shù)r,用這個隨機數(shù)與種群中的個體的累積概率q作比較，如果這個隨機數(shù)落在了這個概率區(qū)間， 那么就保留該個體， 這就完全模擬了

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