基于FPGA实现粒子群算法解最短路径

2019-02-14王飞宇

数字通信世界 2019年1期

王飞宇，胡靖

（黑龙江大学电子工程学院，哈尔滨 150080）

1 二进制粒子群算法硬件实现的优势

最短路径求取是图论的基本问题之一，它是指在有障碍物的地图信息中，寻找一条从固体定起点到终止点的最短或者较优的路径，该路径安全、不碰撞障碍，所走路程较近。常用最短路径规划方法包括启发式图搜索法、人工势场法、神经网络法等，不同程度的提高求解最短路径的速度与规模，但每一种算法都有其局限性。近年来，不少学者采用神经网络、蚁群算法、粒子群算法等进行最短路径求解，用仿生算法进行路径规划成为明显的发展趋势。为了进一步探索更适合路径规划方法，近年也有学者尝试用通过硬件实现粒子群算法进行路径规划，该方法可以在可以获得最优或最短路径，而且其时间较短。然而该方法采用传统粒子群优化算法实现，而传统的粒子群算法是一种用于连续优化的数学模型，这就限制了工作环境不能离散模型而必须是连续模型，而且也会增加计算量增添机器负担，因此这种情况在硬件实现上并不占有优势。为弥补这一不足，本文提出了一种采用二进制编码粒子群算法的硬件实现方法。该算法采用栅格法对地图信息建模，在此基础上，将路径表示为粒子位置的二进制编码，并以路径长度为适应值，产生初始种群后，根据粒子更新策略进行速度位置更新，经过一定迭代次数后即可获得一条我们所需要的最优路径或最短路径。

2 实现方法与模型建立

最短路径的求取问题中，首先要解决的就是环境的模型化，将环境路况信息生成数字模型地图，使机器识别。常见的建模方法有，人工势场法、权值路径法、链图法等，这些方法可以较为精确的实现地图的映射，同时也较为精确的求解出最短路径。但是其数据量较大计算速度较慢，地图更新数据量更为巨大，在硬件实现上，庞大的数据量以及较为复杂的运算并没有体现出其优势，为了减小硬件实现的难度，以及使其更适合硬件实现，采用栅格法实现地图，该方法计算量较小，简单。

将需要做最短路径求取的地图信息采集、处理。根据将要实现的精度，将地图栅格化为只含有0和1的矩阵信息，该矩阵中1代表障碍，0代表可以行驶的道路，每一个0和1对应着现实环境中的路况信息，将障碍物根据所应用的精度化成矩阵中1的信息。将地图信息存至RAM上根据节点的个数设置RAM的深度，宽度为1位。因在FPGA中只可以通过地址进行操作，需要设计一个地址坐标转换电路，将需要计算的地图坐标信息，转换为地址对RAM进行存取操作。该部分通过对矩阵的长宽，与地址关系的对应关系，进行编码，用case语句实现坐标转换的计算。

3 算法的实现流程

因为我使用FPGA来实现粒子群算法，为了应用硬件的优势来做到速度提升，所以采取下面的方法来实现二进制粒子群算法。粒子群算法的来源于生活中动物的行为，机器与动物较为不同的一点是动物是独立的个体，而且之间是可以交流的。通过硬件来实现粒子群算法，的核心就是应用硬件的并行特性，来实现粒子群优化算法并行运算特性。将整体的算法划分为下面几个模块：路径存储模块、路径计算模块（初始化路径生成模块）、路径比较模块、全局与局部距离比较模块、速度，位置更新模块、核心计算模块。具体流程如下：（1）我们将外部采取到的地图信息通过接口将其存与10块并行的RAM，将地图信息存储为十份。（2）这10个RAM块上进行算法的初步操作，计算出10条初始路径与其长度。（3）将计算得出的10条路径的长度进行一次比较。（4）将比较中结果长度最短的路径信息进行存储。（5）通过粒子群算法的公式对路径进行优化。（6）将优化信息反馈到初始化路径求取模块，进行路径的更新。（7）更新后的路径最为局部最优路径与之前的最优路径进行比较，将最小的值进行存储。将这个过程迭代20次，输出最优解。同时再此期间如果得出最短距离等于起点到终点的曼哈顿距离，则视为已求出最短路径跳出循环输出最短路径。

在算法的实现过程中。因为我们引用硬件实现其中的一些部分因硬件实现起来较为困难，对其进行改进，使算法更适合硬件实现，重点改进部分有如下几个部分：（1）因要进行路径的比较，要将路径存储起来，在FPGA上如果对存储区进行操作只能将内容一个一个取出作比较。数据量较多时，将会降低速度有较高的延时，这里我们通过将信息存储到寄存器组上，使比较以及更新更为简单。（2）初始化路径生成为随机生成，我们需要进行随机输的产生，这里使用LFSR这种伪随机的硬件结构产生，通过改变初始变量可得到在一定范围内较多的随机数。（3）一些较大的浮点数的操作计算采用查找表来实现。