车辆最短路径问题研究(3)

菜单

2.2.2 模拟退火法

模拟退火算法是一种通用概率演算法，是用来在一个比较大的搜寻空间内找寻命题的最优解。模拟退火是S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明。模拟退火算法是解决TSP问题的有效方法之一。模拟退火来自物理冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。

2.2.3 蚁群算法

蚁群算法，又称蚂蚁算法，是一种用来在图形中寻找优化路径的机率型算法。它是由Marco Dorigo在1992年的博士论文中提出，其灵感来源自蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种模拟进化优化方法的应用价值。

2.2.4 动态规划

动态规划是运筹学的一个重要分支，是求解决策过程最优化的一种数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的最优化问题时，提出了非常著名的最优化原理，他们把多阶段过程转化成为一系列单阶段问题，利用各个阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。