何國鋒+劉宇紅

摘要： 經(jīng)典遺傳算法通過模擬生物自然進(jìn)化來進(jìn)行求解，但往往面臨局部最優(yōu)以及不能事先確定遺傳所需要的迭代次數(shù)。該文以兩點(diǎn)間的最短路徑為對象，通過分析經(jīng)典遺傳算法中存在的問題，提出了基于閾值比較法與借鑒交叉思想的變異方法兩種思想，在最短路徑問題求解中，與經(jīng)典遺傳算法結(jié)果進(jìn)行比較分析，對相關(guān)參數(shù)進(jìn)行調(diào)整，達(dá)到了預(yù)定的效果。

關(guān)鍵詞： 最短路徑；生物進(jìn)化；遺傳算法

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）25-0162-03

1 概述

遺傳算法（Genetic Algorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法。它由美國J.Holland教授1975年首先提出，把所有可能出現(xiàn)的解做為染色體生成種群，對種群進(jìn)行模擬生物進(jìn)化的遺傳迭代操作，每代中選取對環(huán)境適應(yīng)度大的個體進(jìn)行種群的下一步迭代，從而在迭代的過程中找出最優(yōu)解。最短路徑就是在一點(diǎn)出發(fā)，到達(dá)目的點(diǎn)，找出距離最短的一條路徑，即端到端的最短路徑。在通信網(wǎng)絡(luò)、數(shù)值優(yōu)化、機(jī)器學(xué)習(xí)、模式識別、神經(jīng)網(wǎng)絡(luò)和模糊控制等方面都有著應(yīng)用。

2 最短路徑遺傳算法實現(xiàn)

2.1 遺傳算法的基本概念

染色體：在遺傳算法中，染色體指某一問題的每一種解，染色體中的每一位編碼都稱為一個基因。

種群：所有的染色體集合稱為一個種群，可以模擬生物進(jìn)化進(jìn)行遺傳操作。

選擇：通過一定的規(guī)則來選取染色體需要操作的位置，包括交叉和變異。

交叉：兩個染色體交換部分基因。

變異：對染色體中某一位基因做特定操作。

適應(yīng)度：生成的子代染色體對環(huán)境的適應(yīng)程度。

2.2 最短路徑遺傳算法的實現(xiàn)

染色體的編碼：對于一個給定的圖如圖1，因為是由11個節(jié)點(diǎn)組成的圖，所以一個染色體由11個基因組成，每個基因上包含節(jié)點(diǎn)序號，和節(jié)點(diǎn)是否選中信息，將每個基因隨機(jī)排列后組成一個碼串[1]，這個碼串就是一個染色體，如圖2，是從1節(jié)點(diǎn)到11節(jié)點(diǎn)最短路徑的染色體，其中灰色代表該節(jié)點(diǎn)未被選中，白色代表該節(jié)點(diǎn)被選中，該染色體代表的路徑為1-5-10-6-8-11。

交叉操作：交叉的方法略有不同，主要目的是交換兩條染色體的部分基因，產(chǎn)生具有新的個體。交叉時，隨機(jī)產(chǎn)生兩個數(shù)字m，n（假設(shè)m≤n），然后令染色體X的m至n基因座上的基因保持不動，其他位置的數(shù)字清空；從Y染色體的基因中從左至右選取與X染色體中m至n基因座上基因不同的基因，從左至右填入X染色體中，形成新的染色體X。同理可以得到新染色體Y [1-3]。圖3為交叉過程圖，其中m=3，n=5。

變異操作：將染色體上的某一位基因反轉(zhuǎn)。圖4為一染色體第8位基因變異前后基因排列圖。

3 算法的改進(jìn)

3.1 借鑒“交叉”思想的“變異”

