一种求解等圆Packing问题的柔性位置选择算法

doi:10.3969/j.issn.1004-132X.2021.03.008

摘要/Abstract

摘要： 针对等圆Packing问题，提出一种基于位置选择的构造法。构造法就是将圆形物体逐个置入容器，在这个过程中需要从多个可行位置中选择一个恰当的位置放置圆形物体。所提算法的核心思想是将这一过程看成位置选择过程，并借鉴群智能劳动分工的任务选择实现圆形物体的位置选择。首先给出了格局和可行位置的定义，在此基础上分析了等圆Packing问题的位置选择特性；接着引入群智能劳动分工中的刺激响应原理，将未布局空间的完整度和已布局空间的紧密度分别看作圆形物体选择位置时的刺激和阈值；最后结合群智能劳动分工中的阈值变化规律，设计了自适应阈值调整策略。通过55个代表性算例的数值计算，验证了提出算法的可行性和有效性。

关键词: 等圆Packing问题, 位置选择, 劳动分工, 任务选择, 群智能

Abstract: A construction algorithm was proposed for ECPP based on position selection herein. The construction algorithms built solutions by placing circles one by one into a container. It is necessary to select an appropriate position from multiple feasible positions to place each circle. The key idea of the proposed algorithm was to regard this process as a position selection process, and to use the task selection in swarm intelligence labor division to achieve the position selection in ECPP. Based on the definition of configuration and feasible position, the position selection characteristics of the ECPP were analyzed. By introducing the stimulus-response principle of swarm intelligence labor division, the integrity of the unoccupied spaces was considered as stimulus and the tightness of the occupied space was treated as threshold. An adaptive threshold adjustment strategy was designed by combining with the change rules of threshold in swarm intelligence labor division. The results of 55 representative instances show that the proposed algorithm is feasible and efficient.

Key words: equal circle packing problem(ECPP), position selection, labor division, task selection, swarm intelligence

中图分类号:

王英聪1;张领1;肖人彬2. 一种求解等圆Packing问题的柔性位置选择算法[J]. 中国机械工程, DOI: 10.3969/j.issn.1004-132X.2021.03.008.

WANG Yingcong1;ZHANG Ling1;XIAO Renbin2. A Flexible Position Selection Algorithm for Solving ECPP[J]. China Mechanical Engineering, DOI: 10.3969/j.issn.1004-132X.2021.03.008.

参考文献

