卫星舱布局的若干图形学问题研究

论文摘要

卫星舱布局设计问题属于NP-Hard或NP-Complete问题,它既存在计算复杂性又具有工程复杂性,求解困难,达到工程应用要求更难。卫星舱布局设计属于卫星总体布局设计的重要内容,关系到卫星性能、寿命、可靠性等问题。本课题组多年来从事卫星舱布局设计研究,其中存在若干图形学问题需要解决。为此,本文做了如下3个问题的研究:（1）由于布局与布局模式密切相关,研究了布局模式问题,并将它与遗传算法相结合构成基于布局模式的遗传算法（Layout Pattern Based Genetic Algorithm,LPBGA）,用于求解2-D带性能约束的布局问题;（2）在本课题给出的人机结合的遗传算法中,需检索先验布局图作为参考图,并转化为数值解。为此研究了规则图形检测,又称为图形的形数转换;（3）研究了圆柱体-圆柱体、长方体-长方体和凸多面体-凸多面体的快速干涉计算问题。在基于演化算法的卫星舱复杂布局优化过程中,每次迭代需要对待布物之间作干涉计算,因此,如何寻求迭代过程中快速3-D干涉计算法是一个待解决的问题。将上述研究成果做为卫星舱布局优化的支撑方法和技术,也期望具有一定普遍性。本文主要工作如下:1.本文给出了基于完全关联图的布局模式构造算法,它包括最小多边形法和准边界直线法。本文的布局模式构造方法不论待布物分布稀疏或密集都是适用的,并且准边界直线方法的计算复杂度也较低。进而给出基于布局模式的遗传算法,用于求解2-D带性能约束的布局问题。其关键是在优化迭代过程中的每一代,都自动构造最优个体的布局模式解（个体）替代种群中较差的个体,跳出局部最优,避免早熟以提高求解效率和解的质量。经2-D带性能约束的布局设计的数值实验表明:本文方法与遗传算法（GA）、人机交互遗传算法（HCIGA）和并行混合蚂蚁免疫算法（PHAIA）等相比,具有较高的精度和效率。2.本文提出了一种3类图形的快速检测（图形至数值变换）的广义Hough变换方法。包括:（1）多个圆检测;（2）多个矩形检测;（3）混合多个圆、多个矩形检测。由于减少了无效采样和无效计算,经简化卫星舱布局的2-D规则图形检测等算例验证,提高了其检测效率。3.本文给出了圆柱体-圆柱体、长方体-长方体和凸多面体-凸多面体的快速不干涉检测算法。先将3-D问题投影为2-D问题,然后基于不适合多边形（no-fit polygon,NFP）对2-D问题实现快速不干涉检测,凸多面体不干涉检测算法还采用了向中心线正投影作不干涉加速检测。经遗传天线布局问题等算例验证,表明了其有效性。本文以卫星舱布局问题为背景,研究与该布局问题求解相关的三个图形学问题,即布局模式、2-D规则图形检测（形数变换）和3-D规则图形（圆柱体、长方体和凸多面体）的不干涉检测问题,为卫星舱布局问题求解提供支持。此外,上述算法和方法也具有一定的普遍性,可望推广应用于其它某些布局问题求解。

论文目录

• 摘要
• Abstract
• 缩略语表
• 1 绪论
• 1.1 课题的工程背景和研究的意义
• 1.1.1 研究问题的背景
• 1.1.2 本文研究意义
• 1.2 主要研究内容
• 1.3 研究基础
• 1.3.1 本文问题的研究基础
• 1.3.2 与本文相关的本课题组前期研究基础
• 1.4 论文的组织
• 2 布局问题相关的布局拓扑模式、图形检测和干涉计算的研究现状
• 2.1 布局问题的研究现状
• 2.1.1 布局问题的分类
• 2.1.2 布局问题的求解方法
• 2.2 布局模式的研究现状
• 2.3 图形检测（形数转换）的研究现状
• 2.3.1 圆检测
• 2.3.2 矩形检测
• 2.4 干涉计算的研究现状
• 2.5 小结
• 3 基于完全关联图的布局模式
• 3.1 同构和非同构布局模式
• 3.1.1 相关概念
• 3.1.2 相关知识
• 3.2 基于完全关联图的最小多边形法
• 3.2.1 布局模式控制区
• 3.2.2 算法的可行性分析和适应范围
• 3.2.3 算法复杂度分析
• 3.2.4 布局模式的构造方法
• 3.3 基于完全关联图的准边界直线法
• 3.3.1 布局模式控制区的准边界直线
• 3.3.2 准边界直线控制区
• 3.3.3 待布物布局模式控制区
• 3.3.4 构造同构、非同构布局模式的准边界直线方法
• 3.4 最小多边形法和准边界直线法的适应范围
• 3.5 布局模式的用途
• 3.6 基于布局模式的遗传算法
• 3.6.1 基于事例检索和匹配
• 3.6.2 基于布局模式的遗传算法
• 3.6.3 算例
• 3.6.4 算例结果分析与讨论
• 3.7 小结
• 4 图形检测（形数转换）
• 4.1 问题的提出与相关知识
• 4.1.1 问题的提出
• 4.1.2 图形检测的相关定义和定理
• 4.2 多圆快速随机检测
• 4.2.1 理想情形时多圆的检测
• 4.2.2 复杂情形时多圆的检测
• 4.2.3 算法分析与讨论
• 4.2.4 检测算例
• 4.3 多矩形检测
• 4.4 混合多圆多矩形检测
• 4.4.1 混合多圆多矩形检测策略
• 4.4.2 混合多圆多矩形检测算例
• 4.5 布局图检测算例
• 4.6 图形检测在卫星舱布局求解中的应用
• 4.7 小结
• 5 三维规则图形干涉计算
• 5.1 问题的提出和相关的基础知识
• 5.1.1 问题的提出
• 5.1.2 凸多边形不干涉检测
• 5.1.3 空间图形位置关系的判定
• 5.2 两端带半球的圆柱体不干涉检测
• 5.3 长方体不干涉检测
• 5.4 凸多面体不干涉检测
• 5.5 小结
• 6 总结与展望
• 6.1 全文工作总结
• 6.2 今后的工作
• 参考文献
• 攻读博士学位期间发表学术论文
• 致谢
• 论文创新点摘要
• 作者简介