文档详情

利用遗传算法解决TSP.pdf

发布:2017-10-06约1.42万字共17页下载文档
文本预览下载声明
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
显示全部
相似文档