周文榮

（湖北大學(xué)，湖北 武漢 430062）

基于傳統(tǒng)遺傳算法的改進(jìn)與研究

周文榮

（湖北大學(xué)，湖北 武漢 430062）

遺傳算法是一種采用啟發(fā)式的模擬自然界的進(jìn)化論過程來解決現(xiàn)實(shí)生活中復(fù)雜非線性問題的算法，該算法常用于解決組合問題的最優(yōu)化。在計(jì)算過程中通過對傳統(tǒng)的交叉過程進(jìn)行分析和改進(jìn)，使用反轉(zhuǎn)交叉的交叉方法，可以很好地解決在交叉過程中產(chǎn)生的“不良基因”問題。文章對基于傳統(tǒng)遺傳算法的改進(jìn)進(jìn)行了研究。

遺傳算法；交叉算子；不良基因

1 遺傳算法基本思想及流程

1.1 遺傳算法的基本思想

遺傳算法的基本原理就是對適者生存不適者淘汰規(guī)則的模擬，通過對個(gè)體中染色體進(jìn)行處理，然后再進(jìn)行目標(biāo)選擇，最終達(dá)到求解全局最優(yōu)的問題。

傳統(tǒng)的遺傳算法的作用流程如圖1所示。

圖1 傳統(tǒng)遺傳算法作用流程

1.2 遺傳算法的實(shí)現(xiàn)

傳統(tǒng)遺傳算法的實(shí)現(xiàn)主要包含以下幾個(gè)部分。

1.2.1 編碼方法

遺傳算法實(shí)現(xiàn)的最開始的操作是對種群進(jìn)行初始化，得到的一系列串。獲得這些串的方法叫作編碼。

在具體問題中，如何編碼出容易理解并且清晰的字符串是算法的關(guān)鍵所在。

1.2.2 求適應(yīng)度函數(shù)

在具體情況下適應(yīng)度函數(shù)能夠成為目標(biāo)函數(shù)。例如在TSP問題中，適應(yīng)度函數(shù)就是使路程最短的函數(shù)。把目標(biāo)函數(shù)稱為適應(yīng)度函數(shù)是為了更加貼近自然環(huán)境下適者生存原則。在遺傳算法中，根據(jù)適應(yīng)度函數(shù)求得適應(yīng)值。求解個(gè)體適應(yīng)度的大小的代碼叫作適應(yīng)度函數(shù)[1]。遺傳算法根據(jù)目標(biāo)函數(shù)值來選擇下一代，而目標(biāo)函數(shù)值由適應(yīng)度來表示。

1.2.3 選擇算子

選擇操作是在編碼之后，該操作不會(huì)產(chǎn)生新的染色體，選擇操作的主要目標(biāo)是將適應(yīng)度比較合適的個(gè)體選出來并保留下來，并將適應(yīng)度不合適的個(gè)體進(jìn)行淘汰，即選擇操作在保證染色體上基因完整的同時(shí)，使高性能的個(gè)體保存下來繼續(xù)進(jìn)行迭代。最常用的選擇方法為：

（1）精英選擇，顧名思義精英選擇就是選擇精英。精英選擇的過程首先是找到此次迭代中適應(yīng)度最合適的染色體和最不合適的染色體，然后比較此染色體的適應(yīng)度與之前適應(yīng)度最合適的個(gè)體適應(yīng)度的大小[2]。如果大于，則被選擇保留。并將此個(gè)體當(dāng)成目前適應(yīng)度最好的個(gè)體，并用此個(gè)體去替代適應(yīng)度最不好的個(gè)體，提高平均適應(yīng)度。

（2）錦標(biāo)賽選擇，所謂競標(biāo)賽選擇，就是從種群中選擇一部分個(gè)體進(jìn)行比賽，得勝者被選擇[3]。假設(shè)整個(gè)種群的大小為N，運(yùn)用到遺傳算法中可以解釋為從種群中選擇N/2個(gè)個(gè)體，然后比較這N/2個(gè)個(gè)體的適應(yīng)度，適應(yīng)度最合適的被保留，最不合適的被淘汰。

（3）輪盤選擇，輪盤選擇是用一個(gè)輪盤不停進(jìn)行旋轉(zhuǎn)，每次旋轉(zhuǎn)的時(shí)候，輪盤停下時(shí)，指針指向幾號，這個(gè)號就被選擇。

