带平衡约束的多形状装填问题的两阶段优化算法研究

《带平衡约束的多形状装填问题的两阶段优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码10530学号201330111752分类号TP391密级公开硕士学位论文带平衡约束的多形状装填问题的两阶段优化算法研究学位申请人曾媛指导教师黎自强教授学院名称信息工程学院学科专业计算机科学与技术研究方向智能计算二○一六年六月八日TheResearchofTwoStageOptimizationAlgorithmonMulti-shapedObjectsPackingProblemwithStaticImbalanceConstraintsCandidateZengYuanSupervisorLiZiqiang(professor)CollegeSchoo

2、lofInformationandEngineeringProgramComputerScienceandTechnologySpecializationIntelligentComputingDegreeMasterofScienceUniversityXiangtanUniversityDateJun8th,2016湘潭大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方

3、式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湘潭大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或,扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期：年月日导师签名：日期：年月日摘要卫星舱装填问题可简单描述为：将给定的仪器和设备等有效载荷合理地、紧凑地放置在卫星舱的承载板上，满足给定的性能约束前提下,使舱室尽可能小。

4、求解该问题时，一般都是将仪器和设备简化为圆柱体和长方体，进而将每一个承载面的装填问题归结为平衡约束混合圆和矩形布局问题，但这种简化可能降低其求解精度，进而影响卫星舱整体装填方案的质量。为此，本课题组在国家自然科学基金的资助下，以卫星舱装填设计为背景，研究带平衡约束的多形状仪器和仪表装填的布局设计问题。其思想是：基于几何、数学、计算机图形学和运筹学等知识，首先将仪器和设备简化为圆柱体、半圆柱体、长方体、三棱柱、梯台和半圆柱长方体，进而将每一个承载板表面的装填问题归结为圆、半圆、矩形、三角形、梯形及半圆矩形的多形状混合装填的布局问题；然后探索可行有效的求解方法，主要工

5、作和创新描述如下。1.提出一种基于改进动态调整的平衡约束多形状粗装填方法。将多形状用其外包络矩形替代进行粗装填。提出一种改进的动态调整策略，并将其与拟人拟物算法结合，获得平衡约束多形状粗装填的最优方案。数值实验表明：提出的方法能在迭代求解过程中有较快的收敛速度，特别对大规模布局问题有效。2.提出一种基于移动策略的平衡约束多形状精调方法。对于已经布局好的外包络矩形的布局方案，去除外包络矩形之后的方案还可以进一步优化，本文提出了一种简单的判断干涉的方法，计算待布物之间的嵌入度，并应用试探性的移动策略，优化布局方案。实验表明，本文提出的干涉判断的方法，有效的减少了干涉量

6、计算的时间、提高了求解多个形状的布局方案的效率。本文以卫星舱布局问题为研究背景，研究平衡约束多形状布局问题，提出其粗装填和精调两阶段方法，并进行了算例验证。实验数据表明，本文算法在多形状物体布局问题的计算效率优于现有的算法，希望能作为3-D多形状平衡约束装填问题求解的阶段性成果，也为其它2-D多形状布局问题研究提供参考和借鉴。关键词：矩形布局；多形状装填问题；拟人拟物算法；调整策略IAbstractThepackingproblemofasatellitecabin,ie,placingthegiveninstrumentsandpayloadsonbearing

7、platesofthesatellitemoduleinthebestwaytoreducethespaceinthemostdegreeandgainafeasibleandcompactlayoutsolutioninconditionofperformanceconstraints.Whensolvingtheproblembyexistedalgorithms,objectsarealwayssimplifiedtocuboidsandcylinders,andtransformthepackingproblemoneachbearingboardsurf

8、acest