《遗传算法——tsp (traveling salesman problem)旅行商问题》由会员分享，可在线阅读，更多相关《遗传算法——tsp (traveling salesman problem)旅行商问题（44页珍藏版）》请在金锄头文库上搜索。
1、1摘要 IAbstract II引 言 1第一章 基本遗传算法 21.1 遗传算法的产生及发展 .31.2 基本原理 .31.3 遗传算法的特点 .31.4 基本遗传算法描述 .51.5 遗传算法构造流程 .6第二章 遗传算法的实现技术 62.1 编码方法 .72.1.1 二进制编码 .72.1.2 格雷码编码 .72.1.3 符点数编码 .82.1.4 参数编码 .82.2 适应度函数 .102.3 选择算子 .102.4 交叉算子 .102.4.1 单点交叉算子 .102.4.2 双点交叉算子 .112.4.3 均匀交叉算子 .112.4.4 部分映射交叉 .112.4.5 顺序交叉 .1
2、22.5 变异算子 .122.6 运行参数 .122.7 约束条件的处理方法 .132.8 遗传算法流程图 .14第三章 遗传算法在 TSP 上的应用 153.1TSP 问题的建模与描述 .153.2 对 TSP 的遗传基因编码方法 .163.3 针对 TSP 的遗传操作算子 .173.3.1 选择算子 .173.3.1.1轮盘赌选择 .173.3.1.2最优保存策略选择 .173.3.2 交叉算子 .203.3.2.1 单点交叉 .203.3.2.2 部分映射交叉 .213.3.3 变异算子 .233.4 TSP 的混和遗传算法 .26第四章 实例分析 274.1 测试数据 .274.2 测
3、试结果 .274.3 结果分析 .27摘 要2TSP (Traveling Salesman Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP 问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取
4、值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。关键词：TSP 遗传算法 遗传算子 编码AbstractTSP (Traveling Salesman Problem) is a typical NP - complete problem and genetic 3algorithm (GA) is the perfect method for solving NP - complete problem. The basic theories, characteristics and the basic techniques of GA ar
5、e 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 thre
6、e 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 bett
7、er ones. At last, the application of hybrid genetic algorithm is briefly presented. It is pointed out that a better crossover or mutation routine can be found out which retains the structure from the parent chromosomes and still ends up with a legal tour in the child chromosomes, which leads to a be
8、tter solution than ever before. And the prospect for the future of genetic algorithm in solving TSP is made.Keywords: TSP genetic algorithm genetic operators encoding引 言 4现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然进化规则生存和繁衍，并逐步产生出对
9、其生存环境适应性很高的优良物种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理策略等领域得到了广泛应用。遗传算法给我们呈现出的是一类通用的算法框架，该框架不依赖于问题的种类。遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非线性系统，它更表现出了比其他传统优化方法更加独特和优越的性能。隐含并行性和全局搜索特性是遗传