［1］钱志勤, 滕弘飞. 复杂布局设计问题的算法［J］. 中国机械工程, 2002, 13(8)：696-699.
QIAN Zhiqin, TENG Hongfei. Algorithm of Complex Layout Design Problems［J］. China Mechanical Engineering, 2002, 13(8)：696-699.
［2］刘昕, 余隋怀, 王淑侠, 等. 用户决策驱动的乘用车舱改进PSO布局优化模型［J］. 中国机械工程, 2016, 27(1)：114-121.
LIU Xin, YU Suihuai, WANG Shuxia, et al. Improved PSO Layout Optimization Model for Saloon Cabin Driven by Users Decision Making［J］. China Mechanical Engineering, 2016, 27(1)：114-121.
［3］LIU J, JIANG Y, LI G, et al. Heuristic-based Energy Landscape Paving for the Circular Packing Problem with Performance Constraints of Equilibrium［J］. Physica A：Statistical Mechanics and Its Applications, 2015, 431：166-174.
［4］青巧, 吴红乐, 管卫利. 圆形件卷材排样问题的启发式优化算法［J］. 锻压技术, 2018, 43(4)：175-179.
QING Qiao, WU Hongle, GUAN Weili. Heuristic Optimization Algorithms of Coiled Material Layout for Circular Parts ［J］. Forging & Stamping Technology, 2018, 43(4)：175-179.
［5］EKANAYAKE D B, RANPATIDEWAGE M M, LAFOUNTAIN D J. Optimal Packings for Filled Rings of Circles［J］. Applications of Mathematics, 2020, 65(1)：1-22.
［6］HUANG W Q, LI Y, LIN C, et al. New Heuristics for Packing Unequal Circles into a Circular Container［J］. Computers & Operations Research, 2006, 33 (8):2125-2142.
［7］LYU Z P, HUANG W Q. PERM for Solving Circle Packing Problem［J］. Computers & Operations Research, 2008, 35(5)：1742-1755.
［8］黎自强, 田茁君, 王奕首, 等. 求解平衡约束圆形Packing问题的快速启发式并行蚁群算法［J］. 计算机研究与发展, 2012, 49(9)：1899-1909.
LI Ziqiang, TIAN Zhuojun, WANG Yishou, et al. A Fast Heuristic Parallel Ant Colony Algorithms for Circles Packing Problem with the Equilibrium Constraints［J］. Journal of Computer Research and Development, 2012, 49(9)：1899-1909.
［9］AL-MUDAHKA I, HIFI M, M'HALLAH R. Packing Circles in the Smallest Circle：an Adaptive Hybrid Algorithm［J］. Journal of the Operational Research Society, 2011, 62(11)：1917-1930.
［10］FEKETE S P, von HOVELING S, SCHEFFER C, et al. Online Circle Packing［C］∥ Workshop on Algorithms and Data Structures. Edmonton, 2019：366-379.
［11］LINTZMAYER C N, MIYAZAWA F K, XAVIER EC, et al. Online Circle and Sphere Packing［J］. Theoretical Computer Science, 2019, 776：75-94.
［12］黄文奇, 付樟华, 许如初. 求解不等圆 Packing 问题的带全局变换禁忌搜索算法［J］. 中国科学：信息科学, 2012, 42：843-858.
HUANG Wenqi, FU Zhanghua, XU Ruchu. Tabu Search Algorithm Combined with Global Perturbation for Packing Arbitrary Sized Circles into a Circular Container［J］. Scientia Sinica Informationis, 2012, 42：843-858.
［13］何琨, 杨辰凯, 黄梦龙, 等. 动作空间带平衡约束圆形Packing问题的拟物求解算法［J］. 软件学报, 2016, 27(9)：2218-2229.
HE Kun, YANG Chenkai, HUANG Menglong, et al. Quasi-physical Algorithm Based on Action Space for Solving the Circles Packing Problem with Equilibrium Constraints［J］. Journal of Software, 2016, 27(9)：2218-2229.
［14］ZENG Z Z, YU X G, HE K, et al. Iterated Tabu Search and Variable Neighborhood Descent forPacking Unequal Circles into a Circular Container［J］. European Journal of Operational Research, 2016, 250(2)：615-627.
［15］张维, 杨康宁, 张民. 一种求解不等圆Packing问题的改进遗传模拟退火算法［J］. 西北工业大学学报, 2017, 35(6)：1033-1039.
ZHANG Wei, YANG Kangning, ZHANG Min. An Improved Genetic Simulated Annealing Algorithm to Solve the Unequal Circle Packing Problem［J］. Journal of Northwestern Polytechnical University, 2017, 35(6)：1033-1039.
［16］王英聪, 肖人彬. 基于蚁群劳动分工的空间分配方法求解带平衡约束的圆形装填问题［J］. 计算机集成制造系统, 2019, 25(2)：359-372.
WANG Yingcong, XIAO Renbin. Space Allocation Method Based on Ant Colonys Labor Division for Circular Packing Problem with Equilibrium Constraints［J］. Computer Integrated Manufacturing Systems, 2019, 25(2)：359-372.
［17］LPEZC O, BEASLEY J E. Packing a Fixed Number of Identical Circles in a Circular Container with Circular Prohibited Areas［J］. Optimization Letters, 2019, 13(7)：1449-1468.
［18］CHEN M, TANG X Y, SONG T, et al. Greedyheuristic Algorithm for Packing Equal Circles into a Circular Container ［J］. Computers & Industrial Engineering, 2018, 119：114-120.
［19］黄文奇, 叶涛. 求解等圆Packing 问题的拟物型全局优化算法［J］. 中国科学：信息科学, 2011, 41(6)：686-693.
HUANG Wenqi, YE Tao. Quasi-physical Global Optimization Method for Solving the Equal Circle Packing Problem［J］. Scientia Sinica Informationis, 2011, 41(6)：686-693.
［20］HE K, YE H, WANG Z L, et al. An Efficient Quasi-physical Quasi-human Algorithm for Packing Equal Circles in a Circular Container［J］. Computers and Operations Research, 2018, 92：26-36.
［21］XIAO R B, WANG Y C. Labour Division in Swarm Intelligence for Allocation Problems：a Survey［J］. International Journal of Bio-inspired Computation, 2018, 12(2)：71-86.
［22］BONABEAU E, THERAULAZ G, DENEUBOURG J L. QuantitativeStudy of the Fixed Threshold Model for the Regulation of Division of Labour in Insect Societies［J］. Proceedings of the Royal Society of London. Series B：Biological Sciences, 1996, 263(1376)：1565-1569.
［23］THERAULAZ G, BONABEAU E, DENEUBOURG J N. Response Threshold Reinforcements and Division of Labour in Insect Societies［J］. Proceedings of the Royal Society of London. Series B：Biological Sciences, 1998, 265(1393)：327-332.
［24］IMAMICHI T, YAGIURA M, NAGAMOCHI H. An Iterated Local Search Algorithm Based on Nonlinear Programming for the Irregular Strip Packing Problem［J］. Discrete Optimization, 2009, 6(4)：345-361.

