天津职业技术师范大学电子工程学院，天津

收稿日期：2021年10月12日；录用日期：2021年11月11日；发布日期：2021年11月19日

摘要

路径优化问题是智能运输领域中的核心问题，合理的路径能有效提高运输效率，节约时间成本。基于对连续型和离散型的Hopfield神经网络特点进行分析，设计了一种基于连续型的Hopfield神经网络的路径规划方法，用于无人机路线规划。首先对神经网络的结构进行了说明，其次引入能量函数，用于定义神经网络的稳定性。再将目标函数映射为能量函数，将问题的变量对应到神经元的状态，那么当能量函数趋于最小值时，目标函数的最优解便随即得出。最后对案例进行仿真实验，得出最优解，验证了该方法的有效性和实用性。

关键词

神经网络，能量函数，路径优化

Application of Continuous Hopfield Neural Network in UAV Path Planning

Xueping Gao, Fen Liu^*, Dongyuan Chen, Xiaoqian Liu, Baosheng Li

School of Electronic Engineering, Tianjin University of Technology and Education, Tianjin

Received: Oct. 12^th, 2021; accepted: Nov. 11^th, 2021; published: Nov. 19^th, 2021

ABSTRACT

Path optimization is the core problem in the field of intelligent transportation. A reasonable path can effectively improve transportation efficiency and save time and cost. Based on the analysis of the characteristics of continuous Hopfield neural network and discrete Hopfield neural network, a path planning method based on continuous Hopfield neural network is designed for UAV route planning. Firstly, the structure of neural network is explained. Secondly, the energy function is introduced to define the stability of neural network. And then map the objective function to the energy function, and correspond the variable of the problem to the state of the neuron. When the value of the energy function tends to the minimum, the optimal solution of the objective function is obtained immediately. Finally, the optimal solution is obtained through the simulation of an example, the results show that the proposed method is effective and practical.

Keywords:Neural Network, Energy Function, Path Optimization

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

路径规划问题属于组合优化问题，其目的是从众多可行解中找出最优解，即求出最短路径。传统的求最短路径的方法有Dijkstra算法 [1] [2]、SPFA算法 [3]、A*算法 [4]、Floyd算法 [5] 等。但这些算法或多或少都存在一些缺陷，例如计算量大，运算时间长，只适用于线性问题求解等。Hopfield等神经网络的出现，有效克服了传统方法的不足。Hopfield神经网络能较好的处理非线性问题，且具有并行计算能力，可以快速处理大量数据 [6]。本文利用连续型的Hopfield神经网络进行无人机的路径规划，仿真结果表明，该方法能快速且有效的求出最优解，规划出最短路径。

2. Hopfield神经网络概述

2.1. Hopfield神经网络结构

Hopfield神经网络是由多个互联的神经元组成的网络，属于反馈式神经网络，网络的输出会反馈到神经元的输入，神经元会根据情况进行自我调节，从而不断变化。当神经网络趋于稳定时，神经元的状态便是所求问题的解。Hopfield神经网络分为离散型(Discrete Hopfield neural network, DHNN)和连续型(Continuous Hopfield neural network, CHNN)两种模型。二者在拓扑结构上是类似的，文献 [7] 中给出了CHNN的拓扑结构，如图1所示。

图1. CHNN拓扑结构

CHNN络拓扑结构是利用模拟电路实现对网络的描述， $U_j,C_j,R_j,V_j,I_j$ 分别表示神经元 $j\left(j=1,\text{2,3},\cdots ,n\right)$ 的内部膜电位、细胞膜输入电容、细胞膜传递电阻、输出电压、外部输入电流。图中，R_j和C_j并联，用来模拟神经元的时间常数； $w_{ij}\left(i,j=1,2,3,\cdots ,n\right)$ 为权系数，模拟神经元之间的信息传递；运算放大器模拟非线性特性。通过基尔霍夫电流定律对电路图进行分析，可得如下公式：