設(shè)種群大小是N，種群里編號為i的個(gè)體適應(yīng)度為fi，那么該個(gè)體被選擇保留的可能性為：

通過pi知道個(gè)體被選擇到的概率就是此個(gè)體的適應(yīng)度與種群適應(yīng)度之和的比。解決方法是首先隨機(jī)產(chǎn)生一個(gè)0到1之間的數(shù)，然后將個(gè)體編號為1到N，設(shè)定一個(gè)選擇算子，一般情況下選擇算子的大小為0.7，根據(jù)編號從小到大的順序計(jì)算累計(jì)概率，當(dāng)累計(jì)概率第一次大于或者等于選擇算子時(shí)，對應(yīng)的編號就是被選中的個(gè)體。

1.2.4 交叉算子

交叉算法是讓兩個(gè)父代染色體上的基因進(jìn)行替換，得到新個(gè)體。交叉操作主要方法為：

（1）單點(diǎn)交叉。在單點(diǎn)交叉中，隨機(jī)找到兩個(gè)父代，再根據(jù)交叉算子隨機(jī)找到一個(gè)基因位，將兩個(gè)父代的該基因位置后面的基因進(jìn)行替換。

（2）雙點(diǎn)交叉。在雙點(diǎn)交叉中，唯一和單點(diǎn)不同的是雙點(diǎn)交叉會(huì)選取兩個(gè)點(diǎn)來進(jìn)行替換。

（3）部分映射交叉（Part Mapped Cross，PMX）。和單點(diǎn)交叉一樣，部分映射交叉算法第一步選定兩個(gè)父代，然后在兩個(gè)父代上的基因隨機(jī)選取交叉點(diǎn)，然后根對應(yīng)的映射關(guān)系產(chǎn)生兩個(gè)新的個(gè)體。

其具體操作流程為：第一步隨機(jī)選取一個(gè)交叉點(diǎn)，第二步 對對應(yīng)單點(diǎn)之前的基因進(jìn)行替換。第三步根據(jù)替換的對應(yīng)性，找到內(nèi)部的映射關(guān)系。根據(jù)映射關(guān)系將基因全部替換，得到新的個(gè)體。

部分映射交叉具體過程的流程如圖2所示。

圖2 部分映射交叉

遺傳的目的就是獲得與父代相比基因更加優(yōu)良的個(gè)體。交配為自然進(jìn)化的關(guān)鍵，而交叉也就自然成為遺傳算法的關(guān)鍵。因?yàn)榫哂须S機(jī)性，所有可能產(chǎn)生適應(yīng)環(huán)境的新個(gè)體。也會(huì)在一定情況下產(chǎn)生不良基因，比如新產(chǎn)生的個(gè)體可能會(huì)破壞染色體中的基因重復(fù)性的規(guī)則。

1.2.5 變異算子

在生物學(xué)上，生物的變異是指染色體上的某些位上的基因發(fā)生了改變，主要有翻轉(zhuǎn)、增加、減少等途徑。

變異主要采用的方法是確定染色體上某一位的基因，然后與其他位上的基因發(fā)生替換?；虬l(fā)生了變化，導(dǎo)致產(chǎn)生了新的個(gè)體，具有新的解決方案。變異效果如圖3所示。

圖3 變異操作

在不確定隨機(jī)的問題下，遺傳算法在執(zhí)行時(shí)可能出現(xiàn)過快收斂。變異算子的出現(xiàn)減少了該情況出現(xiàn)的可能性。

2 對傳統(tǒng)遺傳算法的改進(jìn)

本文對遺傳算法過程所作的改進(jìn)是對算法執(zhí)行過程中的交叉操作進(jìn)行改進(jìn)。交叉操作可以產(chǎn)生新的基因組合的個(gè)體。單點(diǎn)交叉和雙點(diǎn)交叉方法在產(chǎn)生新個(gè)體的同時(shí)，可能會(huì)導(dǎo)致不良基因的出現(xiàn)，所謂的不良基因是指個(gè)體上的染色體上出現(xiàn)不符合實(shí)際情況的基因，這樣就必須對每次變異產(chǎn)生的基因進(jìn)行查詢，將含有不良基因的個(gè)體除去或者將其錯(cuò)誤基因修正。針對這一問題，本文提出反轉(zhuǎn)交叉的思想。

