退火算法与神经网络算法结合在路径规划中的研究
李江伟，许伦辉
【摘 要】摘要：路径规划问题是计算机、数学、交通、机器人等包含了众多领域在内的经典问题，它可以被描述为一个最优化问题。为了解决经典算法在求解最优路径时运算时长的问题，该文研究了神经网络和模拟退火算法的特点，建立了一般路网的数学模型；根据神经网络和模拟退火算法的特点设计了适合车辆诱导的路网最优路径算法。结果表明，应用神经网络算法和模拟退火算法相结合，比单独使用任何一个算法的效率高。 【期刊名称】自动化与仪表 【年(卷),期】2017(032)011 【总页数】5
【关键词】路径规划；神经网络；模拟退火算法
一个网络中，在满足一定的约束条件下，找出一条从任意2点之间的最优路径，可以是时间少、距离最短，也可以是费用最低，或者有多个优化目标，考虑这几种因素的综合影响。路径规划在很多领域都有着非常广泛的应用，例如交通、物流、通信系统的路由搜索、机器人行走路线规划等，以及近两年非常热门的无人机，路径规划算法已成为其最为关键的核心技术之一。路径规划问题可以表示为一个数学上的多目标优化问题，因此在路径规划问题就转化为求解相应的数学优化问题。在此，重点研究利用合适的方法求解最优解。
最短路径问题是网络优化中的一个最基本的也是最重要的分支，同时也是所有路径规划问题的基础。许多路径规划问题都可以转化为这样的最短路径问题模型来表达，或者可以用最短路算法作为子程序。
为路径的权值，是特定情况下的约束条件，研究的目的就是在约束条件下求得目标函数的最小值。在实际的交通路网中，路段或者节点的数量都是非常多的，求解的复杂度较高，需要找到一种既能够较好地找到全局最优解，又有着较快的运算速度的方法。因此，提出了一种基于模拟退火-Hopfield神经网络的算法（SA-CHNN），并利用神经网络的高度并行性，借助并行计算技术来提高算法的计算速度，且能够有效地求得全局最优解。
1 模拟退火算法
1.1 退火算法原理
模拟退火是一种随机的搜索方法，其灵感来自于退火的过程。它的基本思想是，首先将温度设置为一个足够高的水平，此时绝大部分的随机运动方向都是可行的，可以在比较大的空间内找到一个目标值相对低的区域；随着温度根据一定的规则慢慢降低，各个方向被选中的概率会变得不一样，当然搜索的精度也不断提高。模拟退火算法的更新迭代过程主要用到MetroPolis准则，具体如下： ①假设状态在xk时，当使用一定的扰动对系统进行影响，使状态发送变化，得到一个新的状态xk+1，前后两个状态对应的系统能量分别为E（xk）和E（xk+1），能量差为ΔE； ②ΔE≤0，则转换为状态 xk+1； ③ΔE≥0，则转换为xk+1的概率为
式中：K为波尔兹曼常量；T为温度；Z（T）为规范化因子。
④设 r＝random（0，1）为（0，1）上的随机数，与 Pr进行比较。若Pr≥r则接受新状态，反之状态维持不变。
温度较高时可以接受较大的能量差，温度下降到一定的程度后，只有较小的能
量差被接受。利用这一思想，当各个条件满足的时候，也就是值达到了最优解。通过类比上述的物理过程，可以得到优化问题的解MetroPolis准则，目标函数为xk和xk+1的解，则由xk转换到xk+1的接受概率为式中：T为退火过程中的温度值。T0为算法迭代过程开始时的起始温度，初始解为x=x0。在算法迭代的过程中不断产生新解，根据上述准则判断接受新解的概率判断是否接受。随着迭代的进行，温度T下降，直至满足收敛条件，算法收敛时就可以得到最优解。
通过随机的方法来产生新的解[1]。假设当前解为，候选解为。当前解xi的某一个分量在一定领域内进行随机变化，产生出新的值，候选解xi+1的计算公式为 式中：r为区间［-1，1］的随机数；d为领域调整因子。在连续模拟退火算法的开始阶段，d可以取较大值，目的是使d能够在较大范围内进行搜索，然后再逐渐减小d，缩小搜索范围。常取d为线性函数d=ηd，其中0＜η＜1。此外，新产生的候选解必须满足优化问题的约束条件。当满足式（3）的2个条件的时候，候选解也可以采取以下形式[2]：
式中：和 分别为 xk取值的上限、下限；scalr（）为函数值为1到0之间递减的函数；r为［-1，1］区间上的随机函数，若r＞0则 xk的值增大；r＜0，xk的值减小。 1.2 参数的设置
在利用模拟退火算法求解优化问题，尤其是非凸优化问题时，参数设置是否合理在很大程度上影响到算法的性能。虽然从理论上来说，只要初始温度够高、下降速度够慢、迭代次数够多，算法就能以1的概率收敛于全局最小值。但是在实际的应用中，不可能花费近乎无限的时间来等待结果，只要求算法能够在
退火算法与神经网络算法结合在路径规划中的研究