經(jīng)典遺傳算法經(jīng)常會出現(xiàn)局部收斂現(xiàn)象，特別是適應(yīng)度還沒達(dá)到最大時，種群中的局部收斂的個體已經(jīng)據(jù)非常多的數(shù)量，并會在選擇操作時被大量選中遺傳到下一代中去。同時，交叉過程也會出現(xiàn)大量相同個體相交叉，相同染色體交叉是不會產(chǎn)生新種類的個體的。同時，由于交叉操作互換的基因都是左右排列順序未改變的，所以即便一條局部收斂值的染色體和另一條其他染色體交叉，產(chǎn)生的新個體也接近局部收斂的染色體，所以新生成的種群中這種局部收斂的染色體值越來越多，最后甚至占據(jù)整個種群，達(dá)到一個局部最優(yōu)。

為了消除這種局部最優(yōu)的出現(xiàn)，本文借助交叉的思想，在每次染色體交叉后，再對每條染色在一定概率下隨機(jī)做兩個基因的交換，這樣就避免了相同染色體在交叉過程中很難改變的基因間的左右順序，消除這種局部最優(yōu)的產(chǎn)生。以下簡稱“交變”操作。圖5為交變操作前后轉(zhuǎn)基因排列圖，對第4位與第6位基因交換位置。

3.2 基于閾值比較的收斂判斷

遺傳算法進(jìn)行運(yùn)算時，無法事先預(yù)測種群何時收斂，迭代數(shù)設(shè)的過小，很可能找不到最優(yōu)解；迭代數(shù)設(shè)置的過大，時間消耗大，效降低。

本文提出了一種基于閾值比較來判斷種群收斂的方法，將上一代中的最優(yōu)個體lastbest與本代中最優(yōu)個體currentbest做對比，如果lastbest優(yōu)于currentbest，則說明本代最優(yōu)解比上一代差，種群衰退，還需進(jìn)化，將變量Flag清零；如果lastbest次于currentbest，說明種群還在進(jìn)化中，變量Flag加1；如果lastbest等于currentbest，F(xiàn)lag保持不變。最后，如若Flag超過設(shè)定閾值Threshod，說明已經(jīng)連續(xù)Threshod次的最優(yōu)解是同一值，此時認(rèn)為種群已經(jīng)最優(yōu)。偽代碼如下：

上述方法雖然可能會出現(xiàn)局部最優(yōu)解，但是在不采用閾值比較時也可能存在局部最優(yōu)。因此，閾值的設(shè)定要根據(jù)算法能夠容忍的最大迭代次N來設(shè)定，經(jīng)過實驗發(fā)現(xiàn)一般設(shè)為N/3比較合適。這樣得到得解，即便是局部最優(yōu)，也已經(jīng)非常接近N次迭代得到的解，同時也保證了算法一直不收斂時可以完成N次的迭代，求出最后解。本文設(shè)計要求結(jié)合3.1中的改進(jìn)方法使用，相互彌補(bǔ)，會達(dá)到更好的效果。

4 C程序仿真結(jié)果

4.1 仿真參數(shù)

利用程序?qū)ap10和圖Map11處理，其中Map10是含有10個節(jié)點(diǎn)的圖，Map11是含有11個節(jié)點(diǎn)的圖，基中矩陣4.1是第2節(jié)中圖1的無向圖。

4.2 借鑒“交叉”思想的“變異”方法測試

（1） 驗證交變思想

圖6和7分別為經(jīng)典遺傳算法對Map10和Map11求解最短路徑輸出文件記錄截圖。

x通過程序輸出文件里的記錄可以看出，當(dāng)用經(jīng)典遺傳算法求Map10和Map11最短路徑時，Map10可以找出最優(yōu)解，而Map11找到了局部最優(yōu)解，不過結(jié)果已經(jīng)非常接近最優(yōu)解。而通過觀察各代的平均值可以看出平均值大致相等，說明整個種群已經(jīng)達(dá)到一個局部穩(wěn)定相似，通過普通交叉很難再形成更優(yōu)的新物種，需要人為對其基因進(jìn)行小幅度調(diào)整。endprint

圖8和圖9為引進(jìn)“交叉”思想的“變異”方法后，再對Map10和Map11求最短路徑的結(jié)果。