在交叉操作發(fā)生之前，第一步是進(jìn)行編碼。例如在求解貨郎擔(dān)問題時(shí)的編碼采用自然數(shù)編碼，每一座城市作為一個(gè)頂點(diǎn)，使用從1開始的自然數(shù)依次對頂點(diǎn)進(jìn)行編號，于是城市的編號不會(huì)重復(fù)。

單點(diǎn)交叉和雙點(diǎn)交叉產(chǎn)生“不良基因”的實(shí)例如圖4所示。

由圖4可知，在A1中4出現(xiàn)了兩次，B1中5也出現(xiàn)了兩次，單點(diǎn)交叉重復(fù)的基因較多。

雖然在實(shí)際的遺傳中染色體上能存在重復(fù)的基因，但是在求解貨郎擔(dān)問題時(shí)，每座城市只有唯一的編號，父代的染色體代表路徑，染色體上的基因代表了頂點(diǎn)的標(biāo)號，頂點(diǎn)的標(biāo)號不可以重復(fù)，通過對單點(diǎn)交叉和雙點(diǎn)交叉的改進(jìn)，之前研究者得到了部分映射交叉，可是在部分交叉映射中也可能同樣存在重復(fù)的基因。

在部分映射交叉重復(fù)的例子如圖5所示。

圖4 單點(diǎn)雙點(diǎn)交叉重復(fù)

圖5 部分交叉映射重復(fù)

通過圖5可知S2和T2中的編號存在重復(fù)。部分交叉映射第一步是進(jìn)行單點(diǎn)交叉，第二步是產(chǎn)生映射關(guān)系，圖7產(chǎn)生的映射關(guān)系為1與2對應(yīng)、2與3對應(yīng)、3與4對應(yīng)。對于中間染色體S1和T1的單點(diǎn)交叉位置之后的基因進(jìn)行映射，因?yàn)榇擞成浯嬖谶^度的傳遞性，對S1中的4進(jìn)行替換，首先用3替換，然后再用2替換，因?yàn)樘鎿Q具有隨機(jī)性，最后可能會(huì)停止替換，于是S2中出現(xiàn)兩個(gè)2，以此對基因4之后的基因進(jìn)行判斷，觀測各個(gè)基因是否具有映射關(guān)系，如果有映射關(guān)系就進(jìn)行判斷，沒有映射關(guān)系則進(jìn)行下一次循環(huán)，對T1也采用了同樣的操作。可知此時(shí)遍歷的時(shí)間復(fù)雜度為O(n2)。

由圖5可知部分交叉映射雖然比單點(diǎn)交叉和雙點(diǎn)交叉的交叉效果要好，但也可能存在重復(fù)。

在產(chǎn)生重復(fù)之后，存在以下幾種方法可以盡量避免“重復(fù)基因”造成的重大影響：

（1）第一種方法是削弱含有重復(fù)基因的個(gè)體的地位。這種方法允許含有重復(fù)基因的染色體繼續(xù)進(jìn)行下一次迭代，但是賦給這些特殊個(gè)體較不合適的適應(yīng)度，于是在選擇操作時(shí)，這樣特殊的染色體被淘汰。這種方法利用下一次的選擇操作將正常染色體保留下來，方法的實(shí)現(xiàn)非常簡單，但非常費(fèi)時(shí)，因?yàn)檫z傳算法在迭代過程中會(huì)花費(fèi)大量的時(shí)間產(chǎn)生無效染色體，再花費(fèi)大量的時(shí)間淘汰無效染色體，效率較低。

（2）第二種方法對無效染色體直接進(jìn)行修復(fù)。當(dāng)碰到重復(fù)的基因時(shí)，會(huì)將重復(fù)的基因用此染色體缺少的基因進(jìn)行替換，即直接將無效染色體經(jīng)過修復(fù)變成有效染色體。修復(fù)本身將消耗大量的時(shí)間。

為了有效避免出現(xiàn)重復(fù)基因的情況，本文在總結(jié)前文的交叉方法的基礎(chǔ)上，提出了新的交叉方法—反轉(zhuǎn)交叉。

反轉(zhuǎn)序列進(jìn)行交叉的過程描述為：

