毕业设计(论文)开题报告
学院：计算机与信息工程学院 课题名称 2015年 3月23日 (学生填表)
遗传算法在玻璃原料配送中的应用 计算机科学 与学生姓名 专业班级 技术 高工 课题类型 软件工程 指导教师 职称 课题来源 工程 1.综述本课题国内外研究动态，说明选题的依据和意义
1.1国内外研究动态
遗传算法(GeneticAlgorithms，简称GA)是人工智能的一个重要分支，它是基于 Darwin的进化论，在计算机上模拟生命进化机制而发展起来的一门新学科，是生命科 学与工程科学互相交叉、互相渗透的产物［210遗传算法由美国J H . Holla nd博士 1975 年提出，随后经过多年的发展，取得了丰硕的应用成果和理论研究的进展。从 年在美国卡耐基一梅隆大学召开的第一届国际遗传算法会议到 具有系统优化、适应和学习高性能计算和建模方法的研究渐趋成熟。 遗传算法本质上是一种求解问题的高度并行性全局搜索算法，它能在搜索过程中 自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传 算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对 问题种类有很强的鲁棒性，因此能够广泛应用于很多学科。目前，遗传算法已在函数 优化、组合优化、生产调度问题、自动控制、机器人智能控制、图像处理、模式识别、 人工智能、遗传程序设计和机器学习等领域投入应用并取得了一定的成果。 旅行商问题(Traveling Salesman Problem简记TSP)是组合数学中一个古老而又困 难的问题，也是一个典型的组合优化问题，现已归入 1985 1997年，遗传算法作为 NP完备问题类。TSP问题的历 史可以分成以下几个阶段：1800—1900年，首次描述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是成阶乘数增长的，故一般很难精确地求出其最优 解。对于这个问题，不论是传统的动态规划、分枝定界法、贪婪法等方法，还是在近 些年的研究过程中采用的各种智能优化算法(禁忌搜索(tabusearch)、模拟退火 (simulated annealing)遗传算法(genetic algorithms)、人工神经网络(neural networks)、 蚂蚁算法(ant algorithms)以及它们的混合算法等)，都存在解的质量不高或者需要的时 空开销太大等问题。 1.2选题依据及意义 本文的主要研究目标就是用改进的遗传算法更好地解决
TSP这个有意义的NP难
问题。在分析了 TSP问题的求解现状及基本遗传算法对 TSP的求解理论、思路与成果 的基础上，提出一种改进的遗传算法进行求解，并用多组数据进行分析与测试，将结 果与传统的求解方法加以比较，证实其可行性。
针对遗传算法在应用过程中出现的收敛速度过慢和封闭竞争问题，可以使用贪心 遗传算法，采用混合方式方法，遗传算法被用于个体中的全局搜索，而贪心算法在染 色体中施行局部探寻。利用贪心算法指导遗传算子操作的策略，次策略强调了
在的搜索方向使子代群体能在次方向前进，快速搜索到其它搞质量的区域，通过 问题实验以说明贪心遗传算法的有效性。
GA潜 TSP
2.研究的基本内容，拟解决的主要问题
（1） 研究的基本内容
通过遗传算法来解决从10个料场（分别存放白云石、长石、萤石、海砂等）将玻璃 原料运送到粉碎车间的TSP问题。即一辆大型货车需要经过 10个料场装载原料，每 个料场必须且仅能经过一次，最后回到粉碎车间。要求依据该现实问题求出最短路径。
（2） 拟解决的主要问题
1） 在设计交叉算子和变异算子的过程中，利用最短路径的数学性质和统计学规律，
设计出改进的启发式顺序交叉算子和启发式变异算子，并与既有的 实验。并对遗传算子、每代最优解的进入和退出演化过程的性能进行了分 析。
OX、CX、ERC等
算子进行比较和分析。对基因规模、变异概率和交叉概率随着代数的增加而变化的动 态性质进行
2） 在程序实现时，大量利用STL和Boost的既有数据结构和算法，并利用设计模 式的
知识，使程序的实现更加灵活高效。
3） 将改进的遗传算法应用于机械加工的孔群加工顺序模拟中，取得良好的效果。 3?研究步骤、方法及措施
调查法：调查遗传算法的实际意义和可行性研究；
行动研究法：应用遗传算法解决 TSP问题，通过编程来验证，在研究过程中了解 浮点数编码、适应度函数、交叉算子和变异算子，遗传算法的三个基本运算（选择、 交叉、变异）等问题。
4. 研究工作进度
第4-6周： 查阅资料；了解国内外的研究动态及目前国内的应用现状，熟悉算 法；对系统进行需求分析并撰写需求分析报告。
第7-9周：
进行系统的总体设计。
第10-13周：模块设计及程序代码编写。
第14-16周：系统调试、功能测试与完善；撰写毕业设计论文。 第17周：
毕业设计答辩。
5. 主要参考文献
[1] 贾丽媛，杜欣，并行遗传算法研究j,湖南城市学院院报（自然科学版），2006 [2] 王小平，曹立明，遗传算法一理论、应用与软件实现
社，2002
M，西安：西安交通大学出版
[3] 毛盛贤，刘国瑞，遗传工程的应用与展望 M，北京师范大学出版社，1986
[4] 刘立平 遗传算法综述J。东莞理工学院学报，2005
⑸李艺，工程结构化设计的混合遗传算法 J。四川大学学报，2005
[6] 傅清祥，王晓东，算法与数据结构 M。北京：电子工业出版社，1998 [7] 邵军力，张景，魏长华，人工智能基础 M，北京：电子工业出版社，2000 [8] 李鑫，陆海东。遗传算法及起应用 J。吉林化工学院院报，2005 [9] 谭家幀，基因和遗传M，北京：科学普及出版社1981 [10] 李金鹏，遗传算法原理及在结构优化设计中的应用
J,辽宁工学学院报，2004
[11] 周明，孙树冻，遗传算法及其应用 M，北京：国防工业出版社，1999 [12] 张文修，梁怡。遗传算法的数学基础 M西安：西安交通大学出版社 2000 [13] 魏英资，赵明杨，黄雪梅，胡玉兰 A。求解TSP问题的贪心遗传算法，2004 [14] 贺毅朝，刘坤起，张翠军，张巍A。求解背包问题的贪心遗传算法极其应用，2007
遗传算法开题报告
