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

吳焱岷

（重慶大學(xué) 計算機(jī)學(xué)院，重慶400044；重慶電子工程職業(yè)學(xué)院，重慶401331）

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

吳焱岷

（重慶大學(xué) 計算機(jī)學(xué)院，重慶400044；重慶電子工程職業(yè)學(xué)院，重慶401331）

遺傳算法為解決復(fù)雜問題，特別是NP類問題提供了一種全新的思路，其編碼方式也將在一定程度上決定算法效率的高低和程序設(shè)計的復(fù)雜程度，需要針對想要解決問題類型的不同而采取不同的編碼方式。

遺傳算法；編碼；值類型；事務(wù)類型

遺傳算法的概念最早是由Bagley J.D在1967年提出的,而開始遺傳算法的理論和方法的系統(tǒng)性研究在1975年開始，這一開創(chuàng)性工作是由Michigan大學(xué)的J.H.Holland所實(shí)行。遺傳算法簡稱GA(Genetic Algorithm)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法，其基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說。

Darwin進(jìn)化論最重要的是適者生存原理。它認(rèn)為每一物種在發(fā)展中越來越適應(yīng)環(huán)境，物種每個個體的基本特征由后代所繼承，但后代又會產(chǎn)生一些異于父代的新變化。

Mendel遺傳學(xué)說最重要的是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(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)得以保存下來。

遺傳算法最大的特點(diǎn)莫過于可以繞過復(fù)雜的數(shù)學(xué)推導(dǎo)而采用最直接的方式在有限空間中搜索結(jié)果。例如求函數(shù) f(x)=x*sin(10πx)+2 在（-1，2）區(qū)間上的極大值，按照常規(guī)思路，需要對函數(shù)求導(dǎo)，找出函數(shù)的變化趨勢和拐點(diǎn)，才能確定最大值的位置。對于相對簡單的函數(shù)，采用這些數(shù)學(xué)的方法還沒有太高的難度，但是對于復(fù)雜的函數(shù)，則需要較為深厚的數(shù)學(xué)功底，同時也增加了程序設(shè)計的復(fù)雜程度。

對于GA，采用一套全新的思路，首先任意給定一組隨機(jī)值x，由此開始進(jìn)行演化，這些值就是代表一系列原始生命，這些生命是否可以延續(xù)，取決于他們的適應(yīng)程度。將這些隨機(jī)值帶入函數(shù)中進(jìn)行運(yù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)境而得到生存的機(jī)會，也可能向相反的方向發(fā)展，從而失去生存的機(jī)會。因此通過某種方式得到新的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，如同生物競爭中只有最強(qiáng)的個體才能生存下來一樣，最終我們可以得到最佳答案。

按照上面的思路，我們?nèi)我猱a(chǎn)生100個隨機(jī)數(shù)，經(jīng)過100代的進(jìn)化，得到如下結(jié)論：

在第27代最早出現(xiàn)最佳運(yùn)算結(jié)論：

共使用4.828125秒，起始時間：21:54:08.31，結(jié)束時間：21:54:12.859

經(jīng)過反復(fù)測試，結(jié)果可以穩(wěn)定x=1.85附近，這和理論值也是非常近似的。那么GA是如何保證這種收斂性的呢？原因就在于它的編碼方式可以很好地與基因理論相融合。

顯然，由于x的編碼方式千差萬別，因此J.H.Holland本人也提及采用二進(jìn)制才是最佳方式，這樣做的好處有兩點(diǎn)：

1.數(shù)據(jù)在計算機(jī)內(nèi)部就是采用二進(jìn)制方式，這樣的編碼方式與計算機(jī)內(nèi)部的數(shù)據(jù)表示相吻合，便于計算機(jī)的處理。

2.如同染色體的基因，每一位二進(jìn)制數(shù)據(jù)單元就是可以進(jìn)行操作的最小單元，便于對交叉與變異這兩種基本的遺傳現(xiàn)象的模擬。

