基于黏菌路径规划的计算装置设计

北京理工大学珠海学院 广东 珠海 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难问题的一种解决方案，具有一定的创新性和实践性。