论文部分内容阅读
卫星舱布局设计(SMLD)属于3D带性能约束的组合优化问题。求解此类问题时，需将三维卫星舱部件简化成圆柱体和长方体。当各部件竖直放于承载板时，该问题可以转化成2D带平衡约束的圆和矩形Packing问题。在体积固定的圆形容器内，该问题旨在满足几何约束和平衡约束条件的前提下，使布局系统的外包络圆的半径尽可能小。目前，国内外已有许多学者对此问题提出了许多有效算法，如启发式算法(如拟物拟人方法)、演化算法(如遗传算法、粒子群算法、蚁群算法等)、协同算法与人机结合等，但还没有检索到求解带平衡约束的矩形、圆与矩形布局问题的拟物拟人算法。另外，演化算法的求解性能有待进一步的提高。为了突破求解效率的瓶颈问题(干涉量计算问题)，本课题组在国家自然科学基金(61272294)、湖南省自然科学基金(11JJ6050)以及湖南省教育厅基金(11A120)等的支持下一直探索更为有效的求解带平衡约束的矩形、圆与矩形布局问题的机理和方法。通过对其进一步研究，本文提出了一种平衡约束的正交矩形Packing问题的拟物拟人算法，同时，也将拟物拟人算法拓展到圆和矩形布局问题中，提出了一种带平衡约束的圆和矩形正交Packing问题的分治拟物拟人算法。本文主要的创新点如下：对于带平衡约束的正交矩形Packing问题，本文提出了一种求解带平衡约束的正交矩形Packing问题的拟物拟人算法。它定义了2个连续、单调递减的嵌入度函数(两正交矩形之间的嵌入度函数，正交矩形与容器的嵌入度函数)，并且给予了证明；然后利用该算法求解本文问题。测试算例的计算结果表明，本文的算法的性能优于已存在的算法。对于带平衡约束的圆和矩形正交Packing问题，本文提出了一种基于弹性势能的求解带平衡约束的圆和矩形正交Packing问题的分治拟物拟人算法。该算法是在一个已知的半径的容器内随机产生一个初始解，然后利用拟物拟人算法找到一个互不干涉的可行解，然后在计算质心和外包络圆半径，如果外包络圆半径小于阈值，则得到满意布局方案，否则重新计算。数值实验表明，本文的方法有较优性能。拟物拟人算法在求解带平衡约束的正交矩形Packing问题和带平衡约束的圆和矩形正交Packing问题上，取得了不错的效果。希望本文算法能为求解其它布局问题提供帮助和借鉴。