一种求解不等圆Packing问题的改进遗传模拟退火算法
|
摘要
不等圆Packing问题是求解半径不等的小圆在一个圆形容器内的优良布局,使得圆形容器的半径值最小。该问题属于NP hard的组合优化问题,使用传统的数学方法很难求解,提出了一种解决该问题的改进遗传模拟退火算法,该算法通过计算生成一个合适大小的初始圆形容器来指导初始种群的生成,以减少搜索范围,采用最优保存策略来保证历代的最优解不被破坏,结合了遗传算法全局搜索能力强的优势和模拟退火算法局部搜索能力强的优势,改进了算法的搜索能力。最后通过算例验证,该算法有效地提高了圆形容器的面积利用率,证明了改进遗传模拟退火算法的有效性。
The unequal circle packing problem is putting several unequal circles into a circular container without overlapping,meanwhile minimize the size of the circular container. This problem belongs to NP hard combinatorial optimization,which is difficult to solve by traditional mathematical method. This paper presents an genetic simulated annealing algorithm to solve the unequal circle packing problem. By calculation to generate an appropriate circular container,which is used to produce an initial population,the search range can be reduced. Using elitist strategy to guarantee the optimal solution of the past dynasties can be preserved.Combining the advantage of global search ability of genetic algorithm and the advantage of local search ability of simulated annealing algorithm can improve the search ability of this algorithm. Finally,some calculation examples are presented,the area utilization ration of the circular container is improved effectively,hence the effectiveness of this algorithm is proved.
The unequal circle packing problem is putting several unequal circles into a circular container without overlapping,meanwhile minimize the size of the circular container. This problem belongs to NP hard combinatorial optimization,which is difficult to solve by traditional mathematical method. This paper presents an genetic simulated annealing algorithm to solve the unequal circle packing problem. By calculation to generate an appropriate circular container,which is used to produce an initial population,the search range can be reduced. Using elitist strategy to guarantee the optimal solution of the past dynasties can be preserved.Combining the advantage of global search ability of genetic algorithm and the advantage of local search ability of simulated annealing algorithm can improve the search ability of this algorithm. Finally,some calculation examples are presented,the area utilization ration of the circular container is improved effectively,hence the effectiveness of this algorithm is proved.
引文
[1]Huang Wenqi,Zhan Shuohao.A Quasi-Physical Method of Solving Packing Problems[J].Acta Math Appl Sinica,1979,2(2):176-180
[2]Wang Huaiqing,Huang Wenqi,Zhuang Quan,et al.An Improved Algorithm for the Packing of Unequal Circles within a Lager Containing Circle[J].European Journal of Operational Research,2002,141:440-453
[3]刘朝霞,刘景发.一种求解圆形Packing问题的模拟退火算法[J].计算机工程,2011,37(19):141-144Liu Zhaoxia,Liu Jingfa.Simulated Annealing Algorithm for Solving Circular Packing Problem[J].Computer Engineering,2011,37(19):141-144(in Chinese)
[4]陆一平,查建中.求解装填布局问题的膨胀方法[J].计算机学报,2001,24(10):1077-1084Lu Yiping,Cha Jianzhong.Principle of Expansion Method for Layout Design[J].Chinese Journal of Computers,2001,24(10):1077-1087(in Chinese)
[5]康燕,黄文奇.基于禁忌搜索的启发式算法求解圆形Packing问题[J].计算机研究与发展,2004,41(9):1554-1558Kang Yan,Huang Wenqi.A Heuristic Algorithm Based on Tabu Search for the Disks Packing Problem[J].Journal of Computer Research and Development,2004,41(9):1554-1558(in Chinese)
[6]陈华根,李丽华,许慧平,等.改进的非常快速模拟退火算法[J].同济大学学报:自然科学版,2006,34(8):1121-1125Chen Huagen,Li Lihua,Xu Huiping,et al.Modified Very Fast Simulated Annealing Algorithm[J].Journal of Tongji University:Natural Science,2006,34(8):1121-1125(in Chinese)
[7]朱颢东,钟勇.一种改进的模拟退火算法[J].计算机技术与发展,2009,19(6):32-35Zhu Haodong,Zhong Yong.A Kind of Renewed Simulated Annealing Algorithm[J].Computer Technology and Development,2009,19(6):32-35(in Chinese)
[8]王银年,葛洪伟.求解Tsp问题的改进模拟退火遗传算法[J].计算机工程与应用,2010,46(5):44-47Wang Yinnian,Ge Hongwei.Improved Simulated Annealing Genetic Algorithm for Solving Tsp Problem[J].Computer Engineering and Applications,2010,46(5):44-47(in Chinese)
[9]薛迎春,须文波,孙俊.基于遗传模拟退火混合算法的矩形包络求解[J].计算机工程与设计,28(22):5457-5460Xue Yingchun,Xu Wenbo,Sun Ji.Rectangle-Packing Optimization Utilizing Hybrid Genetic Algorithms[J].Computer Engineering and Design,28(22):5457-5460(in Chinese)
[10]刘怀亮,刘淼.一种混合遗传模拟退火算法及其应用[J].广州大学学报:自然科学版,4(2):141-145Liu Huailiang,Liu Miao.A Mixed Genetic Simulated Annealing Algorithm and Its Application[J].Journal of Guangzhou University:Natural Science Edition,4(2):141-145(in Chinese)
[2]Wang Huaiqing,Huang Wenqi,Zhuang Quan,et al.An Improved Algorithm for the Packing of Unequal Circles within a Lager Containing Circle[J].European Journal of Operational Research,2002,141:440-453
[3]刘朝霞,刘景发.一种求解圆形Packing问题的模拟退火算法[J].计算机工程,2011,37(19):141-144Liu Zhaoxia,Liu Jingfa.Simulated Annealing Algorithm for Solving Circular Packing Problem[J].Computer Engineering,2011,37(19):141-144(in Chinese)
[4]陆一平,查建中.求解装填布局问题的膨胀方法[J].计算机学报,2001,24(10):1077-1084Lu Yiping,Cha Jianzhong.Principle of Expansion Method for Layout Design[J].Chinese Journal of Computers,2001,24(10):1077-1087(in Chinese)
[5]康燕,黄文奇.基于禁忌搜索的启发式算法求解圆形Packing问题[J].计算机研究与发展,2004,41(9):1554-1558Kang Yan,Huang Wenqi.A Heuristic Algorithm Based on Tabu Search for the Disks Packing Problem[J].Journal of Computer Research and Development,2004,41(9):1554-1558(in Chinese)
[6]陈华根,李丽华,许慧平,等.改进的非常快速模拟退火算法[J].同济大学学报:自然科学版,2006,34(8):1121-1125Chen Huagen,Li Lihua,Xu Huiping,et al.Modified Very Fast Simulated Annealing Algorithm[J].Journal of Tongji University:Natural Science,2006,34(8):1121-1125(in Chinese)
[7]朱颢东,钟勇.一种改进的模拟退火算法[J].计算机技术与发展,2009,19(6):32-35Zhu Haodong,Zhong Yong.A Kind of Renewed Simulated Annealing Algorithm[J].Computer Technology and Development,2009,19(6):32-35(in Chinese)
[8]王银年,葛洪伟.求解Tsp问题的改进模拟退火遗传算法[J].计算机工程与应用,2010,46(5):44-47Wang Yinnian,Ge Hongwei.Improved Simulated Annealing Genetic Algorithm for Solving Tsp Problem[J].Computer Engineering and Applications,2010,46(5):44-47(in Chinese)
[9]薛迎春,须文波,孙俊.基于遗传模拟退火混合算法的矩形包络求解[J].计算机工程与设计,28(22):5457-5460Xue Yingchun,Xu Wenbo,Sun Ji.Rectangle-Packing Optimization Utilizing Hybrid Genetic Algorithms[J].Computer Engineering and Design,28(22):5457-5460(in Chinese)
[10]刘怀亮,刘淼.一种混合遗传模拟退火算法及其应用[J].广州大学学报:自然科学版,4(2):141-145Liu Huailiang,Liu Miao.A Mixed Genetic Simulated Annealing Algorithm and Its Application[J].Journal of Guangzhou University:Natural Science Edition,4(2):141-145(in Chinese)