毕业设计(论文) 学院信息工程学院 专业计算机科学技术与应用 班级 姓名 年月日 目录 摘要 I Abstract II 引言 1 第一章基本遗传算法 2 遗传算法的产生及发展 3 基本原理 3 遗传算法的特点 3 基本遗传算法描述 5 遗传算法构造流程 6 第二章遗传算法的实现技术 6 编码方法 7 二进制编码 7 格雷码编码 7 符点数编码 8 参数编码 8 适应度函数 10 选择算子 10 交叉算子 10 单点交叉算子 10 双点交叉算子 11 均匀交叉算子 11 部分映射交叉 11 顺序交叉 12 变异算子 12 运行参数 12 约束条件的处理方法 13 遗传算法流程图 14 第三章遗传算法在TSP上的应用 15 TSP问题的建模与描述 15 对TSP的遗传基因编码方法 16 针对TSP的遗传操作算子 17 选择算子 17 轮盘赌选择 17 最优保存策略选择 17 交叉算子 20 单点交叉 20 部分映射交叉 21 变异算子 23 TSP的混和遗传算法 26 第四章实例分析 27 测试数据 27 测试结果 27 结果分析 27 摘要 TSP (Traveling Salesman Problem)旅行商问题是一类典型的NP完全问题,遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术;接着针对TSP 问题,论述了遗传算法在编码表示和遗传算子(包括选择算子、交叉算子变异算子这三种算子)等方面的应用情况,分别指出几种常用的编码方法的优点和缺点,并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率,对遗传算法的求解结果和求解效率的影响,经过多次的测试设定出了它们一组比较合理的取值。最后,简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。 关键词:TSP 遗传算法遗传算子编码 Abstract TSP (Traveling Salesman Problem) is a typical NP - complete problem and ic algorithm (GA) is the perfect method for solving NP - complete problem. The basic theories, characteristics and the basic techniques of GA are first introduced. Then the encoding model and ic operators (including selection operation, crossover operation and mutation operation) about GA in solving TSP are discussed. The advantages and disadvantages of various encoding method are respectively indicated, and the application of the three basic ic operators is elaborated. According to the given data, the results and efficiencies are influenced by four parameters in the basic ic algorithm: the size of population, terminate generation, crosser probability and mutation probability. Adjust the parameters, run and try for better ones. At last, the application of hybrid ic algorithm is briefly presented. It is pointed out that a better crossover o
