第1章 绪论
1.1旅行商问题
旅行商问题 (Traveling Salesman Problem，TSP)，也称货郎担问题，是指对于给定的甩个城市，旅行商从某一个城市出发，不重复地访问其余每一个城市，最后又返回到原出发城市，要求找出一条旅行路线，使其的旅行所付出的代价最小。旅行商问题是一个比较古老的问题，最早可追溯到Euler提出的骑士旅行问题，同时它也是个“新问题\，因为计算的复杂性较高，人们一直在尝试用新的方法来改进求解该问题的复杂度。TSP问题是一个具有广泛的应用背景和重要理论价值的组合优化问题，它是一个典型的NP问题。G=（V，E）为赋权图，V=1，2，?，N为顶点集，E为边集，Cij表示旅行商经过对应弧段（i，j）所花的费用，如时间、距离、花费等。TSP问题就是要决定一条经过图中所有顶点，当且仅当一次且代价最小的回路，即代价最小的Hamilton回路，为简化问题。
1.2研究意义
旅行商问题是一个理想化的问题，大多数对于此问题的研究都不是为了直接的实际应用，但这些研究可以经转化后用于许多现实的组合优化问题。在现实生活中，有许多问题都可以归结为TSP问题，如电路板钻孔路线选择、车辆路线问题、计划任务、连锁店货物配送路线、管道铺设、火炬接力等问题，这些问题的求解策略均可依据TSP问题的求解算法来加以实施。所以TSP问题在计算理论上和实际应用上都有很高的价值，将直接带动整个组合优化领域新的发展。而遗传算法是一种的元启发式优化算法,基于遗传算法在许多方面有重要的应用空间。基于此原因，本文的主要是用遗传算法的基本算子解决TSP这个有意义的NP难问题。
1.3 论文的组织结构
第1章绪论。本章论述旅行商问题的基本概念，以及本课题的主要研究内容及其研究意义，并对本文的章节结构加以概述。
第2章，概要介绍了遗传算法的起源和发展、思想及应用等问题，并重点介绍了基本遗传算法。
第3章 概要介绍了TSP问题的定义和数学模型、研究现状及评价标准，现有的求解TSP问题的几种算法。
第4章 本章论述如何用基于遗传算法求解TSP问题。详细论述了用遗传算法在TSP的实现方法和主要参数设置、程序实现。
第5章 总结
第2章 遗传算法理论概述
2.1遗传算法的起源和发展
20世纪40年代以来，科学家努力从生物学中寻找用于计算机科学和人工系统的新思维、新方法和新途径，生命科学与工程科学相互交叉、相互渗透、相互促进成为近代科学发展的显著特点之一。遗传算法正是从大自然的杰作——生物进化论中得到的灵感和启迪，其基本思想是Darwin进化论和Mendel的遗传学说。
Darwin进化论最核心的是自然选择学说。他认为，生物进化是一个缓慢的变化过程，物种不是被创造出来的，而是自然选择的必然结果。“物竞天择，适者生存”。生物要想生存下来，就必须进行生存斗争。斗争是多方面的，有种内斗争、种间斗争以及生物与无机环境间的斗争。只有适应性强的个体才能在斗争中存活下来，并且有更多的机会将有利变异传给后代；而不适应斗争环境、具有不利变异的个体将面临淘汰。Darwin把这种在生存斗争中适者生存、不适者淘汰的过程称为自然选择。
Mendel遗传学说最重要的是基因遗传原理。他认为遗传以密码方式存在于细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
现代遗传学和细胞学的研究表明，生物的遗传物质主要保存在染色体中，染色体由DNA(脱氧核糖核酸)和蛋白质组成；基因则是指携带有遗传信息的DNA序列，是控制性状的基本遗传单位。基因可以精确的复制，也可以发生突变，并可以通过控制蛋白质的合成而控制生物的性状。生物体自身通过对基因的复制和交叉即基因分离、基因自由组合和基因连锁互换的操作使其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多彩的变异现象。
能否将生物进化论应用于科学研究和工程实践中的各种搜索和优化问题中?遗传算法正是从这一疑问开始的。
上个世纪60年代，Michigan大学的J．H．Holland教授开始认识到生物的遗传和自然进化现象与人工自适应系统的相似关系，并将生物遗传机制引入人工自适应系统的研究。1967年，他的学生Bagley J．D．首次提出“遗传算法”一词，并发展了复制、交叉、变异、显性、倒位等遗传算子。70年代，Holland教授出版了专著{(Adaptation in Nature and Artificial Systems))，系统阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理——模式定理，为遗传算法的发展奠定了理论基础。美国De．Jong博士基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了著名的De．Jong五函数测试平台。80年代，遗传算法开始在各个领域得到广泛应用。1980年，Smith将遗传算法应用于机器学习领域；Bethke对函数优化的遗传算法进行了系统的研究。1989年，David Goldberg出版了((GeneticAlgorithm in Search,Optimization and Machine Leaming》一书，成为论述遗传算法的第一本专著。进入90年代，遗传算法进入了兴盛期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗
传算法的应用研究显得格外活跃，被广泛地应用于组合优化、生产调度、机器学习、图像处理、人工生命等领域，不仅如此，利用遗传算法进行优化和规则学习的能力也显著提高。
1985年，美国召开了第一届遗传算法国际会议(ICGA)，在遗传算法发展史上具有里程碑式的意义。此后ICGA每隔一年举行一次，1999年期，ICGA与GP的系列会议合并为一年一次的遗传与进化国际会议(GECCO)。1994年1月，IEEE神经网络委员会出版了第一本《进化计算》专集，同年6月组织召开第一届“进化计算”国际会议，以后每年举行一次。
2.2遗传算法基本原理
遗传算法是从代表问题可能潜在解集的一个种群(Population)开始的，而一个种群则由经过基因(Gene)编码(Coding)的一定数目的个体(Individual)组成。每个个体实际上是染色体(Chromosome)带有特征的实体。作为多个基因的集合，单个染色体是遗传物质的主要载体，其在种群中的命运由其基因组合决定。初始种群产生以后按照优胜劣汰、适者生存的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度(fitness)大小挑选个体，并借助代表于自然遗传学的遗传算子(Genetic Operators)进行交叉(Grossover)和变异(Mutation)，产生出代表新的解集的种群。这个过程导致种群象自然进化一样，后代种群比前代更加适应于环境，末代种群中最优个体经过解码(Decoding)，可以作为问题的近似最优解。
遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与邻域等。与传统搜索算法不同，遗传算法是从一组随机产生的初始解开始搜索过程。种群中的每个个体是问题的一个解，称为“染色体\，染色体是一串符号，比如二进制01串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用适应度(fitness)来测量染色体的好坏。生成的下一代染色体称为后代(offspring)。后代是由前一代染色体通过交叉(crossover)或者变异(mutation)运算形成的。新一代形成中，根据适应度的大小选择部分后代，淘汰部分后代，从而保持种群大小的稳定性。适应度高的染色体被选中的概率高，这样，经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。列出了表2-1生物遗传与遗传算法部分概念的对照
表2-1生物遗传与遗传算法的概念对照
生物遗传 遗传算法 基因 解中每一分量的特征 染色体 解的编码 个体 解 种群 一组解 交配 交叉操作 变异 编码的某一个分量发生变化的过程 适应性 编码解码后得到的适应度函数值 适者生存 选择操作
2.3遗传算法的基本步骤
步骤一:确定参变量及其各种约束条件.即确定个体的表现形式和问题的解空间. 步骤二: 建立优化模型. 即确定出求解问题的目标函数和数学描述形式及量化方法. 步骤三:确定染色体的编码方法.即确定个体的基因形式.
步骤四:确定解码方法.即确定出个体的基因形式到个体的表现形式的对应关系和转化方式. 步骤五: 确定个体适应度的量化评价方法.即确定出目标函数值同个体适应度的转化规则. 步骤六: 设计遗传算子.即确定出选择算子,交叉算子和变异算子等遗传算子的具体操作方法. 步骤七: 确定遗传算法的有关运行参数.即确定出遗传算法
2.4 遗传算法的流程图
图2-1遗传算法流程图
2.5遗传算法的特点
传统的优化方法主要有三种：枚举法、启发式算法和搜索算法。随着问题种类的不同以及问题规模的扩大，需要寻求一种能以有限的代价来解决搜索和优化的通用方法，遗传算法正是为我们提供了一个有效途径，它不同于传统的搜索和优化方法。主要区别在于
(1)自组织、自适应和自学习性。应用遗传算法求解问题时，在编码方案、适应度函数及
遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。由于自然选择策略为“适者生存，不适应淘汰\，因而适应度大的个体具有较高的生存概率。通常，适应度大的个体具有更适应环境的基因结构，在通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代。进化算法的这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环境的特性和规律的能力。自然选择消除了算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施。因此，利用遗传算法的方法，我们可以解决那些复杂的非结构化的问题。
(2)遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。它的并行性表现在两个方面，一是遗传算法的内在并行性(inherentparallelisml，即遗传算法本身非常适合大规模并行。最简单的并行方式是让几百甚至上千台计算机各自进行独立种群的演化计算，运行过程中甚至不进行任何通信(独立的种群之间若有少量的通信一般会带来更好的结果)，等到运算结束才通信比较，选取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要求，可以说，遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，而且对运行效率没有太大的影响。二是遗传算法的内含并行性(implicitparallelism)。由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间内的多个区域，并相互交流信息。使用这种搜索方式，虽然每次只执行与种群规模n成比例的计算，但实质上已经进行了大约O(n3)次有效搜索，这就使遗传算法能以较少的计算获得较大的收益。
(3)遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数。
(4)遗传算法强调概率转换规则，而不是确定的转化规则。 (5)遗传算法可以更加直接的应用。
(6)遗传算法对给定的问题，可以产生许多的潜在解，最终选择可以由使用者确定。
2.6遗传算法的应用
遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学。 (1)函数优化