湖南文理学院芙蓉学院
本科生毕业论文(设计)开题报告书
题    目 基于遗传算法的TSP问题分析与研究
学生姓名 ＿  刘    涛＿＿＿＿＿   
学    号 ＿＿07120111＿＿＿＿＿＿ 
专业班级 ＿计算机技术与科学＿＿＿ 
指导老师 ＿＿方    数据结构与算法论文霞＿＿＿＿＿＿ 
2010年 12月 10日
论文（设计）题目
基于遗传算法的TSP问题分析与研究
课题目的、意义、国内外有关研究动态：
目的：本文的主要研究目标就是用改进的遗传算法更好地解决TSP这个有意义的NP难问题。在分析了TSP问题的求解现状及基本遗传算法对TSP的求解理论、思路与成果的基础上，提出～种改进的遗传算法进行求解，并用多组数据进行分析与测试，将结果与传统的求解方法加以比较，证实其可行性。
意义：遗传算法（Genetic Algorinhm，简称GA）是以Darwin生物进化论哲学思想为启发的搜索技术，GA的基本概念和理论框架是由美国密执安大学的John Holland教授于1975年首先提出来的，模式定理证明了GA具有全局搜索能力。AG中的交叉被认为是贡献于GA的全局搜索性能最重要的因素，变异算子在一定程度上也有这种贡献。然而，遗传算法的搜索方向在遗传操作中很少被强调。为了快速获得高性能的候选解，搜索方向应能指出GA在一定领域中的潜在的前进方向，遗传操作随机收的使用常常会引起候选解在搜索空间中处于随机的位置，如果最优解在区域距当前搜索区域很远又不能预先识别的话，这就降低了发现最优解的速度，尤其是对于多重优化问题。
针对遗传算法在应用过程中出现的收敛速度过慢和封闭竞争问题，可以使用贪心遗传算法，采用混合方式方法，遗传算法被用于个体中的全局搜索，而贪心算法在染体中施行局部探寻。利用贪心算法指导遗传算子操作的策略，次策略强调了GA潜在的搜索方向使子代体能在次方向前进，快速搜索到其它搞质量的区域，通过TSP问题实验以说明贪心遗传算法的有效性。
遗传算法的应用广泛，在卫星路由器中的应用，硬件演化，自适应遗传算法网络资源均衡与优化等很多方面均有实现。随着其应用范围的逐渐扩展，遗传算法的研究方面也出现了新的方面，如基于遗传算法的机器学习。遗传算法与其它智能算法的参透结合，并行遗传算法的研究等方面。这些对于遗传算法的研究，不仅推动着遗传算法自身的发展，同时对其它智能算法的发展有着重要的作用，特别在人工生命的研究上，遗传算法发挥着其不可代替的作用。
遗传算法是由自然界的进化论模拟而来，是一种机制求解级值问题的自组织、自适应的智能算法，它在解决一些复杂问题特别是优化问题方面有其特别与独到之处，是一种值得深入研究的算法。
国内外有关研究动态：遗传算法(GeneticAlgorithms，简称GA)是人工智能的一个重要分支，它是基于Darwin的进化论，在计算机上模拟生命进化机制而发展起来的一门新学科，是生命科学与工程科学互相交叉、互相渗透的产物[21。遗传算法由美国J．H．Holland博士1975年提出，随后经过多年的发展，取得了丰硕的应用成果和理论研究的进展。从1985年在美国卡耐基一梅隆大学召开的第一届国际遗传算法会议(International Conference on Genetic AlgorithmsICGA’85)，到1 997年5月    IEEETransactionsonEvolutionaComputation创刊，遗传算法作为具有系统优化、适应和学习高性能计算和建模方法的研究渐趋成剥51。
遗传算法本质上是一种求解问题的高度并行性全局搜索算法，它能在搜索过程中自动获取和积累有关搜索空问的知识，并自适应地控制搜索过程以求得最优解。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题种类有很强的鲁棒性，因此能够广泛应用于很多学科。目前，遗传算法已在以下领域投入应用并取得了一定的成果：函数优化、组合优化、生产调度问题、自动控制、机器人智能控制、图像处理、模式识别、人工智能、遗传程序设计和机器学习等【3】。而有关遗传算法的理论研究进展则主要集中在以下几个方面：①GA的数学理论方面，如图式定理、算法的复杂分析、算法的收敛性分析等；②编码方面；③初始体生成方面；④适应度函数方面；⑤遗传算子方面；@GA与其它方法的结合方面；⑦GA与问题领域知识结合方面；⑧并行GA方面。
旅行商问题(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城镇的最优解。
TSP可能的路径总数与城市数目n是成阶乘数增长的，故一般很难精确地求出其最优解。对于这个问题，不论是传统的动态规划、分枝定界法、贪婪法等方法，还是在近些年的研究过程中采用的各种智能优化算法(禁忌搜索(tabusearch)、模拟退火(simulated annealing)、遗传算法(genetic algorithms)、人工神经网络(neural networks)、蚂蚁算法(ant algorithms)以及它们的混合算法等[181)，都存在解的质量不高或者需要的时空开销太大等问题。
课题的主要内容（观点）、创新之处：
主要内容：TSP问题是一个NP问题难题，采用传统的算法很难求出问题的最优解。TSP搜索随着城市数n的增加而增加，所有的旅程路线组合数为（n-1）!/2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的困难。借助于遗传算法的搜索能力解决TSP问题，是很好的一个想法。根据问题的规模，制定用户的需求计划，再根据需要开发相应的源代码软件，具体内容包括：
1、 对货郎但问题进行调查，制定用户需求计划。
2、 学习遗传算法原理极其使用。
3、 学习c/c++语言。
4、 接受各自的设计任务，开发相关源代码程序。
5、 总结毕业设计成果，编写有关材料。
6、 准备毕业答辩。
创新之处:
l、在设计交叉算子和变异算子的过程中，利用了最短路径的数学性质和统计学规律，设计出改进的启发式顺序交叉算子和启发式变异算子，并与既有的OX、CX、ERC等算子进行了比较和分析。对基因规模、变异概率和交叉概率随着代数的增加而变化的动态性质进行了实验。并对遗传算子、每代最优解的进入和退出演化过程的性能进行了分析。
2、在程序实现时，大量利用了STL和Boost的既有数据结构和算法，并利用了设计模式的知识，使程序的实现更加灵活高效。
3、将改进的遗传算法应用于机械加工的孔加工顺序模拟中，取得了良好的效果。
研究方法：
调查法：调查遗传算法的实际意义和可行性研究；
    行动研究法：应用遗传算法解决TSP问题，通过编程来验证，在研究过程中了解浮点数编码、适应度函数、交叉算子和变异算子，遗传算法的三个基本运算（选择、交叉、变异）等问题。
毕业论文进度安排：
开始时间：2010年12月10日
提交时间：2011年5月31日
2.27—3.5    调研、文献检索、开题报告初稿。
3.6—3.10    开题报告审定、座谈会
3.11—4.11    外文资料翻译、系统设计
4.12—5.12    编码、测试。做好相关文件模板的建立工作。进行代码编写并调试，统一界面，集成加入课题系统
5.13—5.20    毕业论文报告（论文）的编写，毕业答辩资料的准备
5.21—5.24    上交毕业文档资料，毕业设计报告（论文）、PPT演示文稿、相关图纸准备
5.25—5.26    填写毕业设计答辩申请表
5.28—5.31    提交论文，毕业答辩
主要参考文献与资料：
1 贾丽媛，杜欣，并行遗传算法研究j，湖南城市学院院报（自然科学版），2006
2 王小平，曹立明，遗传算法—理论、应用与软件实现M，西安：西安交通大学出版社，2002
3 毛盛贤，刘国瑞，遗传工程的应用与展望M，北京师范大学出版社，1986
4 刘立平 遗传算法综述J。东莞理工学院学报，2005
5 李艺。工程结构化设计的混合遗传算法J。四川大学学报，2005
6 傅清祥，王晓东，算法与数据结构M。北京：电子工业出版社，1998
7 邵军力，张景，魏长华，人工智能基础M，北京：电子工业出版社，2000
8 李鑫，陆海东。遗传算法及起应用J。吉林化工学院院报，2005
9 谭家幀，基因和遗传M，北京：科学普及出版社1981
10 李金鹏，遗传算法原理及在结构优化设计中的应用J，辽宁工学学院报，2004
11 周明，孙树冻，遗传算法及其应用M，北京：国防工业出版社，1999
12 张文修，梁怡。遗传算法的数学基础M西安：西安交通大学出版社 2000
13 魏英资，赵明杨，黄雪梅，胡玉兰A。求解TSP问题的贪心遗传算法，2004
14 贺毅朝，刘坤起，张翠军，张巍A。求解背包问题的贪心遗传算法极其应用，2007

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。