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

基于遺傳算法的染色體編碼的分析第19卷第1期2010年1月重慶電子工程職業(yè)學院Vo1.19NO.1lan.2010oumalofChon咽inCoUeeofElectronicEnline基于遺傳算法的染色體編碼的分析吳焱岷(重慶大學計算機學院,重慶400044;重慶電子工程職業(yè)學院,重慶401331)摘要:遺傳算法為解決復雜問題,特別是NP類問題提供了一種全新的思路,其編碼方式也將在一定程度上決定算法效率的高低和程序設計的復雜程度.需要針對想要解決問題類型的不同而采取不同的編碼方式.關鍵詞:遺傳算法;編碼;值類型;事務類型中圖分類號:TP39文獻標識碼:A文章編號:16745787(2010)01一【)【】86一O2遺傳算法的概念最早是由BagleyJ.D在1967年提出的.而開始遺傳算法的理論和方法的系統(tǒng)性研究在1975年開始.這一開創(chuàng)性工作是由Michigan大學的J.H.Holland所實行.遺傳算法簡稱GA(GeneticAlgorithm),在本質上是一種不依賴具體問題的直接搜索方法.其基本思想是基于Darwin進化論和Mendel的遺傳學說Darwin進化論最重要的是適者生存原理它認為每一物種在發(fā)展中越來越適應環(huán)境.物種每個個體的基本特征由后代所繼承.但后代又會產生一些異于父代的新變化.Mendel遺傳學說最重要的是基因遺傳原理它認為遺傳以密碼方式存在細胞中.并以基因形式包含在染色體內每個基因有特殊的位置并控制某種特殊性質,所以.每個基因產生的個體對環(huán)境具有某種適應性.基因突變和基因雜交可產生更適應于環(huán)境的后代.經過存優(yōu)去劣的自然淘汰.適應性高的基因結構得以保存下來.遺傳算法最大的特點莫過于可以繞過復雜的數(shù)學推導而采用最直接的方式在有限空間中搜索結果.例如求函數(shù)f(x)=x*sin(10nx)+2在(一1,2)區(qū)間上的極大值,按照常規(guī)思路.需要對函數(shù)求導,找出函數(shù)的變化趨勢和拐點.才能確定最大值的位置.對于相對簡單的函數(shù).采用這些數(shù)學的方法還沒有太高的難度.但是對于復雜的函數(shù).則需要較為深厚的數(shù)學功底.同時也增加了程序設計的復雜程度對于GA.采用一套全新的思路,首先任意給定一組隨機值x.由此開始進行演化.這些值就是代表一系列原始生命.這些生命是否可以延續(xù),取決于他們的適應程度將這些隨機值帶入函數(shù)中進行運算,對得到的一系列函數(shù)值進行排序.求最大值,可以認為值較大的函數(shù)值對應的x接近我們所需要的結論,這些結果可以保留;反之.對于另外一些函數(shù)值較小的x.則表明應該被淘汰.第二步就是按照Mendel的基因理論.對這些將被淘汰的X進行演化.演化分兩步進行:(1)交叉.兩個x值交換數(shù)據(jù),類似生物界的交配,染色體進行重新重組.交換基因以期得到新的品種,新品種可能更加適應環(huán)境而得到生存的機會.也可能向相反的方向發(fā)展.從而失去生存的機會.因此通過某種方式得到新的X的值可以導致函數(shù)值增大.也可能導致減小,他們都將參加新一輪的競爭(2)變異.單一的X值進行自身的調整,這類似于生物界的染色體發(fā)生基因突變.突變后的基因也可能導致物種更加適應或更加不適應環(huán)境.因此通過突變方式后要重新評估函數(shù)值以決定新的X值的去留.同樣新的X值也必將參加新一輪的競爭通過一系列操作.我們始終保留函數(shù)值較大的一系列X.如同生物競爭中只有最強的個體才能生存下來一樣.最終我們可以得到最佳答案按照上面的思路.我們任意產生100個隨機數(shù).經過100代的進化.得到如下結論:在第27代最早出現(xiàn)最佳運算結論:f(1.8505594374083l1=3.85027363583461共使用4.828125秒.起始時間:21:54:08.31,結束時間:21:54:12.859經過反復測試.結果可以穩(wěn)定x=1.85附近.這和理論值也是非常近似的那么GA是如何保證這種收斂性的呢7原因就在于它的編碼方式可以很好地與基因理論相融合.顯然.由于X的編碼方式千差萬別,因此J.H.Holland本人也提及采用二進制才是最佳方式.這樣做的好處有兩點:收稿日期:2009一l2一l8作者簡介:吳焱岷(1974一),男,湖北武漢人,重慶大學計算機學院計算機科學技術專業(yè)2004級在職研究生,重慶電子工程職業(yè)學院計算機應用系黨總支副書記,主要從事軟件設計,網站建設方面的研究.87重慶電子工程職業(yè)學院第19卷1.數(shù)據(jù)在計算機內部就是采用二進制方式.這樣的編碼方式與計算機內部的數(shù)據(jù)表示相吻合.便于計算機的處理2.如同染色體的基因.每一位二進制數(shù)據(jù)單元就是可以進行操作的最小單元.便于對交叉與變異這兩種基本的遺傳現(xiàn)象的模擬正是將生命遺傳,進化的規(guī)律運用到程序設計中,所以程序運行符合自然規(guī)律.可以得到理想的結果遺傳算法在當時提出主要解決科學計算方面的問題.即值類型的問題.采用二進制的形式可以很好的解決編碼問題.一般我們這樣來進行操作:不失一般性.我們可以假設在(a,b)區(qū)間上搜索某一個結論.假設對于X要求精度為小數(shù)點后n位首要問題是需要確定染色體的二進制位數(shù).a到b的長度為fba),每個待編碼的數(shù)據(jù)保留到小數(shù)點后n位.表明1個單位數(shù)據(jù)中包含l0n個待編碼的數(shù).那么整個探索空間中就有(ba)10n個需要編碼的數(shù)據(jù).由于采用二進制編碼.所以要表示這么多數(shù)據(jù),需要至少m位,則有:2(b-a)10一mIn2(b-a)10n)所以m可以由ln(ba)l0的結果向上取整表示,這樣I11位的二進制數(shù)至少可以表示出(b-a)*10n個數(shù)據(jù)了.這種編碼方式對于科學計算類的問題是非常有效的.因為我們的解空間是連續(xù)的,而采用二進制編碼方式.我們也可以近似的認為其表示的數(shù)值空間也是連續(xù)的.這樣我們按照基因組成染色體的方式.可以對二進制數(shù)據(jù)進行重組,以考查哪些基因有利于問題的解決.但是需要注意的問題是.隨著GA在更加廣泛的領域加以應用.有一個新的情況出現(xiàn)了,即對于事務性的問題,二進制編碼同樣高效么?以GA在排課系統(tǒng)的應用為例.如果用二進制表示的話.必須按照定長進行切割P位表示上課教室,q位表示上課時間,每一個課程需要(p+q)位來表示未來課表中的上課時間與上課教室信息.但是由于初始狀態(tài)是隨機的.上課時間和上課教室必然存在很多的沖突或搭配不理想的地方.需要對這些問題進行逐一的統(tǒng)計及處理.那么需要將原來二進制表示的信息還原成原本表示的上課時間,上課教室信息,同時課程表的二維表格被修改成一維空間.這給操作也帶來了很多不必要的麻煩,所以有必要對原有的編碼形式重新認真考慮.針對上述問題.沒有必要一定采用一維的二進制編碼習慣.到底如何表示染色體和基因要視具體情況而定,在排課問題中.我們大可將染色體直接設計成二維模型.表示上課時間,上課教室的二維布局,將課程(含班級,教師信息)填充其中.只要保證一個單元格中僅僅放入一項課程就已經避免了上課時間,上課教室上潛在的沖突的可能性.做了這樣的調整后,在進行交叉,變異操作時,也可以以班級或老師為單位進行.而不必像二進制編碼一般隨機的抽取.這樣可以保留較好的基因.加快收斂的速度以取得更加令人滿意的結果改造后的染色體如下圖所示教室1教室2教室3教室4教室n上課時間l$.上課時間2$上課時間3$上課時間nl基因的編碼可以采用靈活的方式.不一定非要采取二進制形式,因為每一單元格中包含課程,班級,教師等信息,可以用類或結構體將其封裝起來,至于課程,班級,教師等信息的編碼則可以靈活處理.為了和數(shù)據(jù)庫進行數(shù)據(jù)的無縫交流.建議采用十進制編碼形式.以便與數(shù)據(jù)庫內部的代碼保持一致.從而可以省卻許多不必要的編碼和解碼開銷綜上所述.在GA中我們對于染色體的編碼不一定要采取二進制的形式.具體要視待解決問題的性質而定:1.對于值類型的求解問題.可以采用二進制的編碼形式.以便保持數(shù)據(jù)在計算機內部以及染色體表示上的一致.2.對以事務型的求解問題.可以靈活采用一維或多維的染色體表示形式.對基因的編碼.則可以采用更加靈活形式:十進制,字符串,結構體或類等.任何算法需要隨時代的發(fā)展而不斷的修正.在遺傳算法提出之初.我們解決的多是數(shù)值運算類型的問題,用二進制的表達形式便于保持基因內在數(shù)據(jù)與外在表現(xiàn)形式的統(tǒng)一.但是當我們把這種方法移植到事務型問題的求解上時.二進制編碼由于本身的缺陷而不足以表達豐富的含義.反而成為絆腳