圆形件排样优化算法及其并行实现方法的研究

《圆形件排样优化算法及其并行实现方法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学位论文数据集中图分类号TP301学科分类号520．1040论文编号lOOl0201208lO密级公开学位授予单位代码10010学位授予单位名称北京化工大学作者姓名赵政宝学号2009000810获学位专业名称控制科学与工程获学位专业代码0811课题来源国家计委、科委项目研究方向智能算法、分布式计算论文题目圆形件排样优化算法及其并行实现方法研究关键词圆形件排样，NP问题，启发式方法，单亲遗传算法，并行计算论文答辩日期2012-05-24论文类型应用研究学位论文评阕及答辩委员会情况姓名职称工作单位学科专长

2、指导教师楚纪正教授北京化工大学过程建模，仿真，控制评阅人1李宏光教授北京化工大学过程控制评阅人2崔玉龙副教授北京化工大学电力电子技术评阅人3评阅人4评阅人5撇员纵李宏光教授北京化工大学过程控制答辩委员1陈娟教授北京化工大学控制理论答辩委员2夏涛副教授北京化工大学计算机仿真答辩委员3崔玉龙副教授北京化工大学电力电子技术答辩委员4王颖副教授北京化工大学精密测试答辩委员5注：一．四．论文类型：1．基础研究2．应用研究3．开发研究4．其它中图分类号在《(中国图书资料分类法》查询。学科分类号在中华人民共和国国家

3、标准(GB／T13745-9)《学科分类与代码》中查询。论文编号由单位代码和年份及学号的后四位组成。摘要圆形件排样优化算法及其并行实现方法研究排样优化问题广泛存在于国民经济生产中的机械制造、木材服装加工、印刷排版和交通运输等行业，采用排样优化技术实现对这些行业生产及运营各环节资源的优化利用，已成为企业降低生产运营成本，提高经济效益的重要手段之一。排样优化问题是具有极高计算复杂度的NPC类问题，研究其求解方法，不仅可以满足求解生产实践中排样优化问题需要，同时也为其他NPC类问题求解方法研究提供了重要的理

4、论依据。因此，开展排样优化问题求解方法的深入研究，对促进实践生产发展和推动计算科学理论进步都具有极其重要的价值和意义。圆形件排样优化问题普遍存在于工业生产和人们生活中，但相比于其他类型排样优化问题研究情况，其求解方法研究仍然较少，并且由于其排样件形状相对不规则，排样规律难寻，更加大了问题求解难度。本文在总结分析国内外研究现状及发展趋势基础上，分别对矩形容器内及圆形容器内圆形件排样，提出了一系列新的求解方法，主要工作及研究内容有：(1)针对矩形容器内圆形件排样优化问题求解，本文提出一种以启发式多策略布局

5、为基础，基于二分搜索和单亲遗传算法驱动的混合算法(PGA．BOFA)。算法基于一个嵌套双重迭代过程实现：内核OFA算法，通过定义紧凑度、可行度等优选参数，并引入优先占项角、贴边界等布局策略，能够求得定长矩形容器内圆形件排样布局；在OFA基础上，内环BOFAT北京化工大学硕士学位论文算法利用二分搜索白适应找到在指定布局策略下的矩形容器最小长度；外环通过单亲遗传算法迭代进化，动态改变BOFA算法运行的布局策略，驱动整个算法运行，以扩大搜索解空间，提高求解质量。(2)对于圆形容器内圆形件排样优化问题，根据排

6、入容器和排样件特点，本文通过定义伪边、伪顶角等概念，提出了对圆形容器进行拟矩形划分的设计思想，并设计了适用于问题求解的布局策略，使得PGA—BOFA算法同样可以用于圆形容器内圆形件排样优化问题求解。(3)根据PGA．BOFA算法隐含的并行性特点，并结合HPC系统高速并行性，基于并行分而治之思想，本文设计实现适用于求解圆形件排样优化问题的并行PGA．BOFA算法。算法基于主从式．粗粒度并行模型，采用多种群不同控制参数同时进化方式，结合最优解收集协同处理及子种群个体整体迁移策略，不仅加强种群整体的多样性，

7、同时避免盲目搜索，进一步提高算法搜索速度和质量。最后基于MPI技术在构建的HPC系统上实现了上述并行算法。通过大量算例的实验测试和仿真，对以上三种方法进行了验证和性能分析，结果表明其对圆形件排样优化问题求解是可行有效的。关键词：圆形件排样，NP问题，启发式方法，单亲遗传算法，并行计算IIABSTRACTRESEARCHONSOLVINGALGORITHMANDPARALLELMETHODoFCIRCLEPACⅪNGPRoBLEMABSTRACTPackingoptimizationproblemsca

8、nbefoundinmanyareassuchasmachinemanufacturing，garmentprocessing，publicationprintingandtraffictransportation，anditbelongstotheNP—completeproblemwiththemostcomplicatedcomputation．Therefore，researchonsolvingalgorithmofpackingproblem