资源描述：
《基于均匀设计的遗传算法求解旅行商问题【开题报告+文献综述+毕业论文】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、毕业论文本科毕业论文开题报告计算机科学与技术基于均匀设计的遗传算法求解旅行商问题一、综述本课题国内外研究动态，说明选题的依据和意义旅行商（TravelingSalesmanProblem，TSP）是组合数学与图论中的一个古老而有名的NPComplete问题。它可叙述为：设有(n+1)个编码为1，2，3…,(n+1)的城市，任意两个城市之间的距离dd[i]>0,寻找一条经过所有城市且每个城市只走一次的最短的闭合路径。TSP问题在许多领域都有广泛的应用。许多实际问题都可以转化为TSP问题．例如:铁路运营、线路的选择、计算机网络的拓扑结构等。在生活学习工作中最优化问题是人们经常遇到
2、的问题,随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一[1]。TSP最优解的搜索空间随着城市数n成指数型增长，所以，TSP问题虽易于描述，但一般很难精确地求出其最优解[1]。近年来，有很多解决该问题的较为有效的方法不断被推出，例如二叉树描述法、启发式搜索法、遗传算法、模拟退火算法等。遗传算法(Geneticalgorithms:GA)是一种自适应全局概率搜索算法、具有良好的全局寻优能力，成为解决TSP问题的有效方法[2]。GA
3、的概念来自于生物学领域。早在进化论中，达尔就提出了生物进化的动力和机制在于自然选择,自然选择是以变异为基础,并通过生存竞争实现。凡是具有适应环境的有利变异的个体,在生存竞争中将有更多机会生存和繁殖后代,而较差适应性的个体将被淘汰。遗传算法便是模仿这一过程并具有良好自适应能力的算法。遗传算法是由美国密歇根大学的JohnHolland教授在60年代提出的[1]。GA具有很强的鲁棒性，因此在应用在很多领域中[1]。实践证明，遗传算法对于组合优化中的NP问题非常有效，例如遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用[1]。此外，遗传算法也在生产调
4、度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用[1]。43毕业论文函数优化是遗传算法的经典应用领域，对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果[1]。人工智能方面，像机器人学，遗传算法也得到了很好的应用。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面取得了良好的成果[1]。现在越来越多的优化问题是多目标性的,以往的遗传算法在处理这种较为复杂的多目标优化问题时候,经常会有如下问题出现[1]:遇到欺骗性问
5、题会陷入次优解集；当目标函数差别很大,极易导致适应度函数被某一目标函数统治,寻优效果不佳；又由于算法的权值矢量也是随机产生的,在搜索方向上也极有可能集中在某一较小区域,也导致寻优效果不理想。对多目标优化,常采用权值矢量法,如果遗传算法只采用一个权值矢量组成一个适应函数,那么它就只有一个搜索方向,这样就很难找到其他最优点。为了保证搜索是在多个方向上进行的,又采用了多个权值矢量来组成多个适应度函数。然而,先前的方法对权值矢量的选取是随机的,这势必就会导致搜索陷入某一范围,而得不到全局的优化效果。在遗传算法中，参数设置得好坏往往对遗传算法的性能和结果有着重要的影响，往往在解决某一问
6、题的时候，需要设定的参数很多，如何获得最佳的参数组合是一个很重要的问题，以前常用正交设计等试验方法，但是在参数和参数水平个数都很多的问题中，这些传统的方法就不适用了。所以后来又提出了均匀设计的方案。“均匀设计”是80年代由中国科学院数学所王元和方开泰教授将数论和多元统计分析相结合创立的一种新颖的试验方法，它是单纯从均匀性原则出发的试验设计[2]。均匀设计的主要目的是从给定的样本中采样一些点，而这些点能够均匀地分布，它是一种能适应多因数、多水平实验的实验方法，它比以前的实验方法计算次数大大减少，提高了算法速度；其他的实验算法就是在实验范围内挑选出代表性的实验点，从而导致搜索进入
7、某一集中区域得不到优良的解，但均匀设计可以做到实验点在实验范围内均匀分布，这样使搜索范围有很大提高[3]。均匀设计与统计的试验方法——“正交设计”相比,其试验次数大大减少,因而受到工程人员的普遍欢迎.均匀设计的核心思想是用确定性方法寻找空间中均匀分布的点集来替代MonteCarlo中的随机数,因而属于MonteCarlo的范畴,可看成是统计抽样,这些都是引入GA并改进之的依据[2]。利用均匀设计来安排试验，通常有需注意[4]：a.选用合适的因素和相应的水平。b.选择选择的因素不要太多，太多会造成主次不分
