一种求解等圆Packing问题的柔性位置选择算法  

A Flexible Position Selection Algorithm for Solving ECPP

作　　者：王英聪 张领 肖人彬[2] WANG Yingcong;ZHANG Ling;XIAO Renbin(School of Electrical and Information Engineering,Zhengzhou University of Light Industry,Zhengzhou,450002;School of Artificial Intelligence and Automation,Huazhong University of Science and Technology,Wuhan,430074)

机构地区：[1]郑州轻工业大学电气信息工程学院,郑州450002 [2]华中科技大学人工智能与自动化学院,武汉430074

出　　处：《中国机械工程》2021年第3期305-313,共9页China Mechanical Engineering

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

摘　　要：针对等圆Packing问题,提出一种基于位置选择的构造法。构造法就是将圆形物体逐个置入容器,在这个过程中需要从多个可行位置中选择一个恰当的位置放置圆形物体。所提算法的核心思想是将这一过程看成位置选择过程,并借鉴群智能劳动分工的任务选择实现圆形物体的位置选择。首先给出了格局和可行位置的定义,在此基础上分析了等圆Packing问题的位置选择特性;接着引入群智能劳动分工中的刺激响应原理,将未布局空间的完整度和已布局空间的紧密度分别看作圆形物体选择位置时的刺激和阈值;最后结合群智能劳动分工中的阈值变化规律,设计了自适应阈值调整策略。通过55个代表性算例的数值计算,验证了提出算法的可行性和有效性。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.

关 键 词：等圆PACKING问题 位置选择 劳动分工 任务选择 群智能 

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