基于黏菌路徑規劃的計算裝置設計

北京理工大學珠海學院 廣東 珠海 519088

1 研究背景

幾十億年的漫長進化死得黏菌具有高超的食物運輸路線規劃能力，相比傳統計算機，黏菌計算機具有更低的能耗，對NP難問題的求解速度更快，求解結果更加接近最優解。另外，黏菌計算機與傳統計算機交互協作、取長補短的工作方式，可以從根本上提高傳統計算機對復雜數學問題的求解能力。

21世紀初期，日本研究人員用黏菌尋找迷宮的最優路徑，發現黏菌高效的食物運輸路線規劃能力有利于城市交通運輸網絡的建設。在覓食過程中，黏菌展現出驚人的路線搜尋以及解決幾何問題的能力，例如為東京的鐵路系統設計出高效的路線方案。2010年1月22日，日本研究人員利用黏菌避光的特性，使用光斑模擬海岸線和地形，在東京附近重要的地鐵站對應的位置放上食物，讓黏菌從東京往四周生長，從而得到連接各個站點的路線網絡，求解結果與人類花費一百多年設計和不斷改進得到的東京鐵路網絡相差無幾。

NP難問題是數學與計算機科學研究中的主要研究問題之一，在科學研究的過程中難免會遇到NP難問題，其中商旅問題是眾多NP難問題中的典范。商旅問題可作描述為:一個商人想在n個城市銷售商品，他想從一個城市出發走最短的路徑并穿過所有的城市一次，這個問題已經存在很長時間了。這是一個經典的NP難問題，由于其廣泛的應用，在世界上得到了高度的重視。然而，若一個問題被定義為NP難問題則無法用計算機進行精確求解。但是在實際中，NP難問題又是不可避免的，如在路網施工規劃、工業控制、最優路線等實際問題上都要涉及到NP難問題。因此，本文利用黏菌具有優秀的路徑規劃這一生物特性，研發了一套求解NP難問題的輔助計算裝置。

2 計算裝置設計

為了避免研究人員為解決此類問題而做出大量而無效的工作，可以借助數字計算機，采用遺傳算法、粒子群算法、蟻群算法[1]等算法去解決實際問題，但由于傳統計算機的固有缺陷，即便使用這些智能優化算法也無法很好地解決NP難問題，應該從根本上去改變傳統計算機的計算模式。因此，設計一款能解決NP難問題的黏菌計算機有著重要意義。

近年來的學術研究成果表明[2]，黏菌具有一定的計算能力，特別是對于再生道路網絡的路徑規劃計算。這類生物的計算方面數據由引誘劑和驅蟲劑的空間配置表示，可以通過化學信息作用進行覓食，并生成一條最優覓食路線。

本文研究的計算裝置由步進電機、培養皿、鋁框架、同步帶、同步輪、絲桿、滑桿、經改裝過的3d打印筆(注食裝置)、迷你五輪盤、膏狀燕麥食物、黏菌、移動臺、驅動電源、Arduino開發板組成，其中步進電機用于驅動打印筆和滑臺移動，Arduino開發板控制打印筆和滑臺移動，控制3D打印筆注食，從而達到定點定時定量注食的效果。該計算裝置的實現是通過把地區視為瓊脂平板，其中燕麥代表著主要的城市。通過攝像機對黏菌在不同的食物、光照、濕度、溫度、酸堿度條件區域下的活動進行間隔拍攝，將燕麥和瓊脂制成適合黏菌攝食的膏狀食物，使用步進電機、驅動帶、3D打印筆、鋁架等零件組裝。將培養皿劃分網格并運用單片機控制食物注射裝置注射食物，而后接種黏菌在預訂的環境條件下進行培養。運用樹莓派csi攝像頭實現機器視覺技術，識別黏菌規劃出來的最優食物運輸路線并經過相應算法的處理，還原成待解決數學問題的最優解并輸出到計算機。通過定點、定時、定量地向帶有黏菌的培養皿注射膏狀食物，同時將NP難問題及其他各類復雜的非線性數學問題轉化為優化問題求解。實驗結果顯示在求解結果的精確性，擴展性，空間覆蓋率方面比傳統方法更加優秀。

3 總結

我們給出了黏菌計算的圖像結果，在實驗中證明了其擁有優秀的路徑尋優能力和路網導航能力。我們可以利用黏菌路徑規劃模型對多目標旅行商問題[3]中的各目標進行分別得粗略求解，得到大致的“圖像”并使用機器視覺信轉化信息素矩陣，雖然這張“地圖”并不一定準確，但是卻有一定的方向性。同時，我們利用該“地圖”參與初始化蟻群算法的信息素矩陣，優化蟻群算法求解多目標旅行商問題。

圖2 MATLAB處理后的黏菌覓食圖像

總的來說，基于黏菌路徑規劃的計算裝置可以為解決NP難問題提供一種可行方案。與其他生物仿生計算機對生物行為轉化成邏輯門等復雜的設計相比，本文探討的計算裝置主要是通過投放瓊脂作為計算啟動操作，并通過機器視覺重建黏菌覓食的路徑規劃圖像信息，從而得出解決NP難問題的一種解決方案，具有一定的創新性和實踐性。