基本遺傳算法及的應(yīng)用舉例

1、實(shí)用標(biāo)準(zhǔn)文案基本遺傳算法及應(yīng)用舉例遺傳算法(Genetic Algorithms)是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)、高度并行、自適應(yīng)搜索算法。遺傳算法是多學(xué)科相互結(jié)合與滲透的產(chǎn)物。目前它已發(fā)展成一種自組織、自適應(yīng)的多學(xué)科技術(shù)。針對(duì)各種不同類型的問題，借鑒自然界中生物遺傳與進(jìn)化的機(jī)理，學(xué)者們?cè)O(shè)計(jì)了不同的編碼方法來表示問題的可行解，開發(fā)出了許多不同環(huán)境下的生物遺傳特征。這樣由不同的編碼方法和不同的遺傳操作方法就構(gòu)成了各種不同的遺傳算法。但這些遺傳算法有共同的特 點(diǎn)，即通過對(duì)生物的遺傳和進(jìn)化過程中的選擇、交叉、變異機(jī)理的模仿來完成對(duì)最優(yōu)解的自適應(yīng)搜索過程?；诖斯餐c(diǎn)，人們總結(jié)出了最基本

2、的遺傳算法一一基本遺傳算法?；?遺傳算法只使用選擇、交叉、變異三種基本遺傳操作。遺傳操作的過程也比較簡(jiǎn)單、容易理 解。同時(shí)，基本遺傳算法也是其他一些遺傳算法的基礎(chǔ)與雛形。1.1.1編碼方法用遺傳算法求解問題時(shí)，不是對(duì)所求解問題的實(shí)際決策變量直接進(jìn)行操作，而是對(duì)表示可行解的個(gè)體編碼的操作，不斷搜索出適應(yīng)度較高的個(gè)體，并在群體中增加其數(shù)量，最終尋找到問題的最優(yōu)解或近似最優(yōu)解。因此，必須建立問題的可行解的實(shí)際表示和遺傳算法的染色體位串結(jié)構(gòu)之間的聯(lián)系。在遺傳算法中，把一個(gè)問題的可行解從其解空間轉(zhuǎn)換到遺傳算法 所能處理的搜索空間的轉(zhuǎn)換方法稱之為編碼。反之，個(gè)體從搜索空間的基因型變換到解空間的表現(xiàn)型的方

3、法稱之為解碼方法。編碼是應(yīng)用遺傳算法是需要解決的首要問題，也是一個(gè)關(guān)鍵步驟。迄今為止人們已經(jīng)設(shè)計(jì)出了許多種不同的編碼方法?；具z傳算法使用的是二進(jìn)制符號(hào)0和1所組成的二進(jìn)制符號(hào)集 0, 1,也就是說，把問題空間的參數(shù)表示為基于字符集0, 1構(gòu)成的染色體位串。每個(gè)個(gè)體的染色體中所包含的數(shù)字的個(gè)數(shù)L稱為染色體的長(zhǎng)度或稱為符號(hào)串的長(zhǎng)度。一般染色體的長(zhǎng)度L為一固定的數(shù)，如X=10011100100011010100表示一個(gè)個(gè)體，該個(gè)體的染色體長(zhǎng)度L=20。二進(jìn)制編碼符號(hào)串的長(zhǎng)度與問題所要求的求解精度有關(guān)。假設(shè)某一參數(shù)的取值范圍是a, b,我們用長(zhǎng)度為L(zhǎng)的二進(jìn)制編碼符號(hào)串來表示該參數(shù)，總共能產(chǎn)生21種不

4、同的編碼,若參數(shù)與編碼的對(duì)應(yīng)關(guān)系為00000000000 00000000=0一 a00000000000 00000001=1 a+ 811111111111111111111= 2L-1 一 b則二進(jìn)制編碼的編碼精度b a2l 1假設(shè)某一個(gè)個(gè)體的編碼是Xkakak2aki ,則對(duì)應(yīng)的解碼公式為、，cba /C ° L j xk aL7( akj2)21 j 1例如，對(duì)于x 0,1023,若用長(zhǎng)度為10的二進(jìn)制編碼來表示該參數(shù)的話，則下述符號(hào)串:X=0010101111就表示一個(gè)個(gè)體，它對(duì)應(yīng)的參數(shù)值是X=175.此時(shí)的編碼精度為1.二進(jìn)制編碼方法相對(duì)于其它編碼方法的優(yōu)點(diǎn)，首先是編碼