假設(shè)i∈{1,2,…,N}，此時(shí)N=7，a表示一條染色體，此染色體上的基因?yàn)閧a1,a2,a3,a4,a5,a6,a7}={4,6,2,7,3,1,5}，設(shè)有一個(gè)變量m∈{1,2,…,N}表示下標(biāo)，一個(gè)數(shù)組inv來表示得到的反轉(zhuǎn)序列，初始時(shí)變量m為1，數(shù)組inv的元素都為0。

第一步是求出反轉(zhuǎn)序列。反轉(zhuǎn)序列的求法是給出一個(gè)編號ifalse，然后求出在數(shù)組a中等于編號i的元素的前面大于此元素的個(gè)數(shù)，并將這個(gè)數(shù)目賦值給inv[i]。例如在{a1,a2, a3,a4,a5,a6,a7}={4,6,2,7,3,1,5}中，當(dāng)m=1時(shí)，a中為1的為第6號元素，a前五號元素都比1大，于是inv[1]=5；當(dāng)m=2時(shí)，a中為2的為第3號元素，a前兩號元素都比1大，于是inv[2]=2；當(dāng)m=3時(shí)，a中為3的為第5號元素，ae前四號元素有3個(gè)元素比3大，于是inv[3]=3，以此類推，得到反轉(zhuǎn)數(shù)組的元素分別為inv={5,2,3,0,2,0,0}。最后可知反轉(zhuǎn)數(shù)組中的元素的大于介于0和n-1之間。

運(yùn)用此方法，假設(shè)父代S={5,7,1,3,6,4,2}，父代T={4,6,2,7,3,1,5}，得到的反轉(zhuǎn)序列為S1={2,5,2,3,0,1,0}和T1={5,2,3,0,2,0,0}。

第二步是對反轉(zhuǎn)序列進(jìn)行單點(diǎn)交叉，可以得S2={2,5,2,0,2,0,0}，T2={5,2,3,3,0,1,0}。

第三步是對S2和T2進(jìn)行還原，得到子代。在求出反轉(zhuǎn)數(shù)列并進(jìn)行單點(diǎn)交叉之后，再使用以下代碼進(jìn)行還原。

//a表示為得到的子代數(shù)組，inv表示已得到的單點(diǎn)交叉之后的中間數(shù)組

還原之后得到的S3={4,6,1,3,7,5,2}，T3={5,7,2,6,3,1,4}。從S2還原得到S3的過程如表1所示。

表1 還原得到S3的過程

根據(jù)以上描述，可知反轉(zhuǎn)交叉主要分為3步，對整個(gè)過程進(jìn)行簡化，其流程如圖6所示。

圖6 反轉(zhuǎn)交叉過程

由圖6可知反轉(zhuǎn)交叉的性能要比部分交叉映射的性能好。反轉(zhuǎn)交叉有效地處理了可能存在重復(fù)基因即不良染色體的情況，為后面的操作打下了堅(jiān)實(shí)的基礎(chǔ)。通過反轉(zhuǎn)和還原可知，本算法的時(shí)間復(fù)雜度與部分交叉映射的時(shí)間復(fù)雜度一樣都為O(n2)，但因反轉(zhuǎn)交叉不會(huì)產(chǎn)生重復(fù)的基因，最后也不需要修復(fù)，而部分交叉映射可能會(huì)產(chǎn)生重復(fù)的基因，部分交叉映射在產(chǎn)生重復(fù)基因之后需要花費(fèi)較多的時(shí)間進(jìn)行修復(fù)或者進(jìn)行淘汰。

[1]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，2005.

[2]ALP O, ERKUT E, DREZNER Z. An ef fi cient genetic algorithm for p-median problem[J].Annals of Operations Research, 2003（4）：21-42.

[3]薛富強(qiáng)，葛臨東.用于調(diào)制信號特征選擇的改進(jìn)遺傳算法[J].計(jì)算機(jī)工程，2008（3）：213-214.

Research and improvement based on the traditional genetic algorithm

Zhou Wenrong
（Hubei University, Wuhan 430062, China）

Genetic algorithm is a kind of heuristic algorithm that adopts heuristics mode to simulate the natural evolution process to solve optimization of combinatorial problem. Through analysis and improvement of the traditional cross process in the calculation process, using the method of cross cross inversion. Based on that the traditional crossover process is analyzed and improved in the process of calculation, reverse-crossover method is put forward to solve the “bad genes” problem in the process of cross.

genetic algorithm; crossover operator; bad genes

周文榮（1989— ），女，湖北天門。