|
|
|
| Genetic Algorithm for Rectangle Layout Optimization with Equilibrium Constraints |
| XU Yi-Chun1 ,DONG Fang-Min1,LIU Yong1,XIAO Ren-Bin2 |
1.Institute of Intelligent Vision and Image Information,China Three Gorges University,Yichang 443002
2.Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074 |
|
|
|
|
Abstract The 2-dimensional layout optimization problem is studied, where the unequal weighted rectangles are required to be placed in a circular container without overlap. There are two objectives, minimum of the radius of the circle and equilibrium of the system. In most of the literatures, the local search heuristics is applied to the problem. However, the performance of the local search heuristics is not satisfactory. A constructive heuristics is proposed, named orderly positioning technique (OPT). A rectangle is placed close to an already deployed rectangle. Around the deployed rectangle, only finite configurations are considered. Then the time complexity of OPT is polynomial. The output layout of OPT is often with good performance, nevertheless the positioning order of OPT affects the quality of the layout a lot. Thus, a genetic algorithm (GA) to search for the optimal positioning order is designed. In the GA, the crossover operator and mutation operator are specially designed to keep the offspring having a valid placing order. The proposed algorithm is tested on the benchmarks with large-scale instances. The numerical results show that the proposed algorithm has better performance than the local search heuristics from literatures.
|
|
Received: 17 August 2009
|
|
|
|
|
|
[1] Dyckhoff H. A Typology of Cutting and Packing Problems. European Journal of Operational Research, 1990, 44(1): 145-159
[2] Teng Hongfei, Sun Shoulin, Li Yanzhou. Layout Optimization for the Objects Located within a Rotating Vessel-A Three-Dimensional Packing Problem with Behavioral Constraints. Computers Operations Research, 2001, 28(6): 521-535
[3] Teng Hongfei, Zhang Bao, Liu Jun, et al. Spacecraft Layout Design. Journal of Dalian University of Technology, 2003, 43(1): 86-92 (in Chinese)
(滕弘飞,张 宝,刘 峻,等.航天器布局方案设计.大连理工大学学报, 2003, 43(1): 86-92)
[4] Sun Zhiguo, Teng Hongfei, Liu Zhanwei. Some Scientific Problems about Spacecraft Layout Automatic Design. Natural Science Progress, 2003, 13(11): 16-22 (in Chinese)
(孙治国,滕弘飞,刘占伟.航天器舱自动化布局设计的若干科学问题.自然科学进展, 2003, 13(11): 16-22)
[5] Liu Zhanwei. Human Computer Cooperative Design Method with Application to Layout. Ph.D Dissertation. Dalian, China: Dalian University of Technology. School of Mechanical Engineering, 2006 (in Chinese)
(刘占伟.人机结合的布局设计方法及其应用研究.博士学位论文.大连:大连理工大学.机械工程学院, 2006)
[6] Zhang Bao. Particle Swarm Algorithm and the Application to the Layout Optimization of Satellite Module. Ph.D Dissertation. Dalian, China: Dalian University of Technology. School of Mechanical Engineering, 2006 (in Chinese)
(张 宝.粒子群算法及其在卫星舱布局中的应用研究.博士学位论文.大连:大连理工大学.机械工程学院, 2006)
[7] Zhang Bao, Teng Hangfei, Shi Yanjun. Layout Optimization of Satellite Module Using Soft Computing Techniques. Applied Soft Computing Journal, 2008, 8(1): 507-521
[8] Jacquenot G, Bennis F, Maisonneuve J J, et al. 2D Multi-Objective Placement Algorithm for Free-Form Components. [EB/OL]. [2010-01-29]. http://arxiv.org/PS_cache/arxiv/pdf/0911/0911.5657v1.pdf
[9] Liu Jian, Huang Wenqi. A Modified Differential Evolution Algorithm for Solving Circles Packing Problem with Constraints of Equilibrium. Information and Control, 2006, 35(1): 103-107 (in Chinese)
(刘 建,黄文奇.利用改进的微分进化算法求解带平衡约束的圆形packing问题.信息与控制, 2006, 35(1): 103-107)
[10] Li Ning, Liu Fei, Sun Debao. A Study on the Particle Swarm Optimization with Mutation Operator Constrained Layout Optimization. Chinese Journal of Computers, 2004, 27(7): 897-903 (in Chinese)
(李 宁,刘 飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究.计算机学报, 2004, 27(7): 897-903)
[11] Yu Yang, Zha Jianzhong, Tang Xiaojun. A Mixed Global Optimization Algorithm and Its Application in Packing. Journal of Computer Aided Design Computer Graphics, 2001, 13(9): 846-850 (in Chinese)
(于 洋,查建中,唐晓君.一种混合全局寻优算法及其在布局中的应用.计算机辅助设计与图形学学报, 2001, 13(9): 846-850)
[12] Xiao Renbin, Xu Yichun, Amos M. Two Hybrid Compaction Algorithms for the Layout Optimization Problem. BioSystems, 2007, 90(2): 560-567
[13] Wang Huaiqing, Huang Wenqi, Zhang Quan, et al. An Improved Algorithm for the Packing of Unequal Circles within a Larger Containing Circle. European Journal of Operational Research, 2002, 141(2): 440-453
[14] Liu Dequan, Teng Hongfei. An Improved BL-Algorithm for Genetic Algorithm of the Orthogonal Packing of Rectangles. European Journal of Operational Research, 1999, 112(2): 413-420
[15]Huang Wenqi, Li Yu, Li Chumin, et al. New Heuristics for Packing Unequal Circles into Circular Container. Computers Operations Research, 2006, 33(8): 2125-2142
[16] Xu Yichun, Xiao Renbin. An Ant Colony Algorithm for the Layout Optimization with Equilibrium Constraints. Control and Decision, 2008, 23(1):25-29 (in Chinese)
(徐义春,肖人彬.用蚁群算法求解带平衡约束的圆形布局问题.控制与决策, 2008, 23(1): 25-29)
[17] Xu Yichun, Xiao Renbin, Amos M. A Novel Genetic Algorithm for the Layout Optimization Problem // Proc of the IEEE Congress on Evolutionary Computation. Singapore, Singapore, 2007: 3938-3942
[18] Zhai Jingang, Feng Enmin, Li Zhenming, et al. Non-Overlapped Genetic Algorithm for Layout Problem with Behavioral Constraints. Journal of Dalian University of Technology, 1999, 39(3): 352-357 (in Chinese)
(翟金刚,冯恩民,李振民,等.带性能约束布局问题的不干涉遗传算法.大连理工大学学报, 1999, 39(3): 352-357)
[19] Feng Enmin, Gong Zhaohua, Liu Chongyang, et al. Improved GA for Artificial Satellite Module Layout Problem with Performance Constraints. Journal of Dalian University of Technology, 2005, 45(3): 459-463 (in Chinese)
(冯恩民,宫召华,刘重阳,等.带性能约束的卫星舱布局问题改进遗传算法.大连理工大学学报, 2005, 45(3): 459-463)
[20]Xu Yichun, Xiao Renbin, Amos M. Particle Swarm Algorithm for Weighted Rectangle Placement // Proc of the 3rd International Conference on Natural Computation. Haikou, China, 2007, Ⅳ: 728-732
[21] Holland J. Adaptation in Natural and Artificial Systems. Ann Arbor, USA: University of Michigan Press, 1975 |
|
|
|
2010, Vol. 23 