5、、解碼操作簡(jiǎn)單易行；其次是交叉遺傳操作便于實(shí)現(xiàn)；另外便于對(duì)算法進(jìn)行理論分析。2.個(gè)體適應(yīng)度函數(shù)在遺傳算法中，根據(jù)個(gè)體適應(yīng)度的大小來確定該個(gè)體在選擇操作中被選定的概率。個(gè)體的適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體的適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小?；具z傳算法使用比例選擇操作方法來確定群體中各個(gè)個(gè)體 是否有可能遺傳到下一代群體中。為了正確計(jì)算不同情況下各個(gè)個(gè)體的選擇概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或?yàn)榱?，不能是?fù)數(shù)。這樣，根據(jù)不同種類的問題，必須預(yù)先確定 好由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。設(shè)所求解的問題為：

6、maxf(x), x D.對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，理論上只需簡(jiǎn)單地對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(zhuǎn) 化為求目標(biāo)函數(shù)最大值的問題，即min f(x) max( f(x).當(dāng)優(yōu)化問題是求函數(shù)最大值，并且目標(biāo)函數(shù)總?cè)≌禃r(shí)，可以直接設(shè)定個(gè)體的適應(yīng)度函數(shù)值F(x)就等于相應(yīng)的目標(biāo)函數(shù)值 f (x),即 F(x) f (x).但實(shí)際目標(biāo)優(yōu)化問題中的目標(biāo)函數(shù)有正也有負(fù)，優(yōu)化目標(biāo)有求函數(shù)最大值，也有求函 數(shù)最小值，顯然上面兩式保證不了所有情況下個(gè)體的適應(yīng)度都是非負(fù)數(shù)這個(gè)要求，必須尋求出一種通用且有效的由目標(biāo)函數(shù)值到適應(yīng)度之間的轉(zhuǎn)換關(guān)系，有它來保證個(gè)體適應(yīng)度總?cè)》秦?fù)值。為滿足適應(yīng)度取負(fù)值的要求，基本遺傳算法

7、一般采用下面方法將目標(biāo)函數(shù)值f(x)變換為個(gè)體的適應(yīng)度F(x).對(duì)于求目標(biāo)函數(shù)最大值的優(yōu)化方法問題，變換方法為f f(x) Cmin ,f(x) Cmin 0時(shí)，F(xiàn)(x) <00f(x) Cmin 0時(shí)，式中，Cm.為一個(gè)適當(dāng)?shù)南鄬?duì)比較小的數(shù)，它可以是預(yù)先指定的一個(gè)較小的數(shù)，或進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值，又或當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。3 .基本遺傳操作方法(1)比例選擇：選擇或稱復(fù)制，建立在對(duì)個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上。其作用是從當(dāng)前群體中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。 基本遺傳算法采用比例選擇的方法，所謂比例選擇，是指?jìng)€(gè)體在選擇操作中被選中的

8、概率與該個(gè)體的適應(yīng)度大 小成正比。(2)單點(diǎn)交叉。單點(diǎn)交叉又稱簡(jiǎn)單交叉，是遺傳算法所使用的交叉操作方法。(3)基本位變異。基本位變異石最簡(jiǎn)單和最基本的變異操作，也是基本遺傳算法中所使用的變異操作方法。 對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，對(duì)需要進(jìn)行變異操作的某一基因，若原有基因值為 0,則變異操作將該基因值變?yōu)?1 ;反之，若原有基 因值為1 ,則變異操作將其變?yōu)?0.4 .基本遺傳算法的運(yùn)行參數(shù)執(zhí)行基本遺傳算法時(shí)，有4個(gè)參數(shù)需要事先指定。它們是群體的大小 M、交叉概率Pc、 變異概率Pm及終止的代數(shù)T.(1) 群體大小M.群體的大小M表示群體中所含個(gè)體的數(shù)量。當(dāng)M取值較小時(shí)，可

