基本遺傳算法

基本遺傳算法Holland創(chuàng)建的遺傳算法是一種概率搜索算法，它利用某種編碼技術(shù)作用于稱為染色體的數(shù)串，其基本思想是模擬由這些串組成的個體進(jìn)化過程.該算法通過有組織的、然而是隨機(jī)的信息交換，重新組合那些適應(yīng)性好的串.在每一代中，利用上一代串結(jié)構(gòu)中適應(yīng)性好的位和段來生成一個新的串的群體；作為額外增添，偶爾也要在串結(jié)構(gòu)中嘗試用新的位和段來替代原來的部分。遺傳算法是一類隨機(jī)優(yōu)化算法，它可以有效地利用已有的信息處理來搜索那些有希望改善解質(zhì)量的串.類似于自然進(jìn)化，遺傳算法通過作用于染色體上的基因，尋找好的染色體來求解問題.與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進(jìn)行評價，并基于適應(yīng)度值來改變?nèi)旧w，使適應(yīng)性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會.第一章遺傳算法的運(yùn)行過程遺傳算法模擬了自然選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象 ，從任一初始種群(Population)出發(fā)，通過隨機(jī)選擇、交叉和變異操作，產(chǎn)生一群更適應(yīng)環(huán)境的個體，使群體進(jìn)化到搜索空間中越來越好的區(qū)域，這樣一代一代地不斷繁衍進(jìn)化，最后收斂到一群最適應(yīng)環(huán)境的個體(Individual),求得問題的最優(yōu)解。完整的遺傳算法運(yùn)算流程完整的遺傳算法運(yùn)算流程可以用圖1來描述。由圖1可以看出，使用上述三種遺傳算子(選擇算子、交叉算子和變異算子)的遺傳算法的主要運(yùn)算過程如下：編碼：解空間中的解數(shù)據(jù)x,作為遺傳算法的表現(xiàn)形式。從表現(xiàn)型到基因型的映射稱為編碼.遺傳算法在進(jìn)行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合就構(gòu)成了不同的點(diǎn)。初始群體的生成：隨機(jī)產(chǎn)生N個初始串結(jié)構(gòu)數(shù)據(jù)，每個串結(jié)構(gòu)數(shù)據(jù)稱為一個個體，N個個體構(gòu)成了一個群體。遺傳算法以這N個串結(jié)構(gòu)作為初始點(diǎn)開始迭代。設(shè)置進(jìn)化代數(shù)計數(shù)器t(完整)基本遺傳算法■0;設(shè)置最大進(jìn)化代數(shù)T；隨機(jī)生成M個個體作為初始群體P(0)。適應(yīng)度值評價檢測：適應(yīng)度函數(shù)表明個體或解的優(yōu)劣性。對于不同的問題，適應(yīng)度函數(shù)的定義方式不同.根據(jù)具體問題，計算群體P(t)中各個個體的適應(yīng)度。選擇：將選擇算子作用于群體。交叉:將交叉算子作用于群體。變異：將變異算子作用于群體。群體P(t)經(jīng)過選擇、交叉、變異運(yùn)算后得到下一代群體P(t+1).終止條件判斷：若tWT,則t<-t+1,轉(zhuǎn)到步驟(2)；若t>T,則以進(jìn)化過程中所得到的具有最大適應(yīng)度的個體作為最優(yōu)解輸出，終止運(yùn)算。從遺傳算法運(yùn)算流程可以看出，進(jìn)化操作過程簡單，容易理解，它給其他各種遺傳算法提供了一個基本框架。圖1遺傳算法運(yùn)算流程(完整)基本遺傳算法一個簡單的遺傳算法被Goldberg用來進(jìn)行輪廓描述并用來舉例說明遺傳算法的基本組成.t代種群用變量P(t)表示，初始種群P(0)是隨機(jī)設(shè)計的，簡單遺傳算法的偽代碼描述如下：produreGAbegint=0;initializeP(t)；evaluateP(t)；whilenotfinisheddobegint=t+1；selectP(t)fromP(t-1);reproducepairsinP(t);evaluateP(t);endend遺傳算法的基本操作遺傳算法有三個基本操作：選擇(Selection)、交叉(Crossover)和變異(Mutation)。選擇。選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個體，使它們有機(jī)會作為父代為下一代繁殖子孫。根據(jù)各個個體的適應(yīng)度值，按照一定的規(guī)則或方法從上一代群體中選擇出一些優(yōu)良的個體遺傳到下一代群體中。遺傳算法通過選擇運(yùn)算體現(xiàn)這一思想，進(jìn)行選擇的原則是適應(yīng)性強(qiáng)的個體為下一代貢獻(xiàn)一個或多個后代的概率大.這樣就體現(xiàn)了達(dá)爾文的適者生存原則。交叉。交叉操作是遺傳算法中最主要的遺傳操作。通過交叉操作可以得到新一代個體，新個體組合了父輩個體的特性。將群體內(nèi)的各個個體隨機(jī)搭配成對，對每一個個體，以某個概率（完整）基本遺傳算法（稱為交叉概率，CrossoverRate）交換它們之間的部分染色體.交叉體現(xiàn)了信息交換的思想.（3）變異.變異操作首先在群體中隨機(jī)選擇一個個體，對于選中的個體以一定的概率隨機(jī)改變串結(jié)構(gòu)數(shù)據(jù)中某個串的值，即對群體中的每一個個體，以某一概率（稱為變異概率，MutationRate）改變某一個或某一些基因座上的基因值為其他的等位基因。同生物界一樣遺傳算法中變異發(fā)生的概率很低。變異為新個體的產(chǎn)生提供了機(jī)會.基本遺傳算法的數(shù)學(xué)模型基本遺傳算法可表示為SGA=（C,E,P0,M,①，r,甲,T）式中：C——個體的編碼方法；E 個體適應(yīng)度評價函數(shù)；P0——初始種群；M--種群大??；① 選擇算子；r-—交叉算子；甲--變異算子；T 遺傳算法終止條件?；具z傳算法的步驟染色體編碼（ChromosomeCoding）與解碼（Decode）基本遺傳算法使用固定長度的二進(jìn)制符號串來表示群體中的個體，其等位基因由二值{0,1}所組成。初始群體中各個個體的基因可用均勻分布的隨機(jī)數(shù)來生成。例如：x=100111001000101101就可表示一個個體，該個體的染色體長度是n=18。（1）編碼：變量x作為實(shí)數(shù)，可以視為遺傳算法的表現(xiàn)型形式。從表現(xiàn)型到基因型的映射稱為編碼.設(shè)某一參數(shù)的取值范圍為[U1,U2],我們用長度為k的二進(jìn)制編碼符號來表示該參數(shù)，則它總共產(chǎn)生2k種不同的編碼，可使參數(shù)編碼時的對應(yīng)關(guān)系為:000000???0000=0TU1000000???0001=1TU1+S000000-0010=2^U1+2S111111???1111=2k—1TU2(2)解碼：假設(shè)某一個體的編碼為bbb???bb，則對應(yīng)的解碼公式為kk—1k—2 21溫_ _一U-UX=U+Gb*2i-1)* ——1i=1例如：設(shè)有參數(shù)XE[2,4],現(xiàn)用5位二進(jìn)制編碼對X進(jìn)行編碼，得25=32個二進(jìn)制串(染色體):00000,00001,00010,00011,00100,00101,00110,0011101000,01001,01010,01011,01100,01101,01110,0111110000,10001,10010,10011,10100,10101,10110,1011111000,11001,11010,11011,11100,11101,11110,11111對于任一個二進(jìn)制串，只要代入公式①，就可得到相應(yīng)的解碼，如X22=10101,它對應(yīng)的十進(jìn)制為25b-2i-1=1+0*2+1大22+0大23+1大24=21，則對應(yīng)參數(shù)X的值為2+21大(4—2)/(25—1)i=1二3。3548。個體適應(yīng)度的檢測評估基本遺傳算法按與個體適應(yīng)度成正比的概率來決定當(dāng)前群體中各個個體遺傳到下一代群體中的機(jī)會多少。為了正確估計這個概率，要求所有個體的適應(yīng)度必須為非負(fù)數(shù).所以，根據(jù)不同種類的問題，需要預(yù)先確定好由目標(biāo)函數(shù)值到個體適應(yīng)度之間的轉(zhuǎn)換規(guī)律，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時的處理方法。例如，可選取一個適當(dāng)大的正數(shù)C,使個體的適應(yīng)度為目標(biāo)函數(shù)值加上正數(shù)C.

