[發明專利]基于黏菌覓食行為的交通網絡脆弱性問題仿生優化方法

有效

• 申請號: 201910483086.0
• 申請日: 2019-06-04
• 公開（公告）號: CN110288131B
• 公開（公告）日: 2021-10-12
• 發明（設計）人: 蔡政英;熊澤平;萬鯤鵬;胥帆;徐雅琦
• 申請（專利權）人: 三峽大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/26;G06N3/00
• 代理公司: 宜昌市三峽專利事務所 42103
• 代理人: 王玉芳

本發明基于黏菌覓食行為的交通網絡脆弱性問題仿生優化方法，所述方法采用黏菌覓食行為對交通網絡脆弱性問題進行仿生優化，使用單只黏菌的多條黏變形體完成不同方向上的交通網絡路線并行求解，將交通網絡節點模擬成外部食物源，將交通網絡中兩個節點之間的線路模仿成黏變形體，將交通網絡模擬成覆蓋所有外部食物源的黏菌原質團，將交通運輸模擬成體內營養物質的運輸，將交通網絡脆弱性優化問題模擬成黏菌覓食網絡優化問題。本仿生方法能夠高效完成交通網絡脆弱性問題的優化求解，節約社會成本提高資源使用效率，簡化研究人員的問題求解流程。

技術領域

本發明屬于計算機仿生學領域，具體說是基于黏菌覓食行為的交通網絡脆弱性問題仿生優化方法。

背景技術

交通網規劃和設計問題可以歸化為經典的旅行商問題(Traveling SalesmanProblem，TSP)，又譯為推銷員問題、貨郎擔問題。最早使用數學模型來研究TSP問題的是Merrill M.Flood，他在20世紀30年代，首次在數學上解決一個校車路線規劃問題。問題可以描述為，假設有一個旅行商要走遍n個城市，行走線路就必須遍歷每個城市一次，并且最后回到原來的出發城市，旅行商盡可選擇總線路最優的方案。旅行商問題提出已有百年之久，國內外科學家都傾向于接受旅行商問題是一種NP完全問題(NP-Complete或NPC)或NP難題(NP-Hard或NPH)，不存在有效算法，并認為具有多個節點的許多實例(如交通網絡)都無法使用精確算法求解，只能使用近似的優化算法。

交通網絡的規劃不合理很容易導致脆弱性問題，近年來引起了越來越多的研究和關注。已經證明僅僅依靠增加道路網絡容量和基礎設施來解決交通網絡脆弱性問題是不合理的，應當深入挖掘交通網絡脆弱性問題的特征和規律，量化評估道路交通網絡的脆弱路線及其脆弱性變化規律和影響，以便有針對性地對交通網絡脆弱進行優化。對交通網絡網脆弱性問題定量化評價需要考慮網絡或節點受干擾程度，準確識別交通網絡的脆弱線路，提高優化時的針對性，確保交通網絡投資的價值和效率。因此，交通網絡脆弱性問題和優化目前尚無有效的解法。

這件事在9年前突然有了轉機。2010年，日本北海道大學的科學家Atsushi Tero等人在《Science》期刊上發表論文首次使用黏菌求解線路規劃問題，實驗中使用培養皿當地圖，使用燕麥片當作城市，讓黏菌在上面繪制了東京鐵路線路圖。實驗結果顯示，黏菌造的東京鐵路網和人類造的鐵路網極其相似。

東京鐵路系統是人類歷史上最早也是最復雜的鐵路系統之一，于1872年首次連接了日本東京和橫濱兩大城市。之后，人類花了上百年時間去規劃、建設、重建和優化，東京鐵路系統才優化成今天的樣子，然而黏菌僅僅只花了26小時，就得到了同樣高效的優化結果。更驚人是，黏菌非常低等原始，因為它連大腦都沒有，而其求解出的東京鐵路系統方案，幾乎與人類百年來不斷試錯和重建得到的優化網絡完全一樣。不僅如此，黏菌還能夠反復試錯，得到不同優化方案。

黏菌優化算法的研究真正起源于2010年。同一年，西英格蘭大學的AndrewAdamatzky教授也做了類似研究，使用燕麥片和黏菌(slime mold)繪制了14個國家的公路網。其研究后發現，比利時、加拿大和中國的高速公路網和黏菌計算的結果最為相似，而美國和非洲的交通網效率最低。近9年來，不少研究交通運輸網絡優化問題的學者就開始注意到黏菌來求解。2014年，Xiaoge Zhang等人發表了一篇改進的黏菌算法論文。在實驗中，在迷宮出口和入口處放置黏菌的食物燕麥片，入口和出口間有長短不同的線路能夠連接兩處的食物源。然后，將黏菌放到迷宮里，黏菌最終能夠找到迷宮出口，全程花費96小時。

以上文獻均使用真實的黏菌對問題進行求解，雖然有一些優勢，但也有不少缺點。