基本遺傳算法

(完整)基本遺傳算法(完整)基本遺傳算法基本遺傳算法Holland創(chuàng)建的遺傳算法是一種概率搜索算法,它利用某種編碼技術作用于稱為染色體的數串，其基本思想是模擬由這些串組成的個體進化過程.該算法通過有組織的、然而是隨機的信息交換，重新組合那些適應性好的串.在每一代中，利用上一代串結構中適應性好的位和段來生成一個新的串的群體；作為額外增添，偶爾也要在串結構中嘗試用新的位和段來替代原來的部分。遺傳算法是一類隨機優(yōu)化算法，它可以有效地利用已有的信息處理來搜索那些有希望改善更多的繁殖機會.

第一章遺傳算法的運行過程遺傳算法模擬了自然選擇和遺傳中發(fā)生的復制、交叉和變異等現象 ,從任一初始種群（Population）出發(fā),通過隨機選擇、交叉和變異操作，產生一群更適應環(huán)境的個體,使群體進化到搜索空間中越來越好的區(qū)域，這樣一代一代地不斷繁衍進化，最后收斂到一群最適應環(huán)境的個體(Individual),求得問題的最優(yōu)解。一．完整的遺傳算法運算流程完整的遺傳算法運算流程可以用圖1來描述。1）主要運算過程如下：編碼:解空間中的解數據x,遺傳算法在進行搜索之前先將解空間的解數據表示成遺傳空間的基因型串結構數據，這些串結構數據的不同組合就構成了不同的點。NNN←0；設置最大進化代數T;隨機生成M個個體作為初始群體P（0。P(t）中各個個體的適應度。選擇：將選擇算子作用于群體。交叉:將交叉算子作用于群體。變異：將變異算子作用于群體。群體P(t）經過選擇、交叉、變異運算后得到下一代群體P（t+1).終止條件判斷：若t≤T，則t←t+1,轉到步驟（2；若t＞具有最大適應度的個體作為最優(yōu)解輸出,終止運算。了一個基本框架。實際問題參數編碼成位串實際問題參數編碼成位串位串解釋得到參數計算目標函數函數值向適值映射適值調整1計算適應值三種基本遺傳算子：變異算子選擇與遺傳隨機算子12統(tǒng)計結果2經過優(yōu)化的一個或多個參數集（由解碼得到）改善或解決實際問題1遺傳算法運算流程GoldbergP(t）P(0）是隨機設計的，簡單遺傳算法的偽代碼描述如下：produreGAbegint=0;initializeP（t)；evaluateP（t)；whilenotfinishedbegint=t+1；selectP（t)fromP(t-1）;reproducepairsinP(t）;evaluateP(t）;endend二．遺傳算法的基本操作遺傳算法有三個基本操作：選擇（Selection、交叉(Crossover)和變異（Mutation)。強的個體為下一代貢獻一個或多個后代的概率大.這樣就體現了達爾文的適者生存原則。（2）（稱為交叉概率，CrossoverRate）交換它們之間的部分染色體.交叉體現了信息交換的思想.（3)變異.變異操作首先在群體中隨機選擇一個個體，對于選中的個體以一定的概率隨機改變Rate）改變某一個或某一些基因座上的基因值為其他的等位基因。同生物界一樣遺傳算法中變異發(fā)生的概率很低。變異為新個體的產生提供了機會.三．基本遺傳算法的數學模型基本遺傳算法可表示為SGA=（C,E,P，M,，，,T）0式中:C——個體的編碼方法；E-—個體適應度評價函數；P—-初始種群；0M--種群大小；——選擇算子；-—交叉算子；--變異算子；T—-遺傳算法終止條件。四．基本遺傳算法的步驟染色體編碼（ChromosomeCoding）與解碼（Decode）基本遺傳算法使用固定長度的二進制符號串來表示群體中的個體，其等位基因由二值｛0,1｝所組成。初始群體中各個個體的基因可用均勻分布的隨機數來生成。例如：x=100111001000101101n=18。(1）編碼：變量x作為實數，可以視為遺傳算法的表現型形式。從表現型到基因型的映射稱為編碼.設某一參數的取值范圍為［U1

，U],我們用長度為k的二進制編碼符號來表示該參數,則2它總共產生2k種不同的編碼，可使參數編碼時的對應關系為：000000…0000=0→U1000000…0001=1→U+1000000…0010=2→U+21…111111…1111=2k—1→U221其中，=U U .212k1（2）bb

b…b

，則對應的解碼公式為i

U

kk—1

k—2 21XU1

( bii1

1)

2 1 ①2k1X［245位二進制編碼對X25=32（染色體：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對于任一個二進制串，只要代入公式①，就可得到相應的解碼,如X=10101,它對應的十22進制為bii1

2i1=1+0*2+1＊2+0＊23+＊2=21，則對應參數X的值為2+21＊(4—2）/(25—1）=3。3548。個體適應度的檢測評估基本遺傳算法按與個體適應度成正比的概率來決定當前群體中各個個體遺傳到下一代群體C，C.(完整)基本遺傳算法遺傳算子基本遺傳算法使用下列三種遺傳算子：選擇運算使用比例選擇算子.比例選擇因子是利用比例于各個個體適應度的概率決定其子孫的遺傳可能性。若設種群數為M,個體i的適應度為f,則個體i被選取的概率為iPfi i

/M fkk1當個體選擇的概率給定后，產生［0，1汰。我們經常采用的是輪盤賭的原理,個體的的性能進行的一些計算.實值范圍——總和是所率的總和或當前種群中所有個體原始適應度值一方式映像到范圍1

選擇概率是基于它們有個體期望的選擇概65[0,sum]個體被選中為止。2父個體111011單點交叉11000子個體1父個體20110001111子個體2圖2單點交叉示意圖變異運算使用基本位變異算子或均勻變異算子。為了避免問題 過早收斂對于二進制基因碼組成的個體種群，實現基因碼的小概率翻轉,即0變?yōu)?,而1變?yōu)?，如圖3所示。(完整)基本遺傳算法(完整)基本遺傳算法11011 變異 1111111011變異11111圖3圖3變異操作示意圖行參數4M,T,P,Pc mMT100~500；P為交叉概率，一般取為0.4～0.99;cP為變異概率，一般取為0。0001～0.1。m五．遺傳算法的具體例證下面通過具體的例子介紹遺傳算法的實際工作過程。假設目標函數為maxf(x,

)21.5

)

)13.0x

