蚁群算法在汽车导航中应用地研究.pdf

AThesis inNavigation,Guidance and Control Research ofAnt Colony Algorithm inCar Navigation By CHEN Tao Supervisor:Professor GAO Liqun Northeastern University June 2012 万方数据独创性声明本人声明,所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外,不包含其他人己经发表或撰写过的研究成果,也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名:搿,呜期:乒啦牟6甩2-2-目学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定:即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后: 半年口一年口一年半口学位论文作者签名:僭,呜签字日期:驷纽年多月,2目 f 两年∥导师签名:/久■签字日期:勋肛年6目踢目万方数据一II—万方数据东北大学硕士学位论文摘要蚁群算法在汽车导航中的应用研究摘要汽车导航中最短路径问题既是网络分析中的基本问题,也是与道路交通息息相关的热点问题。蚁群算法是一种新型仿生类优化算法,本文进行蚁群算法及其在汽车导航中路径规划的研究,主要研究成果如下: (1)通过分析传统路网模型的数据存储结构的优缺点,提出面向对象的数据存储方法,实现了无用元素的“零”存储,极大的降低了存储空间,同时在文件读取时也提高了读取效率。(2)在寻路径的过程中,讨论单只蚂蚁会陷入自己设置的禁忌表的“回路”中的情况,并提出自己的解决方案,改进蚁群算法,提高了单只蚂蚁寻找路径的成功率。对改进蚁群算法的参数进行了分析,通过实验找到一组适合该算法的最佳参数。(3)在系统分析蚁群算法寻优的基本原理的情况下,融合汽车导航中城市路网的基本特征,提出动态规划搜索区域算法策略,以减小搜索范围。同时对最优路径的存在位置做出分析,并在此基础上设计了限制区域的搜索范围,提高了搜索效率。结合A木算法和改进蚁群算法的优势,提出新的基于动态区域规划的分层蚁群算法。(4)对所提出算法进行了数值仿真实验,实验结果验证了文中所提出方法的有效性。关键词:汽车导航;路径规划;蚁群算法;面向对象;回溯思想-III- 万方数据东北大学硕士学位论文摘要一工V一万方数据东北大学硕士学位论文 ABSTRACT Research of Ant Colony Algorithm inCar Navigation ABSTRACT The shortestpathproblem of car navigation iseither abasicproblem work analysis, or ahotspot which isclosely related recent years,as amember ofthe family ofthe intelligent algorithms,the ant colony algorithm isgradually favored by the majority ofscholars and increasingly being applied plex problems because ofits strong ability tofindbettersolutions Main contributions ofthe dissertation include: (1)By analyzing theadvantages anddisadvantages work model ofthe datastorage structure,we propose anobject—oriented datastorage method inthisdissertation Meanwhile,we implement the“zero”storage ofunwanted elements,which greatly reduces thestorage thesame time,this datastorage structure improves theefficiency offile read (2)In process ofsearching path,we discuss aphenomenon that asingle ant f