基于均匀设计的遗传算法求解旅行商问题【文献综述】

《基于均匀设计的遗传算法求解旅行商问题【文献综述】》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、毕业论文文献综述计算机科学与技术基于均匀设计的遗传算法求解旅行商问题引言：遗传算法(Geneticalgorithms:GA)是由美国Michigan大学的JohnHolland教授在60年代提出的，它是一种自然适应优化方法，该算法是基于自然遗传和自然优选机理的寻优方法[1]。所谓自然遗传和自然优选来自于达尔文的进化论学说，该学说认为在生物进化过程中，任一动植物经过若干代的遗传和变异，使之能够适应新的环境，是优胜劣汰的结果，这种自然遗传思想也适用于求解优化问题。遗传算法具有十分顽强的鲁棒性，这是因为比起普通的优化搜索方法，它采用了许多

2、独特的方法和技术，其中最为重要的是许多传统的搜索方法都是单点搜索算法，即通过一些变动规则，使问题的解从搜索空间中的当前解(点)移动到另一解(点)[1]。这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷入局部的某个峰的优解[1]。与此相反，遗传算法是采用同时理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估，更形象的说，遗传算法是并行爬多个峰，这一特点使遗传算法具有较好的全局搜索性能，减少了陷于局部优解的风险[1]。因此遗传算法的初始分布，即开始搜索前选择的解空间的多个个体，对于算法收敛将是十分重要的[1]。如果初始分布过于

3、集中，就很可能使算法陷入局部最优，因此初始种群的多样性对算法的影响是很大的[1]。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数[1]：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果[1]。随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满

4、意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。670年代，我国在进行航空试验的时候提出要用较少的试验次数来完成参数水平较多的试验，如何来解决这个问题，是当时专家们的一个重要课题。通过对传统试验的研究和鉴于别过提出的创新理论之后，王开泰教授和王元教授提出了均匀设计这个方法[2]。均匀设计能很好得解决在经典遗传算法中对参数设定的问题。首先，遗传算法中需要确定的参数数目比较多，一般在3～5个左右，为

5、了测试出最佳的参数组合，往往需要在确定参数的取值范围后，再划分参数水平，若假定需要确定的参数有3个，参数水平有10个，那么，需要做的试验次数为3的10次方次，这个数目是非常惊人的，往往令人望而生畏。假如运用均匀设计的方法来设计试验，一般只需要做10次左右，这将大大地减少了试验的次数，为试验节约了可观的人力物力。目前均匀设计已经在各大领域中得到了运用，经过不断得发展和完善，将会取得更大的成就。1旅行商问题旅行商（TravelingSalesmanProblem，TSP）是指一名推销员要到N个城市推销货物，从任意一个城市出发，经过其余各城

6、市一次且仅仅一次，然后回到出发点，求其最短行程。该问题是组合数学与图论中的一个古老而有名的NPComplete问题。旅行商(TSP)问题的数学语言描述如下:给出一个图G=(V，E)，任意边e∈E上有非负权值w(e)，寻找G的哈密顿回路C，使得回路的总权值w(c)=Σw(e)（e∈E(c)）最小。2均匀设计简介20世纪70年代，计算机仿真试验设计（Designofcomputerexperiments）在那时是一个最有挑战的课题[2]。虽然很多的传统试验方法已经获得了很好应用效果，但是没有任何实验都适用的实验设计方法。特别是在一些复杂的

7、优化问题中，需要考察得因素较多且变化范围较大，从而要求每个因素有较多的水平，这类问题若用现在流行的试验设计方法（包括优选法和正交设计），则需要做较多的试验，常使使用者望而生畏[2]。“均匀设计”是80年代由中国科学院数学所王元和方开泰教授将数论和多元统计分析相结合创立的一种新颖的试验方法，它是单纯从均匀性原则出发的试验设计[3]。均匀设计的主要目的是从给定的样本中采样一些点，而这些点能够均匀地分布，它是一种能适应多因数、多水平实验的实验方法，它比以前的实验方法计算次数大大减少，提高了算法速度；其他的实验算法就是在实验范围内挑选出代表性

8、的实验点，从而导致搜索进入某一集中区域得不到优良的解，但均匀设计可以做到实验点在实验范围内均匀分布，6这样使搜索范围有很大提高[2]。均匀设计常用一个均匀矩阵U[D][M](D个水平即权值矢量，M个因素即目标函数)来实现