進化計算算法在路徑優化中的應用

段嘉騰

筆者主要想要研究優化領域中和路徑優化相關的問題。在研究路徑優化問題時，主要運用的優化算法是遺傳算法。該算法在進化計算中，是應用范圍最廣的，和其他的算法相比，遺傳算法更有優勢。筆者針對遺傳算法存在的問題對遺傳算法進行了修改，提出了一些優化遺傳算法的建議，并在實際運用中證明了通過優化，遺傳算法可以更好的解決優化路徑問題。

【關鍵詞】路徑優化 遺傳算法 問題

1 遺傳算法

1.1 遺傳算法的基本思想

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

1.2 遺傳算法的步驟

遺傳算法利用自然法則中進化的過程創建模型，其具體的計算方法如下：

（1）將原始數據構造成染色體。最終構成的染色體需要滿足問題的約束條件。遺傳算法對直接解決具體問題是不管用的，而是要先將和問題相關的實例編碼成染色體的形式。在求最優解的過程中，可以有數種不同的編碼方式，但原則是必須符合約束條件，否則會影響計算的準確性。

（2）在選擇初始染色體的時候，應該秉承隨機的原則。原始種群代表的是進化初始階段的種群，初始群體要有多少數量，要根據實際情況來定。

（3）每個染色體在不停進化的時候，優化度都會不斷提高。優化度是用來評價染色體好壞的標準，遺傳算法的目的，就是要找出染色體中最優的那一個。

（4）進化的過程，有復制、交叉和變異等形式的運算，進化將產生子群體。其中主要運用了適者生存的自然法則，交叉，復制主要是來自繁殖，而變異則代表著基因突變。

（5）若達到了終止條件，則將結果輸出。得到最優解。

2 進化計算

2.1 計算的概念

計算實質上是一種物理過程，在自然界的方方面面都存在著計算，無論是花的形狀，還是天然晶體的結構，當然也包括生物的進化過程，社會的發展，宇宙的演變等。人們從自然界中獲得了很多靈感。

2.2 進化計算

進化計算也是從達爾文的遺傳定律中獲得的啟發，通過仿照生物進化的過程，設計出來的計算方法。進化計算今年來的發展非常迅速，時常有新的算法出現。因此筆者無法對下一個具體的定義。進化計算目前還是一個比較抽象的概念，進化計算主要可以分為以下幾種：遺傳算法，進化策略， 進化規劃等。近幾年這些算法都在飛速的發展，并且在眾多領域都有運用的實例，成為了進化計算框架中非常重要的部分。

3 進化算法中的遺傳算法解決路徑優化問題的具體方法

3.1 實驗方法

確定一系列特定的需要訪問的位置，從倉庫調用一定數量的車輛來訪問這些位置。那么怎么選擇，才是車輛的最優路徑，使車輛可以按照一定的順序來訪問各個位置，不僅能滿足特定的約束條件，還能使車輛花費的時間最短，路徑最優。

3.2 使用改進的遺傳算法來計算最優路徑

筆者提出一種改良后的的遺傳算法，將遺傳算法中的編碼機制改為自然數編碼機制，該機制的優點是非常的直觀。再利用三復本錦標賽的方法來進化解。經過實驗證明了改進后的算法能更好的求解出最優路徑。

3.3 具體計算步驟

3.3.1 對染色體進行編碼

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

1：0→2→6→5→0

路線

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

找最優解的時候，先將車輛要經過的位置的頭和尾連接在一起，這樣可以將染色體編碼成256173849。這樣做的缺點是缺少路線分界點，但是之后要交叉操作的時候會更加方便。只要在解碼最優解的時候，按照順序將節點插入到路線中去，就可以解決了。如果有的點時間滿足不了，或是其他約束條件滿足不了，就可以新增一條路徑從插入點插入。根據進化的的思想，路線最優的時候，就會使訪問的總費用和時間降低，因此進化過程中將盡量的往原有的路線中插入位置點。

3.4 實驗結論

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

4 總結

筆者提出了優化路徑的優化算法，并通過實驗。對改良的遺傳算法的作用進行了驗證。最終實驗結果證明了該算法是十分有效的。

參考文獻

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

[2]王凌著.智能優化算法及其應用[M].北京：清華大學出版社，2016.

[3]彭新娟基于進化計算的最大相似雙聚類分析及其應用[D].長沙：湖南大學，2013.

作者單位

廣州現代信息工程職業技術學院 廣東省廣州市 510663