9、提高遺傳算法的運(yùn)算速度，但卻降低了群體的多樣性，有可能會(huì)引起遺傳算法 的早熟現(xiàn)象；而當(dāng)M取值較大時(shí)，又會(huì)使得遺傳算法的運(yùn)行效率偏低。一般建議范圍是20100.(2) 交叉概率Pc。交叉操作室遺傳算法產(chǎn)生新個(gè)體的主要方法，所以交叉概率一般應(yīng)取較大值。但若取值過大的話，它又會(huì)破壞群體活動(dòng)的優(yōu)良模式，對(duì)進(jìn)化運(yùn) 算反而產(chǎn)生不利影響；若取值過小的話，產(chǎn)生新個(gè)體的速度有太慢。一般建議 的取值范圍是 0.41.00.(3) 變異概率Pm。若變異概率Pm取值較大的話，雖能夠產(chǎn)生出較多的新個(gè)體，但也有可能破壞掉很多較好的模式，使得遺傳算法的性能近似于隨機(jī)搜索算法的 性能；若變異概率 pmW值太小的話，則變異操作

10、產(chǎn)生新個(gè)體的能力和抑制早 熟現(xiàn)象的能力就會(huì)較差。一般建議的取值范圍是0.0010.1.(4) 終止彳弋?dāng)?shù)T.終止彳弋?dāng)?shù)T式表示遺傳算法運(yùn)行結(jié)束條件的一個(gè)參數(shù)，它表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行，并將當(dāng)前群體中的最佳個(gè)體作為 所求問題的最優(yōu)解輸出。一般建議的取值范圍是1001000.至于遺傳算法的終止條件，還可以利用某種判定準(zhǔn)則，當(dāng)判定出群體已經(jīng)進(jìn)化成熟且不 再有進(jìn)化趨勢(shì)時(shí)就可終止算法的運(yùn)行過程。如連續(xù)幾代個(gè)體平均適應(yīng)度的差異小于某一個(gè)極小的值；或者群體中所有個(gè)體適應(yīng)度的方差小于某一個(gè)極小的值。這 4個(gè)參數(shù)對(duì)遺傳算法 的搜索結(jié)果及搜索效率都有一定的影響，目前尚無合理選擇它們的理論根

11、據(jù)在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次的試算后才能確定出這些參數(shù)合理的取值范圍或取值大小?；具z傳算法是一個(gè)迭代過程，它模仿生物在自然環(huán)境中的遺傳和進(jìn)化機(jī)理，反復(fù)將選 擇操作、交叉操作、 變異操作作用與群體，最終可得到問題的最優(yōu)解或近似最優(yōu)解。雖然算 法的思想比較簡(jiǎn)單，但它卻具有一定的實(shí)用價(jià)值，能夠解決一些復(fù)雜系統(tǒng)的優(yōu)化計(jì)算問題。遺傳算法的應(yīng)用步驟如下；遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的領(lǐng)域和種 類。對(duì)一個(gè)需要進(jìn)行優(yōu)化計(jì)算的實(shí)際應(yīng)用問題，一般可按下述步驟來構(gòu)造求解該問題的遺傳算法。第一步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)、決策變量及各種約束條件以及數(shù)學(xué)描述形

12、式或量化方法。第二步：確定表示可行解的染色體編碼方法，也即確定出個(gè)體的基因型 x及遺傳算法的 搜索空間。第三步：確定解碼方法，即確定出個(gè)體基因型 x到個(gè)體表現(xiàn)型x的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法。第四步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值f x到個(gè)體適應(yīng)度F x的轉(zhuǎn)換規(guī)則。第五步：設(shè)計(jì)遺傳操作方法，即確定出選擇運(yùn)算、 交叉運(yùn)算、變異運(yùn)算等具體操作方法。第六步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的 M、T、Pc、Pm等參數(shù)。由上述構(gòu)造步驟可以看出，可行解的編碼方法、遺傳操作的設(shè)計(jì)是構(gòu)造遺傳算法時(shí)需要 考慮的兩個(gè)主要問題，也是設(shè)計(jì)遺傳算法時(shí)的兩個(gè)關(guān)鍵步驟。對(duì)不同的優(yōu)化問題需要使用不同