正是將生命遺傳、進(jìn)化的規(guī)律運(yùn)用到程序設(shè)計中，所以程序運(yùn)行符合自然規(guī)律，可以得到理想的結(jié)果。

遺傳算法在當(dāng)時提出主要解決科學(xué)計算方面的問題，即值類型的問題，采用二進(jìn)制的形式可以很好的解決編碼問題，一般我們這樣來進(jìn)行操作：

不失一般性，我們可以假設(shè)在（a,b）區(qū)間上搜索某一個結(jié)論，假設(shè)對于x要求精度為小數(shù)點(diǎn)后n位。

首要問題是需要確定染色體的二進(jìn)制位數(shù)，a到b的長度為（b-a），每個待編碼的數(shù)據(jù)保留到小數(shù)點(diǎn)后n位，表明1個單位數(shù)據(jù)中包含10n個待編碼的數(shù)，那么整個探索空間中就有（b-a）*10n個需要編碼的數(shù)據(jù)，由于采用二進(jìn)制編碼，所以要表示這么多數(shù)據(jù)，需要至少m位，則有：

所以 m 可以由 ln2（（b-a）*10n)的結(jié)果向上取整表示，這樣m位的二進(jìn)制數(shù)至少可以表示出（b-a）*10n個數(shù)據(jù)了。

這種編碼方式對于科學(xué)計算類的問題是非常有效的，因?yàn)槲覀兊慕饪臻g是連續(xù)的，而采用二進(jìn)制編碼方式，我們也可以近似的認(rèn)為其表示的數(shù)值空間也是 “連續(xù)”的。這樣我們按照基因組成染色體的方式，可以對二進(jìn)制數(shù)據(jù)進(jìn)行重組，以考查哪些基因有利于問題的解決。但是需要注意的問題是，隨著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ī)的，上課時間和上課教室必然存在很多的沖突或搭配不理想的地方，需要對這些問題進(jìn)行逐一的統(tǒng)計及處理，那么需要將原來二進(jìn)制表示的信息還原成原本表示的上課時間、上課教室信息，同時課程表的二維表格被修改成一維空間，這給操作也帶來了很多不必要的麻煩，所以有必要對原有的編碼形式重新認(rèn)真考慮。

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

改造后的染色體如下圖所示

基因的編碼可以采用靈活的方式，不一定非要采取二進(jìn)制形式，因?yàn)槊恳粏卧裰邪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ù)在計算機(jī)內(nèi)部以及染色體表示上的一致。

2.對以事務(wù)型的求解問題，可以靈活采用一維或多維的染色體表示形式，對基因的編碼，則可以采用更加靈活形式：十進(jìn)制、字符串、結(jié)構(gòu)體或類等。

任何算法需要隨時代的發(fā)展而不斷的修正，在遺傳算法提出之初，我們解決的多是數(shù)值運(yùn)算類型的問題，用二進(jìn)制的表達(dá)形式便于保持基因內(nèi)在數(shù)據(jù)與外在表現(xiàn)形式的統(tǒng)一，但是當(dāng)我們把這種方法移植到事務(wù)型問題的求解上時，二進(jìn)制編碼由于本身的缺陷而不足以表達(dá)豐富的含義，反而成為絆腳石，我們可以對其編碼方式進(jìn)行調(diào)整，以適應(yīng)問題求解的需要。

在遺傳算法提出之機(jī)，計算機(jī)硬件水平相對較低，需要充分考慮硬件上時間、空間的開銷，而如今硬件水平高速發(fā)展，犧牲一定的空間、時間而帶來程序設(shè)計難度的降低也不失是一種可行的方案。

TP39

A

1674－5787（2010）01－0086－02

2009-12-18

吳焱岷（1974—），男，湖北武漢人，重慶大學(xué)計算機(jī)學(xué)院計算機(jī)科學(xué)技術(shù)專業(yè)2004級在職研究生，重慶電子工程職業(yè)學(xué)院計算機(jī)應(yīng)用系黨總支副書記，主要從事軟件設(shè)計、網(wǎng)站建設(shè)方面的研究。

責(zé)任編輯 王榮輝