发布时间 : 星期二 文章遗传算法及其在TSP问题的应用 - 图文更新完毕开始阅读dcc5093c580216fc700afd4e
第一章 引言
在过去,人们往往只能处理一些简单的问题，对于大型复杂系统的优化和自适应问题，仍然无能为力。但是在这方面，自然界中的生物表现出了其优异的能力，它们能够通过优胜劣汰、适者生存的自然进化法则进行生存和繁衍，并能渐渐地进化出对其生存环境适应性越来越高的优良物种。遗传算法就是模拟自然界中生物进化的一种高效的算法，其基本思想就是模拟自然界进化机制和生物进化论而形成的一种机制求解最优值问题的自组织、自适应的智能算法。
遗传算法[1] (Genetic Algorithm, GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法，尽管各种理论、方法都尚未成熟，有待于进一步地完善和发展，但我们从它的身上看到了解决多种复杂问题的希望。虽然在遗传算法的研究和应用过程中出现过各种不同的算法设计，同时也会遇到过许多不同的难题，但是就目前而言，遗传算法的应用过程已经展现出了其突出的性能和巨大的发展前景。近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术，它已经与遗传算法并驾齐驱。我相信，随着研究工作进一步深入地发展，遗传算法将会在智能计算领域中起到非常重要的作用。
旅行商问题(Traveling Salesman Problem, TSP),是一个著名的组合优化问题[2],该类问题具有非常广泛的运用背景。如物流的调度问题、数控机床上的最优钻孔路线的选取、电路板的焊接都属于旅行商问题。因此旅行商问题受到了各方面的关注，有效解决TSP问题在计算理论和实际应用上都有很高的价值。目前解决TSP的主要方法有遗传算法、模拟退火算法、启发式搜索法、Hopfield神经网络算[3] 、二叉树描述算法。本文主要介绍了应用遗传算法来解决TSP问题。
2
1.1 研究背景
如今的科学技术正步入多学科互相影响、相互交叉、互相渗透的时代，生命科学与工程科学的交叉、渗透和互相促进是其中一个典型的例子，也是近代科学技术发展的一个里程碑。遗传算法也因此诞生。
TSP问题，也称为旅行商问题，就是为人们所广泛研究的典型的组合优化为题。而且由于TSP问题的典型性，使得它已经成为各种启发式的搜索、优化算法(如遗传算法、模拟退火法、神经网络优化法、蚁群优化算法、列表寻优法等[4])的间接比较标准。其中，遗传算法有不俗的表现[5] 。
1.2 国内外发展现况
遗传算法最早由美国Michigan(密执安大学)的Holland [6] [7]教授提出，起源于60年代对自然和人工自适应系统的研究。
70年代De Jong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验。
80年代Goldberg[8]在一系列研究工作的基础上进行总结归纳，形成了遗传算的基本框架。
步入八十年代，遗传算法迎来了兴盛的发展时期，无论在理论研究还是应用研究方面都成为了十分热门的课题。
1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学（International Society of Genetic Algorithms ，ISGA），往后每两年举行一次。
1989年，Holland的学生D.E.Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了遗传算法研究的主要成果，并对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza提出了基于自然选择原则的计算机程序层次化表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。
3
1990年，欧洲开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，遗传算法都是会议的主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际学术会议，集中反映了近些年来遗传算法的最新发展动向。
1991年，L.Davis编辑出版了《遗传算法手册》（Handbook of Genetic lgorithms），书中囊括了遗传算法在工程技术和社会生活中的大量应用实例。
1992年，Koza发表了他的专著《遗传程序设计:基于自然选择法则的计算机程序设计》。
1993年，MIT出版社创刊了新杂志《Evolutionary Computation》。1997年，IEEE又创刊了《Transactions on Evolutionary Computation》。《Advanced Computational Intelligence》杂志也即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。
1994年，Koza接着出版了《遗传程序设计，第二册:可重用程序的自动发现》，使得遗传程序设计更加深化研究，程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在《Artificial Intelligence》、《Genetic Programming and Evoluable Machines》、《Information science》、《Machine Learning》、《Parallel Computing》、《IEEE Transactions on Neural Networks》、《IEEE Transactions on Signal Processing》等杂志上发表。
目前，关于遗传算法的研究热潮仍在持续，越来越多从事各种不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。
4
1.3 主要研究内容
本文通过对遗传算法的研究，并且利用Visual C++集成开发环境将其编程实现来解决TSP问题。在运用遗传算法成功解决TSP问题基础上，再通过改变不同的初始种群数目、遗传代数、交叉率、变异率来比较算法的质量与效率。从而观察、验证这类参数对算法质量和效率的影响程度。
1.4 本文结构
第一章：引言首先对本文的研究背景、遗传算法在国内外目前的发展状况进行了简单的描述,然后再对本文研究的大致内容进行了说明。
第二章：遗传算法与TSP问题的介绍,首先对遗传算法的基本术语概念、个体的编码方式、初始化种群、适应度函数、选择算子、交叉算子、变异算子、运行参数和全局最优收敛进行介绍，然后也对TSP问题的数学模型进行了阐述。
第三章：遗传算法在TSP上的应用与实现,通过选取网上已有最优解的10个城市的TSP问题为例，运用遗传算法求解该TSP问题。然后通过选取不同的参数进行测试，对比结果，从而验证遗传算法的各参数对算法效率和质量的影响程度。并对东莞10个景点的实例TSP问题进行解决。
第四章：结论,对第三章的结果对比进行了总结与归纳。总结了种群大小、遗传代数、交叉率、变异率等参数对算法效率和质量的影响程度及改善方式。
5