浙江大学学报(工学版)  2019, Vol. 53 Issue (11): 2129-2138    DOI: 10.3785/j.issn.1008-973X.2019.11.010
 计算机技术与控制工程

Swarm intelligence labor division algorithm for solving unequal circle packing problem
Ying-cong WANG(),Ling ZHANG
School of Electrical and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China
 全文: PDF(968 KB)   HTML

Abstract:

The unequal circle packing problem (UCPP) is a non-deterministic polynomial hard (NP-hard) global optimization problem. Aiming at the problem, a novel algorithm based on the idea of space allocation, swarm intelligence labor division (SILD) algorithm, was developed. From the space perspective, the UCPP is to allocate the container space to the circles reasonably and efficiently. The core idea of the proposed algorithm is to abstract the UCPP as a space allocation problem, and use the SILD algorithm to achieve the space allocation in the UCPP. The UCPP problem and the SILD algorithm were analyzed from the allocation perspective, where the actions performed by circles were treated as the tasks performed by individuals. Then, stimuli and thresholds were designed respectively for actions and circles. According to the stimulus-response principle of SILD algorithm, the space allocation in the UCPP was achieved by circles performing appropriate actions. Experiments on engineering instances and benchmark function instances show that the proposed algorithm is effective for the UCPP.

Key words: unequal circle packing problem    swarm intelligence labor division    action    stimulus    threshold    optimization    allocation

 CLC: TP 18

 服务 把本文推荐给朋友 加入引用管理器 E-mail Alert 作者相关文章 王英聪 张领

#### 引用本文:

Ying-cong WANG,Ling ZHANG. Swarm intelligence labor division algorithm for solving unequal circle packing problem. Journal of ZheJiang University (Engineering Science), 2019, 53(11): 2129-2138.