[1]	李西兴, 杨道明, 李鑫, 吴锐, . 基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法[J]. 中国机械工程, 2021, 32(08): 938-950，986.
[2]	李成洋. [设计与优化]市域铁路旅客提升设备设计与运行安全保障技术[J]. 中国机械工程, 2021, 32(04): 499-503.
[3]	滕伟;韩琛;赵立;武鑫;柳亦兵. 基于改进粒子滤波的重型燃气轮机跳机故障预测[J]. 中国机械工程, 2021, 32(02): 188-194.
[4]	黄云;甲花索朗;肖贵坚. 镍铝青铜合金仿生表面的砂带磨削及其降噪特性[J]. 中国机械工程, 2020, 31(20): 2497-2504,2511.
[5]	王均山;陈超;石明友;曹静. 悬浮式球转子压电作动器的设计及实验研究[J]. 中国机械工程, 2020, 31(17): 2064-2070.
[6]	刘黎明;陈亮;宋刚. 高强钢低功率脉冲激光诱导熔化极活性气体保护电弧仰焊成形[J]. 中国机械工程, 2020, 31(17): 2137-2141.
[7]	何彦1;凌俊杰1;王禹林2;李育锋1;吴鹏程1;肖圳1. 基于长短时记忆卷积神经网络的刀具磨损在线监测模型[J]. 中国机械工程, 2020, 31(16): 1959-1967.
[8]	江勇;张伟;刘晓源;金博丕. 双电机消隙技术在串联机械臂中的仿真与应用[J]. 中国机械工程, 2020, 31(16): 1991-1997.
[9]	张文旭, 肖人彬, 林文广. 基于产品性能词典的评论数据驱动客户需求模型研究[J]. 中国机械工程, 2020, 31(15): 1866-1876.
[10]	余石龙, 鲍劲松, 李婕, 张启华. 基于误差注意力的晶圆制造数据异常检测[J]. 中国机械工程, 2020, 31(14): 1686-1692.
[11]	宋庭新, 李轲. 基于OPC UA的智能制造车间数据通信技术及应用[J]. 中国机械工程, 2020, 31(14): 1693-1699.
[12]	李敏波, 许鑫星, 李强, 韩乐. 基于JSON文档结构的工业大数据多维分析方法[J]. 中国机械工程, 2020, 31(14): 1700-1707,1716.
[13]	耿凯峰1,2;叶春明1;吴绍兴2;刘丽2. 分时电价下多目标绿色可重入混合流水车间调度[J]. 中国机械工程, 2020, 31(12): 1469-1480.
[14]	詹欣隆1;张超勇1;孟磊磊2;洪辉1. 基于改进引力搜索算法的铣削加工参数低碳建模及优化[J]. 中国机械工程, 2020, 31(12): 1481-1491.
[15]	陈龙;朱颖;徐力;张高朋. 基于权重灵敏度分析的结构形状等几何优化方法[J]. 中国机械工程, 2020, 31(11): 1306-1314.