遺傳算子基本遺傳算法使用下列三種遺傳算子:(1)選擇運(yùn)算使用比例選擇算子.比例選擇因子是利用比例于各個個體適應(yīng)度的概率決定其子孫的遺傳可能性。若設(shè)種群數(shù)為M,個體i的適應(yīng)度為f.,則個體i被選取的概率為P=門丈fk=1當(dāng)個體選擇的概率給定后，產(chǎn)生［0,1］之間的均勻隨機(jī)數(shù)來決定哪個個體參加交配.若個體的選擇概率大，則能被多次選中，它的遺傳基因就會在種群中擴(kuò)大；若個體的選擇概率小，則被淘汰。圖1輪盤賭選擇選擇概率是基于它們有個體期望的選擇概的總和。個體采用一對一個體區(qū)間的大小與賭輪的周長是6個個我們經(jīng)常采用的是輪盤賭的原理，個體的的性能進(jìn)行的一些計算.實(shí)值范圍——總和是所率的總和或當(dāng)前種群中所有個體原始適應(yīng)度值一方式映像到范圍［0,sum］的一連續(xù)區(qū)間，每對應(yīng)個體的適應(yīng)度值相匹配.如圖圖1輪盤賭選擇選擇概率是基于它們有個體期望的選擇概的總和。個體采用一對一個體區(qū)間的大小與賭輪的周長是6個個交叉運(yùn)算使用單點(diǎn)交叉算子。只有一個交叉點(diǎn)位置，任意挑選經(jīng)過選擇操作后種群中兩個個體作為交叉對象，隨機(jī)產(chǎn)生一個交叉點(diǎn)位置，兩個個體在交叉點(diǎn)位置互換部分基因碼，形成兩個子個體，如圖2所示。父個體1父個體2圖父個體1父個體2圖2單點(diǎn)交叉示意圖子個體1子個體2變異運(yùn)算使用基本位變異算子或均勻變異算子。為了避免問題過早收斂，對于二進(jìn)制的基因碼組成的個體種群，實(shí)現(xiàn)基因碼的小概率翻轉(zhuǎn)，即0變?yōu)?,而1變?yōu)?,如圖3所示。

