Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2019, Vol. 53 Issue (11): 2129-2138    DOI: 10.3785/j.issn.1008-973X.2019.11.010
Computer Technology and Control Engineering     
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
Download: HTML     PDF(968KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 25 December 2018      Published: 21 November 2019
CLC:  TP 18  
  TP 391  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Ying-cong WANG
Ling ZHANG
Cite this article:

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.

URL:

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


面向不等圆Packing问题的群智能劳动分工方法

针对具有非确定性多项式难度（NP-hard）的全局优化问题—不等圆Packing问题（UCPP），基于空间分配思路提出新的求解方法—群智能劳动分工（SILD）方法. 从空间的角度来看，不等圆Packing问题就是将容器空间合理高效地分配给圆形物体. 所提出方法的核心思想在于将不等圆Packing问题抽象为空间分配问题，利用群智能劳动分工的任务分配来实现不等圆Packing问题的空间分配. 从分配的角度对比分析不等圆Packing问题和群智能劳动分工，将圆形物体执行的动作看作个体执行的任务，分别为动作和圆形物体设计环境刺激和响应阈值. 在群智能劳动分工刺激-响应原理作用下，圆形物体选择恰当的动作完成空间分配. 实际工程算例和基准函数算例的测试结果表明，所提出方法是求解不等圆Packing问题的有效算法.


关键词： 不等圆Packing问题,  群智能劳动分工,  动作,  刺激,  阈值,  优化,  分配 
Fig.1 Simplified schematic of unequal circle packing problem
Fig.2 Space allocation configuration
性质 群智能劳动分工 不等圆Packing问题
分配类型 不同的个体执行族群中不同的任务，属于任务分配 不同的圆饼占据容器内不同的空间，属于空间分配
离散型 族群任务由一系列离散任务组成，个体执行的是任务集合中某个离散的元素，属于离散分配 容器空间是连续的整体，圆饼在容器内所占据的空间是可以连续变化的，属于连续分配
适应性 群智能劳动分工具有适应性，即在动态环境下始终能够实现有效的任务分配 不等圆Packing问题要求算法具有普适性，即对所有算例均表现出较好的求解性能
Tab.1 Comparison between swarm intelligence labor division and unequal circle packing problem
算例 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
Tab.2 Comparison of computing results for first set of instances
Fig.3 Packing layouts found by SILDA on first set of instances
算例 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
Tab.3 Comparison of computing results of second set of instances
Fig.4 Packing layouts found by SILDA on instances CST10-1, CST20-1 and 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
Tab.4 Best value，worst value，average value and standard deviation of radius on second set of instances found by SILDA
Fig.5 Comparison of elastic potential energy evolution process for SILDA and QP-NS on different instances
[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] Wei-da LI,Zhu WANG,Hong-miao ZHANG,Juan LI,Hong GU. Mechanical design of bed-type gait rehabilitation training system[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(5): 823-830.
[2] Fu-lin ZHAO,Tong ZHANG,Guang MA,Zhe CHEN,Chuang-xin GUO,Jin-jiang ZHANG. Study on flexible operation region of power system considering source and load fluctuation[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(5): 935-947.
[3] Hua-mei YANG,Jing LI,Xi-hua DU. Pyrolysis and product analysis of lignin monomer model compounds[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(5): 976-983.
[4] Ding-hua HU,Shi-yu LIU. Numerical study on dynamic behaviors of Al2O3 nanofluid droplet impacting on solid wall[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(5): 991-998.
[5] Jun CAI,Gang ZHAO,Yong YU,Qiang-wei BAO,Sheng DAI. A rapid reconstruction method of simulation model based on point cloud and design model[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(5): 905-916.
[6] Xin-zhi GAO,Zuo-jun LIU,Yan ZHANG,Ling-ling CHEN. Bicycle riding phase recognition of lower limb amputees based on GWO-SVM[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(4): 648-657.
[7] Ren-qiang XI,Xiu-li DU,Pi-guang WANG,Cheng-shun XU,Kun XU. Integrated seismic response of monopile supported offshore wind turbines[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(4): 757-766.
[8] Yong YU,Jing-yuan XUE,Sheng DAI,Qiang-wei BAO,Gang ZHAO. Quality prediction and process parameter optimization method for machining parts[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(3): 441-447.
[9] Fang LIU,Zhen WANG,Rui-di LIU,Kai WANG. Short-term forecasting method of wind power generation based on BP neural network with combined loss function[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(3): 594-600.
[10] Wei-da LI,Juan LI,Xiang LI,Hong-miao ZHANG,Hong GU,Yi-peng SHI,Hao-jie ZHANG,Li-ning SUN. Dynamic analysis and parameter optimization of under-actuated heterogeneous lower limb rehabilitation robot[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 222-228.
[11] De-bin LIU,Dan WANG,Bai CHEN,Yao-yao WANG,Li-yao SONG. A survey of supernumerary robotic limbs[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 251-258.
[12] Lin-lin JI,Qing-wei WANG,Hao ZHOU,Mei-mei ZHENG. Optimization of cold chain fruit path considering customer satisfaction[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 307-317.
[13] Zhong-yu WANG,Ling WANG,Yan-li WANG,Bing WU. Traffic congestion prevention method during large-scale special events based on variable network topology optimization[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 358-366.
[14] Shi-da CHEN,Qiang LIU,Liang HAN. Gradient sparsification compression approach to reducing communication in distributed training[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 386-394.
[15] Yi-fan MA,Fan-yu ZHAO,Xin WANG,Zhong-he JIN. Satellite earth observation task planning method based on improved pointer networks[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 395-401.