1、北京工商大学毕业论文 (设计)开题报告姓名：姚启迪 班级：微机 011学号： 01042111指导教师：刘杰同组学生姓名：无毕业论文（设计）题目：遗传算法在 TSP问题中的应用选题的目的和意义遗传算法是适应性的启发式搜索算法，研究历史比较短，由美国 Michigan大学 John Holland等人于 20世纪 60年代末首先提出，它以自然选择和遗传机制的进化思想为前提，体现着 “适者生存 ”的竞争机制，以模拟生物进化的机制来构造人工系统的模型。随后的 20余年的发展，取得了很大的进展，特别是近年来世界范围形成的进化计算热潮，计算智能已作为人工智能研究的一个重要方向，以及后来的人工生命研究兴起
2、，使遗传算法受到广泛的关注。遗传算法的一些主要应用领域有：函数优化、组合优化、生产调度问题、自动控制、机器人智能控制、图像处理和模式识别、人工生命、机器学习以及社会经济领域。组合优化问题中一个典型问题就是巡回旅行商问题，也称为货郎担问题，简称为 TSP问题，是一个容易描述但难以处理的典型的 NP难题。 几十年来，针对此问题，出现了很多近似优化算法，如邻近法、贪心算法、最近插入法、最远插入法、双极小生成树法等等。由于遗传算法的强大搜索能力，所以用遗传算法求解 TSP问题是求得满意解的最佳方法，也是继续研究和发展该问题得出更好解决方案的最有潜力的方向。 本题的研究现状及开题前的准备工作v 遗传算法
3、是一种有效的强大的随机搜索方法，其性能主要取决于编码方法及选择、交叉、v 变异所采用的方法。 以往曾对此课题做过研究和探讨，所采用的方案如下： v 袁华 初始种群的生成 加入了均匀设计表 (局限于 20个城市 ) v 选择：排序及轮盘赌v 交叉：顺序交叉（ OX）v 变异：逆转变异v 吴颖 初始种群的生成 加入了均匀设计表 (局限于 20个城市 ) v 选择：联赛v 交叉：边重组v 变异：对换v 朱英： 初始种群的生成 加入了均匀设计表 (编程实现了任意个城市 ) v 选择：轮盘赌方法 轮盘赌与期望值结合的方法v 交叉：部分匹配交叉 (PMX)v 变异：插入变异v 查阅相关的文献资料，理解遗传
4、算法和 TSP问题的基本概念与基本思想，对课题的背景、应用和发展现状有一定的了解与认识，并对前人的方案进行比较，了解编码、选择、交叉、变异操作的各种方法，比较其优劣，以寻求更优方案。 毕业论文的进度安排v 第 周：查阅课题相关的文献资料，对遗传算法与 TSP问题的研究方法和研究现状有一定的认识；比较和研究前人方案，总结和规划出一个更优方案v 第 5周：根据算法特点，按模块编写程序，并在每个阶段对程序进行测试，以验证与以往方案相比，本论文所采取的方案是否更加优化。v 第 周：对实验结果进行分析与探讨，并得出结论。v 第 周：根据周志、参考资料等，概括和总结本次设计的成果、存在的问题及改进，在此基础上，撰写毕业论文，完成毕业设计。 毕业论文（设计）的主要内容v 遗传算法流程图如下：v 在用遗传算法解决 TSP问题过程中，参照以往的研究成果所得出的经验教训，对流程图中编码及生成初始种群、适应度函数、选择操作、交叉操作等环节所采用的方法进行研究改进，同时参考一些当前较新的研究动态，从中得到启发，寻求一种更优的课题解决方案，使遗传算法在组合优化问题中的应用有更进一步的进展。
