全文总字数：5963字

1. 研究目的与意义及国内外研究现状

通过模仿生物遗传学和自然选择的机理，借助生物遗传学的观点，通过编码，选择，交叉，变异等算子构造一类优化搜索算法（遗传算法），在给定一组n个城市和他们两两之间的直达距离的前提下，在合理的时间内，找出一个闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短（tsp问题）。并且算法要达到要求的精度，同时对选择的算法做出适当的分析和评估。

旅行商问题，即tsp问题（traveling salesman problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。tsp问题本质是一个组合优化问题。该问题可以被证明具有npc计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

与传统的优化相比，在求取符合运行要求的全局最优解时候，遗传算法作为一种搜索的方法，已经成为成熟的具有良好收敛性、极高鲁棒性和广泛适用性的优化算法，可以用于tsp问题的求解问题。

国内外研究现状

遗传算法是一种仿生优化算法，，它是借鉴生物界自然选择和遗传机制发展起来的随机搜索算法，即为一种全局优化自适应概率搜索算法。近年来，遗传算法作为一种实用、高效、鲁棒性的优化技术发展极为迅速，受到了越来越多的国内外学者的广泛关注。

2. 研究的基本内容

遗传算法是一种借鉴生物界自然选择和遗传机制的高度并行、随机、自适应的全局优化概率搜索算法,但算法自身的一些不足也有待于进一步地改进和完善。

而作为代表性问题——tsp问题是一个组合优化问题，该问题可以被证明具有npc计算复杂性，该问题的近似求解算法向来是相关领域的研究重点。为此，本课题拟用遗传算法求解tsp问题为研究对象，分析遗传算法的运行机理。因此我将进行以下四方面的研究：

3. 实施方案、进度安排及预期效果

实施方案：

1、大数据量的解决：对城市进行编号，每个城市分别用1到n之间不同的整数表示，n个整数的一个排列就代表了旅行商的一个可能解。（即整数编码问题）

2、①.交配规则：

4. 参考文献

[1] 陈国良，王煦法，庄镇泉，王东生：遗传算法及其应用，人民邮电出版社，1996年

[2] 李敏强，寇纪淞，林丹，李书全：遗传算法的基本理论与应用，科学出版社，2002年

[3] 王小平，曹立民：遗传算法——理论、应用与软件实现，西安交通大学出版社，2002年