基于遗传算法解决TSP问题的研究开题报告

全文总字数：868字

1. 研究目的与意义

遗传算法是一种模拟大自然生物进化过程的计算模型, 它以其简单、全局寻找以及不受搜索空间限制性条件约束等特点而日益受到人们的关注。

遗传算法的群体搜索策略为多目标优化提供了非常合适的解决方案。

tsp问题是一类经典的np完全组合优化问题,传统的优化方法由于计算复杂性过大而难以求得全局最优解。

2. 国内外研究现状分析

遗传算法(Genetic Algorithms，简称GA)是人工智能的一个重要分支，它是基于Darwin的进化论，在计算机上模拟生命进化机制而发展起来的一门新学科，是生命科学与工程科学互相交叉、互相渗透的产物[21。遗传算法由美国J．H．Holland博士1975年提出，随后经过多年的发展，取得了丰硕的应用成果和理论研究的进展。从1985年在美国卡耐基-梅隆大学召开的第一届国际遗传算法会议，到1997年5月IEEE Transactions on Evolutionary Computation创刊，遗传算法作为具有系统优化、适应和学习高性能计算和建模方法的研究。

旅行商问题(Traveling Salesman Problem，简记TSP)是组合数学中一个古老而又困难的问题，也是一个典型的组合优化问题，现已归入NP完备问题类。TSP问题的历史可以分成以下几个阶段：18001900年，首次描述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是成阶乘数增长的，故一般很难精确地求出其最优解。对于这个问题，不论是传统的动态规划、分枝定界法、贪婪法等方法，还是在近些年的研究过程中采用的各种智能优化算法(禁忌搜索、模拟退火、遗传算法、人工神经网络、蚂蚁算法以及它们的混合算法等)，都存在解的质量不高或者需要的时空开销太大等问题。

3. 研究的基本内容与计划

主要内容：tsp问题是一个np问题难题，采用传统的算法很难求出问题的最优解。tsp搜索随着城市数n的增加而增加，所有的旅程路线组合数为（n-1）!/2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的困难。借助于遗传算法的搜索能力解决tsp问题，是很好的一个想法。根据问题的规模，制定用户的需求计划，再根据需要开发相应的源代码软件，具体内容及计划包括：

第1~3周对tsp问题进行调查，学习研究解决问题方法的最优性；

第4~6周学习研究遗传算法原理及其使用；

4. 研究创新点

对于求解TSP问题，相比于其他算法，遗传算法作为一种组合优化的问题求解方法，采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。