$\{\begin{array}{l}{C}_j\frac{\text{d}{U}_j\left(t\right)}{\text{d}t}={\displaystyle \underset{i=1}{\overset{n}{\sum }}{w}_{ij}{V}_i\left(t\right)-\frac{U_j\left(t\right)}{R_j}+I_j}\\ V_j\left(t\right)=g_i\left(U_j\left(t\right)\right)\end{array}$ (1)

上式便是CHNN的动态方程。其中， $j=1,2,3,\cdots ,n$ ；n为神经元个数；g_j为神经元的传递函数。

离散型和连续型两种模型的区别在于DHNN中神经元的传递函数(激活函数) g为离散函数，一般为阶跃函数；而CHNN中神经元的传递函数g为S型的连续函数，一般为Sigmoid函数；此外，DHNN工作方式有异步和同步两种 [8]；CHNN在时间上是连续的，所以网络中各神经元是同步工作的。一般来说，DHNN适用于联想记忆，CHNN适合处理优化问题。路径规划目的是找出最优解，故本文采用连续型的Hopfield神经网络设计算法模型。

2.2. 构造能量函数

连续型Hopfield神经网络的稳定性用能量函数 [9] [10] 来定义。在运行时，能量函数是递减变化的，当其不再改变时，能量函数对应的稳定状态就是网络的输出。所以通过分析能量函数和网络输出的关系来证明网络的稳定性。能量函数 $E\left(t\right)$ 定义为：

$E\left(t\right)=-\frac{1}{2}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{w}_{ij}{V}_i\left(t\right)V_j\left(t\right)}}-{\displaystyle \underset{j=1}{\overset{n}{\sum }}{V}_j\left(t\right)I_j}+{\displaystyle \underset{j=1}{\overset{n}{\sum }}\frac{1}{R_j}}{\displaystyle {\int }_0^{V_j\left(t\right)}{g}^{-1}}\left(V\right)\text{d}V$ (2)

式中， $g^{-1}\left(V\right)$ 是 $V_j\left(t\right)=g_j\left(U_j\left(t\right)\right)$ 的反函数。能量函数 $E\left(t\right)$ 对时间求导数，则有

$\frac{\text{d}E\left(t\right)}{\text{d}t}=-\frac{1}{2}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\displaystyle \underset{i=1}{\overset{n}{\sum }}\left[w_{ij}\frac{\text{d}{V}_i\left(t\right)}{\text{d}t}{V}_i\left(t\right)+w_{ij}{V}_i\left(t\right)\frac{\text{d}{V}_j\left(t\right)}{\text{d}t}\right]}}-{\displaystyle \underset{j=1}{\overset{n}{\sum }}{I}_j\frac{\text{d}{V}_j\left(t\right)}{\text{d}t}}+{\displaystyle \underset{j=1}{\overset{n}{\sum }}\frac{U_j\left(t\right)}{R_j}\times \frac{\text{d}{V}_j\left(t\right)}{\text{d}t}}$ (3)

若存在权重系数 $w_{ij}=w_{ji}$，并将网络的动态方程(1)式代入(3)式，则可以得到：

$\frac{\text{d}E\left(t\right)}{\text{d}t}=-{\displaystyle \underset{j=1}{\overset{n}{\sum }}\frac{\text{d}{V}_j\left(t\right)}{\text{d}t}\times C_j\frac{\text{d}{U}_j\left(t\right)}{\text{d}t}}$ (4)

又由于(1)式中指出， $V_j\left(t\right)=g_j\left(U_j\left(t\right)\right)$，则 $U_j\left(t\right)=g^{-1}\left(V_j\left(t\right)\right)$，故(4)式可改写为：

$\frac{\text{d}E\left(t\right)}{\text{d}t}=-{{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left[\frac{\text{d}{V}_j\left(t\right)}{\text{d}t}\right]}}^2\times C_j\times {\left[g_j^{-1}\left(V_j\left(t\right)\right)\right]}^{\prime }$ (5)

对(5)式进行分析，当传递函数函数g是连续有界且单调递增的函数时，其反函数g⁻¹也为单调递增

函数，所以其导数必大于0；又因电容C_j大于0，那么可得 $\frac{\text{d}E\left(t\right)}{\text{d}t}\le 0$，所以仅当 $\frac{\text{d}{V}_j\left(t\right)}{\text{d}t}=0$ 时，才会有 $\frac{\text{d}E\left(t\right)}{\text{d}t}=0$。由此可说明，神经网络的传递函数g必须要是连续有界的，且由权系数 $w_{ij}$ 构成的权系数矩

阵W是对称的，才能保证网络的稳定性。其次，仅当神经网络的输出趋于平稳，不再变化时，能量函数才不会变化。所以可以用能量函数来定义网络的稳定性。

3. 问题描述及建模

3.1. 问题描述

无人机路径规划是智能运输领域的一个关键技术。其目的是使无人机经过若干个目标点以后，所经历的路线最短，且每个目标点只经过一次。无人机作为一种灵活的运载工具，在地质勘测、航拍、电力巡检等多方面都发挥着重要作用。现需要无人机执行一项任务，对某些指定目标地点进行勘测，要求遍历所有的目标地点，为了节省人力和物力资源，需要找出一条经过所有目标地点的最短路线。

3.2. 换位矩阵

