1、本科毕业设计（20届）基于免疫遗传的机器人路径规划所在学院专业班级电气工程及其自动化学生姓名学号指导教师职称完成日期年月I摘要【摘要】路径规划问题是移动机器人系统需要处理的问题之一，对于路径规划，我们需要做的就是在环境信息空间中，按照一定的规则找出从起始点到终点的最短的或者最优的没有任何碰撞的路径。根据环境信息可知，我们可以分为环境可知的和环境未知，在这当中，我们也要分为环境是静态的或者动态的两种，而本文需要做的就是在已经环境下的静态障碍物的路径规划问题。本文的路径规划问题是采用了遗传免疫算法来进行路径规划的，在静态已知的环境中，我们需要做的就是将起点到终点的最优的路径找出来，遗传算法包括自然
2、选择和进化的思想，免疫算法是生物免疫学的思想，两者合一有很强鲁棒性，同时避免了遗传算法所引起的局部收敛。本文最后设计并实现了一个机器人路径规划，首先通过采用免疫遗传算法给机器人规划了一条路径使其绕过障碍物，使机器人达到规定的目标点，并且得到了最佳路径。【关键词】移动机器人；路径规划；免疫遗传。IIABSTRACT【ABSTRACT】MOBILEROBOTPATHPLANNINGPROBLEMISONEOFTHESYSTEMNEEDTOBEADDRESSED,FORTHEPATHPLANNING,WENEEDTODOISINTHEENVIRONMENTALINFORMATIONSPACE,INA
3、CCORDANCEWITHCERTAINRULESTOTHEENDFROMTHESTARTINGPOINTTOFINDTHESHORTESTORTHEBESTTHEREISNOCOLLISIONPATHACCORDINGTOTHEENVIRONMENTALINFORMATIONWEKNOWTHATWECANKNOWTHATFORENVIRONMENTALINFORMATION,WECANBEDIVIDEDINTOENVIRONMENTALKNOWABLEANDTHEENVIRONMENTISUNKNOWN,INTHIS,WEHAVEDIVIDEDINTOTHEENVIRONMENTISSTAT
4、ICORDYNAMICOFTHETWO,ANDTHISNEEDSTOBEDONEISSTATICOBSTACLESHASBEENTHEPATHOFENVIRONMENTALPLANNINGPATHPLANNINGOFTHISARTICLEISTHEUSEOFAGENETICIMMUNEALGORITHMFORPATHPLANNINGINASTATICKNOWNENVIRONMENT,WENEEDTODOISTOPOINTTOTHEENDTOFINDOUTTHEOPTIMALPATH,GENETICALGORITHMS,INCLUDINGNATURALSELECTIONANDEVOLUTIONT
5、HINKINGOFBIOLOGICALIMMUNEALGORITHMIMMUNOLOGICALTHOUGHT,ASTRONGUNITYBETWEENTHEROBUSTNESSOFGENETICALGORITHMANDAVOIDLOCALCONVERGENCECAUSEDFINALLY,THEDESIGNANDIMPLEMENTATIONOFAROBOTPATHPLANNING,THEFIRSTTHROUGHTHEUSEOFGENETICALGORITHMTOTHEROBOTPLANNEDAPATHTOBYPASSTHEOBSTACLES,ANDTHROUGHTHECPLATFORM,THERO
6、BOTUPTOTHEREQUIREDTARGETPOINT,ANDGETTHEBESTPATH【KEYWORDS】MOBILEROBOT；PATHPLANNING；IMMUNITYGENETICALGORITHMIII目录1绪论错误未定义书签。11什么是移动机器人112移动机器人的发展趋势错误未定义书签。13机器人的发展史错误未定义书签。14本文的主要任务错误未定义书签。2移动机器人的路径规划问题错误未定义书签。21什么是路径规划错误未定义书签。22路径规划的特点错误未定义书签。23传统路径规划方法错误未定义书签。231栅格法错误未定义书签。232可视图法错误未定义书签。233自由空间法错误未
7、定义书签。234人工势场法错误未定义书签。24智能路径规划方法错误未定义书签。241遗传算法错误未定义书签。242人工蚁群法错误未定义书签。243神经网络法错误未定义书签。244模糊逻辑法错误未定义书签。3遗传算法路径规划错误未定义书签。31遗传算法简介错误未定义书签。311遗传算法的起源错误未定义书签。312遗传算法的原理错误未定义书签。32遗传算法的规划错误未定义书签。321编码种群初始化错误未定义书签。322适应度函数错误未定义书签。323选择错误未定义书签。324交叉错误未定义书签。325变异错误未定义书签。33遗传算法的特点错误未定义书签。4基于免疫遗传算法的机器人路径规划错误未定义
8、书签。41遗传算法的缺点错误未定义书签。42免疫算法错误未定义书签。43路径规划的环境错误未定义书签。44适应度函数错误未定义书签。45抗体的编码与初始化抗体的产生错误未定义书签。46遗传免疫算子错误未定义书签。47精英策略选择错误未定义书签。48免疫遗传算法的具体步骤错误未定义书签。49实验仿真错误未定义书签。410结果错误未定义书签。5结论总结和期望5附录811绪论11什么是移动机器人所谓的移动机器人就是由遥控操作器，传感器和自动控制载体组成的一个系统，移动机器人能够完成很多危险的行为，例如从事危险、恶劣的工作环境下的任务和别的一些平常人无法做到的事情，这些事情让他们做起来能够更加的灵活，
9、有效。20世纪60年代，美苏两个超级大国都完成了月球探测计划，并且研制出来很多的移动机器人，方便于他们对于外太空的探索。例如美国的“探测者”3号，就是在地面控制的基础上，在月球上顺利完成了各项任务。同时苏联的探测器“登月者”20号也是在无人驾驶的情况下，通过地面操作，成功从月球获得了研究的材料，并且成功返回地球。20世纪70年代，日本的早稻田大学研究出来具有仿人类的机器人，并且日本近年来一直都在研究这方面，也取得了一定的成果。由此可见，对于移动机器人的发展，各个国家都非常积极，同样也是显示一个国家实力的一个方面，当然，移动机器人在各个领域都有研究应用，比如在核能、海底资源探测等的移动机器人发展
10、也非常地迅速。机器人的发展和研制在各个领域都是不同的，这当中研究的内容也是有很大的差距的，但是他们之间还是有一些共同的特点需要研究的，比如传感器方面，移动技术，路径规划，控制技术等等，很多方面都是需要去研究的，机器人就相当于是人类，也需要眼睛去看，走路，都是和人类有类似的行为。移动机器人当然也分好几类的，比如有些是车轮式的移动机器人，有些是足式的机器人（有2足,4足,6足等等各种类型），当然也有一些比较特殊的移动机器人，需要运用到一些特殊领域，不同的机器人适合不同的工作环境。需要解决各个方面的问题，这样才能够真正地将解决方案结合起来，并研制成功出移动机器人，然后服务于人类社会，造福人类。移动机
11、器人除了在一些比较重要的领域中运用外，在各种工程自动化，建筑，采矿，农业，水利，运输等都有广泛的运用和发展前景12移动机器人的发展趋势从机器人的发展过程中来看，现在的机器人发展仍然存在着很多的问题以及一些相关科学的发展方向，移动机器人目前的发展趋势主要有以下几点1机器人本身将更加地灵活和微小，我们现在需要做的就是将其更加广泛地运用到家庭服务和生活中去。2我们需要做的就是能够让机器人运作的工作效率不断地提高，由于局限于系统水平，计算机的运行等方面，对于机器人的精确度和控制度等都需要更高的要求。3机器人为人类服务的同时，我们也需要一个更好的平台，来给机器人更好的服务，不断地2与机器人沟通，需要一个
12、平台来处理好人与机器人的关系，让机器人能够更好的服务于我们。4安全性能问题，机器人的问题也存在着很大的问题，为了使机器人能够更好地服务于人类社会，使我们能够更加地安全使用机器人，机器人需要遵守“机器人三规律”一、机器人不可以伤害人或者眼看着人将要受伤害不管不问，袖手旁观；二、机器人必须服从人类给与他的指令，除非是和第一条规律相冲突；三、机器人必须保护好自己，除非和第一，第二条相冲突。5产业化问题，如果一味地只是实验而不运用到实际中，不进行产业化是没用意义的，只有给社会真正带来了价值，才能够有更多的人想要去提高它，而产业化是我们理论联系实际的重要一点，只有做好了这一点，我们才能够把科学技术转化为
13、我们的生产力，因此产业化是我们必须要做的。13机器人的发展史1920年，捷克斯洛伐克的作家在他的小说中首先提到了关于机器人的概念，根据捷克文ROBOTA和波兰文ROBOTNIK（都是工人的意思），创造了所谓的“机器人”的概念。1939年，在美国纽约的世博会上，西屋电气公司制造了一个名叫ELEKTRO的家用机器人，并在该届世博会上展出了，它是由一些电缆来控制操作的，它不但能够走路，也可以说话（只有77个字），而且它还可以吸烟，虽然它还不能成为真正意义上的家用机器人，但是也由于这个机器人，让人类对于机器人的前景有了一个新的认识，说明机器人还是能够被发明出来的，并且真正意义上运用到人类社会的。194
14、2年，美国作家阿西莫夫在他的小说中提出了“机器人三定律”，虽然只是在小说中提出来的，但是在后来却是被机器人学术界默认为研发机器人的基本原则。1948年，诺伯特的控制论，详细的阐述了关于机器人的通信和控制原理与人类的感官神经等方面的相似规律，并且第一个提出了以计算机作为核心的自动化工厂。1954年，美国科学家乔治制造出来了世界上第一台真正意义的可进行编程的机器人，并且在美国申请了专利保护。这类机器人能够按照所编辑的程序来从事程序中所要求的工作，因此也具有通用性能和一定的灵活性。1956年，达特茅斯的会议上，马文明斯基自己对于智能的机器人的概念提出了自己的一些想法，也就是说智能机器人可以创建周围环
15、境的一些模拟的东西，如果当他遇到问题时，他就能够从中找出办法并且解决问题。也就是这个想法影响了后来智能机器人的发展方向。1959年，美国发明家约瑟夫英格伯格与德沃尔制造出来了第一台真正的工业机器人，3随后他们成立了世界上第一个机器人公司，也就是大家现在熟悉的UNIMATION公司，当然由于英格伯格对于工业机器人的热衷，以及对其的发展和宣扬，他被大家称之为“工业机器人之父”。1962年，在美国的AMF产出了名叫“VERSTRAN”的机器人，和UNIMATION生产的机器人一样，成为了真正意义上的具有商业化的工业机器人，并且也因为这样这类机器人还出口到国外，掀起了各国科学家针对机器人的研究热情。1
16、9621963年传感器的发展使得机器人的操作器得到了很大的改善。于是科学家们开始在各种各样的机器人上面按照传感器，当然也包括1961年由恩斯特使用的触觉传感器，以及在世界上第一台“灵巧上”上面用到的压力传感器，1963年麦卡锡开始在机器人中加入了视觉传感系统，1965帮助MIT推出了世界上第一台视觉传感器，它是可以识别定位的积木系统。1965年，约翰霍普金斯大学实验室研制出来了一个叫BEAST的机器人。BEAST已经可以使用声纳系统和光电管等等，通过周围环境来确定自己的坐标位置。20世纪60年代中，美国麻省理工学院，英国爱丁堡大学等相继成立了关于机器人的研究室。同时美国开始研究第二代有传感器和
17、感知系统的智能机器人。1968年，美国斯坦福研究所的工作人员宣布他们成功研制出了叫SHAKEY的机器人，它不仅有视觉传感器，而且能够根据指令发现并获得积木，但是他的计算机核心空间非常大。而SHAKEY是可以看成是世界上第一台真正的智能机器人，同时SHAKEY的研制也标志这第三代机器人的开始。1969年，日本早稻田大学的加藤一郎实验室研制出来了第一台用双脚走路的模仿人类的机器人，由于加藤一郎喜欢研制模仿人类的机器人，并且也取得了很大的成功，所以，人们就称之为“仿人机器人之父”，不过在以后的机器人研制中，日本科学家都喜欢研发仿人的机器人，并且在这方面也非常的擅长，后来因为这个也出现了本田公司的AS
18、IMO和索尼公司的QRIO。1973年，世界上第一台微型计算机和机器人合作，诞生了美国CINCINNATIMILACRON公司的T3机器人。1978年，UNIMATION公司生产了通用机器人PUMA，PUMA的生产标志这工业机器人的技术已经成熟，并且值得一说的是，就算到了现在，PUMA还工作在第一线。1984年，英格伯格再一次推出了叫HELPMATE的机器人，他能够在医院里面为病人送药，送饭，送邮件，在这样的情况下，英格伯格因此预言他能够让机器人擦地板，做饭，洗车以及安全检查。41990年，中国学者周海中教授在论机器人中大胆预言，到了21世纪中，纳米机器人将要彻底改变人类现在的生活方式和人类劳
19、动形式。1988年，丹麦的乐高公司生产了机器人套件，这也使得机器人能够通过一些简单的套件组合起来，这也使得机器人走向了个人世界。1999年，日本索尼公司生产的机器人爱宝宠物狗，一上市就销售一空，从此娱乐机器人也迈入了普通的家庭中，相信以后也会有很多的微型机器人的加入。2002年，美国IROBOT公司生产出了一款叫ROOMBA的吸尘器机器人，他能够躲避障碍物，自动进行路径规划，设计路线，还可以在能量不足的情况下，自动走向充电器。ROOMBA的销售是目前世界上最大的，也是最受欢迎，最商业化的机器人。IROBOT公司在中国也授权了代理商，即北京微网智宏科技有限公司。2006年，微软公司生产的MICR
20、OSOFTROBOTICSSTUDIO，是的机器人的平台化，模块化更加的明显，因此，比尔盖茨说，家用机器人不就以后将席卷全世界。14本文的主要任务本文主要是应用遗传免疫算法来进行机器人路径规划方面的研究，由于机器人路径规划之前也有做过很多相关的设计，当然不同的环境建模针对不同的领域有很多种路径规划的方法，环境分为静态障碍物和动态障碍物，本文的研究方向是在静态的环境下，在前人的基础上，通过提出免疫遗传算法的机器人路径规划，效果比较满意。第一章，主要介绍了关于机器人的一部分内容，其中包括机器人的定义，移动机器人的发展史和发展趋势。第二章，主要介绍了关于机器人路径规划方面的一些问题，比如路径规划的定
21、义，路径规划的特点以及传统的路径规划方法和智能路径规划方法。第三章，主要介绍了本文所需要用到的遗传算法的路径规划，对遗传算法的相关问题进行了解释与介绍。第四章，主要介绍了关于基于免疫遗传算法的路径规划的具体方法，所需要用到的一些概念以及方法，并对实验进行仿真与结果。第五章，主要是对该研究的总结与展望。52移动机器人的路径规划问题21什么是路径规划移动机器人路径规划是机器人领域里面一个重要的研究方向，也是机器人学与人工智能的一个比较令人感兴趣的方面。但是无论是那种机器人，他在工作的时候，总是希望按照一定的准则，如用最短的路程，消耗最少的能量等等，在工作空间中沿着某一条最短的路径行走。机器人路径规
22、划是要完成规划路径，避免障碍物，寻找起始点到目标点的任务，移动机器人路径规划是导航的一个重要的任务，根据环境和障碍物的不同可分为以下几类1已知的环境下的静态障碍物路径规划；2未知的环境下的静态障碍物路径规划；3已知的环境下的动态障碍物的路径规划；4未知的环境下的动态障碍物的路径规划。而我们的目标就是从全局规划路径中寻找出提条符合条件的最优的路径规划路线。22路径规划的特点大多数的导航系统都是由局部规划和全局规划两部分组成的，前面主要是解决机器人的定位和路径的跟踪，后者主要是解决全局到局部，再由局部到全局的思想来实现。路径规划存在着很多问题，当然路径规划也有一些特点复杂性在环境建模中，机器人路径
23、规划是一个非常复杂的过程，需要大量的计算量。随机性在比较复杂的环境中，机器人路径规划可能会出现一些意外的事情。23传统路径规划方法传统路径规划有很多种方法，其中包括栅格法、拓扑法、可视图法、概率路径图法、自由空间法、广度优先搜索方法等。本文采用的是栅格法。231栅格法栅格法是当前研究最广泛的路径规划之一，该方法是HOVODEN于1968年提出。栅格法的主要思想是将机器人的工作环境划分成一系列具有二值信息的网格单元，障碍物空间和自由空间分别被不同的数值所标示（如0表示自由栅格，1表示障碍物栅格）。这些栅格构成了一个连通图，在这个连通图上搜索一条从初始位置到目标栅格的路径。在栅格法中，栅格的大小是
24、由机器人行进的区域的可视度所决定的，其直接影响着环境信息存储量的大小和规划时间的长短。栅格选的小，环境的分辨率就高，在密集障碍物或狭窄通道中发现路径的能力强，但环境信息的储存量大，规划时间长，降低了系统的实时性；栅格选的大了，环境信息储存量小，决策速度快，抗干扰能力强，但环境的分辨率低，在相应环境中发现路径的能力变差。因此合理选择栅格的大小是栅格法的重要问题。在某个局部栅格中，所有的参考点（也即机器人穿行环境时收集的传感器数据）应该是互相可6见的。这就意味着在空旷的区域同一时间能够有更多的参考点是可视的，由此一个有着粗糙解析的大栅格就可以将此区域描述出来。相反的在混乱区域，当机器人围绕障碍物转
25、向或穿过门时，它容易很快的丢失掉其他参考点的视线。描述这些区域的栅格就应当较小而且要有一个较好的解析。这也就使得机器人在障碍物间或狭窄走廊中的机动行进成为可能。另外，栅格越小，就更容易做到路径的实时再规划。虽然这种方法不能保证所有可能的路径都能够被发现，但是它提供了一种对环境本能和实践的描述，使得机器人更加人性化，“正如机器人能够自主看见一样”。区域中的栅格通过那些重叠在不同栅格上的参考点相互连接在一起。这样整个机器人的路径规划问题也就分解成了如何规划从一个参考点运行到下一个参考点最优无碰路径问题。232可视图法可视图法是一种以机器人作为一个点，以各个障碍的每一个顶点，还有就是将目标点也作为一
26、个点，我们要达到的目标就是将机器人这两个点和各个障碍物的顶点，以及目标点之间左右的点均连接起来，然后就达到了我们要求的所有的连线，当然这其中也删除掉穿越障碍物的连接线，这样，在搜索任务中，所有的路线都是直线与直线的连接，这样最优路径就是这样从终点到目标点的所有相邻直线的连接中最短的一个。这样的办法能够求出其最短的路径，但是由于要接近所有的顶点，需要做的就是忽略不计机器人的大小，不然就容易碰撞，这样就容易损坏或者使搜索的时间变长。233自由空间法所谓自由空间法的意义就是把机器人的工作空间分成自由空间和障碍物空间两种。一开始我们将定义好的比如广义锥形或者凸多边形等基本形状构造自由空间，然后将自由空
27、间表示成连通图，通过搜索连通图来进行路径规划。自由空间的构造方法是从障碍物的一个顶点开始，依次作其它顶点的链接线，删除不必要的链接线，使得链接线与障碍物边界所围成的每一个自由空间都是面积最大的凸多边形，连接各链接线的中点形成的网络图即为机器人可自由运动的路线。该法比较灵活，起始点和目标点的改变不会造成连通图的重构，但算法的复杂程度与障碍物的多少成正比。对于较狭窄的空间区域，它能保证机器人最大的允许误差，从而避免与障碍物发生碰撞但某些情况下路径偏离机器人前进目标太远，不利于实现最优路径。另外，路径大多复杂多折而不利于机器人行走。该方法主要应用于机器人速度不是很快，规划精度要求不高的场合。按照划分
28、自由空间方法的不同又可分为凸区法、三角形法、广义锥法12。234人工势场法人工势场法最开始是由KHATIB提出来的一种虚拟力法。它的基本思想是让机器人在其工作环境中的运动看成是虚拟的人工受力场的一种运动，障碍物对于机器人有产生斥力，而目标点对机器人也能够产生引力，引力与斥力相互合作作为机器人的加速力，来打到控制机器人的运动方向。该方法简单，而且便于低层的实时的控制，在实时的避障与平滑的轨迹控制等等方面都取得了广泛的应7用，但是对存在局部的所谓最优解的问题，也会容易产生死锁的现象，所以尽可能地使机器人在到达目的地之前就已经处在在局部的最优点。人工势场法是由于它自己的算法比较简单，而且容易扩展开来
29、而引起了广泛的重视，其基本的思想当然是借助于寻找路径点的耗能的函数的最小值点从而使路径能够避开障碍物。通常在这种情况下，它的势函数是一个和距离有联系的标量，因此我们在在找寻路径点的时候，如果考虑障碍物的边界的外形时，很难用方程式计算出来，所以必须要用离散的方法搜索这个函数的最快的下降的方向，但是也因此带来了离散精度与计算量之间的矛盾，如果只是把障碍物近似地看成是圆形的物体，又不可以区别出不同边界障碍物的作用。传统的人工势场法因为缺乏引入优化的过程而比较相对容易局限于局部的极小的区域且不容易调节，所以不适于找寻最短的路径。在我们考虑到机器人在动力学方面约束的时候，机器人怎么样跟踪规划出来的路径同
30、样也是一个问题。有学者考虑移动机器人的动力学约束条件的时候，提出了移动机器人路径规划时候的最优的控制方法，从而使移动机器人能够避开运动障碍物的时候，也能够以最短的路径来达成被编辑所确定的任务。不过这个方法如果在最优路径控制计算的时候，起始点的选择同样也受到了相对比较严的限制，该方法的计算量长，所有比较难保证躲避障碍物的实时性。也有学者提出移动机器人最优化地路径规划的算法，它不但解决了最优的路径规划问题中起始点选择的问题，迅速地提高了算法的运算的速度，而且也实现移动机器人的实时路径规划运动10。24智能路径规划方法智能路径规划方法有很多种，因为在路径规划中具有系统的复杂性，描述问题的不准确性，周
31、围环境变化的随机性以及优化的多约束性和对多目标的要求，经常使我们在使用传统的方法中显得没有办法。于是近年来人们对于从不同角度通过对生物系统及其行为特点进行了描述模拟，使得产生了一些对现代科技发展有重要意义的新型学科，并且被广泛地应用，其中包括遗传算法、神经网络、模拟退火算法、免疫算法、蚁群算法等等，其中免疫遗传算法的综合我们将在第四章讲述。通过广泛使用以上算法，我们在各个领域都取得了很大的成果。241遗传算法对于遗传算法，目前在机器人路径规划方面的研究是用得比较多的一种方法，不管移动机器人是在静态的环境下还是在动态的环境下，遗传算法和它的类似算法都得到了比较广泛的应用，并且取得了一定的成果。孙
32、树栋等通过使用遗传算法完成了在离散的工作环境下的移动机器人的路径规划，并且仿真的实验也取得了比较令人满意的结果，但是由于是处在已经环境的静态障碍物里面，当然跟实际联系还是有差距的。美国的两位学者在使用离散的工作环境下的移动机器人的路径规划的时候，也较问题更加升入，通过采用了栅格序号的方法，统一确定了个体的长度并且随机产生了障碍物的数量和位置，并且在8搜索结果的过程中，还插入了随机的障碍物，使得模拟环境发生了一定量的变化，通过仿真实验他们验证了这种算法的可行性。不过在路径规划中是用栅格法还是有一定的遗憾的，如果栅格太大，那最好路径规划的精度就有很大的差距，但是如果说栅格太小，那所占用的内存就会大
33、很多。所以周明等想出了一种在连续的工作环境下的移动机器人在路径规划中的应用，这种方法利用链接图建模来进行路径规划，他们先用了图论中的比较成熟的算法来搜索出可选路径，然后再对用遗传算法来调整这个路径，然后一步一步得到比较优秀的路径规划，但是该方法对于环境比较复杂的情况下如果使用链接图建模比较困难，无法达到要求。因此他们提出了一种遗传模拟退火方法，在遗传算法和模拟退火方法的结合下来解决所遇到的问题，实验结论也证实了该方法有效地提高了机器人路径规划的计算速度，保证了规划的质量。在多移动机器人方面遗传算法也得到了非常广泛的运用，人们通过在已知环境下的多移动机器人的路径规划中，通过协调运动，借助神经网络
34、，免碰撞的思想，使得机器人路径规划在较为复杂的环境下依然能够协调和优化。242人工蚁群算法所谓人工蚁群算法是一种比较新颖的模拟进化的方法，这个算法是由意大利的学者们提出来的。大家都知道，蚂蚁在寻找食物的时候，在他走过的路中，会留下来一些激素，而这些激素会像标记一样让后面的蚂蚁知道他走的路径，如果说激素留下的越多，那么这条路就越吸引蚂蚁。科学家曾经做过一个实验如果人们利用人造的激素在一张纸上画一条路径出来，蚂蚁会出乎意料的按照这条路径走完，所以，根据这个有趣的现象，人们设计出来一种路径规划的方法，也因为蚂蚁，所以就叫做“蚂蚁算法”。蚂蚁是自然界一种非常普通的动物，但是随着科学研究的不断深入，人们
35、开始利用仿生学来服务科学研究，蚂蚁就是其中的一种，虽然蚂蚁这个小东西很不起眼，但是，越来越多的人开始关注相对比较弱小的动物，如何通过自己这个个体来完成比较复杂的工作呢科学家们研究发现，蚂蚁在寻找食物的时候之所以能寻找出一条优化的路径是因为它们会分泌出来一种激素。蚂蚁在行走的过程中，会不断地分泌出来一种信息素，而这种信息素可以告诉后面来的蚂蚁，吸引它们来走他的这条路径，随着时间的推移，这所谓的信息素也会慢慢蒸发掉，这样，在比较短的时间内如果蚂蚁经过同一条路径的数量比较多，那么就说明这条路径的信息素就比较高，因为信息素高了，也就能够吸引更多的蚂蚁来走这条路径，使得信息素更加多。对于距离比较长的路径
36、，走这条路径的蚂蚁会比较少，因为就算一开始信息素高，但是随着蒸发掉，信息素会减少，蚂蚁也会减少，最后当信息素越来越少就根本无法吸引蚂蚁走这条路了，这样就形成了一个正反馈，对于比较短的路径，蚂蚁就会越来越多的去走一条路径。而人工蚁群算法就是在这个基础上建立起来的。9243神经网络法神经网络法是一个比较有高度的分布式系统，它为解决移动机器人路径规划的实时性比较高的问题提供了一个可能性。它的基本思想是利用动物的神经网络来描绘周围环境的约束条件，并且计算出来碰撞的能量损耗。将迭代的路径点的损耗能力的函数和距离的函数两者作为最优路径的目标函数。通过使用这个方法来优化目标函数，确定点的运动方程式，最后使得
37、路径点趋向于一个最优路径。该种方法具有鲁棒性强等特点，在智能移动机器人路径规划中有非常好的优势，但是神经网络的权值非常难设定。禹建丽等提出了一种基于神经网络的移动机器人路径规划的方法，该方法对于障碍物的形状和位置都已知情况下的移动机器人路径规划的算法进行了研究，它的能量函数是利用神经网络的结构来定义的，根据路径点位于障碍物的不同位置来选取不一样的运动方程式，最后规划出来一种无碰撞的最短的移动机器人的规划路径，该方法计算简单，收敛速度也非常的快。但是为了提高速度，在利用神经网再加上引进线性再励自适应的变步长算法来实现，实现后的方法足足比移动机器人路径规划提高了10倍。244模糊逻辑法模糊逻辑的方
38、法就是在线规划时经常采用的一种规划的方法，这包括建模与局部规划。庄晓东等提出了一种基于模糊概念动态环境的模型，参照物的位置与运动的信息来构造二维的隶属度函数；之后使用模糊综合评价来对各个方向进行较综合的考察，得到搜索的结果。该方法在移动的障碍物和移动目标环境中能够有效地实现移动机器人的避碰。李彩虹等提出一种在未知的环境下的移动机器人的模糊控制的算法，并且对这个算法进行了推导和大量的仿真，证明此算法的鲁棒性强，可以消除传统算法中常存在对机器人的定位精度的敏感以及对环境信息的依赖性强等缺点，使得移动机器人行为表现得较一致和稳定。HARTMUT等提出的一种未知环境下高级机器人的模糊导航的方法，该实验
39、由8个不一样的超声传感器来供应环境的信息，之后使用基于模糊控制中的导航仪器来算出这些信息，计算出来机器人的路径。这种方法在环境未知或者已经发生变化后就够比较快速规划移动机器人的路径，而对于要求有比较少的路径规划时间来说是一种导航的好方法。但是它的缺点是当障碍物的数目增加进去的时候这方法的计算量会非常大，影响规划结果10。103遗传算法介绍33遗传算法简介前人通过用遗传算法在路径规划方面的应用取得了一定的成果，本文是在遗传算法的基础上作出的改进，下面我们将讲述一下有关遗传算法的知识。331遗传算法的起源这些年来，通过生命科学领域被广泛的运用，而随之产生的各种计算方法也不断的出现。而免疫遗传算法是
40、在免疫算法和遗传算法的基础上，结合这两者而共同应用，能够非常完美地配合起来，达到预期的目标，遗传算法是根据达尔文的进化论的自然选择和生物进化理论来进行计算机模拟的，是一种比较好的搜索最优解路径规划的方法，它是有美国密歇根大学的HOLLAND教授在1975提出的，之后才被大家所熟悉，也就是现在大家所知道的遗传算法的简单版本，我们称之为GA算法。332遗传算法的原理遗传算法是受到生物学进化与遗传而得到的启发，形成一种比较独特的方式，所以遗传算法的运算也与生物学的遗传学进化学有着非常惊人的相似之处，而且遗传算法的算子名称都是仿照生物学来的。在遗传算法中的最基本点的就是字符串，其实这就相当于生物学的染
41、色体。而字符串是通过一连串的字符组成的，没一个字符都有一个特定的意义，它反应了所需要解决的问题的某个特征，这其实就相当于生物学的基因。在进行字符串的交换的时候，字符串就发生了变化，其实也就相当于染色体的基因发生了变化，其实也就是生物学的基因交换和突变的操作，遗传算法只是相当于改变其中的某些基因，而不是整个染色体。遗传学非常注重等位基因，它是反应生物相同的特征的，相同的基本上说明是存在一定的相同关系的，其实就放在遗传算法中，也就是某个位置的字符是相同的，基因对应于字符。在遗传学中，杂交产生的子代显现出父代的特性，就称之为显性性状，相反，没有表现的就称之为隐性性状。控制显性性状的是显性基因，控制隐
42、性性状的是隐性基因。运用到遗传算法中，我们也需要对这样字符串加以区别。遗传是生物的基本特征，种瓜得瓜种豆得豆，遗传致使我们知道，鱼不可能遗传之后突然飞上天空。这就是我们所说的遗传。细胞是构成生物的单位，细胞中含有染色体，而我们生物所以的特征都提醒在这个及其微笑的染色体中。遗传信息是由基因组成的，生物的各种行为都是由这写染色体来控制的，基因是其遗传的最基本得单位。细胞通过分裂之后进行自我的复制，然后在细胞分裂的过程中，它的遗传基本也被复制到下一代中，从而他的性状也被后代继承。经过生物学家的研究知道，染色体是有DNA组成的，而DNA就是由一些不同的基因排列而成的，当某一位基因发生变11化的时候就说
43、明基因突变了，所有的这些基因都是具有遗传编码的。在细胞分裂的时候，遗传物质DNA通过复制产生新的细胞，新的细胞继承了就细胞的基因。而有性繁殖过程中，像个染色体之间通过交叉重组，组成新的染色体。在进化的过程中，虽然概率很小，但是还是有可能会出现复制出错，等等各种情况到底发生变异，产出完全的新染色体。生物是需要不断的进化的，为了生存，为了适应我们所生存的环境，我们需要通过基因的改变来改变自己，使得自己能够更加适合环境。34遗传算法的规划遗传算法（GENETICALGORITHM）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的JHOLLAND教授197
44、5年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。对于一个函数求最大值或者最小值的优化问题，一般情况下可以描述成一个数学模型下图的公式中，错误未找到引用源。是我们所求的函数，而对于下面2个式子，都是我们的约束条件，U是所求的基本控件，R是U的一个子集，如果都能满足下列条件，我们就可以称之为可行解，所有的
45、这些解集合在一起就是可行解的集合。错误未找到引用源。31下图是遗传算法的流程图12适应度计算复制交叉变异输出结果YN是否满足条件初始化种群图31典型遗传算法流程操作图341编码种群初始化编码种群是遗传算法中求解问题首先需要解决的，利用遗传算法中的最优问题，一开始应该对可行区域中的各个点进行编码。首先应该用某种编码方式将解映射到编码的空间，每一个编码串都对应问题的一个解，即为个体或者染色体。一般采用程序随机方法来确定从起始点到目标点的一群目标个体，称作种群。编码的方法有很多，其中包括二进制，序号法编码，直角坐标系编码、格雷码、实数编码、符号编码、多参数编码和DNA编码等。BALAKRISHMAN
46、等较全面地讨论了编码方法不同的特性，针对其不同应用，为选择和设计编码方法提供了方法，主要有以下的9个特性紧致性、完备性、封闭性、多重性、个体可塑性、可扩展性、冗余性、非冗余性、模块性和复杂性。当确定了编码方式后，我们就需要将解空间映射到编码空间，然后按照这个编码方式得到初始种群。初始种群的产生有2种方式，一种是采用随机数发生器完全随机产生，另一种是借助于先验知识，通过这些先验知识转换成满足条件的，然后在满足条件中选择一些随机数产生解，当然，这样看的话第二种明显比第一种收敛更加快。10342适应度函数为了体现个体的对环境的适应能力，引入了对问题中的每一个个体即染色体都能够进行度量的13函数，叫做
47、适应度函数。通过对适应度函数的符合程度来决定染色体的优劣，这种方法也体现了现代自然进化论中的淘汰法则。对于优化的问题，适应度函数就是我们的目标函数，适应度函数同时也是评价函数。它作为群体中的每个可能的确定长度的特征字符串中指定的一个适应数值。适应度函数必须可以来计算空间里面每一个特定长度的特征字符串，是遗传算法中决定收敛好坏的一个非常重要的因素。343选择选择就是通过和自然选择现象一样，达尔文的进化论中适者生存不适应者淘汰的理论运用其中就是从种群中按照某一个概率成对选择个体，某个个体被选择的概率和它相对应的适应度值成正比。选择常常是通过轮盘赌来进行的。比如某一个种群的规模是N，其中个体为1X,
48、2X,3XNX其对应的适应度值为1FX,2FX,3FXNFX错误未找到引用源。那么个体错误未找到引用源。被复制到下一代的概率就为式32III1NSIXIFXPFX32个体被选择的概率应对于下面占据的转盘中的某一个区域，轮盘赌图如下图32轮盘赌图为了能够选择交配的个体，我们需要进行多次选择，每一次选择都均匀产生一个01的随机数，用这个随机数来作为选择指标，通过和个体的相对的适应度确定被选择的个体。从图中可以看出来，适应度函数值大的能够到下一代的概率明显就比较大。选择的目的是为了获得更多的适应度高的个体，这对于我们的目标收敛到优化解具有很大的意义，但是为了防止过早收敛，同时达到最优解，我们需要在复
49、制的过程中也要尽量保持种群的多样性，而不是全部选择单一适应度高的多个个体，转轮盘的复制是选择复制概率正比于适应度值，所以我们也称之为比例选择。该方法能够使收敛加快，但是当个体差别大的时候，也可能使其损失多样性而出现过熟的问题。344交叉14在自然界中，生物进化过程中起到重要作用的是基因重组和变异。通过基因重组和变异，有些生物能够更加适应环境的变化，交叉就是指通过两个父代的部分的结构用以替换重组而生成新的个体的操作。这样通过交叉，遗传算法搜索能力便得以飞跃的提高。交叉算子通过交叉率来将种群中两个个体随机地进行交换基因，使其能够产生新基因组合，希望将有用的基因组合成一起。然后根据编码的表示方法不同，可以得到以下的算法单点交叉、多点交叉、实值重组、离散重组、均匀交叉、扩展线性重组、洗牌交叉、中间重组、线性重组、二进制交叉、缩小代理交叉10。其中单点交叉为最常用的。具体的操作是在某个体串中随机地设定一个交叉点，然后实行交叉时，对该点前或者后的两个个体部分的结构进行相互转换，并生成两个新的个体。下面给出有关单点交叉其中的一个例子个体X11011011101010新的个体个体Y10110101011101新的个体345变异变异就是在很小的几率下，某个体在某位基因随机地发生了改变。对于二进制而言，就是相当于其某一位的基因0变成1或者1变成了0，交叉后，子代
