|
|
论文:2017,Vol:35,Issue(6):1033-1039 |
|
|
引用本文： |
|
|
张维, 杨康宁, 张民. 一种求解不等圆Packing问题的改进遗传模拟退火算法[J]. 西北工业大学学报 |
|
|
Zhang Wei, Yang Kangning, Zhang Min. An Improved Genetic Simulated Annealing Algorithm to Solve the Unequal Circle Packing Problem[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 一种求解不等圆Packing问题的改进遗传模拟退火算法 |
|
| 张维, 杨康宁, 张民 |
|
| 西北工业大学 现代设计与集成制造技术教育部重点实验室, 陕西 西安 710072 |
| 摘要: |
| 不等圆Packing问题是求解半径不等的小圆在一个圆形容器内的优良布局，使得圆形容器的半径值最小。该问题属于NP hard的组合优化问题，使用传统的数学方法很难求解，提出了一种解决该问题的改进遗传模拟退火算法，该算法通过计算生成一个合适大小的初始圆形容器来指导初始种群的生成，以减少搜索范围，采用最优保存策略来保证历代的最优解不被破坏，结合了遗传算法全局搜索能力强的优势和模拟退火算法局部搜索能力强的优势，改进了算法的搜索能力。最后通过算例验证，该算法有效地提高了圆形容器的面积利用率，证明了改进遗传模拟退火算法的有效性。 |
| 关键词:
不等圆Packing问题
NP hard
遗传算法
模拟退火算法
最优保存策略
|
|
| An Improved Genetic Simulated Annealing Algorithm to Solve the Unequal Circle Packing Problem |
|
| Zhang Wei, Yang Kangning, Zhang Min |
|
| The Key Laboratory of Contemporary Design and Integrated Manufacturing Technology, Northwestern Polytechnical University, Xi'an 710072, China |
| Abstract: |
| 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. |
| Key words:
unequal circle packing problem
NP hard
genetic algorithm
simulated annealing algorithm
elitist strategy
|
|
| 收稿日期: 2017-02-01
修回日期:
|
| DOI: |
| 基金项目: 西北工业大学基础研究基金（3102015JCS05009）资助 |
| 通讯作者:
Email： |
| 作者简介: 张维(1970-),西北工业大学副教授,主要从事智能制造、布局优化研究。
|
|
| 相关功能 |
|
|
|
|
| 作者相关文章 |
|
| 张维 在本刊中的所有文章 |
| 杨康宁 在本刊中的所有文章 |
| 张民 在本刊中的所有文章 |
|
|
|
|
|
|
|
|
参考文献: |
|
|
[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-144 Liu 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-1084 Lu 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-1558 Kang 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-1125 Chen 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-35 Zhu 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-47 Wang 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-5460 Xue 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-145 Liu 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) |
|
|
|
|
|
|
|
