利用遗传算法解决TSP.pdf

2013 利用GA 解决TSP 朱晓东 2010011521 清华大学自动化系01 班 《利用遗传算法解决TSP 》 清华大学自动化系01 班 朱晓东 2010011521 2013.12.23 利用遗传算法解决TSP 朱晓东 （清华大学自动化系01 班） 摘要： 本文介绍了遗传算法 （Genetic Algorithm ，GA ）的基本流程、在组合优 化中的特点、关键参数与操作的设计以及具体的实现，并利用遗传算法解决了 10 城市和20 城市的旅行商问题（Traveling Salesman Problem，TSP ），给出了20 城市情况下20 次随机实验的统计结果，典型的某一次目标性能下降曲线，以及 最优结果的图形。 关键词： 遗传算法 旅行商问题 最优结果 近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理机制的人 工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难越来越明 显，从而使得寻求一种适合于大规模问题并具有自组织、自适应、自学习能力的 算法成为有关学科的一个研究目标。遗传算法是J Holland 与1975 年受生物进化 论的启发而提出的。GA 是基于“适者生存”的一种高度并行、随机和自适应优 化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群 （population ）的一代代不断进化，包括复制（reproduction ）、交叉（crossover ） 和变异（mutation ）等操作，最终收敛到“最适应环境”的个体，从而求得问题 的最优解和满意解。GA 是一种通用的优化算法，其编码技术和遗传操作比较简 单，优化不受限制性条件的约束，而其两个最显著特点则是隐含并行性和全局解 空间有哪些信誉好的足球投注网站。目前，随着计算机技术的发展，GA 越来越得到人们的重视，并在机 器学习、模式识别、图像处理、神经网络、优化控制、组合优化、VLSI 设计、 遗传学等领域得到了成功应用。 旅行商问题，也称为货郎担问题，是一个较古老的问题。最早可以追溯到1759 年Euler 提出的骑士旅行问题。1948 年，由美国兰德公司推动，TSP 成为近代组 合优化领域的一个典型难题。应该说，TSP 是一个具有广泛的应用背景和重要理 论价值的组合优化问题，它已被证明属于NP 难题。TSP 可以简单描述为：一位 销售商从n 个城市中的某一个城市出发，不重复地走完其余n-1 个城市并回到原 出发点，在所有可能路径中求出路径长度最短的一条。用数学语言描述如下：设 1 / 16 《利用遗传算法解决TSP 》 清华大学自动化系01 班 朱晓东 2010011521 2013.12.23 有限n 个城市集合C  C , C ,…, C ；设两个城市间的距离为d (C , C ) Z  ，其  1 2 n  i j n1  min d (C ,C d C 中C , C C(1 i, j n) ；求使  ) ( ,C ) 的城市序列  I ( i ) I ( i 1 ) I (n )  i j I ( 1 ) i1  C , C , ,  I ( 1 ) I ( 2 )… C  ，其中I (1), I