1. 研究目的与意义
本文的主要研究目标就是用改进的启发式算法更好地解决TSP这个有意义的NP难问题。在分析了TSP问题的求解现状及基本启发式算法对TSP的求解理论、思路与成果的基础上，提出一种改进的启发式算法进行求解，并用多组数据进行分析与测试，将结果与传统的求解方法加以比较，证实其可行性。
针对启发式算法在应用过程中出现的收敛速度过慢和封闭竞争问题，可以使用贪心启发式算法，采用混合方式方法，启发式算法被用于个体中的全局搜索，而贪心算法在染色体中施行局部探寻。利用贪心算法指导遗传算子操作的策略，次策略强调了GA潜在的搜索方向使子代群体能在次方向前进，快速搜索到其它搞质量的区域，通过TSP问题实验以说明贪心启发式算法的有效性。本文主要研究启发式算法对于二维背包问题的针对性解决。
2. 研究内容和预期目标
(1) 研究的基本内容
通过启发式算法来解决从二维背包问题。
(2) 拟解决的主要问题
3. 国内外研究现状
启发式算法(GeneticAlgorithms，简称GA)是人工智能的一个重要分支，它是基于Darwin的进化论，在计算机上模拟生命进化机制而发展起来的一门新学科，是生命科学与工程科学互相交叉、互相渗透的产物[21。启发式算法由美国J．H．Holland博士1975年提出，随后经过多年的发展，取得了丰硕的应用成果和理论研究的进展。从1985年在美国卡耐基一梅隆大学召开的第一届国际启发式算法会议到1997年，启发式算法作为具有系统优化、适应和学习高性能计算和建模方法的研究渐趋成熟。
启发式算法本质上是一种求解问题的高度并行性全局搜索算法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。启发式算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题种类有很强的鲁棒性，因此能够广泛应用于很多学科。目前，启发式算法已在函数优化、组合优化、生产调度问题、自动控制、机器人智能控制、图像处理、模式识别、人工智能、遗传程序设计和机器学习等领域投入应用并取得了一定的成果。
旅行商问题(Traveling Salesman Problem，简记TSP)是组合数学中一个古老而又困难的问题，也是一个典型的组合优化问题，现已归入NP完备问题类。TSP问题的历史可以分成以下几个阶段：1800—1900年，首次描述TSP；1920．1950年；开始意识到TSP是“难'的问题；1954年，42城市的TSP求得最优解。从1954年以后，求得最优解的TSP规模越来越大，在1998年，求得了模拟美国13509个城镇的最优解，在2001年，求得了模拟德国15112个城镇的最优解，但这一工程代价也是巨大的，据报道，解决15112个城镇问的TSP共使用了美国Rice大学和普林斯顿大学之间网络互连的、由速度为500MHz的CompaqEV6 Alpha处理器组成的110台计算机，所有计算机花费的时间之和为22．6年。在2004年5月，瑞典求得了模拟24978城镇的最优解。
4. 计划与进度安排
调查法：调查启发式算法的实际意义和可行性研究；
行动研究法：应用启发式算法解决TSP问题，通过编程来验证，在研究过程中了解浮点数编码、适应度函数、交叉算子和变异算子，启发式算法的三个基本运算（选择、交叉、变异）等问题。
第4-6周：查阅资料；了解国内外的研究动态及目前国内的应用现状，熟悉算法；对系统进行需求分析并撰写需求分析报告。第7-9周： 进行系统的总体设计。第10-13周：模块设计及程序代码编写。第14-16周：系统调试、功能测试与完善；撰写毕业设计论文。第17周：毕业设计答辩。
5. 参考文献
[1]贾丽媛，杜欣，并行启发式算法研究j，湖南城市学院院报（自然科学版），2006
[2]王小平，曹立明，启发式算法—理论、应用与软件实现M，西安：西安交通大学出版社，2002
[3]毛盛贤，刘国瑞，遗传工程的应用与展望M，北京师范大学出版社，1986
