Abstract: The idea of sequencing and positioning was applied to solve the circle packing problem,and the positioning of circles in the container was regarded as a position selection problem.By using the task selection in ant colony's labor division,the position selection in the positioning of circles was achieved,and an ant colony labor division algorithm was proposed.The selection characteristics of the circle packing problem were analyzed under the sequencing and positioning solution framework.The mapping relations between task selection and position selection were established.The positioning algorithm was presented by introducing the stimulus-response mechanism of ant colony's labor division.The sequencing and positioning solution for the circle packing problem was achieved by combining ant colony optimization algorithm,which was designed to search the placement order.The results of two test sets showed that the proposed algorithm was feasible and efficient.

Key words: circle packing problem, position selection, ant colony's labor division, task selection, ant colony optimization

摘要： 采用定序定位的思路求解圆形布局问题,将确定圆形物体在容器内摆放位置的定位过程看作位置选择问题。借鉴蚁群劳动分工的任务选择实现圆形布局定位过程中的位置选择,提出一种蚁群劳动分工算法。首先分析了定序定位求解框架下圆形布局问题的选择特性;然后建立了任务选择与位置选择之间的映射关系;接着引入蚁群劳动分工中的刺激-响应原理,提出相应的定位算法;最后结合蚁群算法优化放置顺序,完成对圆形布局问题的定序定位求解。通过两组国际公开测试集的数值计算,验证了所提算法的可行性和有效性。

关键词: 圆形布局问题, 位置选择, 蚁群劳动分工, 任务选择, 蚁群优化