吳焱岷

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

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

吳焱岷

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

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

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

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

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

Mendel遺傳學(xué)說最重要的是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個(gè)基因有特殊的位置并控制某種特殊性質(zhì),所以，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性?；蛲蛔兒突螂s交可產(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ī)思路，需要對(duì)函數(shù)求導(dǎo)，找出函數(shù)的變化趨勢(shì)和拐點(diǎn)，才能確定最大值的位置。對(duì)于相對(duì)簡(jiǎn)單的函數(shù)，采用這些數(shù)學(xué)的方法還沒有太高的難度，但是對(duì)于復(fù)雜的函數(shù)，則需要較為深厚的數(shù)學(xué)功底，同時(shí)也增加了程序設(shè)計(jì)的復(fù)雜程度。

對(duì)于GA，采用一套全新的思路，首先任意給定一組隨機(jī)值x，由此開始進(jìn)行演化，這些值就是代表一系列原始生命，這些生命是否可以延續(xù)，取決于他們的適應(yīng)程度。將這些隨機(jī)值帶入函數(shù)中進(jìn)行運(yùn)算，對(duì)得到的一系列函數(shù)值進(jìn)行排序，求最大值，可以認(rèn)為值較大的函數(shù)值對(duì)應(yīng)的x接近我們所需要的結(jié)論，這些結(jié)果可以保留；反之，對(duì)于另外一些函數(shù)值較小的x，則表明應(yīng)該被淘汰。

第二步就是按照Mendel的基因理論，對(duì)這些將被淘汰的x進(jìn)行演化，演化分兩步進(jìn)行：

（1）交叉。兩個(gè)x值交換數(shù)據(jù)，類似生物界的交配，染色體進(jìn)行重新重組，交換基因以期得到新的品種，新品種可能更加適應(yīng)環(huán)境而得到生存的機(jī)會(huì)，也可能向相反的方向發(fā)展，從而失去生存的機(jī)會(huì)。因此通過某種方式得到新的x的值可以導(dǎo)致函數(shù)值增大，也可能導(dǎo)致減小，他們都將參加新一輪的競(jìng)爭(zhēng)。

（2）變異。單一的x值進(jìn)行自身的調(diào)整，這類似于生物界的染色體發(fā)生基因突變，突變后的基因也可能導(dǎo)致物種更加適應(yīng)或更加不適應(yīng)環(huán)境，因此通過突變方式后要重新評(píng)估函數(shù)值以決定新的x值的去留，同樣新的x值也必將參加新一輪的競(jìng)爭(zhēng)。

通過一系列操作，我們始終保留函數(shù)值較大的一系列x，如同生物競(jìng)爭(zhēng)中只有最強(qiáng)的個(gè)體才能生存下來一樣，最終我們可以得到最佳答案。

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

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

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

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

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

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

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

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

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

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

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

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

這種編碼方式對(duì)于科學(xué)計(jì)算類的問題是非常有效的，因?yàn)槲覀兊慕饪臻g是連續(xù)的，而采用二進(jìn)制編碼方式，我們也可以近似的認(rèn)為其表示的數(shù)值空間也是 “連續(xù)”的。這樣我們按照基因組成染色體的方式，可以對(duì)二進(jìn)制數(shù)據(jù)進(jìn)行重組，以考查哪些基因有利于問題的解決。但是需要注意的問題是，隨著GA在更加廣泛的領(lǐng)域加以應(yīng)用，有一個(gè)新的情況出現(xiàn)了，即對(duì)于事務(wù)性的問題，二進(jìn)制編碼同樣高效么？

以GA在排課系統(tǒng)的應(yīng)用為例，如果用二進(jìn)制表示的話，必須按照定長(zhǎng)進(jìn)行切割p位表示上課教室、q位表示上課時(shí)間，每一個(gè)課程需要（p＋q）位來表示未來課表中的上課時(shí)間與上課教室信息，但是由于初始狀態(tài)是隨機(jī)的，上課時(shí)間和上課教室必然存在很多的沖突或搭配不理想的地方，需要對(duì)這些問題進(jìn)行逐一的統(tǒng)計(jì)及處理，那么需要將原來二進(jìn)制表示的信息還原成原本表示的上課時(shí)間、上課教室信息，同時(shí)課程表的二維表格被修改成一維空間，這給操作也帶來了很多不必要的麻煩，所以有必要對(duì)原有的編碼形式重新認(rèn)真考慮。

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

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

基因的編碼可以采用靈活的方式，不一定非要采取二進(jìn)制形式，因?yàn)槊恳粏卧裰邪n程、班級(jí)、教師等信息，可以用類或結(jié)構(gòu)體將其封裝起來，至于課程、班級(jí)、教師等信息的編碼則可以靈活處理，為了和數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)的無縫交流，建議采用十進(jìn)制編碼形式，以便與數(shù)據(jù)庫(kù)內(nèi)部的代碼保持一致，從而可以省卻許多不必要的編碼和解碼開銷。

綜上所述，在GA中我們對(duì)于染色體的編碼不一定要采取二進(jìn)制的形式，具體要視待解決問題的性質(zhì)而定：

1.對(duì)于值類型的求解問題，可以采用二進(jìn)制的編碼形式，以便保持?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部以及染色體表示上的一致。

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

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

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

TP39

A

1674－5787（2010）01－0086－02

2009-12-18

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

責(zé)任編輯 王榮輝