進(jìn)化計(jì)算算法在路徑優(yōu)化中的應(yīng)用

段嘉騰

筆者主要想要研究?jī)?yōu)化領(lǐng)域中和路徑優(yōu)化相關(guān)的問(wèn)題。在研究路徑優(yōu)化問(wèn)題時(shí)，主要運(yùn)用的優(yōu)化算法是遺傳算法。該算法在進(jìn)化計(jì)算中，是應(yīng)用范圍最廣的，和其他的算法相比，遺傳算法更有優(yōu)勢(shì)。筆者針對(duì)遺傳算法存在的問(wèn)題對(duì)遺傳算法進(jìn)行了修改，提出了一些優(yōu)化遺傳算法的建議，并在實(shí)際運(yùn)用中證明了通過(guò)優(yōu)化，遺傳算法可以更好的解決優(yōu)化路徑問(wèn)題。

【關(guān)鍵詞】路徑優(yōu)化 遺傳算法 問(wèn)題

1 遺傳算法

1.1 遺傳算法的基本思想

遺傳算法是在上世紀(jì)70年代被提出來(lái)的。遺傳算法是從達(dá)爾文的遺傳定律受到的啟迪，達(dá)爾文遺傳定律包括自然選擇，主要是對(duì)生物進(jìn)行篩選，和適者生存主要是來(lái)完成生物的進(jìn)化。這也是遺傳算法所運(yùn)用的原理，最開始遺傳算法是為了解釋自然界中生物為了適應(yīng)環(huán)境，而不斷進(jìn)化的復(fù)雜過(guò)程。后來(lái)仿照生物進(jìn)化的過(guò)程，將遺傳算法引入了優(yōu)化算法中。該算法主要是為了服務(wù)于優(yōu)化計(jì)算。一個(gè)問(wèn)題的解決方法很多，需要優(yōu)化選擇最優(yōu)解的時(shí)候，遺傳算法將這個(gè)問(wèn)題的原始狀態(tài)看作是一個(gè)種群，其中的每一種狀態(tài)都將編碼為染色體。初始群體會(huì)在條件的約束下，不斷進(jìn)化，最終得出最優(yōu)解，從而產(chǎn)生新的種群。從最后一個(gè)種群中找出最優(yōu)解，解碼成問(wèn)題的最優(yōu)路徑，就是遺傳算法在實(shí)踐中的運(yùn)用。

1.2 遺傳算法的步驟

遺傳算法利用自然法則中進(jìn)化的過(guò)程創(chuàng)建模型，其具體的計(jì)算方法如下：

（1）將原始數(shù)據(jù)構(gòu)造成染色體。最終構(gòu)成的染色體需要滿足問(wèn)題的約束條件。遺傳算法對(duì)直接解決具體問(wèn)題是不管用的，而是要先將和問(wèn)題相關(guān)的實(shí)例編碼成染色體的形式。在求最優(yōu)解的過(guò)程中，可以有數(shù)種不同的編碼方式，但原則是必須符合約束條件，否則會(huì)影響計(jì)算的準(zhǔn)確性。

（2）在選擇初始染色體的時(shí)候，應(yīng)該秉承隨機(jī)的原則。原始種群代表的是進(jìn)化初始階段的種群，初始群體要有多少數(shù)量，要根據(jù)實(shí)際情況來(lái)定。

（3）每個(gè)染色體在不停進(jìn)化的時(shí)候，優(yōu)化度都會(huì)不斷提高。優(yōu)化度是用來(lái)評(píng)價(jià)染色體好壞的標(biāo)準(zhǔn)，遺傳算法的目的，就是要找出染色體中最優(yōu)的那一個(gè)。

（4）進(jìn)化的過(guò)程，有復(fù)制、交叉和變異等形式的運(yùn)算，進(jìn)化將產(chǎn)生子群體。其中主要運(yùn)用了適者生存的自然法則，交叉，復(fù)制主要是來(lái)自繁殖，而變異則代表著基因突變。

（5）若達(dá)到了終止條件，則將結(jié)果輸出。得到最優(yōu)解。

2 進(jìn)化計(jì)算

2.1 計(jì)算的概念

計(jì)算實(shí)質(zhì)上是一種物理過(guò)程，在自然界的方方面面都存在著計(jì)算，無(wú)論是花的形狀，還是天然晶體的結(jié)構(gòu)，當(dāng)然也包括生物的進(jìn)化過(guò)程，社會(huì)的發(fā)展，宇宙的演變等。人們從自然界中獲得了很多靈感。

2.2 進(jìn)化計(jì)算

