心遗传算法求解TSP问题.docVIP

毕 业 设 计（论 文）任 务 书 课题名称 贪心遗传算法求解TSP问题 姓 名 何熙之 学 号 050640307 院 系 信息与计算机科学系 专 业 计算机科学与技术 指导教师 贾丽媛 (副教授) 2009年 1 月 12 日 一、设计（论文）的教学目的 通过本课题的设计，培养学生综合运用所学知识分析和解决实际问题的能力；培养学生独立思考、调查研究、查阅中英文文献和收集资料的能力；使学生提高理论分析、开发软件的能力，从而拓宽学生的知识视野，锻炼和提高学生运用可视化编程工具进行软件开发的能力。 二、设计（论文）的主要内容 TSP问题是一个NP难题，采有传统的算法很难求出问题的最优解。TSP有哪些信誉好的足球投注网站空间随着城市数n的增加而增加，所有的旅程路线组合数为(n-1)！/2。在如此庞大的有哪些信誉好的足球投注网站空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的困难。借助于遗传算法的有哪些信誉好的足球投注网站能力解决TSP问题，是很好的一个想法。根据问题的规模，制定用户的需求计划，再根据需要开发相应的源代码软件，具体内容包括： 1、对货郎担问题进行调查，制定用户需求计划。 2、学习遗传算法原理及其使用。 3、学习C++等面向对象语言。 4、接受各自的设计任务，开发相关源代码程序。 5、总结毕业设计成果，编写有关材料。 6、准备毕业答辩。 设计（论文）的基本要求 通过毕业设计过程，要求学生掌握遗传算法的基本知识，并能通过计算机 编程解决TSP实际问题。逐步了解软件开发的基本步骤。 四、进度安排 序号 论 文（设 计）各 阶 段 内 容 起止日期 1 开题、准备资料、相关知识准备 2009.3.1-2009.3.31 2 对已有方法的检验、分析，并进行设计 2009.4.1-2009.4.20 3 对改进（或新的）方法的实现与测试，毕业论文初稿 2009.4.21-2009.5.18 4 整理资料、修改毕业论文，准备答辩 2009.5.19-2009.5.30 5 毕业答辩 2009.5.31 五、主要参考文献 [1] 贾丽媛,杜欣.并行遗传算法研究[J].湖南城市学院院报(自然科学版),2006,15:22- 23 [2] 王小平,曹立明.遗传算法—理论、应用与软件实现[M]. 西安:西安交通大学出版社， 2002 [3] 毛盛贤,刘国瑞.遗传工程的应用与展望[M].北京:北京师范大学出版社,1986. [4] 刘立平．遗传算法综述[J] ．东莞理工学院学报，2005，12（3）：48～52 [5] 李艺．工程结构优化设计的混合遗传算法[J] ．四川大学学报，2005，37（4）：16～ [6] 傅清祥,王晓东. 算法与数据结构[M]. 北京: 电子工业出版社,1998 [7] 邵军力,张景,魏长华.人工智能基础[M]. 北京: 电子工业出版社,2000 [8] 李鑫,陆海东.遗传算法及其应用[J].吉林化工学院院报,2005,22:45-46 [9] 谈家桢.基因和遗传[M].北京:科学普及出版社,1981. [10] 李金鹏．遗传算法原理及在结构优化设计中的应用[J]辽宁工学院学 报2004,24（3）56～59 学 生 毕 业 设 计（论 文） 开 题 报 告 书 课题名称 贪心遗传算法求解TSP问题 姓 名 何熙之 学 号 050640307 院 系 信息与计算机科学系 专 业 计算机科学与技术 指导教师 贾丽媛 (副教授) 2009 年 3 月 19 日 设计（论文）题目 贪心遗传算法求解TSP问题 课题的根据：1）说明本课题的理论、实际意义 2）综述国内外有关本课题的研究动态和自己的见解 ⑴课题的理论：遗传算法（Genetic Algorithm,简称GA）是以Darwin生物进化论哲学思想为启发的有哪些信誉好的足球投注网站技术，GA的基本概念和理论框架是由美国密执安大学的John Holland教授于1975年首先提出来的。模式定理证明了GA具有全局有哪些信誉好的足球投注网站能力。GA中的交叉被认为是贡献于GA的全局有哪些信誉好的足球投注网站性能最重要的因素，变异算子在一定程度上也有这种贡献。然而，遗传算法的有哪些信誉好的足球投注网站方向在遗传操作中很少被强调。为了快速获得高性能的候选解，有哪些信誉好的足球投注网站方向应能指示出GA在一定领域中潜在的前进方向，遗传操作随机数的使用常常会引起候选解在有哪些信誉好的足球投注网站空间中处于随机的位置，如果最优解所在区域距当前有哪些信誉好的足球投注网站区域很远又不能预先识别的话，这就降低了发现最优解的速度，尤其是对于多重优化问题。 ⑵课题的实际意义：遗传算法基于遗传算法的机器学习调查法行动研究法选择、交叉、变异）等问题。 完成期限和