论文部分内容阅读
布局问题(或称为装填问题)研究的是将多个物体互不嵌入地放置在有限空间的容器内,要求尽可能地提高容器的利用率。布局问题是一类NP-hard问题,该类问题的求解既要解决数学上的组合爆炸问题,又要解决复杂的工程问题。本文以卫星舱为背景,主要研究带性能约束的二维矩形和三维简化卫星舱布局优化问题。首先根据问题各自特点不同,分别给出待布物之间不同的干涉性判断条件和干涉量计算方法,由此给出具体的数学模型;然后分别针对不同模型提出一种单目标和多目标优化算法进行求解;另外在布局优化过程中,糅合了一些局部搜索策略和启发式策略,以进一步提高算法的优化效率。具体研究内容如下:(1)研究了带质量平衡约束的正交矩形布局问题。对于该问题,首先采用拟物方法,建立数学优化模型。然后对吸引盘填充(BF)算法中直方图更新机制进行改进,并使用启发式的占角策略更新布局,通过将带加速、回退策略的基于梯度法的局部搜索策略与吸引盘填充算法相结合,为带质量平衡约束的正交矩形布局问题提出了一种改进的吸引盘填充(IBF)算法。使用两组算例(其中一组来自于文献,另一组随机生成)对IBF算法进行了测试。实验结果表明,该算法是求解带质量平衡约束的正交矩形布局问题的一种有效算法。另外,为了测试算法中各种策略的效果,设计了 3组对比实验,分别对拟人占角策略、回退策略和直方图更新机制进行了详细的测试。(2)以国际商业通信卫星(INTELSAT-Ⅲ)系列卫星舱为背景,研究带性能约束卫星舱三维布局问题。首先对实际问题进行简化,建立三维简化模型,然后使用两种基于不同策略的多目标粒子群优化算法(MOPSO)进行全局搜索。第一种策略是利用目标空间分割法和轮盘赌法进行粒子的更新与粒子最优位置的选取;第二种策略是使用最近最远候选解法维护Pareto最优解集,基于解之间的距离选择每个粒子的历史最优位置和全局最优位置。为了使布局系统各待布物之间互不干涉,引入了一种变异操作和基于梯度法的合法化操作。最后使用一组包含53个待布物的测试算例进行了算法测试。实验结果表明,两种MOPSO算法均优于当前文献中的其他方法,是求解多目标三维卫星舱布局优化问题的有效算法。