進(jìn)化計(jì)算也是從達(dá)爾文的遺傳定律中獲得的啟發(fā)，通過(guò)仿照生物進(jìn)化的過(guò)程，設(shè)計(jì)出來(lái)的計(jì)算方法。進(jìn)化計(jì)算今年來(lái)的發(fā)展非常迅速，時(shí)常有新的算法出現(xiàn)。因此筆者無(wú)法對(duì)下一個(gè)具體的定義。進(jìn)化計(jì)算目前還是一個(gè)比較抽象的概念，進(jìn)化計(jì)算主要可以分為以下幾種：遺傳算法，進(jìn)化策略， 進(jìn)化規(guī)劃等。近幾年這些算法都在飛速的發(fā)展，并且在眾多領(lǐng)域都有運(yùn)用的實(shí)例，成為了進(jìn)化計(jì)算框架中非常重要的部分。

3 進(jìn)化算法中的遺傳算法解決路徑優(yōu)化問(wèn)題的具體方法

3.1 實(shí)驗(yàn)方法

確定一系列特定的需要訪問(wèn)的位置，從倉(cāng)庫(kù)調(diào)用一定數(shù)量的車輛來(lái)訪問(wèn)這些位置。那么怎么選擇，才是車輛的最優(yōu)路徑，使車輛可以按照一定的順序來(lái)訪問(wèn)各個(gè)位置，不僅能滿足特定的約束條件，還能使車輛花費(fèi)的時(shí)間最短，路徑最優(yōu)。

3.2 使用改進(jìn)的遺傳算法來(lái)計(jì)算最優(yōu)路徑

筆者提出一種改良后的的遺傳算法，將遺傳算法中的編碼機(jī)制改為自然數(shù)編碼機(jī)制，該機(jī)制的優(yōu)點(diǎn)是非常的直觀。再利用三復(fù)本錦標(biāo)賽的方法來(lái)進(jìn)化解。經(jīng)過(guò)實(shí)驗(yàn)證明了改進(jìn)后的算法能更好的求解出最優(yōu)路徑。

3.3 具體計(jì)算步驟

3.3.1 對(duì)染色體進(jìn)行編碼

采用的新的編碼機(jī)制使得編碼的過(guò)程十分直接，對(duì)各種規(guī)模的問(wèn)題都可以應(yīng)對(duì)。并且要設(shè)立特殊位置，作為基因位。而訪問(wèn)特定位置的順序就是所需要求的解（要包括不可行解）。每個(gè)基因位都有其需要滿足的約束條件。如位置地點(diǎn)、需要到達(dá)的時(shí)間等。例如，若問(wèn)題的解路線為：

1：0→2→6→5→0

路線

2：0→8→3→7→1→0

找最優(yōu)解的時(shí)候，先將車輛要經(jīng)過(guò)的位置的頭和尾連接在一起，這樣可以將染色體編碼成256173849。這樣做的缺點(diǎn)是缺少路線分界點(diǎn)，但是之后要交叉操作的時(shí)候會(huì)更加方便。只要在解碼最優(yōu)解的時(shí)候，按照順序?qū)⒐?jié)點(diǎn)插入到路線中去，就可以解決了。如果有的點(diǎn)時(shí)間滿足不了，或是其他約束條件滿足不了，就可以新增一條路徑從插入點(diǎn)插入。根據(jù)進(jìn)化的的思想，路線最優(yōu)的時(shí)候，就會(huì)使訪問(wèn)的總費(fèi)用和時(shí)間降低，因此進(jìn)化過(guò)程中將盡量的往原有的路線中插入位置點(diǎn)。

3.4 實(shí)驗(yàn)結(jié)論

通過(guò)改良的遺傳算法，可以解決企業(yè)、郵政快遞、高速公路配貨過(guò)程中找尋最優(yōu)路徑的問(wèn)題。其他行業(yè)關(guān)于最優(yōu)路徑的問(wèn)題也能得到解決。研究該遺傳算法有助于提高相關(guān)企業(yè)的利潤(rùn)、企業(yè)也能為顧客提高更好的服務(wù)，人們的需求也能得到最大程度得到滿足。因此該算法的推廣和運(yùn)用是非常有意義的。

4 總結(jié)

筆者提出了優(yōu)化路徑的優(yōu)化算法，并通過(guò)實(shí)驗(yàn)。對(duì)改良的遺傳算法的作用進(jìn)行了驗(yàn)證。最終實(shí)驗(yàn)結(jié)果證明了該算法是十分有效的。

參考文獻(xiàn)

[1]黃嵐，王康平，周春光，原媛，龐巍.基于螞蟻算法的混合方法求解旅行商問(wèn)題[J].吉林大學(xué)學(xué)報(bào)（理學(xué)版），2012（04）.

[2]王凌著.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2016.

[3]彭新娟基于進(jìn)化計(jì)算的最大相似雙聚類分析及其應(yīng)用[D].長(zhǎng)沙：湖南大學(xué)，2013.

作者單位

廣州現(xiàn)代信息工程職業(yè)技術(shù)學(xué)院 廣東省廣州市 510663