1.2.3  遗传算法源]自{优尔·~论\文}网·www.youerw.com/

刘先生、徐万江在分析了目前各种路径规划方法优缺点的基础上，采用遗传算法来解决动态环境下移动机器人的路径规划问题。首先针对路径规划问题的特点，对遗传算法的各个环节进行了细致的分析，包括地图环境的建立，染色体的表示和编码、适应度函数的设计，遗传操作算子的设计，算法参数的分析和选取等。然后基于MATLAB 和VC++ 可视化编程语言，开发了基于遗传算法的机器人的路径规划仿真系统。并在动态环境下开展了移动机器人的仿真实验，分析了实验结果。

遗传算法是基于自然选择和遗传学原理的搜索算法。它将“适者生存”这一基本的达尔文进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着信息交换的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。遗传算法的基本思想是：在问题的求解过程中，把搜索空间视为遗传空间，把问题的每一个可能解看作一个个体，个体里面有基因，所有的个体组成群体。依据某种评价标准对每一个个体进行评价，计算其适应度，并根据适应度对每一个个体进行选择、变异和交叉操作，淘汰适应度小的个体，留下适应度大的染色体，从而得到新的群体，新的群体优于旧的群体。对新的群体再施加自然选择法则，结果一代胜过一代，直到达到预定的优化标准。以上就是遗传算法的基本原理。

1.2.4  粒子群算法

粒子群优化是Kennedy 等借鉴鸟群的集体捕食行为，提出的一种随机群进化方法。相对传统的优化方法，该方法易于实现、可调参数少，以及收敛速度快，已成功应用于函数优化、模式识别、神经网络训练、数据挖掘，以及路径规划等领域。但是，利用粒子群优化进行机器人路径规划，存在局部收敛、效率低下，以及精度不高等缺点，尤其是含有非规则密集障碍物的复杂环境，优化的路径多与障碍物碰撞。

针对粒子群优化用于密集障碍物环境机器人全局路径规划存在的问题，可用双层微粒群优化方法(Two-layer particle swarm optimization， LPSO)改进[6]。国海涛，岳峻，苏庆堂[7]也在粒子群算法的基础上提出了基于自适应混沌变异粒子群算法的路径规划。

1.2.5  蚁群算法

蚁群算法的基本模型可以简单表述如下：在初始时刻 进行初始化的过程，所有的蚂蚁成员被放置在不同的节点，每个节点间的子路径段都有一个信息激素强度值的属性 ，初始化的过程中初始 。每只蚂蚁也都有一个列表属性叫做禁忌列表，为了避免对同一个节点的多次重复访问， 每次经过一个节点蚂蚁都保存到这个节点到禁忌列表tau-k 中，tau-k 用于记录到目前为止已经访问的节点，禁忌列表的作用是防止蚂蚁原路徘徊，重新访问经过的节点，禁忌列表的第一个元素一般为它的开始节点。当所有蚂蚁都完成了一次周游（从起始点移动到目标点）后，一次循环结束，这时各个蚂蚁成员的禁忌列表也被写满，最后，计算每一只蚂蚁成员 的路径总长度 ，找出本次循环中的最优路径MinLk，也就是局部最优路径[8]。

针对一群算法的不足，可用定义禁忌栅格[9]的方法来改进。王玫，孟正大[10]以汽车内饰件切割路径优化为研究对象，提出了一种改进禁忌表蚁群算法，显著提高水切割作业的效率和质量。

1.2.6  其他路径规划算法

在传统路径规划算法的基础上，蓝志坤，蓝志环[11]采用了基于连接特性的改进Dijkstra 算法；李耀宇，朱一凡，李群基于Legendre 伪谱法的UGV 避障路径规划[12]；基于改进群搜索优化算法的群体路径规划方法（MPGSO)[13]；基于云模型的路径规划算法[14]；基于三维虚拟爬行角色的路径规划技术[15]；动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[16]；基于蜂窝地图的步进式机器人路径规划[17]；基于时间窗的自动导引车动态路径规划方法[18]；栅格法和混沌遗传算法相融合的移动机器人路径规划算法[19]等等。