基于遺傳算法的染色體編碼的分析

1、基于遺傳算法的染色體編碼的分析第19卷第1期2010年1月重慶電子工程職業(yè)學(xué)院Vo1.19NO.1lan.2010oumalofChon£咽in£CoUeeofElectronicEnline基于遺傳算法的染色體編碼的分析吳探岷(重慶大學(xué)計算機學(xué)院，重慶400044;重慶電子工程職業(yè)學(xué)院，重慶401331)摘要:遺傳算法為解決復(fù)雜問題，特別是NP類問題提供了一種全新的思路，其編碼方式也將在一定程度上決定算法效率的高低和程序設(shè)計的復(fù)雜程度.需要針對想要解決問題類型的不同而米取不同的編碼方式.關(guān)鍵詞:遺傳算法;編碼;值類型;事務(wù)類型中圖分類號：TP39文獻(xiàn)標(biāo)識碼:A文章編號：1

2、6745787(2010)01)86一O2遺傳算法的概念最早是由BagleyJ.D在1967年提出的.而開始遺傳算法的理論和方法的系統(tǒng)性研究在1975年開始.這一開創(chuàng)性工作是由Michigan大學(xué)的J.H.Holland所實行.遺傳算法簡稱GA(GeneticAlgorithm),在本質(zhì)上是一種不依賴具體問題的直接搜索方法.其基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說Darwin進(jìn)化論最重要的是適者生存原理它認(rèn)為每一物種在發(fā)展中越來越適應(yīng)環(huán)境.物種每個個體的基本特征由后代所繼承.但后代又會產(chǎn)生一些異于父代的新變化.Mendel遺傳學(xué)說最重要的是基因遺傳原理它認(rèn)為遺傳以密碼方式存在

3、細(xì)胞中.并以基因形式包含在染色體內(nèi)每個基因有特殊的位置并控制某種特殊性質(zhì)，所以.每個基因產(chǎn)生的個體對環(huán)境具有某種適應(yīng)性.基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代.經(jīng)過存優(yōu)去劣的自然淘汰.適應(yīng)性高的基因結(jié)構(gòu)得以保存下來.遺傳算法最大的特點莫過于可以繞過復(fù)雜的數(shù)學(xué)推導(dǎo)而采用最直接的方式在有限空間中搜索結(jié)果.例如求函數(shù)f(x)=x*sin(10"n'x)+2在(一1,2)區(qū)間上的極大值，按照常規(guī)思路.需要對函數(shù)求導(dǎo)，找出函數(shù)的變化趨勢和拐點才能確定最大值的位置.對于相對簡單的函數(shù).采用這些數(shù)學(xué)的方法還沒有太高的難度.但是對于復(fù)雜的函數(shù).則需要較為深厚的數(shù)學(xué)功底.同時也增加了程序設(shè)

4、計的復(fù)雜程度對于GA.采用一套全新的思路，首先任意給定一組隨機值x.由此開始進(jìn)行演化.這些值就是代表一系列原始生命.這些生命是否可以延續(xù)，取決于他們的適應(yīng)程度將這些隨機值帶入函數(shù)中進(jìn)行運算，對得到的一系列函數(shù)值進(jìn)行排序.求最大值,可以認(rèn)為值較大的函數(shù)值對應(yīng)的x接近我們所需要的結(jié)論，這些結(jié)果可以保留；反之.對于另外一些函數(shù)值較小的x.則表明應(yīng)該被淘汰.第二步就是按照Mendel的基因理論.對這些將被淘汰的X進(jìn)行演化.演化分兩步進(jìn)行：(1)交叉.兩個x值交換數(shù)據(jù)，類似生物界的交配，染色體進(jìn)行重新重組.交換基因以期得到新的品種，新品種可能更加適應(yīng)環(huán)境而得到生存的機會.也可能向相反的方向發(fā)展.從而失去

5、生存的機會.因此通過某種方式得到新的X的值可以導(dǎo)致函數(shù)值增大.也可能導(dǎo)致減小，他們都將參加新一輪的競爭(2)變異.單一的X值進(jìn)行自身的調(diào)整，這類似于生物界的染色體發(fā)生基因突變.突變后的基因也可能導(dǎo)致物種更加適應(yīng)或更加不適應(yīng)環(huán)境.因此通過突變方式后要重新評估函數(shù)值以決定新的X值的去留同樣新的X值也必將參加新一輪的競爭通過一系列操作.我們始終保留函數(shù)值較大的一系列X.如同生物競爭中只有最強的個體才能生存下來一樣.最終我們可以得到最佳答案按照上面的思路.我們?nèi)我猱a(chǎn)生100個隨機數(shù).經(jīng)過100代的進(jìn)化.得到如下結(jié)論：在第27代最早出現(xiàn)最佳運算結(jié)論：f（1.8505594374083l1=3.85027

6、363583461共使用4.828125秒.起始時間：21:54:08.31,結(jié)束時問:21:54:12.859經(jīng)過反復(fù)測試.結(jié)果可以穩(wěn)定x=1.85附近.這和理論值也是非常近似的那么GA是如何保證這種收斂性的呢7原因就在于它的編碼方式可以很好地與基因理論相融合.顯然.由于X的編碼方式千差萬別，因此J.H.Holland本人也提及采用二進(jìn)制才是最佳方式.這樣做的好處有兩點：收稿日期：2009l2l8作者簡介:吳探岷（1974），男，湖北武漢人，重慶大學(xué)計算機學(xué)院計算機科學(xué)技術(shù)專業(yè)2004級在職研究生，重慶電子工程職業(yè)學(xué)院計算機應(yīng)用系黨總支副書記，主要從事軟件設(shè)計，網(wǎng)站建設(shè)方面的研究.87重慶電

