基于遗传算法的TSP问题求解方法的研究与实现.doc

项目编号： 衡阳师范学院大学生课外学术 科技创新基金项目申报表 项目名称：基于遗传算法的TSP问题求解方法 的研究与实现 申 请 者： 苏伟鹏 系（院）专业： 数学与计算科学系 联系电话： 14789336474 申请日期： 2011-4-11 项目类别: ■自然科学类学术论文 □哲学社会科学类社会调查报告和学术论文 □科技发明制作 共青团衡阳师范学院委员会制 二○一一年三月 项目基本情况 项目名称 基于遗传算法的TSP问题求解方法的研究与实现 项目类别 自然科学类学术论文 研究期限 一年 申请经费 1000 项目负责人姓名 苏伟鹏 专业 信息与计算科学 所属系（院） 数学与计算科学系 主要合作人员 姓 名 系（院）及专业 陈 晶 数学与计算科学系信息与计算科学专业 匡励午 数学与计算科学系信息与计算科学专业 邓小丽 数学与计算科学系信息与计算科学专业 李敏芝 数学与计算科学系信息与计算科学专业 指导老师 姓 名 工作单位及称谓 王增波 数学与计算科学系 项目简介 首先利用Matlab.7.0编写基于遗传算法的程序，实现TSP问题的求解。 然后，依据实现TSP问题求解优越性的两个重要指标——求解结果的最优性和时效性，认真分析遗传算法和实验结果，通过实验法和对比法合理调整各种参数指标，力求达到结果的最优性和时间复杂性的平衡。但是考虑到把二者完全兼顾是不可能达到的理想状态，因此课题主要是在TSP的问题求解结果的最优性上下功夫，同时亦要保证一定的时间复杂性。最后，通过遗传算法与其他智能优化算法的比较，突出基于遗传算法求解的优越性。 二、立论依据（项目的意义、现状分析、参考文献等） 项目的意义： TSP在科学管理与经济决策等许多应用领域中的很多实际问题如电路布线、输油管路铺设、车辆运输路径、物流配送等，通过对经常需要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素进行集中概括和简化形式后都可以转化而成TSP问题，因此对对TSP问题求解方法的研究具有重要的应用价值。然而TSP作为一种典型--易描述但难于解决的组合优化问题,经过证明是一个NP-hard问题，利用简单的排列组合的方法在实际中完成是永远无法完成的，所以人们一直在努力寻求另外一种求解TSP问题方法。故有效解决TSP问题在计算理论上和实际应用上都有很高的价值。 国内外研究现状分析 对于求解TSP问题，国内外都有相当好的进展，周培德于2000年用点集凸壳的多项式时间算法解决了31个顶点的中国货郎担问题。1998年，美国加利弗利亚大学Dan Gusfiled根据出度、入度均为的2的有向图G中有一条H‘ilton路的这一特性，提出了用Greedy算法求解出度、入度均为2的TSP。同年，澳大利亚VladlmirG.Deineko证明T距离满足Demidenko矩阵时，MaxTSP(指遍历所有城市的最大权Hamilton 圈)是NP-难题，而之前已证TSP在此条件下是多项式时间可解的。几十年来对于求解TSP 问题出现了很多传统方法，其中有精确算法如线性规划方法、动态规划方法、分支定界方法;近似优化算法有插入法、生成树法等。近年来，有很多解决该问题的较为有效的智能方法不断被推出，例如禁忌搜索方法、遗传算法、模拟退火算法等。 主要参考文献 [1]李薇.遗传算法及其在TSP问题中的应用研究[D].贵州:贵州大学2008.4.1， [2]薛宏智.遗传算法在TSP上的应用及改进[D].西安：长安大学,2006 [3]彭丹平.遗传算法在TSP问题上的应用[D]南京：东南大学，2006.5.20 [4]xiepengqh686.遗传算法求解TSP问题?[z].?中南大学，2011年1月 [5]宗满意.遗传算法的TSP(旅行商问题)的求解 [z].北京:北京航空航天大学，2004 [6]赵雪梅.遗传算法及其在TSP问题求解中的应用 [J].?四川兵工学报， 2009，30(11):22-26 [7] 雷英杰等编著.MATLAB 遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005.4 [8] 王小平，曹立明．遗传算法[M]．西安：西安交通大学出版社，2001． 三、研究方案 a)研究目标、研究内容和拟解决的关键问题： 研究目标和研究内容： 利用遗传算法实现TSP问题求解，主要在求解结果的最优性上下功夫，并通过与其他智能优化算法的比较，突出基于遗传算法求解的优越性。 拟解决的关键问题： 选取合适的适应度函数和遗传操作，逼进最优解。 b)拟采取的研究方法及可行性分析 研究方法： 1. 采用文献调研法，