2 x

1 2 2 ②5.81 2該函數有多個局部極值點。第一步,確定決策變量和約束條件。x,x3。0≤x≤12。1，4.1≤x5.8。1 2 1 2第二步，建立優(yōu)化模型.式②已給出了問題的數學模型。第三步，確定編碼方法。要進行編碼工作，即將變量轉換成二進制串。串的長度取決于所要求的精度。例如，變量x［a，b4(bj j j ja）＊104個部分。對一個變量的二進制串位數（用mj

表示，用以下公式計算：2mj1 bj

a)*142mj1j第四步，確定解碼方法。從二進制串返回一個實際的值可用下面的公式來實現：x a decimal(substring

)*bjajj j

2mj1decimal(subing)x的十進制值。j j4x1

和x可以轉換為下面的串:2（12。1—（-3。0)）＊10000=151000217＜151000≤218，

=181(5。8-4.1）*10000=17000214＜17000≤215,

=152m=m

+m=18+15=331 2這樣,一個染色體串是33位，如圖4所示。33位18位33位18位15位4一個染色體二進制串x1

和x的實值如表1所示。表1表1染色體二進制與十進制比較較變量x1x2二進制數000001010100101001101111011111110十進制數541724318x=-3。0+5417＊（12。1（-3.0))/21-1）=2。6879691x=4。1+24318＊（5.8—。1）（215-1）=5.3616532初始種群可隨機生成如下：U=[000001010100101001101111011111110］1U=[001110101110011000000010101001000]2U=［111000111000001000010101001000110]3U=［100110110100101101000000010111001］4U=［000010111101100010001110001101000]5U=［111110101011011000000010110011001]6U=[110100010011111000100110011101101]7U=[001011010100001100010110011001100］8U=［111110001011101100011101000111101]9U=[111101001110101010000010101101010]10相對應的十進制的實際值為U=［x,x］=［—2。687969，5。361653]1 1 2U=［x,x］=[0。474101，4。170144]2 1 2U=［x,x］=［10。419457,4.661461]3 1 2U=[x,x］=[6。159951，4.109598］4 1 2U=［x,x2。301286，4.477282]5 1 2U=［x，x［11.788084，4。174346]6 1 2U=[x，x］=［9。342067，5。121702］7 1 2U=[x,x]=[-0.330256,4.694977]8 1 2U=[x,x］=［11.671267，4.873501]9 1 2U=[x，x］=[11.446273,4。171908]10 1 2第五步，確定個體評價方法。對一個染色體串的適應度評價由下列三個步驟組成：將染色體串進行反編碼,轉換成真實值。在本例中，意味著將二進制串轉換成實際值:xk=(xk，x),k=1,2,…1 2（2)評價目標函數f（xk。(3）將目標函數值轉為適應度。對于極大值問題，適應度就等于目標函數值，即eval（U=f（k)，k=1,2,…k價。上述染色體的適應度值如下:eval(U

)=f（—2。687969，5。361653)=19。8051191eval（U)=f(0.474101，4.170144)=17。3708962eval（U)=f(10.419457，4。661461)=9。5905463eval(U

）=f（6。159951，4。109598）=29.4061224eval（U）=f(—2.301286,4.477282)=15。6860915eval(Ueval(Ueval(Ueval(U

)=f(11。788084，4。174346)=11.9005416）=f(9。342067,5.121702)=17.9587177）=f(—0。330256，4.694977)=19.7631908)=f(11.671267,4.873501）=26.4016699eval（U10

）=f(11.446273,4.171908）=10。252480由以上數據可以看出，上述染色體中最健壯的是U，最虛弱的是U。4 3第六步，設計遺傳算子和確定遺傳算法的運行參數。選擇運算使用輪盤選擇算子。為基礎的概率分配來選擇新的種群。其步驟如下：①計算各染色體U的適應度值eval（Ukkeval（U）=f(x，k=1,2,…k②計算群體的適應度值總和：popsizeF eval(U)kk1③計算對應于每個染色體Uk的選擇概率Pk：eval(Uk)k F④計算每個染色體U的累計概率Q：k kkj1

P,jj在實際工作中，選擇新種群的一個染色體按以下步驟完成:①生成一個[0，1］間的隨機數r如果r≤QUkU（2≤k≤pop-size)，使得1 1 kQ≤k≤Qk—1 k那么,本例中種群的適應度總和為F10k1

eval(Uk

)178.135372Uk

（k=1，2,…，10)的選擇概率Pk

如下:P=0.1111801

=0。0975152

=0。0538393

=0.1650774

=0。0880575P=0。0668066

=0.1008157

=0.1109458

=0.1482119

=0。05755410Uk

（k=1,2,…，10）的累計概率Qk

如下：Q=0。1111801

=0。2086952

=0.2625343

=0。4276114

=0.5156685Q=0。5824756

=0.6832907

=0.7942348

=0。9424469

=1。000000101010［0,1］間的隨機數如下：0.301431 0.322062 0.766503 0。881893 0.3508710。583392 0.177618 0.343242 0.032685 0。197577第一個隨機數r1

=0301431Q3

QU4

=03220622

Q

被再次選中.最終,新的種群由下列染色體組成:3 4 4U=［100110110100101101000000010111001] （U）1 4U=[100110110100101101000000010111001］ (U)2 4U=[001011010100001100010110011001100］ （U）3 8U=[111110001011101100011101000111101] （U）4 9U=［100110110100101101000000010111001] （U）5 4U=[110100010011111000100110011101101] (U）6 7U=[001110101110011000000010101001000] （U）7 2U=[100110110100101101000000010111001］ （U)8 4U=［000001010100101001101111011111110］ （U)9 1U=［001110101110011000000010101001000] (U)10 2交叉運算使用單點交叉算子。染色體如下所示(節(jié)點隨機選擇在染色體串的第17位基因：UU=[100110110100101101000000010111001]1U=[001011010100001100010110011001100]2P=2525％的染色體進行交叉。交叉操作的過程如0下：開始k←0；當k≤10時繼續(xù)r←［0,1］之間的隨機數；k如果r＜0.25，則k選擇Uk結束

為交叉的一個父輩；k←k+1;結束結束假設隨機數如下：0.6257210。2668230。2886440.2951140。1632740。5674610.0859400.3928650。7707140.548656那么，就意味著染色體U5

U[1,32］733）pos1染色體從第一位分割，新的子輩在第一位右端的部分互換而生成，即U=［100110110100101101000000010111001］5U=［001110101110011000000010101001000］7U05U7變異運算使用基本位變異算子U1

181，0。于是，染色體在變異后將是：U=［100110110100101101000000010111001]1U*11P=0.011%要進行變異。m33＊10=3303。3概率是相等的。因此，我們要生成一個位于[0，1rk

（k=1,2，…，330）.假設表2列出的基因將進行變異。2基因變異示例基因位置染色體位置基因位數隨機數105461645321997132910320.0098570.0098570.001130。0009460.001282U=11U*=[100110110100101101000000010111001］ U