基于黏菌路徑規(guī)劃的計(jì)算裝置設(shè)計(jì)

北京理工大學(xué)珠海學(xué)院 廣東 珠海 519088

1 研究背景

幾十億年的漫長進(jìn)化死得黏菌具有高超的食物運(yùn)輸路線規(guī)劃能力，相比傳統(tǒng)計(jì)算機(jī)，黏菌計(jì)算機(jī)具有更低的能耗，對NP難問題的求解速度更快，求解結(jié)果更加接近最優(yōu)解。另外，黏菌計(jì)算機(jī)與傳統(tǒng)計(jì)算機(jī)交互協(xié)作、取長補(bǔ)短的工作方式，可以從根本上提高傳統(tǒng)計(jì)算機(jī)對復(fù)雜數(shù)學(xué)問題的求解能力。

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

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

2 計(jì)算裝置設(shè)計(jì)

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

近年來的學(xué)術(shù)研究成果表明[2]，黏菌具有一定的計(jì)算能力，特別是對于再生道路網(wǎng)絡(luò)的路徑規(guī)劃計(jì)算。這類生物的計(jì)算方面數(shù)據(jù)由引誘劑和驅(qū)蟲劑的空間配置表示，可以通過化學(xué)信息作用進(jìn)行覓食，并生成一條最優(yōu)覓食路線。

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

3 總結(jié)

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

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

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