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

作     者：丁寅 

作者单位：华中科技大学 

学位级别：硕士

导师姓名：胡迎松

授予年度：2012年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：路径规划 遗传算法 蚁群算法 自适应 融合 

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