The Divide-conquer Based Hybrid Algorithm For Solving Satellite Module Layout Problem

Layout design problems(Packing) derive from many engineering fields, such as the engineering machine design, sheet cutting, satellite module design, wiring of electronic components and so on. These problems can usually be described as that all objects are packed in a container as small as possible, or more objects are placed within a given container, in order to improve the space utilization. Whether one-dimensional, two-dimensional or three-dimensional layout problem, it is difficult to get the optimal solution in a polynomial time. Its solutions mainly include heuristic algorithm, evolutionary algorithms, collaborative algorithms, and human-computer interaction algorithms. Heuristic algorithms are not of general-purpose approach.Evolution algorithm has a slow convergence speed and is easy to fall into local optimal solution. Collaborative algorithm and human computer interaction provide a new idea for solving complex problems, but it is necessary to combine them with other methods. In this paper, the satellite module layout problem is solved based on the strategy of three stages as follows:(a) the decomposition of the solution space,(b)the optimization of the packing scheme of the subspace(bearing surface) and(c) a total scheme consisted by optimal subspace schemes is optimized to make the error of mass centroid and inertia angle as less as possible. The research focuses on stages(b)and(c). For the stage(b), the packing problem of the subspace is converted into the circle and rectangle packing problem and the existing results of this research group are used for the rectangle layout problem. For the stage(c), the bearing surface rotation based the genetic algorithm is used to optimize of inertia angles. The main innovations of this paper are as follows:(1) A heuristic ant colony algorithm is proposed for the circle and rectangle layout problem. This paper proposes an improved region-positioning and centroid-moving strategy, i.e. it is moved slowly toward the centroid step by step to get a better solution when each component is placed in the blank area, and then proposes an improved heuristic ant colony algorithm for the circle and rectangle layout problem.Experimental results test the feasibility of the proposed algorithm.(2) A genetic algorithm is proposed for the optimization of the error of mass centroid and inertia angles. Based on the strategy of rotating the bearing surface,this paper presents a genetic algorithm to get an optimal total solution with less error of mass centroid and inertia angles. Compared with existing algorithms, the proposed algorithm has less calculation time, smaller size of the container and smaller inertia angle.