文档介绍：分类号学号 M200972518
学校代码 1 0 4 8 7 密级

硕士学位论文

基于遗传和蚁群的自适应
路径规划算法研究

学位申请人: 丁寅
学科专业: 计算机应用技术
指导教师: 胡迎松副教授
答辩日期: 2012 年 1 月 15 日
A Thesis Submitted in Partial Fulfillment of the Requirements
for the Degree of Master of Engineering

Research on Self-adaptive Path Planning
Algorithm Based on ic and
Ant Colony Algorithms

Candidate : Ding Yin
Major : Computer Application Technology
Supervisor : Associate Prof. Hu Yingsong

Huazhong University of Science and Technology
Wuhan, Hubei 430074, P. R. China
January, 2012
独创性声明

本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研
究成果。尽我所知,除文中已经标明引用的内容外,本论文不包含任何其他个人或
集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在
文中以明确方式标明。本人完全意识到,本声明的法律结果由本人承担。

学位论文作者签名:
日期: 年月日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权
保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。
本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检
索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

保密□,在_____年解密后适用本授权书。
本论文属于
不保密□。
(请在以上方框内打“√”)

学位论文作者签名: 指导教师签名:

日期: 年月日日期: 年月日
华中科技大学硕士学位论文
摘要
智能寻径问题源自几何学领域。当前随着机器人寻路、道路导航、虚拟现实、
计算机游戏等领域研究逐步深入,该问题成为了一个很重要的研究课题。人工智能
路径规划方法因其具有全局搜索、信息反馈和自我学习等优点,对它们的研究显得
尤为重要。其中仿生学算法是人们受到生物进化和生物日常行为启发研究出的用来
解决复杂优化问题的方法。其中包括遗传算法,神经网络,蚁群算法等知名算法。
介绍了当前几种常用的路径规划算法,并比较了它们的优势和不足。重点介绍
了人工智能算法中的遗传算法和蚁群算法。遗传算法具有很强的快速全局搜索能力、
鲁棒性,但是无法利用系统的反馈信息,容易在后期做大量无谓的冗余迭代,导致
收敛速度下降。蚁群算法具有很好的信息反馈性,但是由于初期信息素匮乏导致求
解速度较慢。给出了一种基于两种算法自适应动态融合的方法,前期利用遗传算法
生成一组解作为蚁群算法的初始信息素分布,后期用收敛速度参数使蚁群算法自适
应地融合遗传算子。不仅提高了解的收敛速度,而且改善了蚁群算法后期收敛过快
导致陷入局部最优的问题,增强了整个算法的全局搜索性。
利用栅格法构建路径规划环境,在多种障碍物环境下进行仿真实验。通过大量
实验对自适应动态融合算法的各个阶段参数对算法的影响以及它们的协同关系进行
研究,得出了较为优化的参数组合方法。同时,对比基本融合算法和给出的自适应
动态融合算法,在有效性、可行性以及算法性能方面得出了较为满意的结果。

关键词:路径规划,遗传算法,蚁群算法,自适应,融合
I
华中科技大学硕士学位论文
Abstract
Intelligent path finding problem stems from the field of geometry. With
the gradual in-depth study in the areas of robot path finding, road navigation, virtual