1、毕业设计开题报告 计算机科学与技术 基于均匀设计的遗传算法求解旅行商问题 一、 综述本课题国内外研究动态，说明选题的依据和意义 旅行商（ Traveling Salesman Problem， TSP）是组合数学与图论中的一个古老而有名的NPComplete 问题。 它可叙述为：设有 (n+1)个编码为 1， 2， 3 ,(n+1)的城市，任意两个城市之间的距离 ddi0,寻找一条经过所有城市且每个城市只走一次的最短的闭合路径。 TSP 问题在许多领域都有广泛的应用。许多实际问题都可以转化为 TSP 问题例如 : 铁路运营、线路的选 择、计算机网络的拓扑结构等。 在生活学习工作中最优化问题是人
2、们经常遇到的问题 ,随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一 1。 TSP 最优解的搜索空间随着城市数 n 成指数型增长，所以， TSP 问题虽易于描述，但一般很难精确地求出其最优解 1。 近年来，有很多解决该问题的较为有效的方法不断被推出，例如二叉树描述法 、 启发式搜索法 、 遗传算法 、 模拟退火算法等 。 遗传算法 (Genetic algorithm s: GA )是一种自适应全局概率搜索算法 、 具有良好的全局寻优能力，成为解
3、决 TSP 问题的有效方法 2。 GA 的概念来自于生物学领域。早在进化论中， 达尔就提出了生物进化的动力和机制在于自然选择 , 自然选择是以变异为基础 , 并通过生存竞争实现。凡是具有适应环境的有利变异的个体 , 在生存竞争中将有更多机会生存和繁殖后代 , 而较差适应性的个体将被淘汰。遗传算法便是模仿这一过程并具有良好自适应能力的算法。 遗传算法是由美国密歇根大学的 John Holland 教授在 60年代提出的 1。 GA具有很强的鲁棒性，因此在应用在很多领域中 1。实践证明，遗传算法对于组合优化中的 NP 问题非常有效 ， 例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划
4、分问题等方面得到成功的应用 1。此外，遗传算法 也在生产调度问题、自动控制、机器人学、图象处理、 人工生命 、遗传编码和 机器学习 等方面获得了广泛的运用 1。 函数优化是遗传算法的经典应用领域，对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果 1。 人工智能方面，像机器人学，遗传算法也得到了很好的应用。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面取得了良好的成果 1。 现在越来越多的优化问题是多目标性的 ,以往的遗传算法在处理这种较为复杂的多 目标优化问题时候
5、,经常会有如下问题出现 1:遇到欺骗性问题会陷入次优解集；当目标函数差别很大 ,极易导致适应度函数被某一目标函数统治 ,寻优效果不佳；又由于算法的权值矢量也是随机产生的 ,在搜索方向上也极有可能集中在某一较小区域 ,也导致寻优效果不理想。对多目标优化 ,常采用权值矢量法 ,如果遗传算法只采用一个权值矢量组成一个适应函数 ,那么它就只有一个搜索方向 ,这样就很难找到其他最优点。为了保证搜索是在多个方向上进行的 ,又采用了多个权值矢量来组成多个适应度函数。然而 , 先前的方法对权值矢量的选取是随机的 ,这势必就会导 致搜索陷入某一范围 , 而得不到全局的优化效果。 在遗传算法中，参数设置得好坏往往
6、对遗传算法的性能和结果有着重要的影响，往往在解决某一问题的时候，需要设定的参数很多，如何获得最佳的参数组合是一个很重要的问题，以前常用正交设计等试验方法，但是在参数和参数水平个数都很多的问题中，这些传统的方法就不适用了。所以后来又提出了均匀设计的方案。 “均匀设计”是 80 年代由中国科学院数学所王元和方开泰教授将数论和多元统计分析相结合创立的一种新颖的试验方法，它是单纯从均匀性原则出发的试验设计 2。 均匀设计的主要目的是从给 定的样本中采样一些点 ， 而这些点能够均匀地分布 ， 它是一种能适应多因数、多水平实验的实验方法 ， 它比以前的实验方法计算次数大大减少 ， 提高了算法速度；其他的实
7、验算法就是在实验范围内挑选出代表性的实验点 ， 从而导致搜索进入某一集中区域得不到优良的解 ， 但均匀设计可以做到实验点在实验范围内均匀分布 ， 这样使搜索范围有很大提高 3。 均匀设计与统计的试验方法 “正交设计”相比 , 其试验次数大大减少 , 因而受到工程人员的普遍欢迎 . 均匀设计的核心思想是用确定性方法寻找空间中均匀分布的点集来替代 Monte Carlo 中的随机 数 , 因而属于 Monte Carlo 的范畴 , 可看成是统计抽样 , 这些都是引入 GA 并改进之的依据 2。 利用均匀设计来安排试验，通常有需注意 4： a.选用合适的因素和相应的水平。 b.选择选择的因素不要太
8、多，太多会造成主次不分。 c.试验范围尽可能大，因此每个参数的水平个数也要适当地大一些。 在运用均匀设计的方法来设计试验方案时，可以到文献 4中参考附录中给出的均匀设计表，均匀设计表的一些特点 4： a.每个因素的每个水平做且仅做一次试验。 b.任两个因素的试验点点在平面的格子点上 ,每行每列有且仅有一个试 验点。 c.均匀设计表任两列组成的试验方案一般并不等价。 d.当因素的水平数增加时 ， 试验数按水平数的增加量在增加。每一个均匀设计表必须有一个附加使用表，使用表也将给使用者提供。 我想，均匀设计和遗传算法的结合使用，效果应该会是很好的。在文献 3中的仿真试验可以看出，这种方法是可行的。
9、二、研究的基本内容，拟解决的主要问题： 研究基本内容：利用 C+语言编程实现算法功 能。 拟解决的主要问题： 1、 旅行商问题 2、算法的设计与实现。 三、研究步骤、方法及措施： 研究步骤： 1.查阅相关资料，做好笔记；仔细阅读研究文 献资料； 2.理清整个课题的思路，撰写开题报告和文献综述；翻译英文资料； 3.根据需求分析，编写算法，实现算法功能； 4. 撰写论文；上交论文初稿； 5.反复修改论文；论文定稿。 方法、措施： 充分利用好学校和网络资源，搜集与遗传算法、旅行商问题及均匀设计相关的资料， 仔细阅读、分析、总结。 在老师指导下，与同组同学研究讨论，解决设计中所碰到的问题。 四、参考文
10、献 1 周明，孙树栋 . 遗传算法原理及应用 . 国防工业出版社， 1999 2 文明瑶 . 基于遗传算法的 TSP的优化问题 . 电脑与信息技术， 2002.1.23 3 高齐圣，潘德惠 . 基于均匀设计的遗传算法及其应用 . 信息与应用， 1999.28(3) 4 方 开泰 .均 匀试 验 设计 的理 论、 方法 和 应用 历史 回顾 .数理 统计 与管 理 ，2004.23(3).pp69-77 5 何毅 ， 魏衡华 . 均匀设计在遗传算法中的研究和应用 . 计算机仿真， 2006.23(4) 6 余楠 . 一种改进的遗传算法及其在旅行商问题中的应用 . 电脑开发与应用， 2009.22(1) 7 李久坤 ,吴黎明 ,孙洪波 . 均匀设计模型的优化 . 沈阳建筑工程学院学报， 1997.13(2) 8 何大阔 , 王福利 ,张春梅 . 基于均匀设计的遗传算法参数设定 . 东北大学学报 (自然科学版 )， 2003.24(5) 9 邹亮 ,汪国强 . 均匀试验设计在遗传算法中的应用 . 华南理工大学学报 (自然科学版 )，2003.31(5) 10 周本达 ， 陈明华 ， 任哲 .均匀设计抽样混合遗传算法求解图的二划分问题 . 计算机应用， 2008(11)
