Layout Algorithms For Two-dimensional Rectangle And Simplified Three-dimensional Satellite Module Layout Problems With Performance Constraints

With n objects and a bounded space provided with given shape and size, the packing problem is to research how best to pack these objects into the bounded space without overlaps, so as to improve the space utilization of the container. The packing problem is a classical NP-hard problem. It not only solves combinatorial explosion problems in mathematics, but also aims at complex engineering system problems.Under the background of the satellite module layout design, we study how to optimize the layout with performance Constraints. According to the features of each model, we use single-objective and multi-objective optimization to solve two problems, respectively. Considering the actual situation for different problems, we use different methods for calculating the interference condition. Combining local search algorithm, heuristic strategy and global algorithms, a hybrid algorithm is proposed to solve those problems. The concrete research contents and results are as follows:(1) We study the orthogonal rectangular packing problem (ORPP) with mass balance constraint. Based on the quasi-physical strategy, we convert the problem into an unconstrained optimization problem. We use the improved Basin filling(IBF)algorithm to solve the ORPP with mass balance constraint. In the IBF, in order to avoid the energy landscape paving falling into narrow and deep valleys of energy landscape, a new update mechanism of the histogram function in the ELP is put forward. In addition,a quasi-human corner-occupying strategy and a local movement strategy based on the adaptive gradient method with retreatment and acceleration are used to update the layouts. Two instances (one is from the literature and the other is generated randomly) are used to test the IBF algorithm. Experimental results show that the proposed algorithm is an effective method for solving the ORPP with mass balance constraint. Moreover, three groups of contrast experiments are designed to test the quasi-human corner-occupying strategy, the retreat strategy, and the new update strategy of the histogram function in the IBF algorithm.(2) Then, we study the simplified 3D satellite component distribution and layout optimization problem with performance Constraints by using INTELSAT- Ⅲsatellites. First, we simplify the actual problem and establish a 3D model, and then we use the multi-objective particle swarm optimization algorithm (MOPSO) to search a feasible layout. In the P SO algorithm, we use two different strategies to improve algorithm. Within the first strategy,we partition objective space of layout to assess fitness of each particle and select the best particle by using the roulette wheel.Within the second strategy, we use nearest-farthest method to maintain Pareto optimum sets, and choose pBest and gBest based on distance of solutions. In addition,we use mutation operation and legitimation operation which is based on the gradient method to improve the algorithm. Finally, one instance with 53 objects is tested.Experimental results show that the proposed algorithms both are effective methods for solving the simplified 3D satellite component distribution and layout optimization problem with performance Constraints.