采用连续 神经网络解决路径规划问题时，可以用 $N\times N$ 的矩阵表示访问路径 。用数字1代表访问过这个地点，用数字0表示不访问这个地点，路径规划要求经过所有的目标地点仅一次，那么在矩阵中，每行每列都只有一个位置上的元素是1，这样的矩阵被称为换位矩阵 [11]。例如有5个目的地，分别以字母A、B、C、D、E表示，如果地点B是第四个访问的地点，那么就可以用00010表示。若访问顺序为C-A-E-B-D，用数字0和1对其表示，则可以得到5 × 5的矩阵，如表1所示。

表1. 目标地点访问顺序

针对实际问题，需要优化能量函数，改进后的能量函数包含目标项(最短路径)和约束项(换位矩阵) [11]，故网络的能量函数可以定义为：

$E=\frac{A}{2}{\displaystyle \underset{x=1}{\overset{N}{\sum }}{\left({\displaystyle \underset{i=1}{\overset{N}{\sum }}{V}_{xi}-1}\right)}^2}+\frac{A}{2}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\left({\displaystyle \underset{i=1}{\overset{N}{\sum }}{V}_{xi}-1}\right)}^2}+\frac{D}{2}{\displaystyle \underset{x=1}{\overset{N}{\sum }}{\displaystyle \underset{y=1}{\overset{N}{\sum }}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{V}_{xi}{d}_{xy}{V}_{y,i+1}}}}$ (6)

式中前两项为约束项，最后一项为待优化的目标项。

结合(1)式可得推导出网络的动态方程为：

$\frac{\text{d}{U}_{xi}}{\text{d}t}=-\frac{\partial E}{\partial V_{xi}}=-A\left({\displaystyle \underset{i=1}{\overset{N}{\sum }}{V}_{xi}-1}\right)-A\left({\displaystyle \underset{y=1}{\overset{N}{\sum }}{V}_{yi}-1}\right)-D{\displaystyle \underset{y=1}{\overset{N}{\sum }}{d}_{xy}{V}_{y,i+1}}$ (7)

4. MATLAB仿真实现

根据任务目标，拟定了一定数量的目标地点位置坐标，所有的坐标值都经过了归一化处理，目标地点位置分布如图2(a)和图3(a)所示，将无人机需要遍历的两组目标地点坐标作为输入数据。利用MATLAB软件进行仿真，对路线进行组合优化，并对结果进行分析。

从图2(a)和图3(a)可以看出，目标地点随机分布，想要遍历所有目的地，拥有很多条路线。假设目

标地点数目为N，那么存在的路径数目应为 $\frac{\left(N-1\right)!}{2}$，随着N的增大路径数目会急剧增大，面对庞大的

计算量，神经网络表现出了较好的性能，可以快速处理大量数据。

在寻优过程中，网络会输出不同的结果，随着仿真次数的增加，最终可以找到最优解。仿真过程中，用换位矩阵表示城市的访问顺序时，矩阵中每一行每一列都只有一个1，矩阵中的元素1的位置对应无人机航行经过的目标地点，随即可以得出最优路径。如果寻优路径无效，需要重新运行程序进行路径优化。最终得到的最优结果如图2(c)和图3(c)所示。

针对求解无人机分别经过一定数量的目的地的最优路径问题，利用 神经网络进行路径规划。从图2的图2(b)和图2(c)可以看出，优化前的路径长度为6.4529，优化后的路径长度为3.1534，路径总长度明显缩短，且路线没有交叉，每个目的地只访问了一次。图3的图3(b)和图3(c)也验证了这一方法的可靠性，长度由最初的12.1937缩短到4.1022，总长度大大缩短。图2(d)和图3(d)分别表示在访问不同数量目的地情况下的能量函数曲线变化图，从图中可看出，能量函数的值随着迭代次数的增加而减少，最终趋于平稳。能量函数收敛到极小值时，说明了无人机路径规划问题的最优解已经得出。

图2. 访问地点数量为20时的情况

图3. 访问地点数量为30时的情况

5. 结语

本文采用连续型的Hopfield神经网络对无人机路线进行优化，采用MATLAB对经过不同数量的目标城市路线进行仿真实验，结果表明，基于神经网络对无人机飞行路径进行规划，具有运行效率高，计算速度快的优势。当目的地数量增加时，可以增加迭代次数改善寻优结果。但并非迭代次数越多越好，还应该结合具体的情况进行分析，这也是接下来神经网络针对路径规划需要进一步研究的问题。随着无人机飞行环境多变，对无人机航迹规划提出了更高的要求，未来可将二维平面的路径规划与三维环境的路径规划有效结合，提出更完善的规划方法。

文章引用

高雪苹,刘 芬,陈东园,刘晓倩,李保胜. 连续型Hopfield神经网络在无人机路径规划中的应用
Application of Continuous Hopfield Neural Network in UAV Path Planning[J]. 计算机科学与应用, 2021, 11(11): 2718-2724. https://doi.org/10.12677/CSA.2021.1111275

参考文献