#### 链接本文:

 图 1  不等圆Packing问题简化图 图 2  空间分配格局 表 1  群智能劳动分工和不等圆Packing问题之间的比较 表 2  第1组算例的实验结果比较 图 3  SILDA在第1个测试集上的布局结果图 表 3  第2组算例的实验结果比较 图 4  SILDA在算例CST10-1、CST20-1和CST30-1上的布局结果图 表 4  SILDA在第2组算例上的半径最优值、最差值、平均值和标准差 图 5  SILDA与QP-NS在不同算例上的弹性势能演化对比
 1 黄文奇, 付樟华, 许如初 求解不等圆Packing问题的带全局变换禁忌搜索算法[J]. 中国科学: 信息科学, 2012, 42: 843- 858HUANG Wen-qi, FU Zhang-hua, XU Ru-chu Tabu search algorithm combined with global perturbation for packing arbitrary sized circles into a circular container[J]. Science China: Information Sciences, 2012, 42: 843- 858 2 王鹏, 黄帅, 朱舟全 求解带平衡约束圆形Packing问题的改进人工蜂群算法[J]. 西北工业大学学报, 2014, 32 (2): 240- 245 WANG Peng, HUANG Shuai, ZHU Zhou-quan Exploring improved artificial bee colony algorithm for solving circle packing problem with equilibrium constraints[J]. Journal of Northwestern Polytechnical University, 2014, 32 (2): 240- 245 doi: 10.3969/j.issn.1000-2758.2014.02.016 3 何琨, 杨辰凯, 黄梦龙, 等 动作空间带平衡约束圆形Packing问题的拟物求解算法[J]. 软件学报, 2016, 27 (9): 2218- 2229HE Kun, YANG Chen-kai, HUANG Meng-long, 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 4 张维, 杨康宁, 张民 一种求解不等圆Packing问题的改进遗传模拟退火算法[J]. 西北工业大学学报, 2017, 35 (6): 1033- 1039 ZHANG Wei, YANG Kang-ning, ZHANG Min An improved genetic stimulated annealing algorithm to solve the unequal circle packing problem[J]. Journal of Northwestern Polytechnical University, 2017, 35 (6): 1033- 1039 doi: 10.3969/j.issn.1000-2758.2017.06.015 5 WANG H Q, HUANG W Q, ZHANG Q, et al An improved algorithm for the packing of unequal circles within a larger containing circle[J]. European Journal of Operational Research, 2002, 141 (2): 440- 453 doi: 10.1016/S0377-2217(01)00241-7 6 黄文奇, 付樟华, 许如初 不等圆Packing问题的拟物型邻域搜索算法[J]. 华中科技大学学报: 自然科学版, 2012, 40 (4): 1- 4HUANG Wen-qi, FU Zhang-hua, XU Ru-chu Neighborhood search algorithm associated with quasi-pgysical method for solving unequal circle packing problem[J]. Journal of Huazhong University of Science and Technology: Natural Science Edition, 2012, 40 (4): 1- 4 7 LOPEZ C O, BEASLEY J E Packing unequal circles using formulation space search[J]. Computers and Operations Research, 2013, 40 (5): 1276- 1288 doi: 10.1016/j.cor.2012.11.022 8 LOPEZ C O, BEASLEY J E A formulation space search heuristic for packing unequal circles in a fixed size circular container[J]. European Journal of Operational Research, 2016, 251 (1): 64- 73 doi: 10.1016/j.ejor.2015.10.062 9 LIU J F, XUE S J, LIU Z X, et al An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle[J]. Computers and Industrial Engineering, 2009, 57 (3): 1144- 1149 doi: 10.1016/j.cie.2009.05.010 10 刘景发, 李刚 求解带平衡性能约束的圆形装填问题的吸引盘填充算法[J]. 中国科学: 信息科学, 2010, 40 (3): 423- 432LIU Jing-fa, LI Gang Basin filling algorithm for the circular packing problem with equilibrium behavioral constraints[J]. Science China: Information Sciences, 2010, 40 (3): 423- 432 11 FU Z H, HUANG W Q, LU Z P Iterated tabu search for the circular open dimension problem[J]. European Journal of Operational Research, 2013, 225 (2): 236- 243 doi: 10.1016/j.ejor.2012.10.022 12 ZENG Z Z, YU X G, HE K, et al Iterated Tabu search and variable neighborhood descent for packing unequal circles into a circular container[J]. European Journal of Operational Research, 2016, 250 (2): 615- 627 doi: 10.1016/j.ejor.2015.09.001 13 HUANG W Q, LI Y, LIN C M, et al New heuristics for packing unequal circles into a circular container[J]. Computers and Operations Research, 2006, 33 (8): 2125- 2142 doi: 10.1016/j.cor.2005.01.003 14 LU Z P, HUANG W Q PERM for solving circle packing problem[J]. Computers and Operations Research, 2008, 35 (5): 1742- 1755 doi: 10.1016/j.cor.2006.10.012 15 AKEB H, HIFI M, M'HALLAH R A beam search algorithm for the circular packing problem[J]. Computers and Operations Research, 2009, 36 (5): 1513- 1528 doi: 10.1016/j.cor.2008.02.003 16 AKEB H, HIFI M, M’HALLAH R Adaptive beam search lookahead algorithms for the circular packing problem[J]. International Transactions in Operational Research, 2010, 17 (5): 553- 575 doi: 10.1111/j.1475-3995.2009.00745.x 17 HIFI M, M’HALLAH R A dynamic adaptive local search algorithm for the circular packing problem[J]. European Journal of Operational Research, 2007, 183 (3): 1280- 1294 doi: 10.1016/j.ejor.2005.11.069 18 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 doi: 10.1057/jors.2010.157 19 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 doi: 10.1504/IJBIC.2018.094186 20 肖人彬, 王英聪 面向群体利益分配的蚁群劳动分工建模与仿真[J]. 管理科学学报, 2016, 19 (10): 1- 15 XIAO Ren-bin, WANG Ying-cong Modeling and simulation of ant colony’s labor division for interests allocation of social groups[J]. Journal of Management Sciences in China, 2016, 19 (10): 1- 15 doi: 10.3969/j.issn.1007-9807.2016.10.001 21 WU H S, LI H, XIAO R B, et al Modeling and simulation of dynamic ant colony’s labor division for task allocation of UAV swarm[J]. Physica A, 2018, 491: 127- 141 doi: 10.1016/j.physa.2017.08.094 22 WANG Y C, XIAO R B, WANG H M A flexible labour division approach to the polygon packing problem based on space allocation[J]. International Journal of Production Research, 2017, 55 (11): 3025- 3045 doi: 10.1080/00207543.2016.1229070 23 DUARTE A, WEISSING F J, PEN I, et al An evolutionary perspective on self-organized labor division in social insects[J]. Annual Review of Ecology, Evolution, and Systematics, 2011, 42: 91- 110 doi: 10.1146/annurev-ecolsys-102710-145017 24 BONABEAU E, THERAULAZ G, DENEUBOURG J L Quantitative study 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 doi: 10.1098/rspb.1996.0229 25 THERAULAZ G, BONABEAU E, DENEUBOURG J L 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 doi: 10.1098/rspb.1998.0299 26 刘建, 黄文奇. 求解不等圆装填问题的一种新的连续优化算法[C]// 全国第15届计算机辅助设计与图形学学术会议. 大连: 电子工业出版社, 2008: 611-615.LIU Jian, HUANG Wen-qi. A new continuous optimization algorithm for solving unequal circles packing problem [C]// The 15th China Conference on Computer-Aided Design and Computer Graphics. Dalian: Publishing house of electronics industry, 2008: 611-615.
 [1] 李伟达,王柱,张虹淼,李娟,顾洪. 床式步态康复训练系统机构设计[J]. 浙江大学学报(工学版), 2021, 55(5): 823-830. [2] 赵福林,张通,马光,陈哲,郭创新,张金江. 考虑源-荷波动的电力系统灵活性运行域研究[J]. 浙江大学学报(工学版), 2021, 55(5): 935-947. [3] 高新智,刘作军,张燕,陈玲玲. 基于GWO-SVM的下肢假肢穿戴者骑行相位识别[J]. 浙江大学学报(工学版), 2021, 55(4): 648-657. [4] 熊慧,景昭,刘近贞. 新型经颅磁刺激三层-8字形线圈的结构设计[J]. 浙江大学学报(工学版), 2021, 55(4): 793-800. [5] 于勇,薛静远,戴晟,鲍强伟,赵罡. 机加零件质量预测与工艺参数优化方法[J]. 浙江大学学报(工学版), 2021, 55(3): 441-447. [6] 李伟达,李娟,李想,张虹淼,顾洪,史逸鹏,张浩杰,孙立宁. 欠驱动异构式下肢康复机器人动力学分析及参数优化[J]. 浙江大学学报(工学版), 2021, 55(2): 222-228. [7] 季琳琳,王清威,周豪,郑美妹. 考虑顾客满意度的冷链水果路径优化[J]. 浙江大学学报(工学版), 2021, 55(2): 307-317. [8] 王忠宇,王玲,王艳丽,吴兵. 基于网络变结构优化的大型活动交通拥堵预防方法[J]. 浙江大学学报(工学版), 2021, 55(2): 358-366. [9] 徐利锋,黄海帆,丁维龙,范玉雷. 基于改进DenseNet的水果小目标检测[J]. 浙江大学学报(工学版), 2021, 55(2): 377-385. [10] 陈世达,刘强,韩亮. 降低分布式训练通信的梯度稀疏压缩方法[J]. 浙江大学学报(工学版), 2021, 55(2): 386-394. [11] 马一凡,赵凡宇,王鑫,金仲和. 基于改进指针网络的卫星对地观测任务规划方法[J]. 浙江大学学报(工学版), 2021, 55(2): 395-401. [12] 王进,王向坤,扶建辉,陆国栋,金超超,陈燕智. 重载机器人横梁结构静动态特性分析与优化[J]. 浙江大学学报(工学版), 2021, 55(1): 124-134. [13] 李笑竹,王维庆. 区域综合能源系统两阶段鲁棒博弈优化调度[J]. 浙江大学学报(工学版), 2021, 55(1): 177-188. [14] 楼恺俊,俞峰,夏唐代,马健. 黏土中地下连续墙支护结构的稳定性分析[J]. 浙江大学学报(工学版), 2020, 54(9): 1697-1705. [15] 陈浩,王新杰,王炅,席占稳,曹云. 基于克里金模型的微电热驱动器优化设计[J]. 浙江大学学报(工学版), 2020, 54(8): 1490-1496.