一种遗传蚁群算法的机器人路径规划方法.pdf

《一种遗传蚁群算法的机器人路径规划方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第27卷第3期计算机仿真2010年3月文章编号：1006-9348(2010)03-0170—05一种遗传蚁群算法的机器人路径规划方法何娟，涂中英，牛玉刚(华东理工大学信息科学与工程学院，上海200237)摘要：研究遗传算法和蚁群算法可作为新兴的智能优化算法，在解决多目标、非线性的组合优化问题E表现出了传统优化算法无可比拟的优越性。基于将两种智能优化算法动态融合的思想提出了一种新的遗传蚁群算法(GA—ACO)。与已有的将遗传算子引入蚁群算法的结合方式不同之处在于．GA—ACO算法第一阶段采用了遗传算法生成初始信息素分布，在第二阶段采用蚁群算法求出最优解，从而

2、有效地结合了遗传算法的快速收敛性和蚁群算法的信息正反馈机制。仿真结果表明，在具有深度陷阱的特殊障碍物环境下，应用GA—ACO算法求解机器人路径规划问题可以得到较好的的结果。关键词：遗传算法；蚁群算法；机器人路径规划中图分类号．TP24文献标识码：AAMethodofMobileRoboticPathPlanningBasedonIntegratingofGAandACoHEJuan，TUZhong—ying，NIUYu—gang(SchoolofInformationScienceandEngineering，EastChinaUniversityofSci

3、enceandTechnology，Shanghai200237，China)ABSTRACT：Astwopopularintelligenceoptimalalgorithm，AntColonyOptimalAlgorithm(ACO)andGeneticA1-gorithm(GA)performbetterthantraditionaloptimalalgorithmsinmanyfields．Basedontheintegrationofthetwoalgorithms，thepaperproposesakindofGA—ACOAlgorithm．Di

4、fferfromtheexistentmethodofinsertinggenetic叩-eratorsintoACO，thebasicthoughtoftheGAACalgorithmisthat，thealgorithmusesGAtogeneratetheinitialphero-monedistributionintheformerstageandthenusesACOtoworkoutthefinalsolutioninthelaterstage．BydoingSO，themeritsofthetwoalgorithmscanbemadethemo

5、stuseoftoobtaintheefficiencyoftimeandprecision．Thesimu·lationresultindicatesthatintroducingGA—ACOalgorithmtomobileroboticpathplanningprobleminobstacleenvir-omentwithdeeptrapsilluminatesitsefficiency．KEYWORDS：Geneticalgorithm；Antcolonyoptimalalgorithm；Mobileroboticpathplanningl引言路径规

6、划问题是移动机器人研究领域的一个重要的课题，根据事先掌握环境信息的程度，路径规划问题可分为基于先验环境信息的全局路径规划和基于传感器的局部路径规划。传统的全局路径规划方法主要有栅格法、可视图法、拓扑法和自由空间法等，这些传统的方法均存在计算效率低，不适用于高维的优化问题的缺点¨1。随着神经网络、蚁群算法和遗传算法等智能仿生优化算法的提出和快速发展，许多学者将这些算法应用于机器人路径规划领域旧’3’4J，取得了很好的效果。基金项目：国家自然科学基金(60674015)；上海市重点学科项目(B504)收稿日期：2008—11—20修回日期：2009—02—02-

7、--——170．-．——遗传算法(GeneticAlgorithm，GA)是一种借鉴了自然界中自然选择和自然遗传机制的随机优化算法，自美国Michi．gan大学的Holland教授于1975年提出以来，在众多领域获得了广泛的应用。蚁群算法(AntColonyOptimizationAlgo-rithm，ACO)是Dorigo等在1996年提出的模拟自然界真实蚂蚁觅食过程的一种仿生算法。问世短短几年来，其在许多方面获得了成功的应用，受到了广泛的关注。由于机器人路径规划问题的复杂性，往往单独采用一种方法很难达到令人满意的效果。一些学者尝试将两种算法结合起来求解作

8、业车间调度∞J、TsPp’8’9J、连续函数优化等问