您所在位置：网站首页 > 海量文档
 > 学术论文 > 大学论文
C语言遗传算法在求解TSP问题设计.doc46页
本文档一共被下载：次,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
毕 业 设 计(论 文)
学院 信息工程学院
专业 计算机科学技术与应用
班级 1625
姓名 徐东
4月 15日
目 录
摘要I
AbstractII
引 言1
第一章 基本遗传算法2
1.1 遗传算法的产生及发展3
1.2 基本原理3
1.3 遗传算法的特点3
1.4 基本遗传算法描述5
1.5 遗传算法构造流程6
第二章 遗传算法的实现技术6
2.1 编码方法7
2.1.1 二进制编码7
2.1.2 格雷码编码7
2.1.3 符点数编码8
2.1.4 参数编码8
2.2 适应度函数10
2.3 选择算子10
2.4 交叉算子10
2.4.1 单点交叉算子10
2.4.2 双点交叉算子11
2.4.3 均匀交叉算子11
2.4.4 部分映射交叉11
2.4.5 顺序交叉12
2.5 变异算子12
2.6 运行参数12
2.7 约束条件的处理方法13
2.8 遗传算法流程图14
第三章 遗传算法在TSP上的应用15
3.1TSP问题的建模与描述15
3.2 对TSP的遗传基因编码方法16
3.3 针对TSP的遗传操作算子17
3.3.1 选择算子17
轮盘赌选择17
最优保存策略选择17
3.3.2 交叉算子20
单点交叉20
部分映射交叉21
3.3.3 变异算子23
3.4 TSP的混和遗传算法26
第四章 实例分析27
4.1 测试数据27
4.2 测试结果27
4.3 结果分析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 genetic 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 genetic 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 genetic operators is elaborated. According to the given data, the results and efficiencies are influenced by four parameters in the basic genetic algorithm: the size of population, terminate generation, crosser probability and mutation probability. Adjust the parameters, run and try for better ones. At last, the applicati
发表评论
请自觉遵守互联网相关的政策法规，严禁发布色情、暴力、反动的言论。
用户名:
验证码:
匿名?
发表评论
如果觉得《c语言遗传算法在求解tsp问题 C语言遗传算法在求解TSP问题设计.doc》对你有帮助，请点赞、收藏，并留下你的观点哦！