變異圖3變異操作示意圖 4.基本遺傳算法的運(yùn)行參數(shù)基本遺傳算法有下列4個運(yùn)行參數(shù)需要預(yù)先設(shè)定，即M,T,Pc，Pm。M為群體大小，即群體中所含個體的數(shù)量，一般取為20~100；T為遺傳算法的終止進(jìn)化代數(shù)，一般取為100~500;P為交叉概率，一般取為0.4?0.99；P為變異概率，一般取為0。0001?0.1。五.遺傳算法的具體例證下面通過具體的例子介紹遺傳算法的實(shí)際工作過程。假設(shè)目標(biāo)函數(shù)為maxf(x,x)=21.5+xsin(4^x)+xsin(20Kx)1 2 1 1 2 2 ②-3.0<氣<12.1,4.1<x2<5.8該函數(shù)有多個局部極值點(diǎn)。下面介紹求解該優(yōu)化問題的遺傳算法的構(gòu)造過程。第一步，確定決策變量和約束條件。式②給出，決策變量為x1,x2，約束條件為一3。0Wx1W12。1,4.1Wx2W5.8。第二步，建立優(yōu)化模型.式②已給出了問題的數(shù)學(xué)模型。第三步，確定編碼方法。要進(jìn)行編碼工作，即將變量轉(zhuǎn)換成二進(jìn)制串。串的長度取決于所要求的精度。例如，變量x」的區(qū)間是】a「bj，要求的精度是小數(shù)點(diǎn)后4位，也就意味著每個變量應(yīng)該被分成至少邕一a,大104個部分。對一個變量的二進(jìn)制串位數(shù)(用m」表示)，用以下公式計算：2mj-1(b—a,)*104<2mj—1第四步，確定解碼方法。從二進(jìn)制串返回一個實(shí)際的值可用下面的公式來實(shí)現(xiàn):x=a+decimal(substring)* %-jj j2mj—1其中，decimal(subing)代表變量x.的十進(jìn)制值。不妨設(shè)要求的精度為小數(shù)點(diǎn)后4位，則目標(biāo)函數(shù)的兩個變量x1和x2可以轉(zhuǎn)換為下面的串:(12。1—(-3。0))大10000=151000TOC\o"1-5"\h\z2i7V151000W2i8, m1=18(5。8-4.1)*10000=170002mV17000W215, m2=15m=m1+m2=18+15=33這樣，一個染色體串是33位，如圖4所示。r 33位 r000001010100101001 1011110111111101—18位 —15位—*圖4一個染色體二進(jìn)制串對應(yīng)的變量x1和x2的實(shí)值如表1所示。表1染色體二進(jìn)制與十進(jìn)制比立.較變量二進(jìn)制數(shù)十進(jìn)制數(shù)x 1 0000010101001010015417x 2 10111101111111024318x1=-3。0+5417大(12。1-(-3.0))/(218-1)=—2。687969x2=4。1+24318大(5.8—4。1)/(215-1)=5.361653初始種群可隨機(jī)生成如下：U1=[000001010100101001101111011111110]U2=[001110101110011000000010101001000]U3=[111000111000001000010101001000110]U4=[100110110100101101000000010111001]U5=[000010111101100010001110001101000]U6=[111110101011011000000010110011001]U7=[110100010011111000100110011101101]U=[001011010100001100010110011001100]8U9=[111110001011101100011101000111101]U10=[111101001110101010000010101101010]相對應(yīng)的十進(jìn)制的實(shí)際值為U1=[x1,x2]=[—2。687969,5。361653]U2=[x1,x2]=[0。474101,4。170144]U3=[x1,x2]=[10。419457,4.661461]U4=[x1,x2]=[6。159951,4.109598]U5=[x1,x2]=[-2。301286,4.477282]U6=[x1,x2]=[11.788084,4。174346]U7=[x1,x2]=[9。342067,5。121702]U8=[x1，x2]=[-0.330256,4.694977]U9=[x1,x2]=[11.671267,4.873501]U10=[x1,七]=[11.446273,4。171908]第五步，確定個體評價方法。對一個染色體串的適應(yīng)度評價由下列三個步驟組成：將染色體串進(jìn)行反編碼，轉(zhuǎn)換成真實(shí)值。在本例中，意味著將二進(jìn)制串轉(zhuǎn)換成實(shí)際值:xk=(x1k,x2k),k=1,2,^(2)評價目標(biāo)函數(shù)f(xk)。(3)將目標(biāo)函數(shù)值轉(zhuǎn)為適應(yīng)度。對于極大值問題，適應(yīng)度就等于目標(biāo)函數(shù)值，即eval(七)=f(xk)，k=1,2，…在遺傳算法中，評價函數(shù)起著自然進(jìn)化中環(huán)境的角色，它通過染色體的適應(yīng)度對其進(jìn)行評價。上述染色體的適應(yīng)度值如下：eval(U1)=f(—2。687969，5。361653)=19。805119eval(U2)=f(0.474101，4.170144)=17。370896eval(U3)=f(10.419457，4。661461)=9。590546eval(U4)=f(6。159951，4。109598)=29.406122eval(U5)=f(—2.301286,4.477282)=15。686091eval(U)=f(11。788084，4。174346)=11.9005416eval(U7)=f(9。342067,5.121702)=17.958717eval(U8)=f(—0。330256，4.694977)=19.763190eval(U)=f(11.671267,4.873501)=26.4016699eval(U10)=f(11.446273,4.171908)=10。252480由以上數(shù)據(jù)可以看出，上述染色體中最健壯的是U4，最虛弱的是U3。第六步，設(shè)計遺傳算子和確定遺傳算法的運(yùn)行參數(shù)。(1)選擇運(yùn)算使用輪盤選擇算子。為基礎(chǔ)的概率分配來選擇新的種群。其步驟如下：計算各染色體七的適應(yīng)度值eval(Uk)：eval(七)=f(xk)，k=1,2，…計算群體的適應(yīng)度值總和：poprsizeF=尤eval(U)k=1計算對應(yīng)于每個染色體Uk的選擇概率Pk：

