改进的蚁群遗传优化算法及其应用
开篇：润墨网以专业的文秘视角，为您筛选了一篇改进的蚁群遗传优化算法及其应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：
针对当前移动机器人的一些路径规划算法存在的局限性，提出了一种基于改进蚁群优化和遗传优化的融合算法。利用改进的信息素更新技术和路径节点选择技术使算法尽快找到优化路径，来形成融合算法的初始种群，机器人每前进一步，蚂蚁就对局部路径重新搜索，并处理随机出现的障碍物；然后利用遗传算法（GA）对种群个体进行全局优化，从而能使机器人沿一条全局优化的路径到达终点。仿真结果表明了该融合算法的可行性和有效性。
关键词：
蚁群优化；遗传算法；移动机器人；路径规划；信息素
0引言
移动机器人的路径规划问题是移动机器人研究领域的热点问题。移动机器人路径规划技术的研究起始于20 世纪70 年代，斯坦福研究院的Nils Nilssen和Charles Rosen等，在1966年至1972年研制出了取名Shakey的自主移动机器人[1-6]，在20世纪80年代中期，设计和制造机器人的浪潮席卷全世界[5-7]。根据以往的研究，从机器人对环境感知的角度，将移动机器人路径规划方法分为三类[7-10]：基于环境模型的全局路径规划方法、基于传感器信息的局部路径规划方法和基于行为的路径规划方法。目前，已有的局部路径规划算法有人工势场法、模糊逻辑法等[2，5]，已有的全局路径规划算法有A*方法、可视图法、遗传算法、蚁群算法等[11-17]。本文提出了一种基于蚁群优化算法（Ant Colony Optimization， ACO）和遗传算法（Genetic Algorithm， GA）的移动机器人路径规划融合算法（ACO+GA），该算法克服了遗传算法在初始可行解的有效构造以及针对复杂环境设计相应的遗传算子等方面的困难，特别是
在遇到非规则障碍物的复杂环境下使用蚁群采用最近邻居搜索策略完成机器人局部最优路径的搜索。
在遇到非规则障碍物的复杂环境下使用蚁群算法采用最近邻搜索策略完成机器人局部最优路径的搜索。
仿真结果表明，该算法能够快速、高效地规划出优化路径，特别适合复杂地形环境下的机器人路径规划。
1蚁群算法原理及改进的相关技术
1.1蚁群算法原理
蚁群优化算法是Marco Dorigo等学者在20世纪90年代提出的一种基于真实蚂蚁觅食行为的、具有高度创新性的元启发式算法[11-13]。Goss等此处的人名与文献13中的人名不一致，请作相应调整。在1990年用双桥试验验证了蚂蚁这种自身催化或者正反馈的特征[13]。
1.2改进的相关技术
为了方便操作将问题进行简化，首先说明以下几个问题[11-13]：
1）该蚁群算法应用在栅格模型的路径优化上；
2）在蚂蚁数量为m的蚁群中，每个蚂蚁在访问过的单位栅格上释放的信息素为常量；
3）蚁群释放的信息素与它们发现的路径长度成反比，即：
2基于蚁群优化和遗传优化的算法融合
2.1个体编码与种群初始化
如图1所示，机器人由其起始位置B沿图中带箭头的折线所示路径运动到终点位置E，即为一个个体。取路径点的标识序列数作为路径编码，规定每条路径中不能出现重复的标识序列号。在图1情况下，一条路径表示为：p={0，10，20，31，42，53，…，99}。从起始点出发，利用环境信息和局部搜索技术，随机选取与起始点相邻的一个非障碍物点作为下一路径点，如此反复，直到找到终点为止。如图1所示，在机器人运动的起点B到终点E之间，用一系列随机选择、自由、不一定连续的栅格序号连接B和E。因此，初始种群如式（10）所示：
2.2适应性函数
一条优化路径是无碰的、不间断的可执行路径，然后要求该条路径是最短的。因此，路径个体适应性函数要包含路径长度信息、无碰撞信息和路径不间断信息[15-17]，所以，适应性函数定义如下：
2.3遗传算子
复制算子初始种群作为优化过程的开始，由算法本身随机产生， N为群体规模，即随机生成路径pj （j=1，2，…，N），同传统复制算子一样，采用与适配值成正比例的概率来选择个体。具体做法是：
1）计算选择复制的概率：
Pcopy=fj（p）/∑fj（p）（15
2）计算期望的复制数：
Dcopy=fj+1（p）/fj（p）（16
3）实际得到的复制数：按四舍五入原则对期望的复制数取整。
交叉算子第1步是将复制产生的个体随机两两配对；第2步是随机地选择交叉点，对匹配的个体按一定的交叉概率Pc（一般在0.7左右）进行交叉繁殖，产生一对新的个体。
随机突变变异是对群体中的元素（基因）加入随机扰动，使其发生变异。变异概率为Pm的取值很小（一般在0.001～0.1），变异有节制地和交叉一起使用，是一种防止过度成熟而丢失一些重要遗传信息的保险策略，但变异多保持低概率，以避免损坏下一代个体的结构。
2.4融合算法流程
根据以上的原理和相关技术，融合算法的具体执行步骤如下：
第1步利用栅格法对机器人的工作环境建模，确定起始点gbegin和终点gend，将m 只蚂蚁放置在出发点gbegin，并设置禁忌表tabuk（k=1，2，…，m），设τij（0）=τ0，τ0为一常数，设置计数器s=0。
第2步以当前节点（或起始点gbegin）为中心，按照路径节点转移概率式（9）的值选择下一个节点，将无效节点加入禁忌表tabuk，直到终点gend，将有效解路径形成初始种群。
第3步利用适应性函数式（11）对种群路径个体计算适应值。
第4步利用复制算子中的式（15）和（16）对期望值高的个体进行复制，利用交叉概率Pc、变异概率Pm进行交叉和变异操作。
第5步判断是否有符合条件的路径个体出现，若有转向第7步算法结束；否则进行下一步。
第6步根据式（7）更新信息素，s=s+1，转向第2步，进入下一次循环。
第7步算法结束。
3仿真实验与分析
为了验证本文算法的有效性，在VC环境下进行了大量的仿真实验，结果令人十分满意。在实验中，通过不同数量的栅格数、随机设置障碍物、多次改变起始点和目标点等方法进行环境建模，来实现路径规划。
实验一该实验仿真了蚁群寻食过程中的情形。图2（a）给出了蚁群在寻食过程中没有遇到障碍物的情况；图2（b） 给出了在蚂蚁寻食的路径上出现了障碍物的情形， 此时的蚂蚁基本以相等的概率从障碍物的两侧通过，但此时蚂蚁在绕过障碍物的较短路径上稍多一些，因此沉积的信息素也相对多一些，这样就会引导更多的蚂蚁经过此路径；图2（c）给出了蚁群最终选择的路径。
4结语
蚁群算法和遗传算法都是智能仿生类随机搜索优化算法，已广泛应用到组合优化等领域，具有很好的适应性。针对移动机器人路径规划问题，本文提出了一种基于蚁群算法和遗传算法的路径规划融合算法，该融合算法是兼有两种算法的性能，综合了两种算法长处的一种启发式算法。只要有可行通道客观存在， 即使在非常复杂的地形环境， 也能迅速找到一条优化路径。仿真结果表明了该融合算法在移动机器人路径优化中的有效性和实用性。