摘 要遗传算法（Genetic Algorithm, GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J. Holland教授于1975年首先提出的。遗传算法的大致过程是这样的：将每个可能的解看作是群体中的一个个体或染色体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，即给出一个适应度值。开始时，总是随机的产生一些个体，根据这些个体的适应度利用遗传算子——选择（Selection）、交叉（Crossover）、变异（Mutation）对它们重新组合，得到一群新的个体。这一群新的个体由于继承了上一代的一些优良特性，明显优于上一代，以逐步向着更优解的方向进化。遗传算法主要的特点在于：简单、通用、鲁棒性强。4852
旅行商问题(Traveling Salesman Problem, TSP)是典型的NP完全问题，遗传算法是求解NP完全问题的一种常用方法。本48文利用遗传算法解决组合优化问题——TSP问题，考察遗传算法在求解NP问题中的性能，并在MATLAB中用遗传算法对TSP问题进行求解，进行了选择、交叉和变异算子进行了算法设计，最后在MATLAB软件上进行编程实现，并对测试结果作适当的分析。通过两点交叉和部分映射交叉(Partially Mapped Crossover, PMX)这两种交叉操作的比较，探讨了采用PMX交叉算子的改进遗传算法解决旅行商问题时的特点。
关键词：遗传算法，TSP问题，MATLAB软件，PMX
Abstract
Genetic Algorithm (GA) is an evolutionary computing originally proposed by Dr J. Holland in the year 1975 and developed by him and his students and colleagues. As can be seen literally, Genetic Algorithm is inspired by Darwins theory about evolution. A basic GA employs selection, crossover and mutation operators. The whole process can be referred to as "reproduction". Algorithm is started with a set of solution (represented by chromosomes) called sub-population. Solutions from one sub-populations are taken and used to form a new sub-population by a hope that the new population will be better, at least not worse than the old one. Solutions are selected according to their fitness. The more suitable they are the more chances they have to reproduce. The main characteristic of the GA is that it is simple, universal and robust. After about 20 year’s development, GA has been successfully used in a lot of fields such as the Travelling Salesman Problem, Scheduling, Function Optimization, Machine Learning etc.
Traveling Salesman Problem is a typical NP complete problem, GA is the perfect method for solving it. This paper uses GA in MATLAB software to solve the typical TSP problem，and the performance of GA in solving TSP problem was analyzed. We designed algorithms for all genetic operators (select, intercross, mutate). Finally, we programmed in Matlab to implement the algorithms, and discussed the characteristic of partially mapped crossover in GA through comparing two point crossover with PMX.
Keywords: Genetic Algorithm, TSP, MATLAB, PMX
目 录
1 绪论.1
1.1 遗传算法简介.1
1.2 旅行商问题..3
1.3 本文研究内容.5
1.4 全文安排6
2 遗传算法的基本原理和实现技术..7
2.1 理论基础7
2.2 编码策略.10
2.3 群体设定.12
2.4 适应度数.13
2.5 遗传操作.13
2.6 本章小结.16
3 改进的遗传算法17
3.1 遗传算法存在的问题.17
3.2 现有的遗传算法的几种改进17
3.3 分析遗传算法的交叉操作.18
3.4 改进交叉算子.18
3.5 算法描述19
3.6 本章小结..20
4 基于改进遗传算法的仿真实验.21
4.1 算法总体设计.21
4.2 算法详细设计.21
4.3 实验结果及分析25
4.4 改进算法性能分析..29
4.5 本章小结.35
5 总结及展望..36 MATLAB遗传算法的改进及其在TSP问题中的应用:http://www.751com.cn/zidonghua/lunwen_1652.html