13、的編碼方法和不同的遺傳操作，它們與所求解的具體問題密切相關(guān)，因而對(duì)所求解問題的理解程度是遺傳算法應(yīng)用成功與否的關(guān)鍵。例1 . 1 . 1求解規(guī)劃問題22max f xi, x2xix2,s.t. xi0,1,2, ,7 ,x20,1,2,7.解主要運(yùn)算過程如表 7-3所示。(1)個(gè)體編碼.遺傳算法的運(yùn)算對(duì)象是表示個(gè)體的符號(hào)串，所以必須把變量1 . 1基本遺傳算法的構(gòu)成要素 為，x2編碼為一種符號(hào)串。該例題中， 為和x2取07之間 的整數(shù)，可分別用 3位無符號(hào)二進(jìn)制整數(shù)來表示，將它們連接在一起所組成的6位無符號(hào)二進(jìn)制整數(shù)就形成了個(gè)體的基因型，表示一個(gè)可行解。例如，基因型 x=101110 所對(duì)應(yīng)

14、的 表現(xiàn)型是x= (5, 6) T。個(gè)體的表現(xiàn)型 x和基因型x之間可以通過編碼和解碼相互轉(zhuǎn)換。(2)初始群體的產(chǎn)生。遺傳算法是對(duì)群體進(jìn)行遺傳操作，需要準(zhǔn)備一些表示起始搜索點(diǎn)的初始群體數(shù)據(jù)。本例中群體規(guī)模的大小M取為4,即群體由4個(gè)個(gè)體組成，每個(gè)個(gè)體可通過隨機(jī)方法產(chǎn)生。一個(gè)隨機(jī)產(chǎn)生的初始群體如表7-3中第2欄所示。(3)適應(yīng)度計(jì)算。本例中，目標(biāo)函數(shù)總?cè)》秦?fù)值， 并且是以求函數(shù)最大值為優(yōu)化目標(biāo)， 故可直接利用目標(biāo)函數(shù)值作為個(gè)體的適應(yīng)度，即F x f X。為計(jì)算函數(shù)的目標(biāo)值，需先對(duì)個(gè)體基因型X進(jìn)行解碼。表7-3中第3、第4欄所示為初始群體各個(gè)個(gè)體的解碼結(jié)果，第5欄所示為各個(gè)個(gè)體所對(duì)應(yīng)的目標(biāo)函數(shù)彳1,

15、它也是個(gè)體的適應(yīng)度，第 5欄中還給出了群 體中適應(yīng)度的最大值和平均值。表7-31個(gè)體編號(hào)i2初始群體P(0)3X14X25fi X,X26fi/fi10111013534fi 14334fmaX 5025 f 35.75500.242101011530.243011100340.174111001710.357選擇次數(shù)8選擇結(jié)果9配對(duì)情況10交叉點(diǎn)位直11父義結(jié)果12變異點(diǎn)13變異結(jié)果10111011-23-41-2 : 23-4 : 4011001501100111110011111011111110101011101001101001211100111101111101114子代群體P (

16、1)15X116X217fi X,X20110013110fi1921111117798fmax981010015126f481110117358(4)選擇操作.其具體操作過程是先計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和fi及每個(gè)個(gè)體的相對(duì)適應(yīng)度的大小fi/fi ,如表7-3中5、6欄所示。表7-3中第7、8欄表示隨機(jī)產(chǎn)生的選擇結(jié)果。(5)交叉操作。本例中采用單點(diǎn)交叉的方法，并取交叉概率 Pc=1.00 。表7-3中第 11欄所示為交叉運(yùn)算的結(jié)果。(6)變異操作。為了能顯示變異操作，取變異概率Pm=0.25,并采用基本位變異的方法進(jìn)行變異運(yùn)算。表 7-3第13欄所示為變異運(yùn)算的結(jié)果。對(duì)群體P (t)