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