求解卫星舱布局问题的分治混合算法

《求解卫星舱布局问题的分治混合算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码10530学号201330111825分类号TP301密级公开硕士学位论文求解卫星舱布局问题的分治混合算法学位申请人张妙指导教师黎自强教授学院名称信息工程学院学科专业软件工程研究方向软件工程技术二○一六年五月五日TheDivide-conquerBasedHybridAlgorithmforSolvingSatelliteModuleLayoutProblemCandidateZhangMiaoSupervisorProf.LiZiqiangCollegeSoftwareEngineeringProgramSoftwareEngineeringInstituteDegreeMas

2、terofEngineeringUniversityXiangtanUniversityDateMay5th2016湘潭大学学位论文原创性声明本人郑重声明；所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加Ｗ标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中Ｗ明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名；曰期：办／知告月曰学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部口或机构

3、送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湘潭大学可Ｗ将本学位论文的全部或部分内容编入有关属性库进行检索，可Ｗ采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：故＾日期：又《年＾月＾日导师签名日期：年ｂ月ｉ日摘要布局设计问题(Packing问题)来源于许多工程应用领域，例如工程机械设计，板材切割排版，建筑空间设计、电子元器件摆放设计和卫星舱布局设计等。这些问题的求解目标通常是要求装填给定物体的容器尺寸尽可能小，或者是在一个给定尺寸的容器内放置更多的装填物，以达到充分利用容器空间的目的。布局问题，尤其是三维布

4、局问题，难以在一个多项式时间内求得最优解。目前求解布局问题的算法主要包括启发式算法、演化算法、协同算法以及人机交互。启发式算法的针对性太强不具有普适性，很难找到具有共性的启发式思路。演化算法收敛速度慢，且容易陷入局部最优解。协同算法以及人机交互为求解复杂问题提供了新思路，但要求与其它方法相结合，才能获得更好的效果。本文基于三阶段分治策略对卫星舱布局问题求解。三个阶段分别是：(a)问题的解空间分解；(b)子空间(承载面)装填方案优化求解；(c)将最优子空间方案合并成整体方案，并对其质心偏移量及惯性夹角进行优化。本文研究的重点是在(b)和(c)两阶段。对于(b)，将子空间装填优化问题归结为圆

5、和矩形混合布局问题，并充分利用本课题组已有的矩形装填布局成果。对于(c)，通过旋转承载面，采用遗传算法实现惯量夹角的优化。本文主要创新工作如下：(1)提出圆和矩形混合布局问题的启发式蚁群算法。对于圆和矩形混合布局问题，提出区域定位及向质心移动策略的构造布局方案，将移动策略进行优化调整，并提出了一种新的启发式蚁群算法。待布局物选择空白区域放置时，分多步慢慢向质心移动，减小移动步长，可能获得更好的解，通过实验证明了可能的存在性。(2)提出质心偏移量及惯性夹角优化的遗传算法。对于整体质心偏移量及惯性夹角的优化问题，本文基于合力为零的力学分析和承载面旋转，通过遗传算法迭代，得到质心偏移量和惯性夹

6、角均最小的整体最优解。通过多个算例的结果和已有方法比较，本文方法计算时间较少、并且容器的尺寸小、质心偏移量和惯性夹角都较小。关键字：布局问题；Packing问题；卫星舱布局问题；圆和矩形混合布局问题；启发式算法；蚁群算法；遗传算法；分治算法IAbstractLayoutdesignproblems(Packing)derivefrommanyengineeringfields,suchastheengineeringmachinedesign,sheetcutting,satellitemoduledesign,wiringofelectroniccomponentsandsoon.Th

7、eseproblemscanusuallybedescribedasthatallobjectsarepackedinacontainerassmallaspossible,ormoreobjectsareplacedwithinagivencontainer,inordertoimprovethespaceutilization.Whetherone-dimensional,two-dimensionalorthree-dimen