[發明專利]一種基于神經網絡求解時變環境下多目標最短路徑的方法

在審

• 申請號: 202011275087.5
• 申請日: 2020-11-11
• 公開（公告）號: CN112836845A
• 公開（公告）日: 2021-05-25
• 發明（設計）人: 黃瑋;劉晉;王勁松
• 申請（專利權）人: 天津理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/06;G06N3/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

一種基于神經網絡求解時變環境下多目標最短路徑的方法，該方法包括：利用地圖軟件對城市交通網絡實時監測采集數據，獲取網絡中各邊的成本函數，構造出交通網絡模型；結合網絡的拓撲結構，設計嶄新的神經元結構并構造出神經網絡模型。將交通網絡的拓撲信息加載到神經網絡模型中，運用神經元的波發生器和過濾器使其向后繼神經元發出自動波，激活網絡中的其他神經元，而每個神經元利用過濾器忽略對部分波的應答。該方法通過設計神經網絡將非最優子路徑剪枝掉，極大減少計算復雜度，實現了在時變環境下精確求解多目標最短路徑這一網絡優化領域的難題。此外，該方法運用神經網絡并行計算加快了問題求解速度。

技術領域

本發明屬于網絡優化技術領域與人工智能技術領域的結合，具體涉及設計一種基于神經網絡求解時變環境下多目標最短路徑的方法。

背景技術

經典的多目標最短路徑問題是優化多個目標的路由問題，例如在交通運輸過程中，希望找尋路程短且路況好的路徑，那么需要同時優化兩個目標函數，最短的旅行時間和距離。網絡中每條邊權重函數值是不隨時間發生變化的。但是，比如在交通運輸過程中，運輸時間隨著路況的擁堵情況發生變化的，也就是邊權重函數是依賴于時間的，這也就擴展出時變環境下求解多目標最短路徑的問題。

近年來，國內外學者相繼開展時變環境下多目標最短路徑的研究，其技術難點主要集中在求解方法、求解速度和求解精度。

求解方法方面，從國內外的研究成果來看，時變環境下求解多目標問題計算復雜度高，傳統的圖論求解方法如動態規劃和標號設置算法等難以突破，而智能算法如遺傳算法和蟻群算法等無法求得精確解。

求解速度方面，國內外的研究論文求出精確解的方法基于傳統算法如動態規劃、標號設置算法等因計算量大，算法效率低，運行環境大都依賴高性能計算機的支持，在大眾化的PC機上無法滿足實際需要。

求解精度方面，一般系統采用的傳統路由算法忽略時變環境去尋找多目標最短路徑，換言之將網絡看作靜態，很難求出精確解。

發明內容

本發明的目的是為克服上述現有技術存在的缺點和不足，提供一種基于神經網絡求解時變環境下多目標最短路徑的方法。

本發明所述的一種基于神經網絡求解時變環境下多目標最短路徑的方法，具體步驟包括：

第1步，利用地圖軟件實時采集網絡拓撲信息構建交通網絡模型，采集的信息包括各節點前驅和后繼，以及各邊權重函數，比如路由時間函數B_ij(t_i)和路由成本函數R_ij(t_i)；

第2步，根據采集到的網絡拓撲信息加載到神經網絡模型中，且設計構建的神經網絡模型的拓撲結構與交通網絡的拓撲結構相同，不用前期數據集對神經網絡訓練；

第3步，初始化神經網絡，包括各個神經元的接收器、過濾器、存儲器、波產生器和波發送器5個部分，在接收器中設置解碼函數F，在過濾器中設置過濾函數D，在存儲器開辟存儲空間S，在波產生器中初始化能量函數E和閾值函數θ，在波發生器中設置編碼函數J并設置網絡的初始時刻為t＝0；

第4步，更新神經網絡，分為3個子步驟：自動波的接收與過濾、自動波的存儲與產生和自動波的激活和轉發；采用“神經元激活”技術和“自動波過濾”技術更新每個神經元在網絡t時刻的狀態；

第5步，更新網絡時刻t＝t+1，重復第4步直到t＝T，其中T是網絡的時間上限；

第6步，遍歷目的神經元接收到的波利用回溯的方法尋找到所有的多目標最短路徑。

第1步所述的權重函數是根據記錄拓撲數據利用統計軟件計算變量的概率分布函數，一般為分段函數或線性連續函數。

第2步所述的神經網絡模型的拓撲結構與交通網絡的拓撲結構相同，不用前期數據集對神經網絡訓練。