带性能约束的二维矩形及三维卫星舱布局算法研究

摘要

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

目录

声明

摘要

第一章 绪论

1．1 研究背景和意义

1．2 国内外研究现状与进展

1．3 论文的主要工作

1．4 论文的组织结构

1．5 本章小结

第二章 布局优化算法

2．1．1 遗传算法

2．1．2 模拟退火算法

2．1．3 势能曲面变平算法

2．1．4 粒子群优化算法

2．2 布局优化算法分析

2．3 本章小结

第三章 带质量平衡约束的正交矩形布局问题的吸引盘填充算法

3．1 问题描述与数学模型

3．2 问题的求解思路

3．3 干涉量的计算方法

3．4 基于拟人化策略的改进的吸引盘填充算法

3．4．1 吸引盘填充算法

3．4．2 改进的势能曲面变平算法

3．4．3 启发式选择策略

3．4．4 拟人化占角策略

3．4．5 局部搜索策略

3．4．6 基于拟人化策略的改进的吸引盘填充算法

3．5 算法测试及评价

3．5．1 经典算例的测试

3．5．2 随机算例的测试

3．5．3 性能分析

3．6 本章小结

第四章 带性能约束卫星舱三维布局问题的多目标粒子群算法

4．1 问题描述与数学模型

4．2 问题的求解思路

4．3 干涉量的计算方式

4．4 基于目标空间分割法的多目标粒子群算法

4．4．1 Pareto最优解集

4．4．2 目标空间分割法

4．4．3 选择策略

4．4．4 启发式的变异操作和基于梯度法的合法化操作

4．4．5 多目标粒子群优化算法

4．5 基于最近最远候选解法的多El标粒子群算法

4．5．1 最近最远候选解法

4．5．2 解之间距离的计算方法

4．5．3 标量化目标函数

4．5．4 选择策略

4．5．5 基于最近最远法的多目标粒子群优化算法

4．6 实验结果和分析

4．6．1 测试算例

4．6．2 结果分析

4．7 本章小结

第五章 总结与展望

5．1 论文所做的工作

5．2 论文的主要创新点

5．3 研究展望

致谢

参考文献

作者简介