文档介绍：1绪论
遗传算法是最近几十年来发展起来的新型优化方法，在六十年代末七十年代 初主要由美国密歇根大学的John Holland教授与其同事、学生们共同研究形成了 较完整的理论和方法,70年代De Jong基于遗传算法的思想在计算机上进行了大 量的纯数值函数的优化计算实例，80年代由Goldberg归纳总结了一系列研究工 作，形成了遗传算法的基本框架。目前人们已经将遗传算法和其他诸如模拟退火 算法、贪婪算法、最速下降法等结合起来形成了混合遗传算法，使得对所求解的 问题有更快的收敛速度和更强的鲁棒性。从20世纪90年代开始我国对遗传算法 的研究处于升温时期，在最近的几年里也取得了举世瞩目的成绩。遗传算法的主 要应用领域有函数优化、组合优化、生产调度、自动控制、机器人智能控制学、 图像处理和模式识别、人工生命、遗传编程和机器学****br/>TSP是组合优化问题中的NP难问题，可能的路径数随着城市的数目的增大 呈指数级增长，城市数目越大寻优路径的难度也就越大，到目前为止已经提出了 许多种解法。本文基于遗传算法对对称旅行商问题进行求解，并对各种实现方法 进行对比讨论。全文包括遗传算法概述、基于遗传算法对TSP的实现及对四组 遗传算子的比较、总结等几大部分组成。在遗传算法概述部分简单介绍了遗传算 法的机理、各种不同的编码方法、适应度函数和遗传操作，在基于遗传算法对 TSP的实现及对四组遗传算子的比较部分首先对TSP作了简要概述，然后介绍 了常用的编码方法、适应度函数的确定和针对TSP的遗传算子的设计，接着阐 述了实现部分匹配交叉法时需要注意的问题和新设计的交叉算子类贪婪交叉算 子，最后对四种实现方法的结果进行对比评价。总结部分对全文的内容进行了总 结并指出了文章的不足之处。
2遗传算法概述
遗传算法是通过模拟生物在自然环境中遗传和进化的过程而形成的一种自 适应的全局优化概率搜索算法，借鉴生物学遗传机制，模仿进化过程中的选择、 交叉和变异机理，以群体的方法进行自适应搜索，找到目标空间中的近似最优解 或满意解。
遗传算法是一个迭代求解的过程，首先初始化当前种群，然后从当前种群中 按照某种机制选择适量个体进行遗传操作，在产生新一代种群后找到当前种群中 的最佳个体，然后将新产生的种群作为当前种群，继续以上操作，直到满足某种 终止条件为止。
首先引入模式（schema）的概念。模式是一个描述字符串集的模板，该字符 串集中串的某些位置上存在相似性。一个串中可以隐藏多个模式，一个模式可以 隐藏在多个串中，不同的字符串之间通过模式相互联系，所以说遗传算法中串的 运算实质上是模式的运算。例如二进制编码中字符集为{0,1,*}, *是通配符，可 以是0或1, o***io****i*则表示一种模式。模式阶是指模式中确定的位置的个 数，定义距指的是模式中第一个确定位置和最后一个确定位置之间的距离。比如 编码为o***io****i*表示的模式，它的阶为4,定义距为10。
模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距和 平均适应度高于群体平均适应度的模式在子代中将以指数级增长。
我们把低阶、短定义距以及高适应度的模式叫做积木块。由此引出积木块假 设。
积木块假设：积木块在遗传算子的作用下相互结合能生成高阶、长定义距、 高平均适应度的模式，可最终生成全局最优解。
模式定理保证了较优模式的样本数呈指数级增长，从而满足了寻找最优解的 必要条件，即遗传算法存在找到最优解的可能性，而积木块假设指出了遗传算法 具备找到全局最优解的能力。
遗传算法是通过模仿生物学中遗传和进化的机理完成对问题域中最优解的 搜索。首先对目标问题进行编码，编码是表现型到基因型的映射，而遗传算法的 实现基础是基因，因此需要将问题域转换成基因空间；其次确定种群大小和适应 度函数，种群中的合法个体在解码后其表现型满足目标问题的约束条件，算法在 迭代的种群中逐步搜索目标问题的最优解或满意解，因此最优解或满意解经过有 限次迭代后一定可以找到，适应度函数是用来评价优良个体的依据，适应度高的 个体得以保留，适应度低的个体被淘汰掉；再次随机产生初始种群，产生初始种 群时要确保个体的合法性约束，算法从初始种群开始对种群中的每个个体执行遗 传操作；基本遗传算子包括选择算子、交叉算子和变异算子，选择算子以个体的 适应度为标准来决定哪些个体是否能够保留，交叉和变异算子是产生新一代种群 的关键遗传算子，随机确定交叉点和变异点在编码串中的位置，可以产生新个体 从而使种群进化逐步逼近最优解或满意解；最后确定中止代数，即达到什么条件 终止算法的执行。因为算法是在计算机上执行的，而计算机要求一定的精度，因 此目标函数的最优解无法达到理论上的