Chinese Journal of Computers   Full Text
Title	An Improved Scatter Search for Circles Packing Problem with the Equilibrium Constraint
Authors	WANG Yi-Shou1),2) SHI Yan-Jun2) TENG Hong-Fei2),3)
Address	1)(School of Aeronautics and Astronautics, Dalian University of Technology, Dalian, Liaoning 116024) 2)(School of Mechanical Engineering, Dalian University of Technology, Dalian, Liaoning 116024) 3) (Department of Computer Science and Engineering, Dalian University of Technology, Dalian, Liaoning 116024)
Year	2009
Issue	No.6(1214—1221)
Abstract &   Background	Abstract The equilibrium-constrained circles Packing problem with the background of satellite module layout design belongs to NP-hard problem. The authors extend scatter search(SS) to deal with this problem, and propose the improved scatter search. The authors empirically study the coordinate transformation-based diversification method and the reference set update method on the basis of two dissimilarities. The gradient descent algorithm and Nelder-Mead simplex algorithm are adopted to improve the trial solution generated at two different stages in SS, respectively. The improved scatter search can make a tradeoff between exploration and exploitation. Experiment results show the feasibility and effectiveness of the improved scatter search. Keywords equilibrium constrained Packing problem; scatter search; local search; heuristic method Background The author’s subject group has been engaged in research on spacecraft layout optimization problems, including circles packing problem with the equilibrium constraint in this study. Research on circles Packing contributes on the exploration of theoretical nature of layout design, and effective solution approach. This work focuses on scatter search (SS) for circles packing problems with the equilibrium constraint in order to apply it into 3D layout design of satellite module. This work is supported by the National Natural Science Foundation of China under grant Nos.50275019, 50575031, 60674078, and the National High Technology Research and Development Program (863 Program) of China under grant No.2006AA04Z109. The state-of-the-art of layout design reveals that evolutionary algorithms and heuristic algorithms have recently shown the great promise in solving circles packing problems with the equilibrium constraint; however, how to improve solution quality and computational efficiency are an open issue. According to the authors’ experiences of tackling complex layout problem, the hybrid approach integrating effective evolutionary algorithm with context-dependent heuristic or local search algorithm seem to be a more potential and effective means. The SS methodology is very flexible. Each of its elements can be implemented in a variety of ways according to the specific domain problem. Especially, SS is easy to integrate heuristic or local search algorithms to enhance the solution quality. How to apply SS into complex layout design deserves to further study.