[發明專利]一種基于遺傳算法的求指定點約束下的路由方法

在審

• 申請號: 201710103929.0
• 申請日: 2017-02-24
• 公開（公告）號: CN106875064A
• 公開（公告）日: 2017-06-20
• 發明（設計）人: 楊剛;姚洪濤;姜福義
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12
• 代理公司: 西安西達專利代理有限責任公司61202
• 代理人: 劉華

技術領域

本發明屬于網絡圖路徑搜索技術領域，具體涉及一種指定點約束條件下利用改進的遺傳算法搜索到最優路徑的方法。

背景技術

路徑規劃問題是傳統的組合優化問題，有著較為廣泛的實際應用。比較經典的路徑規劃問題是求解網絡圖各個點之間的的最多路徑，不過，隨著網絡圖規模的增大和對高效率的需求，在某些特定應用場景中，我們需要求解網絡圖中在指定點約束下的最短路徑。

目前，關于網絡圖中指定點約束下的最短路徑的方法主要有：窮盡搜索算法和啟發式搜索法和智能搜索算法。

窮舉搜索算法，該算法又細分為深度度優先搜索和廣度優先搜索；深度優先搜索是指從起點選擇某一擴展節點，之后接著再擴展節點上繼續搜索，直到搜索到終點，或者當沒有搜索到合理的路徑時進行回溯。寬度優先搜索是指從起點尋找終點的過程中，根據節點的出度情況依次擴展，每一條搜索分支都保持同樣的深度；以上兩種思想都是窮舉網絡圖的整個解空間，當網絡圖規模比較大時，很難在規定的時間內找到合適的解，實時性比較差。

啟發式搜索法,該方法是對窮極搜索算法的一種改進，窮極搜索是一種盲目搜索，沒有充分利用到現有路徑的信息，沒有對擴展路徑進行預判，啟發式搜索維持一個優先隊列，擬合一個權重函數，按照當前路徑值和擴展后的路徑權重以及包含必經點的數量，有選擇的進行搜索。該方法雖然沒有窮舉解空間，但是由于需要維護一個優先隊列，當網絡圖規模比較大時，優先隊列的排序選擇會消耗大量時間，精確度和實時性沒有得到根本改善。

智能搜索算法，以遺傳算法為代表的智能搜索算法從全局的角度進行解空間的搜索，可以大大提高搜索的效率。不過，目前利用遺傳算法求解該問題時，將所有的點都進行編碼，導致編碼復雜，染色體參差不齊，對后續的交叉、變異等算子都帶來很多不便，最終導致傳統的遺傳算法求解該問題也相對比較復雜。

發明內容

為了克服上述現有技術的不足，本發明的目的是提供一種基于遺傳算法的求指定點約束下的路由方法，可以將問題轉化，進一步降低問題的解空間的復雜度，從而解決現有搜索方法中搜索時間長和精度低的技術問題。

為了實現上述目的，本發明采取的技術方案為：

1、一種基于遺傳算法的求指定點約束下的路由方法，包括以下步驟：

1）讀取網絡圖信息，用鄰接矩陣A方式存儲信息，并將指起始點和指定點信息放入集合S中；

2）對網絡圖進行預處理，結合矩陣A和集合S的數據，求出起始點及指定點相互之間的最短路徑，并將其存儲在一個二維矩陣D中；

3）以起始點和指點的信息及集合S為基礎進行編碼，構建染色體C，從而將問題轉化成一個類TSP問題；

4）利用改進后的遺傳算法求解具有以下步驟：

a、固定起點和終點，隨機產生若干個有指定點組成的隨機序列，插入在起點和終點之間形成初始化種群；

b、以一定概率的方式從種群中挑選若干對染色體進行交叉運算；

c、以一定概率的方式從種群中挑選若干個染色體進行變異運算；

d、根據適應度評價函數，對種群中的個體進行排序，結合若干個歷史最優解就行選擇，優勝劣汰，得到下一代種群；

e、未達到預設的迭代次數則跳轉到步驟4）的步驟a）,否則結束本步驟；

5）根據矩陣D中的信息，檢查路徑P’的合法性，如果路徑存在環，可利用路徑修復函數R進行處理，最終將D中信息帶入到P’中得到一個完整的路徑。

進一步，所述的步驟2）中求出起始點和指定點相互之間路徑，通過如下方法確定：求取起始點到終點和指定點的最短路徑，求取每一個指定點到其他指定點及終點的最短路徑；求取方法可采用Dijkstra算法和堆結構相結合的方法，減少計算復雜度，如果相互之間不存在滿足條件的路徑則記為無窮大。

進一步，所述的步驟3）中構建染色體C，并且初始化一定數量的種群P，通過如下步驟確定：

a、構建一個一維向量，固定好起點和終點的位置，然后將其他指定點隨機的插入起點和終點之間就可以得到染色體C；

b、重復步驟3）的步驟a）的操作，即可得到相應數量的種群P。

進一步，所述的步驟4）中的交叉算子，通過如下方法確定：從種群中選取一對染色體Ca和Cb，在除起點和終點外，隨機的選擇兩個位置pos1和pos2，則可以將兩個染色體各分為三段Ca1、Ca2、Ca3和Cb1、Cb2、Cb3;保持起點和終點的位置不變交換Ca1和Cb3，然后依次將剩下的指定點依次插入到染色體中，得到兩個新的染色體Ca’和Cb’。