Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2019, Vol. 53 Issue (11): 2129-2138    DOI: 10.3785/j.issn.1008-973X.2019.11.010
计算机技术与控制工程     
面向不等圆Packing问题的群智能劳动分工方法
王英聪(),张领
郑州轻工业大学 电气信息工程学院，河南 郑州 450002
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
摘要：

针对具有非确定性多项式难度（NP-hard）的全局优化问题—不等圆Packing问题（UCPP），基于空间分配思路提出新的求解方法—群智能劳动分工（SILD）方法. 从空间的角度来看，不等圆Packing问题就是将容器空间合理高效地分配给圆形物体. 所提出方法的核心思想在于将不等圆Packing问题抽象为空间分配问题，利用群智能劳动分工的任务分配来实现不等圆Packing问题的空间分配. 从分配的角度对比分析不等圆Packing问题和群智能劳动分工，将圆形物体执行的动作看作个体执行的任务，分别为动作和圆形物体设计环境刺激和响应阈值. 在群智能劳动分工刺激-响应原理作用下，圆形物体选择恰当的动作完成空间分配. 实际工程算例和基准函数算例的测试结果表明，所提出方法是求解不等圆Packing问题的有效算法.
关键词： 不等圆Packing问题;  群智能劳动分工;  动作;  刺激;  阈值;  优化;  分配    
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
收稿日期: 2018-12-25 出版日期: 2019-11-21
CLC:  TP 18  
基金资助: 国家自然科学基金青年基金资助项目（61702463）；河南省科技攻关资助项目（192102210111）；郑州轻工业大学博士科研基金资助项目（2017BSJJ004）
作者简介: 王英聪（1987—），男，讲师，博士，从事群智能、布局优化、复杂系统建模与分析研究. orcid.org/0000-0002-5553-3117. E-mail： ying_cong_wang@163.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
王英聪
张领

引用本文:

王英聪,张领. 面向不等圆Packing问题的群智能劳动分工方法[J]. 浙江大学学报(工学版), 2019, 53(11): 2129-2138.

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.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2019.11.010    或    http://www.zjujournals.com/eng/CN/Y2019/V53/I11/2129

图 1  不等圆Packing问题简化图
图 2  空间分配格局
性质 群智能劳动分工 不等圆Packing问题
分配类型 不同的个体执行族群中不同的任务，属于任务分配 不同的圆饼占据容器内不同的空间，属于空间分配
离散型 族群任务由一系列离散任务组成，个体执行的是任务集合中某个离散的元素，属于离散分配 容器空间是连续的整体，圆饼在容器内所占据的空间是可以连续变化的，属于连续分配
适应性 群智能劳动分工具有适应性，即在动态环境下始终能够实现有效的任务分配 不等圆Packing问题要求算法具有普适性，即对所有算例均表现出较好的求解性能
表 1  群智能劳动分工和不等圆Packing问题之间的比较
算例 GSA[4] IGSA[4] SILDA
Rmin Ra/% Rmin Ra/% Rmin Ra/%
1 9.872 5 51.30 8.312 1 72.37 7.886 9 80.38
2 13.918 5 51.62 11.499 0 75.63 11.035 7 82.11
3 9.116 1 54.15 7.813 7 73.71 7.680 9 76.28
4 13.681 7 48.08 11.190 6 71.87 10.623 6 79.74
5 10.685 4 52.55 8.960 6 74.73 8.610 7 80.92
6 11.425 8 49.79 9.413 2 73.36 8.861 8 82.77
表 2  第1组算例的实验结果比较
图 3  SILDA在第1个测试集上的布局结果图
算例 TS/NP[18] GP-TS[1] QP-NS[6] ITS-VND[12] SILDA
Rmin t/s Rmin t/s Rmin t/s Rmin t/s Rmin t/s
CST5-1 1.751 552 1 270 1.751 600 1 1.751 552 <1 1.751 600 100 000 1.751 600 <1
CST6-1 1.810 077 3 169 1.810 800 1 1.810 077 <1 1.810 100 100 000 1.810 100 <1
CST7-1 1.838 724 5 152 1.838 800 1 1.838 724 <1 1.838 800 100 000 1.838 800 <1
CST8-1 1.864 532 8 428 1.858 500 1 1.858 401 <1 1.858 500 100 000 1.858 500 <1
CST9-1 1.878 813 10 489 1.878 900 1 1.878 813 <1 1.878 900 100 000 1.878 900 <1
CST10-1 1.920 960 14 739 1.913 500 3 1.913 436 2 1.913 500 100 000 1.913 500 <1
CST12-1 1.959 311 10 919 1.949 900 37 1.949 824 5 1.949 900 100 000 1.949 900 12
CST14-1 2.006 005 14 885 1.986 300 54 1.983 071 12 1.980 300 100 000 1.981 000 35
CST16-1 2.031 021 22 418 2.008 400 13 2.008 386 31 2.004 600 100 000 2.004 700 58
CST18-1 2.065 764 25 499 2.039 700 70 2.048 725 14 2.028 100 100 000 2.032 700 43
CST20-1 2.083 187 38 164 2.071 600 93 2.074 201 35 2.051 500 100 000 2.060 200 65
CST25-1 2.143 192 30 929 2.123 600 37 2.124 727 22 2.097 600 100 000 2.112 400 44
CST30-1 2.188 324 63 970 2.167 900 72 2.170 038 10 2.140 000 100 000 2.156 800 83
CST35-1 2.220 271 90 387 2.203 700 367 2.209 698 16 2.171 900 100 000 2.194 100 97
表 3  第2组算例的实验结果比较
图 4  SILDA在算例CST10-1、CST20-1和CST30-1上的布局结果图
算例 Rmin
最优值 最差值 平均值 标准差
CST5-1 1.751 6 1.760 0 1.755 8 0.004 2
CST6-1 1.810 1 1.837 2 1.826 2 0.011 6
CST7-1 1.838 8 1.889 9 1.852 6 0.019 9
CST8-1 1.858 5 1.890 0 1.870 6 0.010 6
CST9-1 1.878 9 1.890 1 1.885 0 0.005 7
CST10-1 1.913 5 2.000 0 1.972 5 0.038 9
CST12-1 1.949 9 2.123 9 2.014 0 0.082 7
CST14-1 1.981 0 2.098 8 2.039 9 0.051 6
CST16-1 2.004 7 2.099 2 2.058 1 0.042 7
CST18-1 2.032 7 2.139 8 2.098 5 0.044 4
CST20-1 2.060 2 2.157 4 2.134 0 0.030 6
CST25-1 2.112 4 2.180 3 2.161 8 0.025 2
CST30-1 2.156 8 2.230 5 2.203 2 0.028 8
CST35-1 2.194 1 2.260 3 2.239 8 0.022 6
表 4  SILDA在第2组算例上的半径最优值、最差值、平均值和标准差
图 5  SILDA与QP-NS在不同算例上的弹性势能演化对比
1 黄文奇, 付樟华, 许如初 求解不等圆Packing问题的带全局变换禁忌搜索算法[J]. 中国科学: 信息科学, 2012, 42: 843- 858
HUANG 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- 2229
HE 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- 4
HUANG 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- 432
LIU 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.