7、子工程職業(yè)學(xué)院第19卷1 .數(shù)據(jù)在計算機內(nèi)部就是采用二進(jìn)制方式.這樣的編碼方式與計算機內(nèi)部的數(shù)據(jù)表示相吻合.便于計算機的處理2 .如同染色體的基因.每一位二進(jìn)制數(shù)據(jù)單元就是可以進(jìn)行操作的最小單元.便于對交叉與變異這兩種基本的遺傳現(xiàn)象的模擬正是將生命遺傳進(jìn)化的規(guī)律運用到程序設(shè)計中，所以程序運行符合自然規(guī)律.可以得到理想的結(jié)果遺傳算法在當(dāng)時提出主要解決科學(xué)計算方面的問題.即值類型的問題.采用二進(jìn)制的形式可以很好的解決編碼問題.一般我們這樣來進(jìn)行操作：不失一般性.我們可以假設(shè)在(a,b)區(qū)間上搜索某一個結(jié)論.假設(shè)又t于X要求精度為小數(shù)點后n位首要問題是需要確定染色體的二進(jìn)制位數(shù).a到b的長度為fba

8、),每個待編碼的數(shù)據(jù)保留到小數(shù)點后n位.表明1個單位數(shù)據(jù)中包含10n個待編碼的數(shù).那么整個探索空間中就有(ba)10n個需要編碼的數(shù)據(jù).由于采用二進(jìn)制編碼.所以要表示這么多數(shù)據(jù)，需要至少m位,則有：2>(b-a)10“一mIn2(b-a)10n)所以m可以由1n(ba)10的結(jié)果向上取整表示，這樣I11位的二進(jìn)制數(shù)至少可以表示出(b-a)*10n個數(shù)據(jù)了.這種編碼方式對于科學(xué)計算類的問題是非常有效的.因為我們的解空間是連續(xù)的，而采用二進(jìn)制編碼方式.我們也可以近似的認(rèn)為其表示的數(shù)值空間也是"連續(xù)”的.這樣我們按照基因組成染色體的方式.可以對二進(jìn)制數(shù)據(jù)進(jìn)行重組，以考查哪些基因有利于

9、問題的解決.但是需要注意的問題是.隨著GA在更加廣泛的領(lǐng)域加以應(yīng)用.有一個新的情況出現(xiàn)了，即對于事務(wù)性的問題，二進(jìn)制編碼同樣高效么？以GA在排課系統(tǒng)的應(yīng)用為例.如果用二進(jìn)制表示的話.必須按照定長進(jìn)行切割P位表示上課教室，q位表示上課時間，每一個課程需要(p+q)位來表示未來課表中的上課時間與上課教室信息.但是由于初始狀態(tài)是隨機的.上課時間和上課教室必然存在很多的沖突或搭配不理想的地方.需要對這些問題進(jìn)行逐一的統(tǒng)計及處理.那么需要將原來二進(jìn)制表示的信息還原成原本表示的上課時間，上課教室信息，同時課程表的二維表格被修改成一維空間.這給操作也帶來了很多不必要的麻煩，所以有必要對原有的編碼形式重新認(rèn)真

10、考慮.針對上述問題.沒有必要一定采用一維的二進(jìn)制編碼習(xí)慣.到底如何表示染色體和基因要視具體情況而定，在排課問題中.我們大可將染色體直接設(shè)計成二維模型.表示上課時間，上課教室的二維布局，將課程（含班級，教師信息）填充其中.只要保證一個單元格中僅僅放入一項課程就已經(jīng)避免了上課時間，上課教室上潛在的沖突的可能性.做了這樣白調(diào)整后，在進(jìn)行交叉，變異操作時，也可以以班級或老師為單位進(jìn)行.而不必像二進(jìn)制編碼一般隨機的抽取.這樣可以保留較好的基因.加快收斂的速度以取得更加令人滿意的結(jié)果改造后的染色體如下圖所示教室1教室2教室3教室4教室n上課時間l$.-.上課時間2$上課時間3$上課時間nl基因的編碼可以采

11、用靈活的方式.不一定非要采取二進(jìn)制形式，因為每一單元格中包含課程，班級，教師等信息，可以用類或結(jié)構(gòu)體將其封裝起來，至于課程，班級，教師等信息的編碼則可以靈活處理.為了和數(shù)據(jù)庫進(jìn)行數(shù)據(jù)的無縫交流建議采用十進(jìn)制編碼形式.以便與數(shù)據(jù)庫內(nèi)部的代碼保持一致.從而可以省卻許多不必要的編碼和解碼開銷綜上所述.在GA中我們對于染色體的編碼不一定要采取二進(jìn)制的形式.具體要視待解決問題的性質(zhì)而定：1.對于值類型的求解問題.可以采用二進(jìn)制的編碼形式.以便保持?jǐn)?shù)據(jù)在計算機內(nèi)部以及染色體表示上的一致.2.對以事務(wù)型的求解問題.可以靈活采用一維或多維的染色體表示形式.對基因的編碼.則可以采用更加靈活形式:十進(jìn)制，字符串，結(jié)構(gòu)體或類等.任何算法需要隨時代的發(fā)展而不斷的修正.在遺傳算法提出之初.我們解決的多是數(shù)值運算類型的問題，用二進(jìn)制的表達(dá)形式便于保持基因內(nèi)在數(shù)據(jù)與外在表現(xiàn)形式的