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

1、進(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)題?！娟P(guān)鍵詞】路徑優(yōu)化 遺傳算法 問(wèn)題1 遺傳算法1.1 遺傳算法的基本思想遺傳算法是在上世紀(jì) 70 年代被提出來(lái)的。遺傳算法是 從達(dá)爾文的遺傳定律受到的啟迪，達(dá)爾文遺傳定律包括自然 選擇，主要是對(duì)生物進(jìn)行篩選，和適者生存主要是來(lái)完成生 物的進(jìn)

2、化。這也是遺傳算法所運(yùn)用的原理，最開(kāi)始遺傳算法 是為了解釋自然界中生物為了適應(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)造成染色體

3、。最終構(gòu)成的染色體需 要滿(mǎn)足問(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)化初始階段的種群，初始群體要有多少 盜浚 ?要根據(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)用了適

4、者生存的自然法則， 交叉，復(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ì)算主要可以分為以下幾種：

5、遺傳算法， 進(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ù) 量的車(chē)輛來(lái)訪問(wèn)這些位置。那么怎么選擇，才是車(chē)輛的最優(yōu) 路徑，使車(chē)輛可以按照一定的順序來(lái)訪問(wèn)各個(gè)位置，不僅能 滿(mǎn)足特定的約束條件，還能使車(chē)輛花費(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í)

6、驗(yàn)證明了改進(jìn) 后的算法能更好的求解出最優(yōu)路徑。3.3 具體計(jì)算步驟對(duì)染色體進(jìn)行編碼 采用的新的編碼機(jī)制使得編碼的過(guò)程十分直接，對(duì)各種 規(guī)模的問(wèn)題都可以應(yīng)對(duì)。 并且要設(shè)立特殊位置， 作為基因位。 而訪問(wèn)特定位置的順序就是所需要求的解（要包括不可行 解）。每個(gè)基因位都有其需要滿(mǎn)足的約束條件。 如位置地點(diǎn)、 需要到達(dá)的時(shí)間等。例如，若問(wèn)題的解路線(xiàn)為：1 : 0宀2宀6宀5宀0路線(xiàn)2 : 0宀8宀3宀7宀1宀0找最優(yōu)解的時(shí)候，先將車(chē)輛要經(jīng)過(guò)的位置的頭和尾連接 在一起，這樣可以將染色體編碼成256173849 。這樣做的缺點(diǎn)是缺少路線(xiàn)分界點(diǎn)，但是之后要交叉操作的時(shí)候會(huì)更加方 便。只要在解碼最優(yōu)解的時(shí)候，

7、按照順序?qū)⒐?jié)點(diǎn)插入到路線(xiàn) 中去，就可以解決了。如果有的點(diǎn)時(shí)間滿(mǎn)足不了，或是其他 約束條件滿(mǎn)足不了，就可以新增一條路徑從插入點(diǎn)插入。根 據(jù)進(jìn)化的的思想，路線(xiàn)最優(yōu)的時(shí)候，就會(huì)使訪問(wèn)的總費(fèi)用和 時(shí)間降低，因此進(jìn)化過(guò)程中將盡量的往原有的路線(xiàn)中插入位置點(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ù)，人們的需求也 能得到最大程度得到滿(mǎn)足。因此該算法的推廣和運(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 （ 0