并行遗传退火算法的圆形件下料问题求解

摘要

圆形件切割下料工艺涉及到工业生产的方方面面。在铂金、飞行器制造、玻璃切割、变压器生产等行业中，圆形零件的切割下料有着广泛的应用。此类问题的优化目标是在定额的原材料上寻求有效、科学的方法切割出尽可能多的圆形零件，提高原材料的利用率，降低企业生产成本。圆形件下料问题主要有三个研究方向，第一种是板材中圆形件的下料问题，第二种是卷材中圆形件的下料问题，第三种是球体的集装箱问题研究。目前，圆形件的下料问题仍然是国内外研究的一个热点。
　　本文研究的是圆形件在卷材中的下料问题，是指将一定规格和数量的圆形件毛坯放置在定宽不定长的卷材上，目标是使消耗的卷材长度最短。因此，本文所做的主要工作如下:
　　(1)在最佳位置放置算法(Best Location Place-BLP)盼基础上，提出改进的最佳位置放置算法对圆形件进行定位排样。根据两种位置搜索策略，直接在已放置的圆弧上搜索可行位置，使两个毛坯相切放置，在保证利用率的同时，提高圆形件放置的速度。采用自适应遗传算法对圆形件下料序列进行引导。引入动态遗传算子在种群进化过程中对个体的交叉和变异概率进行自适应的非线性调整，提高算法收敛速度。在进化过程中，采用较好的选择交叉和变异策略寻求最优的排样序列。
　　(2)将自适应遗传算法与模拟退火算法融合求解圆形件下料问题，遗传算法局部搜索能力差，很容易陷入“早熟”状态，影响最终的求解质量。为此，在遗传算法进化过程中，引入模拟退火算法，通过模拟退火中的Metropolis准则对个体进行接受判定，使其具有了跳出局部极值的能力。采用遗传退火算法求解圆形件下料问题，要双次计算种群中个体的适应度值，时间复杂度比较高。为了更适用于工业生产的要求，采用主从式遗传退火策略，将个体的适应度评价过程即圆形件的放置过程分多线程同时处理。以此提高算法的时间性能。
　　(3)采用JAVA编程语言设计开发圆形件下料系统，通过国际通用数据与参考文献中的算法进行对比，表明本文的算法具有更高的下料利用率。

目录

声明

摘要

第1章 绪论

1．1 下料问题研究背景及意义

1．2 国内外研究现状

1．2．1 圆形件下料问题研究现状

1．2．2 智能算法求解下料问题研究现状

1．3 主要研究内容及创新点

1．4 论文的组织结构

第2章 本文相关基础介绍

2．1 圆形件下料问题概述

2．1．1 圆形件下料问题分类

2．1．2 基于卷材的圆形件下料问题描述

2．2 圆形件定位算法

2．2．1 圆弧搜索放置算法

2．2．2 BLP放置算法

2．2．3 橡皮筋势能放置算法

2．3 圆形件序列优化算法

2．3．1 遗传算法

2．3．2 自适应遗传算法

2．3．3 并行遗传算法

2．3．4 模拟退火算法

2．4 本章小结

第3章 自适应遗传算法圆形件下料问题求解

3．1 放置规则设计

3．1．1 ABLP位置搜索规则

3．1．2 最佳位置选取策略

3．1．3 ABLP定位步骤

3．2．1 遗传算子设计

3．2．2 自适应遗传算法圆形件下料问题求解步骤

3．3 测试实验

3．3．1 与其他文献的对比分析

3．3．2 自适应策略有效性分析

3．4 本章小结

第4章 并行遗传退火算法圆形件下料求解

4．1 遗传退火算法的圆形件下料求解

4．1．1 模拟退火算法设计

4．1．2 遗传退火算法求解圆形件的求解步骤

4．2 算法并行化处理

4．2．1 种群的分割

4．2．2 算法的并行化设计

4．2．3 并行算法的圆形件下料问题求解

4．3 测试实验

4．3．1 AGSA算法利用率测试

4．3．2 AGSA算法有效性分析

4．3．3 PAGSA算法时间性能的分析

4．3．4 PAGSA算法与其他文献算法对比

4．4 本章小结

5．1 总结

5．2 展望

参考文献

附录

致谢

攻读硕士学位期间发表和录用的论文