通過結(jié)果數(shù)據(jù)可以看出，通過引進(jìn)這種類似于“交叉”思想的“變異”后，算法對兩個圖都找到了最優(yōu)解。下面研究Pe選取不同值時對結(jié)果是否存在影響。

表1和表2分別為對Map10和Map11在Pe取值為0到1時第一次找到最優(yōu)解的迭代次數(shù)記錄，其中X表示未找到最優(yōu)解，即產(chǎn)生了局部最優(yōu)解?？梢园l(fā)現(xiàn)，除了Map11中Pe=0（即不引入交變操作）和Pe=0.1時未能找到最優(yōu)解，其他測試情況均找到最優(yōu)解。而Pe=0.1時經(jīng)典遺傳算法同樣未找到最優(yōu)解，說明引入交變思想不會阻礙找到最優(yōu)解。

將表1，表2中數(shù)據(jù)繪制成如圖10、圖11的曲線圖，可以直觀的看出，Pe值的大小會對算法的收斂速度造成影響。在Pe值為0.2-0.3與0.6-0.8間，初次找到最優(yōu)解的迭代次數(shù)最小。造成這種雙凹陷的原因是當(dāng)Pe值過小時，交變操作對算法的影響太小，算法基本上靠經(jīng)典遺傳算法來對結(jié)果進(jìn)行控制；當(dāng)Pe值過大時，對算法的影響又太大，打亂了種群中大部分染色體基因順序，使收斂減緩。因此，選取合適的Pe值也會使算法更優(yōu)，仿真里選取Pe=0.3。

4.3 改進(jìn)點(diǎn)2判斷收斂方法測試

圖6、圖7、圖8和圖9都是沒有判斷種群是何時收斂的，都是完成最大迭代次數(shù)（本實現(xiàn)中為200）后才輸出結(jié)果。而對圖8和圖9輸出記錄文件查找發(fā)現(xiàn)，對于Map10和Map11分別在第8次和第18次迭代中就已經(jīng)找出最優(yōu)解，如圖10和圖11所示，其它180多次的迭代浪費(fèi)了大量時間。

圖12和圖13是通過閾值比較法判斷種群是否收斂后的結(jié)果，可以看出，算法分別在40次和50次迭代后找出最優(yōu)解，避免了不必要的迭代。

5 結(jié)束語

通過前面仿真結(jié)果已經(jīng)可以看出，改進(jìn)的遺傳算法在求最短路徑的問題中取得了不錯的效果，并且效率也有所提升。同時這種改進(jìn)方法思想也適用于其他應(yīng)用；另一方面，改進(jìn)的遺傳算法也不能完全抑制局部最優(yōu)，要對各參數(shù)進(jìn)行測試選取?？傮w來說，這種改進(jìn)的遺傳算法達(dá)到了預(yù)定的效果。下一步將繼續(xù)完善算法，并在其他問題中測試。

參考文獻(xiàn)：

[1] 康曉軍，王茂才.基于遺傳算法的最短路徑問題求解[J].計算機(jī)工程與應(yīng)用， 2008，44（23）：23.

[2] 張勇.實數(shù)遺傳算法的改進(jìn)研究[D].東北農(nóng)業(yè)大學(xué)， 2014：13-14.

[3] 張書源，郭聰.基于遺傳算法的最短路徑問題及其MATLAB實現(xiàn)[J].交通世界（運(yùn)輸車輛），2009（6）：104-105

[4] 邊霞，米良.遺傳算法理論及其應(yīng)用研究進(jìn)展[J].計算機(jī)應(yīng)用研究， 2010，27（7）：2427.

[5] 汪定偉，王俊偉，王洪峰.智能優(yōu)化方法[M].高等教育出版社，2007：279-306.

[6] 徐綜本.計算智能——模擬進(jìn)化計算[M].北京：高等教育出版社，2005：1-101.

[7] 陳國良，王熙法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，2003：1-162.

[8] 賀毅朝，宋建民，張敬敏，等.遺傳算法求解靜態(tài)與動態(tài)背包問題的研究[J].計算機(jī)應(yīng)用研究， 2014（32）.endprint