基于遗传算法解无重复规格一维下料问题

摘要

一维下料问题在建筑、电力、水利等工程实践领域获得了越来越广泛的应用。寻找一种最优的下料方案，可以节省原材料，降低生产成本，从而为企业带来直接的经济效益。一维下料问题的研究不仅具有工程应用价值，同时对于设计自动化也具有重要意义。 一维下料问题本身具有NP-完全的性质，为满足诸多的限制条件，找到原材料数量长度、零件毛坯数量长度之间的最佳对应关系，问题的解集十分庞大。当前对于一维下料问题的研究大多是针对有限数量的毛胚规格长度重复的下料问题，而对于毛胚规格长度基本不重复的一维下料问题研究较少。 遗传算法作为一种随机搜索优化技术，是解决组合优化类复杂的问题有效方法。通过对无重复规格一维下料问题的系统研究，改进了基于遗传算法求解该问题的算法：设计出针对该问题的可行解的编码方式，对初始种群的产生提出了可行高效的随机排列后重组算法及最大长度优先排列重组算法；为了保证遗传算法的运行效率又要保证获得全局最优解，根据算法进程在杂交算子中由多点杂交逐级降为一点杂交，在变异算法中由多点变异逐级降为一点变异；根据解的适应度函数值采用轮盘赌方法产生下一代种群，最优保存策略来保持种群中的优良个体；系统地构造了解一维无重复规格下料问题的遗传算法框架。 通过实验数据测试，结果表明新算法能有效地求解一维无重复规格的下料问题，是解决该问题的可行算法。

目录

文摘

英文文摘

声明

引言

问题的提出

无重复规格一维下料问题简介

一维下料问题的研究进展

论文的理论依据

论文的主要内容

论文的内容安排

第一章一维无重复规格下料问题的数学模型

1.1视作组合优化的问题

1.2计算机程序实现一个可行的下料方案

第二章遗传算法的基本理论

2.1遗传算法的生物学基础

2.2遗传算法的基本流程

2.3遗传算法的基本定理及算法要点

2.3.1遗传算法原理

2.3.2编码方法

2.3.3适应度函数

2.3.4选择算子

2.3.5交叉算子

2.3.6变异算子

2.4遗传算法的应用及发展方向

第三章遗传算法求解无重复规格的一维下料问题

3.1算法设计思想

3.1.1初始种群

3.1.2编码方法

3.1.3遗传算子

3.1.4适应度函数

3.1.5遗传算法的控制参数

3.2算法描述

3.3计算实例和结果分析

结论

参考文献

谢辞