Abstract: Under the background of satellite module layout design,the circular packing problem with equilibrium constraints was researched and a space allocation method based on ant colony's labor division was proposed.The core idea of the method was to treat the circular packing problem as a space allocation problem,and used the task allocation in ant colony's labor division to achieve the space allocation in the circular packing problem.The problem was converted from a multi-objective constrained optimization problem into a single objective unconstrained optimization problem based on the center translation strategy and the allowing overlap strategy.The mapping relation between ant colony's labor division and the circular packing problem was presented from the perspective of space.The Space Allocation Method (SAM) was put forward by introducing the stimulus-response mechanism of ant colony's labor division.SAM defined four actions for the circular objects as well as stimuli and thresholds,and used the stimulus-response way to solve the problem.The experiments on three sets of benchmarks consisting of thirteen representative instances showed that SAM obtained the first or the second-best container radii and the minimum equilibrium deviations.

Key words: circular packing problem, ant colony's labor division, stimulus-response mechanism, space allocation method, static non-equilibrium constraints

摘要： 针对以卫星舱布局为背景的具有NP难度的全局优化问题——带平衡约束的圆形装填问题,提出基于蚁群劳动分工的空间分配方法。该方法将圆形装填问题看作空间分配问题,并借鉴蚁群劳动分工的任务分配来实现圆形装填问题的空间分配。通过中心平移策略和允许干涉策略,将带平衡约束的圆形装填问题由多目标带约束优化转化为单目标无约束优化。从空间的角度出发,建立了蚁群劳动分工与圆形装填问题之间的映射关系。引入蚁群劳动分工中的刺激—响应原理,提出了空间分配方法。该方法为圆形待布物定义了4个占位动作,并设计了相应的刺激和阈值,进而通过刺激—响应方式完成问题求解。通过3组共13个代表性算例的计算结果及与其他算法的比较表明,所提方法找到的圆形容器半径多为最优或者次优,且静不平衡量的精度最高。

关键词: 圆形装填问题, 蚁群劳动分工, 刺激&mdash, 响应原理, 空间分配方法, 静不平衡约束