遺傳算法的編碼機(jī)制研究new

《遺傳算法的編碼機(jī)制研究new》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、維普資訊http://www.cqvip.com第26卷第2期信息與控制Voi．26．No21997年4月hf0rnmtionandControlApr．，1997／／■1_、遺傳算法的編碼機(jī)制研究ff／／張曉繢方浩V戴冠中‘西北工業(yè)大學(xué)自動控．0系西安∞。．耍對遺傳算法中的編碼機(jī)制進(jìn)行了研究．分析了二進(jìn)制與十進(jìn)制編碼在搜索能力和保遺傳算法自其創(chuàng)始人Holland于7O年代初提出以來，在許多領(lǐng)域都有了成功的應(yīng)用．近年來有越來越多的學(xué)者開始研究遺傳算法及其在工程中的應(yīng)用．Holland提出的遺傳算法是采用二進(jìn)制編碼的．后來許多學(xué)

2、者對遺傳算法進(jìn)行了各種改進(jìn)，有人提出了十進(jìn)制編碼．我們知道編碼機(jī)制對遺傳算法的性能影響很大．到底采用二進(jìn)制黼編碼還是采用十進(jìn)制編碼，本文針對這一問題對二進(jìn)制編碼與十進(jìn)制編碼在搜索能力與保持靛種群穩(wěn)定性方面做了定量的分析．2遺傳算法遺傳算法是一種以自然選擇和遺傳理論為基礎(chǔ)，將生物進(jìn)化過程中適者生存規(guī)則與種群內(nèi)部染色體的隨機(jī)信息交換機(jī)制相結(jié)臺的優(yōu)化搜索算法．設(shè)求解的優(yōu)化問題為黼，：lJ．，]一R(I)l一】10其中1[]cR．這里[．]是第個變量的范圍．用遺傳算法求解問題時，首先對問題的解進(jìn)行編碼，構(gòu)成“染色體”，不同的染色體構(gòu)成

3、種群．每個染色體叫做種群中的個體．每個個體根據(jù)適應(yīng)函數(shù)有一個適應(yīng)值．然后通過選擇、交換和變異3個操作構(gòu)成新一代更好的種群．這樣不斷進(jìn)化，直到求出問題的較優(yōu)解．其基本執(zhí)行過程如下．(1)隨機(jī)選擇一個初始個體z，，?，z，每個個體有工個基因位置，≠一0．(2)計算每個個體的適應(yīng)值，(z)，一1，?，n．(3)選擇操作從種群中選擇出一個個體，個體z：在n個個體中所占的百分比為，r-、=一，這n個新個體記為Z，．?．∑，()J一_(4)交換操作：從z：，，?，z中以相同的概率P獨(dú)立地選出兩個個體，在I～工1之l9g6一O7I5收稿維普

4、資訊http://www.cqvip.comz期張曉績等，遺傳算法的■瑪機(jī)■研究間隨機(jī)選擇一個交換點(diǎn)，在交換點(diǎn)互換兩個個體的碼段，產(chǎn)生兩個新個體．重復(fù)這一過程，直到形成新種群_】，I2，?，．’(5)變異操作：按變異概率P．隨機(jī)地改變對每個個體的每一個基因位，形成新一代種群?1，?，．+】．(6)是否滿足結(jié)束條件，如果滿足則停止I否則，￡+1，轉(zhuǎn)(2)．3編碼機(jī)制搜索能力的分析3．1+進(jìn)制編碼假定1假定種群中個體數(shù)目為n，表示第￡代的第i個個體，i∈{1，2’．．·，n)．每個個體的基因位置效L—m，由m個實(shí)效構(gòu)成，個體∈R。

5、，：可以表示成m維的行向量，一[“’)．．·]．這樣第￡代的種群咒可以表示為一個一×m的矩陣，冠一[一]T．初始種群矩陣x[矗?：]中沒有相同的兩行，而且每列中沒有相同的元素，即種群中所有的個體互異，對任意≠，，∈{1，2，?，n}，有≠矗；而且個體中沒有兩個個體的同一基因位是相同的，即對任意f≠』，i，∈{1，2，?，n)，∈{1，2'．．·，m)，有≠．現(xiàn)在我們來討論交換操作的情況．定理1在假定1情況下，設(shè)初始種群經(jīng)交換操作產(chǎn)生的新個體屬于可敬集合D，則集合D中元素的數(shù)目7’。為7'D一2一1)c=(2)證明因?yàn)榉N群中個體

6、的數(shù)目為一，任取兩個進(jìn)行交換的可能情況有，又知有m一1個交換位置，由假定條件保證交換后產(chǎn)生的兩個新個體是不相同的，因此所有這些可能的情況產(chǎn)生的個體就構(gòu)成了集合D，所以定理1得證．定理2設(shè)兩個互異的個體：和+且一“一d，那么它們交換后產(chǎn)生的新個體：要么滿足l“一”l—d(3)要么滿足l一I一0(4)其中i，∈{1，2，?，n)，且≠，∈{1，2，?，m)，聲∈{i，j)．證明因?yàn)榻粨Q后產(chǎn)生的新個體：的第個基因位∈{，)，所以定理2顯然成立．定理2表明了對于任意兩個互異的個體，交換圖1立方體后產(chǎn)生的新個體一定在這兩個父個體所構(gòu)成的

7、超體H[min(，)，max(，)]的頂點(diǎn)上．如圖1所示，父個體一[“。]構(gòu)成了一個立方體，交換產(chǎn)生的新個體只能在這個立方體的頂點(diǎn)上．3．2二進(jìn)制編碼用二進(jìn)制編碼時，不失一般性，設(shè)每個實(shí)數(shù)用f位二進(jìn)制表示．這樣對問題(1)，每個個體∈(佃)，IBE{0，1}，這樣每個個體基因位數(shù)目L=m1．個體：可以表示為mf維的行向量，即l一[“·““州1．．·?：“一””?]．第￡代種群蜀可以表示為一個n×維普資訊http://www.cqvip.com信息與控飼mf的矩陣置一[?]t．個體；的第個長度為f的二進(jìn)制碼串轉(zhuǎn)化為實(shí)數(shù)的解碼函數(shù)

8、r為r(矗，量)=嘶上三{(∑z×2J)(5)t—I定理3設(shè)用二進(jìn)制編碼的初始種群是假定1的十進(jìn)制編碼的初始種群轉(zhuǎn)化為相應(yīng)的二進(jìn)制編碼后的種群．設(shè)經(jīng)交換操作產(chǎn)生的新個體屬于可敬集合B，則集合口中的元素數(shù)目T滿足T≥2n(n—no)-FTD(6)這里n。表示種群中第一位二進(jìn)制碼