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

Swarm intelligence labor division algorithm for solving unequal circle packing problem

作　　者：王英聪 张领 WANG Ying-cong;ZHANG Ling(School of Electrical and Information Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China)

机构地区：[1]郑州轻工业大学电气信息工程学院

出　　处：《浙江大学学报（工学版）》2019年第11期2129-2138,共10页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金青年基金资助项目(61702463);河南省科技攻关资助项目(192102210111);郑州轻工业大学博士科研基金资助项目(2017BSJJ004)

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

关 键 词：不等圆Packing问题 群智能劳动分工 动作 刺激 阈值 优化 分配 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP391[自动化与计算机技术—控制科学与工程]