一种求解等圆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.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.cmemo.org.cn/CN/10.3969/j.issn.1004-132X.2021.03.008

http://www.cmemo.org.cn/CN/Y2021/V32/I03/305

参考文献

［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]. 中国机械工程, 2024, 35(03): 445-456.
[2]	王洪, 吴立辉, 陈达, 张洁. 基于孪生人工蜂鸟算法的多作业模式半导体封测环节调度[J]. 中国机械工程, 2024, 35(02): 260-267，279.
[3]	陈重远, 陈珂, 刘浩, 欧阳小平, . 外肢体机器人驱动单元低速死区自适应补偿方法[J]. 中国机械工程, 2024, 35(01): 56-66.
[4]	谢阳, 戴逸群, 张超勇, 刘金锋. 融合集成模型与深度学习的机床能耗识别与预测方法[J]. 中国机械工程, 2023, 34(24): 2963-2974.
[5]	张其聪, 姜晨, 叶卉, 申岭鑫, 矫梦蝶. 动压辅助非牛顿流体抛光工具设计与工艺研究[J]. 中国机械工程, 2023, 34(23): 2805-2811，2823.
[6]	于树博, 刘占生, 赵辰. 动力学仿真数据驱动的域自适应智能诊断方法[J]. 中国机械工程, 2023, 34(23): 2832-2841.
[7]	陈剑, 许畅, 徐庭亮, . 基于位错叠加法和改进概率神经网络的离心泵故障诊断方法[J]. 中国机械工程, 2023, 34(23): 2854-2861.
[8]	魏光艳, 叶春明. 分布式多柔性装配作业车间调度问题研究[J]. 中国机械工程, 2023, 34(20): 2442-2455.
[9]	籍永建, 姚利诚, . 机器人铣削加工颤振自适应识别方法研究[J]. 中国机械工程, 2023, 34(18): 2165-2176.
[10]	秦国浩, 张楷, 丁昆, 黄锋飞, 郑庆, 丁国富, . 动态宽卷积残差网络的轴承故障诊断方法[J]. 中国机械工程, 2023, 34(18): 2212-2221.
[11]	胡博, 罗炜韬, 王少飞, 蓝希旺. 基于支持向量机参数优化的高温合金表面缺陷磁异常定量研究[J]. 中国机械工程, 2023, 34(17): 2058-2064.
[12]	梁向檩, 宋豫川, 雷琦, 孙爱红. 考虑工人数量配置优化的柔性作业车间调度问题研究[J]. 中国机械工程, 2023, 34(17): 2065-2076.
[13]	史双元, 熊禾根. 考虑加班的无拖期作业车间调度问题多目标金鹰优化算法研究[J]. 中国机械工程, 2023, 34(17): 2077-2088.
[14]	李西兴, 周文龙, 唐红涛, 吴锐, . 考虑设备预维护的特种车辆白车身试制车间绿色调度优化方法[J]. 中国机械工程, 2023, 34(15): 1832-1847.
[15]	屈力刚, 苏岩, 邢宇飞. 基于SHO-NSGA混合算法的飞机油舱管路自动布局方法[J]. 中国机械工程, 2023, 34(15): 1864-1872.