TSP问题通过遗传算法求解

这是毕业论文，主要的一个运行程序，文章里面已经分开分析了，剩下的另外传。 1.1 研究背景 如今的科学技术正在步入多学科相互交叉、互相渗透、互相影响的时代、生命科学与工程科学的交叉、渗透和相互促进是其中一个典型的例子，也是近代科学技术发展的一个显著点。遗传算法从此诞生。 TSP问题，也称为巡回旅行商问题，就是为人们所广泛研究的典型的组合优化为题。而且TSP问题由于其典型性已经成为各种启发式的搜索、优化算法(如遗传算法、神经网络优化法、列表寻优法、模拟退火法等[2][3][4])的间接比较标准。遗传算法在此体现出了不俗的表现[5] 1.2 国内外发展现状 最早美国Ｍichigan(密执安大学) [6] [7]的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代De Jong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验。在一系列研究工作的基础上80年代Goldberg进行总结归纳，形成了遗传算的基本框架。 进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。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)方法，成功地解决了许多问题。 在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。 1991年，L.Davis编辑出版了《遗传算法手册》（Handbook of Genetic lgorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。 1992年，Koza发表了他的专著《遗传程序设计:基于自然选择法则的计算机程序设计》。1994年，他又出版了《遗传程序设计，第二册:可重用程序的自动发现》深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machines》、《IEEE Transactions on Neural Networks》、《IEEE Transactions on Signal Processing》等杂志上发表。1993年，MIT出版社创刊了新杂志《Evolutionary Computation》。1997年，IEEE又创刊了《Transactions on Evolutionary Computation》。《Advanced Computational Intelligence》杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。 遗传算法(Genetic Algorithm, GA)是近三十年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来.国际上已召开了多次遗传算法的学术会议和研讨会.国际遗传算法学会组织召开的ICGA( International Conference on Genetic Algorithms)会议和FOGA( Workshop on Foundation of Genetic Algorithms)会议。为研究和应用遗传算法提供了国际交流的机会。 作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。 近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术，它已经与遗传算法并驾齐驱。 1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。现在的基因表达式算法应该算是遗传算法的继承者。 1.3 本文研究的内容 本文通过对遗传算法的研究来解决旅行货郎问题。在运用遗传算法成功解决TSP问题基础上，再通过采用不同的初始种群数目、遗传代数、交叉率、变异率来比较算法的质量与效率。从而观察这类参数对算法质量和效率的影响程度。 1.4 本文结构 第一章引言,首先对本文的研究背景、遗传算法在国内外的发展情况进行了简单的描述。然后再对本文研究的大致内容进行了阐述。 第二章：遗传算法与TSP问题的介绍,首先对遗传算法和TSP问题进行了简单的介绍。然后对遗传算法的基本术语、个体的编码方式、初始化种群、适应度函数、选择算子、交叉算子、变异算子、运行参数和全局最优收敛以及TSP问题的数学模型进行了阐述。 第三章：遗传算法在TSP上的应用与实现,首先通过选取10个城市的TSP问题为例，运用遗传算法求解该TSP问题。然后通过选取不同参数进行结果对比，从而验证遗传算法的各参数对算法质量和效率的影响程度。 第四章：混合遗传算法的展望,简单介绍了一些近年来与遗传算法想结合的高效算法。如模拟退火遗传算法、免疫遗传算法、小生境遗传算法、模糊遗传算法、混沌遗传算法、量子遗传算法。 第五章：结论,对第三章的计算结果进行了总结与归纳。验证了种群大小、遗传代数、交叉率、变异率等参数对算法质量和效率的影响程度。