Research On The Intelligent Computational Methods For The Layout Optimization Problems In Satellite Capsule

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 performances 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 conducive 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 -dimensional 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, which 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 the 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 positioning 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 the two-step optimization introduced above.Next, we study the two-dimensional problem of packing polygon objects. We first 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 for 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 genetic 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 spaces 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. Our researches demonstrate that combination of the heuristic method and meta-heuristic method is a powerful tool for the layout problems in satellite.