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

发布时间：2017-08-13 04:40

  本文关键词：求解卫星舱布局问题的分治混合算法

  更多相关文章： 布局问题 Packing问题 卫星舱布局问题 圆和矩形混合布局问题 启发式算法 蚁群算法 遗传算法 分治算法

【摘要】：布局设计问题(Packing问题)来源于许多工程应用领域,例如工程机械设计,板材切割排版,建筑空间设计、电子元器件摆放设计和卫星舱布局设计等。这些问题的求解目标通常是要求装填给定物体的容器尺寸尽可能小,或者是在一个给定尺寸的容器内放置更多的装填物,以达到充分利用容器空间的目的。布局问题,尤其是三维布局问题,难以在一个多项式时间内求得最优解。目前求解布局问题的算法主要包括启发式算法、演化算法、协同算法以及人机交互。启发式算法的针对性太强不具有普适性,很难找到具有共性的启发式思路。演化算法收敛速度慢,且容易陷入局部最优解。协同算法以及人机交互为求解复杂问题提供了新思路,但要求与其它方法相结合,才能获得更好的效果。本文基于三阶段分治策略对卫星舱布局问题求解。三个阶段分别是:(a)问题的解空间分解;(b)子空间(承载面)装填方案优化求解;(c)将最优子空间方案合并成整体方案,并对其质心偏移量及惯性夹角进行优化。本文研究的重点是在(b)和(c)两阶段。对于(b),将子空间装填优化问题归结为圆和矩形混合布局问题,并充分利用本课题组已有的矩形装填布局成果。对于(c),通过旋转承载面,采用遗传算法实现惯量夹角的优化。本文主要创新工作如下:(1)提出圆和矩形混合布局问题的启发式蚁群算法。对于圆和矩形混合布局问题,提出区域定位及向质心移动策略的构造布局方案,将移动策略进行优化调整,并提出了一种新的启发式蚁群算法。待布局物选择空白区域放置时,分多步慢慢向质心移动,减小移动步长,可能获得更好的解,通过实验证明了可能的存在性。(2)提出质心偏移量及惯性夹角优化的遗传算法。对于整体质心偏移量及惯性夹角的优化问题,本文基于合力为零的力学分析和承载面旋转,通过遗传算法迭代,得到质心偏移量和惯性夹角均最小的整体最优解。通过多个算例的结果和已有方法比较,本文方法计算时间较少、并且容器的尺寸小、质心偏移量和惯性夹角都较小。
【关键词】：布局问题 Packing问题 卫星舱布局问题 圆和矩形混合布局问题 启发式算法 蚁群算法 遗传算法 分治算法
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：V423.4;TP18
【目录】：

• 摘要4-5
• Abstract5-9
• 第1章 绪论9-17
• 1.1 课题背景9-10
• 1.2 问题描述10-13
• 1.3 研究现状13-15
• 1.4 内容和意义15-16
• 1.5 论文的组织16-17
• 第2章 子空间布局优化17-28
• 2.1 引言17-19
• 2.1.1 矩形布局问题研究现状17-18
• 2.1.2 圆和矩形布局问题研究现状18-19
• 2.2 问题的数学模型19
• 2.3 启发式定序和定位19-23
• 2.3.1 启发式定序19-20
• 2.3.2 区域定位20-21
• 2.3.3 向质心移动策略21-22
• 2.3.4 算法的步骤22-23
• 2.4 实验结果与分析23-26
• 2.4.1 数值实验23-26
• 2.4.2 分析26
• 2.5 小结26-28
• 第3章 卫星舱整体布局优化28-35
• 3.1 引言28
• 3.2 问题的数学模型28-29
• 3.3 遗传算法求解29-31
• 3.3.1 编码方式29
• 3.3.2 适应度计算29-30
• 3.3.3 选择操作30
• 3.3.4 交叉操作30
• 3.3.5 变异操作30
• 3.3.6 更新操作30
• 3.3.7 算法优化步骤30-31
• 3.4 试验结果与分析31-34
• 3.4.1 数值试验31-34
• 3.4.2 分析34
• 3.5 小结34-35
• 第4章 总结与展望35-36
• 参考文献36-40
• 致谢40-41
• 附录A：攻读硕士学位期间参与的研究项目41

，

本文编号：665467