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

周文榮

（湖北大學，湖北 武漢 430062）

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

周文榮

（湖北大學，湖北 武漢 430062）

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

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

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

1.1 遺傳算法的基本思想

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

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

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

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

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

1.2.1 編碼方法

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

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

1.2.2 求適應度函數(shù)

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

1.2.3 選擇算子

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

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

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

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

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

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

1.2.4 交叉算子

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

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

（2）雙點交叉。在雙點交叉中，唯一和單點不同的是雙點交叉會選取兩個點來進行替換。

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

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

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

圖2 部分映射交叉

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

1.2.5 變異算子

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

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

圖3 變異操作

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

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

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

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

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

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

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

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

圖4 單點雙點交叉重復

圖5 部分交叉映射重復

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

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

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

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

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

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

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

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

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

運用此方法，假設父代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)序列進行單點交叉，可以得S2={2,5,2,0,2,0,0}，T2={5,2,3,3,0,1,0}。

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

//a表示為得到的子代數(shù)組，inv表示已得到的單點交叉之后的中間數(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步，對整個過程進行簡化，其流程如圖6所示。

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

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

[1]周明，孫樹棟.遺傳算法原理及應用[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]薛富強，葛臨東.用于調(diào)制信號特征選擇的改進遺傳算法[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— ），女，湖北天門。