《卫星舱布局问题的智能求解方法研究》由会员分享，可在线阅读，更多相关《卫星舱布局问题的智能求解方法研究（118页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学博士学位论文卫星舱布局问题的智能求解方法研究姓名：徐义春申请学位级别：博士专业：机械设计及理论指导教师：肖人彬20080715I 摘摘 要要 本文针对复杂的卫星舱布局优化设计问题，采用现代智能优化技术，研究了多种布局情形，多种布局方法，并通过算例验证了这些方法的良好性能。 首先介绍了布局优化问题的背景，指出充分利用问题本身的启发式信息有利于求解卫星舱布局优化问题。 本着从简单到复杂的原则， 分别对卫星舱二维圆形布局问题、卫星舱二维多边形布局问题、以及卫星舱三维布局问题展开研究。 针对卫星舱二维圆形布局问题，改进了现有的计算模型，将多目标优化问题分为两个步骤求解。第一个步骤中引进一般
2、圆形布局问题中基于快速下降法的局部搜索方法，第二个步骤考虑平衡约束。为了得到近似全局最优解，采用多次迭代方法，从多点出发求解。通过在测试集上的计算，表明本文的处理方法相对于文献中的方法有更好的性能。 其次， 给出了卫星舱二维圆形布局问题的构造方法。 该方法在定位规则的约束下，逐个布置每个布局物的位置。因为采用不同的定位次序会得到不同的布局质量，本文采用了粒子群优化算法、遗传算法、以及蚁群优化算法等三种方法来进行定位次序的全局优化搜索。在相同的测试集上，构造法的计算效果对比最速下降法有进一步的提高。 随后，研究了卫星舱二维多边形布局问题。在以定量的方式定义了多边形的覆盖之后，采用模拟退火方法进行
3、覆盖量和不平衡量的优化。设计了一个可计算出理论最优值的多边形布局物测试集，该测试集既包含凸多边形布局物，也包含凹多边形布局物。在该测试集上的计算表明，在布局物数目不多的情况下，算法能保证所求布局解的性能。通过在一个现有的矩形布局物的测试集上的计算，表明算法的性能优于文献中的遗传算法。 最后，综合二维计算的研究成果，给出了卫星舱三维布局问题的求解方法。利用启发式方法将布局物分成两个集合，采用模拟退火方法对每个集合中的布局物在卫星舱中进行布局优化计算。 利用五个测试算例， 验证了方法的可行性。 与现有算法相比，II 本文的算法具有优势。 简言之，本文针对卫星舱布局优化问题的多种模型，采用了多种方法
4、进行计算。本文的计算结果表明，采用启发式方法，结合元启发式方法，是求解卫星舱复杂布局优化问题的有力手段。 关键词：关键词：布局优化 智能计算 启发式方法 III Abstract The main topic of this thesis is solving the layout optimization problems in satellite by the modern intelligent computation methods. Several models and a series of methods for the problems are studied. The per
5、formances of these methods are investigated by the computations on some benchmarks. We begin the thesis by introducing the background of the general layout optimization problems, and then we point out reasonably that making full use of the heuristic information of the problems themselves is conduciv
6、e to solving them. Under the problem-solving philosophy of from simple to complex, we first study the two-dimensional layout problem in satellite, in which the packed objects are circular. Then we continue to study the cases of packing polygon objects. Finally, we extend the research to the three di
7、mensional problems. For the two-dimensional problem of packing circular objects in satellite, we first modify the existed computational models in order that we can solve the problem in two steps. In the first step, we use the existed local search algorithm for the general circle packing problem, whi
8、ch is based on the gradient descent method, to obtain a layout without overlaps. In the second step, we concern the balance issue. To search for the global optimal solution, we run the two-step optimization multiple times and each time the algorithm starts from different point. The computation on th
9、e benchmarks shows that our method has better performance than literatures. Secondly, we invent a constructive heuristic for the two-dimensional problem of packing circular objects. In the constructive heuristic, the objects are positioned in a sequence by the construction rules. Because different p
10、ositioning sequences can result in layouts with different quality, we develop three meta-heuristics to search for the optimal positioning sequence, including the discrete particle swarm algorithm, the genetic algorithm, and the ant colony algorithm. On the same benchmarks, the new methods outperform
11、 the two-step optimization introduced above. Next, we study the two-dimensional problem of packing polygon objects. We first IV define the measurement of the overlaps between the polygons, and then we use simulated annealing method to optimize the overlaps and the unbalance. We design a benchmark fo
12、r the problem, in which the theoretical solution for each instance is known. The results on the benchmark show that the algorithm has good performance if the amount of objects is not very large. On another old benchmark for packing rectangle objects, the algorithm shows better performance than the g
13、enetic algorithm in literature. At last, we integrate the techniques on the two-dimensional problems, and apply them on the three-dimensional problem. We provide a heuristic to divide the objects into two sets, and then use the simulated annealing to pack the objects in each set on the two packing s
14、paces of the satellite. The algorithm is tested on a 5-instance benchmark, and the results show that the solving strategy is feasible and able to compete with other existed algorithms. In short, we studied several models for the packing problems in satellite, and provide some algorithms for them. Ou
15、r researches demonstrate that combination of the heuristic method and meta-heuristic method is a powerful tool for the layout problems in satellite. Keyword: Layout Optimization, Intelligent Computation, Heuristic 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发
16、表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_年解密后适用本授权书。 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属于 11 绪论绪论 布局问题是工业生产中常见的问题。在玻璃切割、服装裁减、以及木材加工和金属加工等行业，需要在一块或者多块
