因此，在不可能求出全部解的情况下处理好组合优化问题成为了一个具有挑战性 的问题。而在解决这类问题时遗传算法却能发挥出非常优秀的作用。

1。3  旅行商问题研究现状

一、国外研究现状： 旅行商问题最为一个最典型的组合优化问题，大多数国外学者已经做出过很多系

统的理论。近些年来国外遗传算法的主要研究方向转为怎样提高遗传算法跳出局部最 优解的能力以及怎样加快遗传算法的收敛速度。学者们通过改善遗传算法的如编码方 式，创新交叉策略还有参数辅助进行了大量的试验和研究。比如有些学者结合 Vose-Liepins5模型和 Markov6链这两个描述，研究出了有关遗传算法的 Markov 链模 型。还有分析遗传算法的“隐性并行性”与“模式定理”两大基本理论，并且以此为依据 提出了一种理想浓度模型，总结出了一个结论：即遗传算法的本质是一个具有定向制 导的随机搜索技术。

二、国内研究现状： 旅行商问题作为一个典型的组合优化问题，国内学者也已经做出大量的研究报告。

2012 年国内学者周永权，黄正新，刘红霞提出一种萤火虫组合优化算法，该方法可 以在解决旅行商问题具有在求解大规模的旅行商问题时可以收敛迅速，并且最优解误 差在 1%以内。2013 年上海一些学者就遗传算法的结合蚁群算法做出大量研究，使的 在蚁群算法解决旅行商问题时所拥有的准确性的同时又拥有了跳出局部极值的能力。

1。4 本文的主要研究工作及内容 本文主要研究对象是： (1)研究遗传算法的算法流程，及其各算子的表达方式。

(2)如何在能找出最优解的情况下找到一组遗传算子能使其够稳定收敛。 (3)比较保留精英选择算子与轮盘赌选选择算子的差异。

1。5  本文概述

接下来本文第二章主要就论文题目做出一定的预备知识，比如旅行商问题定义， 以及研究方法。并且总结了旅行商问题的分类，和解决旅行商问题的不同方法。最后

指出解决旅行商问题的重要意义。第二章还讲述了遗传算法的发展史以及遗传算法的 发展现状。以及遗传算法的基本步骤。

本文第三章讲述了利用遗传算法解决旅行商问题，遗传算法的各个参数的编码， 以及遗传算子的选择。介绍了遗传算法算法解决旅行商问题的基本流程。

本文第四章是这次的重点部分，首先本文就遗传算法解决旅行商问题做出四组实 验。第一组是就遗传算法解决旅行商问题可行性研究；第二组就遗传算法的遗传算子 进行计算研究选出稳定收敛的一组参数；第三组试验就遗传算法的普适性做出多组实 验，验证遗传算法在不同规模的旅行商问题都具有一定的可行性。最后，第四组实验 将用另一种选择算子来比较，总结两种选择算子的优劣。

最后，就这次毕业设计做出一个总体结论。

第二章 预备知识

2。1  旅行商问题

2。1。1  旅行商问题的发展历史

早在十九世纪初，爱尔兰数学家 Sir Willian Rowan Hamilto7和英国数学家 Thomas Penyngton Kirkman 就对旅行商问题给出了具体的数学描述。二十世纪二十年 代在维也纳，经济学家和数学家 Karl Menger8向他的同事阐述了有关旅行商问题的 有关事项。1948 年，在美国兰德公司的推动下，将旅行商问题（TSP）变为组合优化 问题难题的典型范例。TSP 问题不仅具有广泛的实际应用背景而且在组合优化问题上 也有着巨大的理论价值9，旅行商问题已被证明是一个 NP 难题。