p_eval(U)kF''計算每個染色體Uk的累計概率Q「Qk=丈P.，j=1,2,...j_i在實(shí)際工作中，選擇新種群的一個染色體按以下步驟完成:①生成一個［0，1］間的隨機(jī)數(shù)r②如果rWQ1，就選擇染色體U1；否則，選擇第k個染色體Uk(2WkWpop-size),使得Qk—iWkWQk那么，本例中種群的適應(yīng)度總和為F=i°eval(U)=178.135372k=1對應(yīng)于每個染色體Uk(k=1,2,…，10)的選擇概率Pk如下：Pi=0.111180P2=0o097515P3=0o053839P4=0.165077P5=0o088057P6=0o066806P7=0.100815P8=0.110945P9=0.148211P10=0o057554對應(yīng)于每個染色體Uk(k=1,2，…，10)的累計概率Qk如下：Q=0.5156685Q1=0o111180Q2=0o208695Q3=0.262534Q4Q=0.5156685Q=0o5824756Q=0.6832907Q=0.794234Q=0o5824756Q=0.6832907Q=0.7942348Q=0o9424469Q10=1o000000現(xiàn)在，我們轉(zhuǎn)動輪盤10次，每次選擇一個新種群中的染色體.假設(shè)這10次中生成的】0,1］間的隨機(jī)數(shù)如下：0.301431 0.322062 0.766503 0°881893 0.3508710o583392 0.177618 0.343242 0.0326850o197577第一個隨機(jī)數(shù)r=0o301431大于。小于Q,這樣染色體U被選中；第二個隨機(jī)數(shù)r=0o322062TOC\o"1-5"\h\z1 3 4 4 2也大于Q3小于Q4,于是染色體U4被再次選中.最終，新的種群由下列染色體組成：U1=[100110110100101101000000010111001] (U4)U2=[100110110100101101000000010111001] (U4)U3=[001011010100001100010110011001100] (U8)U4=[111110001011101100011101000111101] (U9)U5=[100110110100101101000000010111001] (U4)U6=[110100010011111000100110011101101] (U7)U7=[001110101110011000000010101001000] (U2)U8=[100110110100101101000000010111001] (U4)U=[000001010100101001101111011111110] (U )9 1U10=[001110101110011000000010101001000] (U2)（2）交叉運(yùn)算使用單點(diǎn)交叉算子。隨機(jī)選擇一個染色體串的節(jié)點(diǎn)，然后交換兩個父輩節(jié)點(diǎn)右端部分來產(chǎn)生子輩.假設(shè)兩個父輩染色體如下所示（節(jié)點(diǎn)隨機(jī)選擇在染色體串的第17位基因）：U=[100110110100101101000000010111001]U「[001011010100001100010110011001100]假設(shè)交叉概率為P0=25%,即在平均水平上有25%的染色體進(jìn)行交叉。交叉操作的過程如下：開始k?0;當(dāng)kW10時繼續(xù)rk?[0,1]之間的隨機(jī)數(shù)；如果rk<0.25，則選擇Uk為交叉的一個父輩；結(jié)束ki+1；結(jié)束結(jié)束假設(shè)隨機(jī)數(shù)如下：0.625721 0。266823 0。288644 0.295114 0。1632740。567461 0.085940 0.392865 0。770714 0.548656那么，就意味著染色體U5和U7被選中作為交叉的父輩.在這里，我們隨機(jī)選擇一個[1,32]間的整數(shù)(因?yàn)?3是整個染色體串的長度)作為交叉點(diǎn)。假設(shè)生成的整數(shù)pos為1,那么兩個染色體從第一位分割，新的子輩在第一位右端的部分互換而生成，即U5=[100110110100101101000000010111001]U=[001110101110011000000010101001000]7IU5*=[101110101110011000000010101001000]U「=[000110110100101101000000010111001]變異運(yùn)算使用基本位變異算子假設(shè)染色體U1的第18位基因被選作變異，即如果該位基因是1,則變異后就為0。于是，染色體在變異后將是：U1=[100110110100101101000000010111001]U「二[100110110100101100000000010111001]將變異概率設(shè)為P=0.01,就是說，希望在平均水平上，種群內(nèi)所有基因的1%要進(jìn)行變異。m在本例中，共有33大10=330個基因，希望在每一代中有3。3個變異的基因，每個基因變異的概率是相等的。因此，我們要生成一個位于[0,1]之間的隨機(jī)數(shù)系列rk(k=1,2,…，330).假設(shè)表2列出的基因?qū)⑦M(jìn)行變異。表2基因變異示例基因位置染色體位置基因位數(shù)隨機(jī)數(shù)105460.0098571645320.00113199710。00094632910320.001282在變異完成后，得到了最終的下一代種群：U*=[100110110100101101000000010111001]1U*=[10011011010010110100000001