| The application background of Layout problem (Packing problem) includes layoutdesign of the satellite module and printed circuit board (PCB), facility layout inworkshop, plate cutting in processing industry and so on. For solving of theseproblems, it is required to use as small space as possible and must have to satisfygiven performance constraints. Therefore, these problems are called layout problemswith performance constraints. The circle packing problem with equilibriumconstraints (ECPP problem) is one of them. It is difficult to solve, due to its nature ofNP-hard. So, many scholars studied this problem in depth and proposed someeffective algorithms, for example, heuristic algorithm and evolutionary algorithm(genetic algorithm, simulated annealing, taboo algorithm, the ant colony optimizationand particle swarm algorithm). The pertinence of heuristic algorithm is stronger thanother algorithms, and overlapping calculation has become the bottleneck that restrictsfurther improvement on performances of evolutionary algorithms for the layoutproblems, particularly for larger scale layout problems. Therefore, in support of theNatural Science Foundation of Hunan Province and under the satellite module layoutdesign background, our subject group study on the heuristic algorithm, the stepwiseoptimization strategy and parallel ant colony optimization for solving circle packingproblem with constraints of equilibrium, and achieveda number of research results toimprove the efficiency, accuracy and the stability of the algorithms. The main worksof this paper include three aspects:(1) A fast heuristic strategy is proposed, and on the basis of it the random searchalgorithm (HRSA) is put forward for solving ECPP problem. The heuristic orderingrule is to take circular radius and mass as heuristic information of probabilitycomputation of roulette wheel selection, and the circles are located by arrangingaround the existing peripheral circles with counterclockwise. Compared withstep-by-step ordering and positioning algorithm (Xu Yichun, control the decision,2007), the computational complexity is lower, and both radius of container circle andamount of static unbalance are smaller. The experimental results show theeffectiveness of the algorithm.(2) A fast heuristic ant colony algorithm (FHACOA) is presented for solvingECPP problem. The based idea of the proposed algorithm is to combine the proposedheuristic strategy with ant colony optimization based on positive feedback principle to avoid the overlapping area calculation in the iterative process. The experimentalresults show that the proposed algorithm improves the solving accuracy andcomputational efficiency of ECPP problem.(3) A parallel stepwise ant colony algorithm (SPACOA) is proposed for solvingECPP. The stepwise optimization strategy includes that the solution space is dividedinto several subspaces, and then the each subspace is optimize in turn one by one toobtaim its optimal solution components. Optimization of each subspace is iterated thegiven times on the whole solution space for all individuals, and the solutioncomponents of the sub-space optimized remains unchanged. The combining stepwiseant colony optimization and parallel mechanism improve the solving accuracy,computational efficiency and stability of the algorithm. The experimental results showthe good formance of the proposed algorithm.Under the background of satellite module, this paper discusses circle packingproblem with equilibrium constraint, and three effective algorithms are proposed.Auther hopes the proposed algorithms can be applied to solve other layout problemswith performance constraints. |
PDF Full Text Request