改進(jìn)的遺傳算法在最短路徑中的應(yīng)用

何國(guó)鋒+劉宇紅

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

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

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

1 概述

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

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

2.1 遺傳算法的基本概念

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

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

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

交叉：兩個(gè)染色體交換部分基因。

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

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

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

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

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

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

3 算法的改進(jìn)

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

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

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

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

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

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

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

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

4.1 仿真參數(shù)

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

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

（1） 驗(yàn)證交變思想

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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