基于遗传算法的移动机器人路径规划研究.doc

江南大学硕士学位论文基于遗传算法的移动机器人路径规划研究姓名：杜宗宗申请学位级别：硕士专业：控制理论与控制工程指导教师：刘国栋20090501砀，：，；，“”，：，独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名：超壶蔓日期：关于论文使用授权的说明本学位论文作者完全了解江南大学有关保留、使用学位论文的规定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。签名：柱呈仝、巧导师签名：由！盟日期：三！旦：三：皇墨第一章绪论第一章绪论移动机器人避障路径规划技术大部分的机器人应用中都需要机器人（或机械手）沿一条特殊路径到达目的地而圆满地完成任务，并且要求避免与工作空间中的障碍物相碰撞。对于移动机器人来说，无论是执行简单的装配、搬运等任务，还是执行复杂的抢险救灾、医疗探测等任务，都需要有一个路径规划的过程，尤其是对机器人作业精度要求较高的任务，如工业焊接、医疗手术等，路径规划尤为重要。路径规划不仅要求机器人能够按照某一指标到达目的地，而且还要求机器人能够避免与工作空间中的障碍物相碰撞，其中的障碍物包括静止的障碍物和移动的障碍物。路径规划的好坏直接影响机器人执行任务的质量，所以，找到一种既快又好的规划方法尤为重要。由此可以看出：路径规划技术是机器人研究领域中的一个重要分支，而且成为移动机器人领域的一个研究热点。避障路径规划问题的表达、分类和特点规划问题源于计算机几何学的传统研究课题。七十年代中期，智能机器人研究的需求，促进规划问题的研究。因为装配机器人、移动机器人都涉及到路径规划技术。八十年代初，搬钢琴问题【】，位姿空间法【】，广义锥法【】使规划问题的研究得到了进一步的发展。他认为环境的表达会影响到路径的搜索，及（提出的人造势场法考虑到了机器人的动态性能及直接控制【】。随着研究的深入，位姿空间法及人造势场法得到了广泛的应用并发展成为两种较为成熟的规划方法，并在此基础上产生了许多类似的方法。由于路径规划问题的复杂性，不同的研究者从不同的角度研究某一方面的问题，对具体问题的提法也不完全相同。典型的路径规划问题的提法是指在有障碍物的工作环境中，如何为机器人寻找从起点到终点的运动路径，让机器人在运动过程中能安全、无碰撞的通过所有的障碍物。路径规划问题的研究涉及到环境表达、规划方法、路径执行。环境表达有两层含义，其一是有效的获取环境信息，这与视觉传感器相关；其二是如何将环境信息有效的表达出来。规划方法关心的是在环境表达的基础上，采用有效的方法规划路径并且进行优化。路径的执行与底层控制密切相关，并且考虑机器人的动力学特性，控制机器人按照设定的路径行走。路径规划问题已有的研究方法可以分为全局型方法、局部型方法以及混合型方法三种。全局规划方法依照己获取的环境信息，给机器人规划出一条路径。规划路径的精确程度取决于获取环境信息的准确程度。全局方法通常可以寻找最优解，但是需要预先知道环境的准确信息，并且计算量很大。局部规划方法侧重于考虑机器人当前的局部环境信息，让机器人具有良好的避碰能江雨大学硕士学位论文力。很多机器人导航方法通常是局部的方法，因为它的信息获取仅仅依靠传感器系统获取的信息，并且随着环境的变化实时的发生变化。和全局规划方法向比较，局部规划方法更具有实时性和实用性。缺陷是仅仅依靠局部信息，有时会产生局部极点，无法保证机器人能顺利到达目的地。混合型方法试图结合全局和局部的优点，将全局规划的“粗”路径作为局部规划的子目标。从而引导机器人最终找到目标点。从机器人工作环境的角度区分规划方法，可以分为静态确定环境规划方法和动态时变环境规划方法。目前许多研究工作集中在静态环境下，如装配机器人；在动态环境下的规划问题已经引起了人们的重视，并且已经取得了一些成果，这将是今后的一个发展方向。路径规划问题具有如下特点：（）复杂性：在复杂环境尤其是动态时变环境中，机器人路径规划非常复杂，且需要很大的计算量。（）随机性：复杂环境的变化往往存在很多随机性和不确定因素。动态障碍物的出现也带有随机性（）多约束：人的形状制约，机器人的运动存在几何约束和物理约束。几何约束是指机器而物理约束是指机器人的速度和加速度。（）多目标：机器人运动过程中路径性能要求存在多种目标，如路径最短，时间最优，安全性能最好，能源消耗最小。但它们之间往往存在冲突。避障路径规划的研究现状全局规划方法依照己获取的环境信息，给机器人规划出一条路径。规划路径的精确程度取决于获取环境信息的准确程度。全局方法通常可以寻找最优解，但是需要预先知道环境的准确信息，并且计算量很大。国内外的研究者在移动机器人静态环境下路径规划方面己经做了大量的研究工作。静态环境下路径规划应用的主要方法大致可以分为两类：传统方法和智能方法。（）传统方法的路径规划的研究现状传统路径规划方法包括：自由空间法、图搜索法、栅格解祸法、人工势场法等几种主要的方法。大部分机器人路径规划中的全局规划都是基于上述几种方法进行的。自由空间法应用于机器人路径规划，采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间，并将自由空间表示为连通图，通过搜索连通图来进行路径规划。易展，樊晓平，罗熊运用图论及算法，研究了由大尺度简单多边形障碍物构成的平面场景情况下平面移动机器人最短路径规划的几何算法，给出了详细的实现算法。在场景中的障碍物有凹多边形的情况下，该算法可大大降低计算量【】。图搜索方法中的路径图由捕捉到的存在于机器人一维网络曲线（称为路径图）自由空间中的节点组成，建立起来的路径图可以看作是一系列的标准路径。而路径的初始状态和目标状态同路径图中的点相对应，这样路径规划问题就演变为在这些点间搜索路径的问题。经常使用的图搜索方法有两种：可视图法（）和图表法。可视图法把机器人视为一质点，将机器人、目标点和多边形障碍物的各顶点之间，目标点和蔓童堡垒障碍物各顶点之间以及各障碍物顶点与顶点之间的连线，均不能穿越障碍物，即直线是可视的。搜索最优路径的问题就转化为，经过这些可视直线的从起始点到目标点最短距离问题【】栅格解耦法是目前研究最广泛的路径规划方法。该方法将机器人的工作空间解耦为多个简单的区域，一般称为栅格。由这些栅格构成了一个连通图，在这个连通图上搜索一条从起始栅格到目标栅格的路径，这条路径是用栅格的序号来表示的。栅格法将机器人工作环境分解成一系列具有二值信息的网格单元，多采用四叉树或八叉树表示工作环境并通过优化算法完成路径搜索。该法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响着环境信息存储量的大小和规划时间的长短。栅格划分大了，环境信息存储量小，规划时间短，但分辨率下降，在密集环境下发现路径的能力减弱；栅格划分小了，环境分辨率高，在密集环境下发现路径的能力强，但环境信息存储量大。和采用人工势场法进行机器人的路径规划，人工势场法把移动机器人在环境中的运动视为一种在抽象的人造受力场中的运动，目标点对移动机器人产生“引力，障碍物对移动机器人产生“斥力”，最后通过求合力来控制移动机器人的运动。王醒策等综合势场法和栅格法的优点，提出了一个新的全局路径规划方法势场栅格法，算法在避免局部占优点和降低计算量方面，有着良好的效果；并且可以自动确定栅格粒度。但是，由于势场法把所有信息压缩为单个合力，这样就存在把有关障碍物分布的有价值的信息抛弃的缺陷，且易陷入局部最小值。但是，该方法结构简单，易于实现，因此得到广泛应用【】。以上这些传统方法在路径搜索效率及路径优化方面尚有待于进一步的改善。（）智能方法的路径规划的研究现状近年来，随着模糊控制、神经网络和遗传算法等智能方法的广泛应用，机器人路径规划方法也有了长足的进展，许多研究者把目光放在了基于智能方法的路径规划研究上。其中，模糊方法是在线规划（动态环境）中通常采用的一种规划方法，在静态环境中应用较多的算法主要有神经网络和遗传算法。刘国栋等提出了一种动态环境路径规划方法，该方法针对机器人领域较难解决的动态环境路径规划方法该方法，充分挖掘可应用遗传算法解决移动机器人动态路径规划的潜力，动态规划能力较好【。禹建丽等提出了一种基于神经网络的机器人路径规划算法，研究了障碍物形状和位置已知情况下的机器人路径规划算法，其能量函数的定义利用了神经网络结构，根据路径点位于障碍物内外的不同位置选取不同的动态运动方程，规划出的路径达到了折线形的最短无碰路径，计算简单，收敛速度快【。陈宗海等提出了一种在不确定环境中移动机器人的路径规划方法，将全局路径规划分解为局部路径规划的组合，为了提高规划的效率，在避障规划中采用了基于案例的学习方法，以汀一神经网络实现案例的匹配学习和扩充，满足了规划的实时性要求【。和在采用离散空间进行路径规划的同时，将问题更深入化，栅格序号采用二进制编码，统一确定其个体长度随机产生障碍物位置及数目，并在搜索到最优路径后，再在环垩堕奎堂堡主堂竺丝茎境空间中随机插入障碍物，模拟环境变化，通过仿真结果验证了算法的有效性和可行性遗传算法是目前机器人路径规划研究中应用较多的一种方法。周明等提出一种连续空间下基于遗传算法的机器人路径规划方法，该方法在规划空间利用链接图建模的基础上，先使用图论中成熟算法粗略搜索出可选路径，然后再使用遗传算法来调整路径点，逐步得到较优的行走路线。该方法的染色体编码不会产生无效路径，且仅使用基本遗传算法就可以完成路径规划。但是该方法对于环境复杂、障碍物数目较多的情况，链接图的建立会有一定的困难【。陈刚等研究了一种复杂环境下路径规划问题的遗传算法求解方法，并针对复杂环境的特点设计了有效的路径遗传算子，还提出了一种新的度量路径个体适应度的计算方法，并通过试验证明，该算法有很强的鲁棒性【。张颖等采用栅格法表示机器人工作环境模型，用序号编码，直角坐标与序号混合应用，采用遗传算法产生初始路径种群，并对其优化找出最短路径，然后增加删除、插入算子达到路径规划中避障的要求。并通过仿真表明遗传算法进行避障和路径规划的有效性和可行性【。孙树栋等用遗传算法完成了离散空间下机器人的路径规划，并获得了较好的仿真结果。但是，该路径规划是基于确定环境模型的，即工作空间中的障碍物位置是己知的、确定的【。和采用栅格法建模，应用遗传算法设计了一种在静态和动态环境中路径规划的方法。王仲民等针对模拟退火算法收敛速度慢这一缺陷，提出了一种基于共轭方向法和模拟退火算法相结合的新型混合优化算法，并成功应用于机器人神经网络路径规划中。该算法可以使优化解不陷入局部极值解而得到全局最优解。并通过仿真实验研究表明：这种新型混合优化算法，计算简单，收敛速度快，显著提高了求解移动机器人全局最优化问题的计算效率【。张宏烈等对模拟退火在路径规划中的应用作了探讨，因为常规的神经网络算法、遗传算法本身也存在着一些缺陷，如局部寻优能力差、遗传算法的早熟现象等问题就很突出，严重影响路径规划的计算效率和可靠性。为提高路径规划问题的求解质量和求解效率，在利用神经网络算法、遗传算法进行路径规划的基础上，引入模拟退火算法，既能抑制遗传算法的早熟现象，又克服了其局部寻优能力较差的缺点，形成一种新的路径规划算法来解决机器人路径规划问题【。和提出了一种人工势场法和模拟退火相结合的路径规划方法，其中人工势场法的引入增加了系统规划的鲁棒性，而模拟退火的引入又可以跳出局部最优【】。综上所述，遗传算法等智能方法在机器人路径规划技术中已受到广泛的重视及研究，在障碍物环境已知情况下，已取得一定的研究成果。路径规划问题概述（）路径规划问题是十九世纪初爱尔兰的数学家和英国数学家提出的，通常被描述为：对给定城市交通网络，如何为一个推销商选择一条路线，从网络的某一点（驻地）出发，经过每一个结点后回到出发点，使得总行程最短，移动机器人的许多全局路径规蔓二雯堑丝划问题都可转化为一种问题。路径规划问题是著名的完全难题，也是组合优化、计算机科学界经典的问题之一。它在广泛的应用于运输、生产、国防、生物、计算机等领域以外，还为离散优化中各类算法提供了思想方法平台，因而对旅行商问题（）求解方法的研究具有重要的实际价值。标准的在图论的意义就是所谓的最小圈问题。由于其在许多领域都有着广泛的应用，因而寻找其实际而又有效的算法显得颇为重要，遗憾的是，计算复杂性理论给予我们的结论是：这种可能性尚属未知。在理论上已归结为所谓的完备问题类，即非确定性多项式完备问题。路径规划问题研究现状关于路径规划这类十分困难的问题，现在所知道的仅仅是：任何完备问题都不能用己知的多项式算法来解决；用多项式算法去研究问题起于五十年代，如线性规划算法、动态规划算法、分枝定界法。这些算法虽然对一些小规模的路径规划问题可精确求解，但计算的复杂度与城市的数目成指数增长。在大规模的问题上，这些精确算法显得无能为力，而且容易产生组合爆炸，因而人们退而寻求非尽善尽美的所谓启发式算法（近似算法），来处理各种实际问题。七十年代和八十年代是启发式算法的全盛时期，但由于绝大多数启发式算法都是按某种确定性的搜索规则来运行，想要改进所得解的可能性极小。因此，从八十年代后期一直到九十年代，一些来自其它学科的新一代求解方法相继出现，在组合优化问题的求解中取得相当的成功和一系列成果。如和提出用神经网络联想记忆技术求解，年等首先提出了源于固体物理的模拟退火算法求解复杂的组合优化问题，年等提出的源于生物学的遗传算法求解路径规划问题，以及近几年来问世的源于昆虫王国的蚂蚁算法。我国的许多学者研究中国城市的路径规划问题，基本上都采用神经网络求解。尽管仍未找到最优解，但是求解它的算法逐渐改进。年，马良总结、归纳出年到年国内外近几十年求解路径规划的算法，可分为两类：一类是精确算法如线性规划、动态规划、分枝定界法等；另一类是近似算法（启发式算法），如插入算法、算法、神经网络算法、模拟退火算法、遗传算法、蚂蚁算法等。目前，对于求解路径规划问题，国内外都有相当好的进展【】。年，周培德用点集凸壳的多项式时间算法解决了个顶点的中国货郎担问题【】。年，美国加利弗利亚大学根据出度、入度均为的的有向图中有一条路的这一特性，提出了用算法求解出度、入度均为的。年，澳大利亚证明了距离满足矩阵时，（指遍历所有城市的最大权圈）是难题，而之前己证在此条件下是多项式时间可解的。许智宏等用蚂蚁算法和模拟退火算法解大规模，比较两个算法的性能，分析造成其性能差异的原因，并提出了改进建议。蒋泰等用带有约束优化的遗传算法求解，针对实际中的约束条件讨论了罚方法在遗传算法中的应用【】。几十年来对于求解路径规划问题出现了很多传统方法，其中有精确算法如线性江雨大学硕士学位论文规划方法、动态规划方法、分支定界方法；近似优化算法有插入法、最近邻算法、算法、生成树法、算法、算法、混合算法、概率算法等。近年来，有很多解决该问题的较为有效的智能方法不断被推出，例如禁忌搜索方法、遗传算法、模拟退火算法等。从问题对应到图的类型，通常有两种基本的分类：（）任意两个城市之间来往的路径均相等或可以不相等；就可以归结为无向图或有向图问题。（）任意两个城市之间来回均存在路径或至少有两个城市之间仅存在单行路径；这种类型可以归结为完全图或者非完全图问题。将上述两种情况加以组合，便可得到以下四种的路径关系：（）完全有向图；（）完全无向图；（）非完全有向图；（）非完全无向图。目前针对的算法主要分为两类：精确算法和启发式算法（近似算法）。（）精确算法精确算法能保证完全搜索问题的整个解空间，从而找到最优解，但需要消耗门！）级的运算时间；有些精确算法虽然运用一些精巧的技术来减少搜索空间，但其本质上还是进行全局搜索，并没有降低运算时间复杂度。线性规划方法求解的最早的一种算法，主要是采用整数规划中的割平面法，即先求解模型中由前两个约束构成的松弛问题，然后通过增加不等式约束产生割平面，逐渐收敛到最优解。等人早在年就求过的最优解，年代中期对于多面体理论的研究，产生了一些比较有效的不等式约束，如子回路消去不等式、梳子不等式等。由于该方法在寻找割平面时常常凭借经验，因此，后来很少作为一般方法使用。动态规划方法记为集合，的子集，（，）为从出发遍历中的点并终止在的最优行程。当时，（七），）儡。，（，刀），当时，根据最优性原理，可将的动态规划方程写成：（，）（，）叱，（）再按方程规划可迭代求解。由于动态规划算法的时复杂度为（”，空间复杂度为（”，故一般除了很小规模的问题外，几乎不予采用。分支定界算法分支定界算法是一种应用范围很广的搜索算法，它通过有效的约束界限来控制搜索进程使之能向着空间状态树上有最优解的分支推进，以便尽快找出一个最优解。该方法的关键在于约束界限的选取，不同的约束界限可形成不同的分支定界法。但是分支定界算法对于解大规模问题不是十分有效。（）启发式算法启发式算法不能保证搜索问题的全部解空间，所以也不能保证能够搜到最优解，甚启发式算法不能保证搜索问题的全部解空间，所以也不能保证能够搜到最优解，甚至在某些实例上连解都得不到，但它们与精确算法相比却具有运算时间上的优势，即它们的运算时间复杂度都只是多项式，并不会随着输入规模的扩大而产生“组合爆炸。这类算法采用的是启发式策略来指导搜索，普遍比精确算法要快。对的启发式算法的研究是本文的重点。对于启发式算法，算法的好坏常用来衡量，为启发式算法所得到的总行程，为最优总行程，为最坏情况下的近似解与最优总行程之比的上界值。这类算法有：插入算法插入型算法可按插入规则的不同而分为若干类，其一般思想为：通过某种插入方式选择插入边（，）和插入点，将插和之间，形成，；：依次进行直至形成回路解。适用范围：无向图的最近邻算法：任取一出发点；依次取最近的点加入当前解中直至形成回路解。适用范围：无向图的算法：任取一出发点，计算印吒：将各，由大至卅、歹；：将排好后的各（，）依次适当联接，形成回路解。适用范围：无向图的双生成树算法：首先求出最小生成树。将树中各边都添一重复边并求出其回路：在回路点序列中去除重复点，形成回路解。适用范围：无向图的（蔓）算法：首先求出最小生成树；：对树中所有奇顶点求最小权匹配问题：将匹配边添入生成树并求出其回路：在回路点序列中去除重复点，形成回路解。适用范围：无向图的算法该方法是一种局部改进搜索算法，由等人（）提出，其思想是对给定的初始回路，通过每次交换，条边来改进当前解。对不同的，根据大量计算发现，法江南大学硕士学位论文比法好，而，等并不比优，况且，越大，运算时间越长。所以一般采用法。适用范围：无向图的本文研究的目的和研究内容研究目的本文在对大量相关文献进行深入分析的基础上，分别将基本遗传算法和模拟退火算法相结合，形成遗传模拟退火算法应用到移动机器人避障路径规划中，从而避免了移动机器人避障路径规划中局部寻优能力差、收敛速度较慢、易陷入局部极值点等问题的发生。采用了栅格法对环境进行建模，为了提高路径规划的效率，本文采用了一种改进的避障算法来生成初始种群，达到了较好的避障路径规划的效果。在移动机器人路径规划问题的研究中，设计了一类解路径规划问题的混合遗传算法，提出了依概率近邻法，用其生成的初始种群优于随机产生初始种群，较近邻法略差，但个体多样性水平优于近邻法，并将相似性的概念引入到路径规划问题中。仿真结果表明此方法具有较好的路径规划效果。研究内容本论文的研究内容包括六个部分：第一章介绍了移动机器人避障路径规划技术和移动机器人避障路径规划的国内外发展现状，还介绍了移动机器人路径规划问题的内容以及路径规划问题的发展过程和发展现状。第二章阐述了遗传算法、模拟退火算法的内容，并将两种算法进行优势互补形成了遗传模拟退火算法。第三章应用模拟退火算法进行移动机器人避障路径规划。设计新型的初始种群生成方法，提高了路径规划的效率。第四章介绍了遗传算法在求解路径规划问题的基本原理及实现方法。对于遗传算法运行性能有重要影响的一些参数进行分析讨论，而且用基本遗传算法对种群规模为的路径规划问题分别进行计算机模拟仿真，分析讨论了基本遗传算法在求解中出现的不足，为下一章的算法改进打下基础。第五章针对现有的遗传算法的不足和本身的特点，设计了两种改进的混合遗传算法，提出了依概率近邻法新型路径规划初始种群的生成方法，并将相似性的概念引入到路径规划问题中。第六章总结与展望，对本文进行归纳，概括本文的主要工作和创新点，提出下一步研究工作和研究方向。第二章遗传模拟退火算法第二章遗传模拟退火算法避障路径规划的传统的优化方法（如梯度法、可行方向法等）是通过梯度信息来寻找目标函数的最优值，适用于求解具有连续性函数关系的优化问题，而对求解无法获取梯度信息的离散变量优化问题无能为力。遗传算法和模拟退火算法是目前解决全局优化问题比较有效的算法。两种算法都是模拟自然界的某些现象进行大规模优化问题求解的随机性方法，都不要求目标函数的连续性、可微性，而且算法简单，易于实现。遗传算法虽然能从概率的意义上以随机的方式寻求到全局最优解，但它在实际应用过程中也可能会产生一些问题。这些问题中最主要的是局部寻优能力差、收敛速度较慢、易陷入局部极值点等。而另一方面，模拟退火算法却具有较强的局部搜索和摆脱局部最优点的能力。所以使用遗传算法与模拟退火算法相结合的方法，是解决上述问题的有效途径。本章针对遗传算法和模拟退火算法的优势和不足，采用了遗传模拟退火算法，并分别简要的介绍了这三种算法。遗传算法遗传算法（，）由美国大学等在世纪年代末期到年代初期研究形成的一个较完整的理论方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。随后经过余年的发展，取得了丰硕的应用成果和理论研究的进展，特别是近年来世界范围形成的进化计算热潮，计算智能己作为人工智能研究的一个重要研究方向，以及后来的人工生命研究兴起，使遗传算法受到广泛的关注，遗传算法作为具有系统优化、适应和学习的高性能计算的建模方法的研究渐趋成熟。遗传算法概述遗传算法是基于自然选择的生物进化，是一种模仿生物进化过程的随机方法，下面先介绍几个生物学的基本概念和术语，这对于理解遗传算法是非常重要的。染色体：生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由多个遗传因子一基因组成。基因座：遗传基因在染色体中所占据的位置。同一基因座可能有的全部基因称为等位基因。个体：指染色体带有特征的实体。种群：染色体带有特征的个体的集合称为种群。该集合内个体的总数称为群体的大小。有时个体的集合也称为个体群。进化：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。适应度：在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语江南大学硕士学位论文度量某个物种对于生存环境的适应程度。对生存环境适应度程度高的物种获得更多的繁殖机会，而生存环境适应度低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝。选择：指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。复制：细胞在分裂时，遗传物质通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。交叉：有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，亦即在两个染色体的某一个相同位置处被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称为基因重组，俗称“杂交”。变异：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。编码：中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。解码：从遗传子型到表现型的映射。遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生越来越好的近似解。在每一代，根据问题域中个体的适应度大小来挑选个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题的近似最优解。遗传算法模式定理模式定理是遗传算法的基本定理。定义：模式是一个描述字符串集的模板，该字符串集中的串的某些位置上存在相似性。定义：模式阶：模式日中确定位置的个数称为该模式的阶，记作（。定义：模式日中的第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距，记作（。模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义长度并且平均适应度高于群体平均适应度的模式在子代中将得以指数级增长。遗传算法的特点和步骤遗传算法是基于自然选择和遗传学原理的搜索算法。它将“适者生存这一基本的达尔文进化理论引入二进制串结构，并且在串与串之间进行有组织但又随机的信息交换。伴随信息交换的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。这一过程就像生物进化那样，好的特征被不断的继承下来，坏的特征就逐渐淘汰。第章遗传模拟退火算法代个体中包含着上一代个体的大量信息，新一代的个体不断地在总体特性上超过上一代，从而使整个群体向前进化发展。对于遗传算法就是不断地接近最优化解，研究遗传算法的主要目的之一，就是将自然生物的系统机理运用到人工系统的设计中【啦】。遗传算法的中心问题是“鲁棒特性，所谓鲁棒特性是指能在许多不同的环境中通过效率及功能之间的协调平衡以求生存的能力。人工系统很难达到生物系统的“适者生存的进化原理，从而使它具有在复杂空间中进行鲁棒搜索的能力。遗传算法具有极简单的计算方法，但却具有很强的功能，它对搜索空间基本不做要求，如连续性、可微、凸性等。遗传算法的本质特征可归纳为以下几点：（）遗传算法是对参数编码进行操作，而不是对参数本身。（）遗传算法是从许多初始点开始并行操作，而不是从一个点开始。因此可以有效防止搜索过程收敛于局部最优解。（）遗传算法通过目标函数来计算适配值，而不需要其它的推导和附加信息，从而对问题的依赖性很小。（）遗传算法使用概率的转变规则，而不是确定性规则。（）遗传算法在解空间内不是盲目地穷举或完全随机测试，而是启发式搜索，其搜索效率往往优于其他方法。（）遗传算法对目标函数基本没有限制，它既不需要函数连续，也不需要既可以是解析的表达，也可以是映射矩阵、甚至隐含数，因而应用非常广泛。（）遗传算法具有并行的特点，因而可通过大规模并行计算来提高计算效率。（）遗传算法更适合于大规模优化问题。遗传算法的流程图如图，可以更清楚的理解遗传算法是如何表达生物进化思想的。江南大学硕士学位论文随机产生初始种群计算各个体的适应度值磊收敛准则是否嘉趸）藉面覆綦石藁堙执行复制操作按交叉概率进行交叉操作按变异概率进行变异操作图遗传算法流程图由上面的流程图可以得出遗传算法的主要步骤如下：制定编码、解码策略，把目标问题的解空间转换为位串结构的编码空间。：确定适应度值函数归（）即目标函数。：确定遗传策略，包括确定群体大小，选择、交叉、变异等遗传操作的方法，以及交叉概率见、变异概率等遗传参数。：随机生成初始群体异（）。：对群体中个体位串进行解码，并计算其适应度值（）。：按照遗传策略，对群体的个体进行选择、交叉和变异等遗传操作，形成下一代群体。：判断进化过程是否可以结束，如群体性能是否满足某一指标，或己完成预定的迭代次数，不可结束则返回步骤。遗传算法的组成遗传算法主要由六个部分组成：编码方式、初始群体产生的方法、适应度函数、遗传操作、算法终止条件、算法参数的设置。要利用遗传算法成功的解决优化问题，每个部分的设计都非常关键【引。（）编码原理编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。传统的二进制编码是、字符构成的固定长度串。二进制编码的一个缺点是汉明悬崖，就是在某些相邻整数的日进制代码之间有很大的汉明距离，使得遗传算法的交叉和突变第二章遗传模拟退火算法都难以跨越。为克服此问题而提出的格雷码，在相邻整数之间汉明距离都为，然而汉明距离在整数之间的差并非单调增加，引入了另一层次的汉明悬崖。依据模式定理，提出较为客观明确的编码准则：有意义的积木块编码规则，即所定编码应当易于生成与所求问题相关的短距和低阶的积木块；最小字符集编码规则，所定编码应采用最小字符集以使问题得到自然的表示或描述。近来一些学者从理论上证明了推导最小字符集编码规则时存在的错误，提出大符号集编码可提供更多的模式。通常的编码方法包括：二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法、多参数级联编码方法、多参数交叉编码方法。二进制编码和浮点数编码比较而言，一般二进制编码比浮点数编码搜索能力强，但浮点数编码比二进制编码在变异操作上能够保持更好的种群多样性。（）初始种群的设计初始化过程有很多种。在研究遗传算法时，常常随机产生初始群体，这样做的好处是产生方式不依赖于问题，也就是对于任何问题，我们都可以采用这种方式来生成初始群体，因此从随机初始群体出发能更清楚地考察算法的行为和性能。当然这也存在一定的问题，例如对于一个有约束的非线性规划问题，随机初始群体可能存在着不满足约束的不可行解，虽然对于一个好的算法来讲这并不会影响到最后的优化结果，算法最终得到的最优个体中关键的特性是算法的搜索和重组机制产生的，而不是由初始化过程产生的。但是，这还是可能对优化的速度产生一定的影响。如果初始群体都是可行解，我们就有可能加快收敛速度。在实际应用中，可以采用更有效的初始化方法来加快搜索，比如用贪婪算法等启发式算法的输出结果、利用人的直观解答和加权随机初始化过程等。（）适应度函数的设计适应度函数是遗传算法与问题的接口，对遗传算法的收敛速度和结果影响很大。根据问题的特点而设计合适的适应度函数，能产生适宜于遗传算法处理的状态空间，能使算法快速有效地收敛。适应度函数的规范化方法是根据搜索空间中点的原始优劣情况计算其评价函数值。适应度函数对遗传算法的性能影响很大：如果过分强调当前的较优个体，就会使较优个体过分繁殖，很快降低群体中的结构的多样性，使算法过早收敛到局部最优值；而如果对当前较优个体强调得不够，算法就很容易丢失当前群体中较优个体的结构信息，不能在合理的时间内收敛到较好的个体。从数学角度看，遗传算法实质上是一种概率性搜索算法，但它也具有一定的智能特征。遗传算法是在适应度函数的指导下进行搜索，而不是穷举式的全面搜索。适应度函数评估是选择操作的依据，各个体适应度函数值的大小决定了它们是继续繁衍还是消亡，相当于是自然界中各生物对环境的适应能力的大小。通常，适应度大的个体具有更适应环境的基因结构，再通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代。改变种群内部结构的操作皆通过适应度加以控制。适应度函数的选取直接影响到遗传算法的收敛性及收敛速度，对于提高遗传算法的智能程度显得尤为重要。适应度函数求取的是极大值，而且是非负值。可以直接利用问题的目标函数来定义江南大学硕士学位论文适应度函数，也可以用目标函数变换的形式来定义。适应度函数的设计主要满足以下条件：单值、连续、非负、最大化。这个条件是很容易理解和实现的。合理、一致性。要求适应度值反映对应解的优劣程度，这个条件的达成往往比较难以衡量。计算量小。适应度函数设计应尽可能简单，这样可以减少计算时间和空间上的复杂性，降低计算成本。通用性强。适应度对某类具体问题，应尽可能通用，最好无需使用者改变适应度函数中的参数。从目前而言，这个条件应该不属于强要求。（）遗传操作基本遗传操作包括：选择、交叉、变异。选择选择操作决定如何从当前种群中选取个体作为产生下一代种群的父代个体。选择策略对算法性能会起到举足轻重的影响，不同的选择策略将导致不同的选择压力，即最佳个体选中的概率与平均选中概率的比值。较大的选择压力使最优个体具有较高的选中概率，从而使得算法收敛速度较快，但也较容易出现过早收敛现象；较小的选择压力能使种群保持足够的多样性，从而增大算法收敛到全局最优的概率，但算法收敛速度一般较慢。个体选择概率的常用分配方法有以下两种：）按比例的适应度分配：按比例的适应度分配，可称为选择的蒙特卡罗法，是利用比例于各个个体适应度的概率决定其子孙的遗留可能性，选择概率大的个体，能多次被选中，它的遗传因子就会在种群中扩大。）基于排序的适应度分配：在基于排序的适应度分配中。种群按目标值进行排