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

A Flexible Position Selection Algorithm for Solving ECPP

针对等圆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.