一种基于蚁群劳动分工的卫星舱布局方法

摘要

本发明提出了一种基于蚁群劳动分工的卫星舱布局方法，步骤为：建立卫星舱布局的数学模型，将卫星舱布局由多目标带约束优化问题转化为单目标无约束优化问题；建立蚁群劳动分工与卫星舱布局之间的映射关系，提出基于蚁群劳动分工的布局方法；设计固定、平移、交换和跳跃四种占位动作，定义环境刺激和响应阈值，根据蚁群劳动分工的刺激‑响应原理设计待布物的空间位置占据方式；结合刺激‑响应原理和卫星舱布局的特点，设计环境刺激和响应阈值的更新规则、并行占位动作执行方式、不同格局变换策略下的格局更新准则。本发明继承了蚁群劳动分工的柔性特点，布局方案利用率高，完全满足卫星舱的平衡性能约束，可推广应用于其他装填、下料等布局问题。

说明书

技术领域

本发明涉及航天器布局设计的技术领域，尤其涉及一种基于蚁群劳动分工的卫星舱布局方法，适用于带平衡性能约束的圆形装填问题的布局。

背景技术

日常生活和生产中存在大量的布局问题，如在货物运输、机械设计、大规模集成电路设计等领域，需要将一些小型的对象，如货品、零件、集成块等，装入一个大的容器，如车厢、包装箱或电路板等中，要求装载的对象数目最多。这种高利用率具有广阔的工程背景，相关应用涉及到140多个行业。在实际生产中，合理的布局方案可有效节省材料，降低生产成本。以卫星舱布局设计为例，布局方案质量的优劣将直接影响到卫星在轨运行时的动力学性能、控制性能、使用寿命甚至总体方案的成败。

布局问题的一般描述为：给定一个布局空间和若干布局物体，按照一定的要求，将布局物体最优地排放在布局空间中。称布局物体为待布物，布局空间为容器，典型的布局问题通常要求待布物之间、待布物与容器之间无干涉，并尽量提高容器利用率。除了上述无干涉约束，卫星舱布局还要求整个系统的静不平衡量尽可能小，以减小卫星舱自旋时产生的磨损、震动、发热、噪音等。从计算复杂性理论看，卫星舱布局属于NP完全问题。对于这类问题，目前缺乏高效寻找最优解的算法，现有的优化方法以随机算法和启发式算法为主。随机算法收敛速度慢，而启发式算法普适性不强，且二者都容易陷入局部最优。

任何固体材料都占据着一定的空间。从空间的角度来看，一个卫星舱布局方案就是不同的设备在卫星舱容器内占据着不同的空间。因此，卫星舱布局可以看成是一个空间分配问题，即将卫星舱容器空间合理有效地分配给给定的设备。在蚁群中，不同的个体执行不同的任务，这种现象叫做劳动分工。蚁群劳动分工的显著特点是任务分配柔性，即在动态环境下能以自组织的方式快速有效地实现任务分配，从而满足族群需要，是蚁群生态成功的重要保障。蚁群劳动分工的任务分配对卫星舱布局的空间分配求解具有启发意义。更重要的是，蚁群劳动分工的快速、柔性、高效的分配方式能够有效克服已有方法收敛速度慢、普适性不强和容易陷入局部最优的不足。

发明内容

针对现有优化方法收敛速度慢，适应性差，容易陷入局部最优的技术问题，本发明提出一种基于蚁群劳动分工的卫星舱布局方法，将卫星舱布局抽象为空间分配问题，并借鉴蚁群劳动分工的任务分配来实现卫星舱布局的空间分配，该方法继承了蚁群劳动分工的柔性特点，在动态环境下得到的布局方案利用率高，且完全满足卫星舱的平衡性能约束，并可推广应用于其他装填、下料等布局问题。

为了达到上述目的，本发明的技术方案是这样实现的：一种基于蚁群劳动分工的卫星舱布局方法，其步骤如下：

步骤一：在传统布局问题数学模型的基础上，建立卫星舱布局的数学模型，通过平移策略和干涉策略，将卫星舱布局由多目标带约束优化问题转化为单目标无约束优化问题；

步骤二：从空间的角度出发，建立蚁群劳动分工与卫星舱布局之间的映射关系，将卫星舱布局抽象为空间分配问题，提出基于蚁群劳动分工的布局方法；

步骤三：设计固定、平移、交换和跳跃四种占位动作，根据占位动作的特点定义环境刺激，根据待布物的特点定义响应阈值，根据蚁群劳动分工的刺激-响应原理设计待布物的空间位置占据方式；结合刺激-响应原理和卫星舱布局的特点，设计环境刺激和响应阈值的更新规则、并行占位动作执行方式、不同格局变换策略下的格局更新准则；

步骤四：初始化算法参数，随机生成初始格局；

步骤五：采用步骤二得到的基于蚁群劳动分工的布局方法求解卫星舱布局问题，更新容器半径，循环求解过程，直到满足停止条件；

步骤六：输出最终布局结果，包括容器半径、待布物坐标和布局结果图。

所述步骤一中卫星舱布局的单目标无约束优化问题的建立方法为：设卫星舱为圆形的容器C₀，待布物C_i为n个质量分布均匀的圆柱体，i∈{1,2,…,n}，容器C₀的初始半径为R，容器C₀的中心为坐标原点(0,0)，待布物C_i的半径为r_i、质量为m_i、质心坐标为(x_i,y_i)，则待布物的布局为

根据卫星舱布局要求，建立如下多目标带约束数学模型：

且

其中，R(X)指当前布局X下所有待布物的最小外包络圆半径，J(X)指当前布局X下整个系统的静不平衡量；

平移策略：将卫星舱系统的质心平移到容器C₀的中心：待布物C_i做相应的平移：此时，则多目标带约束数学模型转化为单目标带约束数学模型：

且

根据干涉策略，将单目标带约束数学模型转化为固定容器半径R下，系统的弹性势能最小化问题，建立如下单目标无约束数学模型：找到最优解后缩小容器半径R继续搜索，可逐渐逼近最小半径，得到合法的布局；

其中，E_i表示待布物C_i的挤压弹性势能，为待布物C_i与待布物C_j之间的干涉量；为待布物C_i与容器C₀之间的干涉量。

所述步骤二中将卫星舱布局抽象为空间分配问题的方法为：卫星舱布局视为将容器空间合理有效地分配给给定的待布物，每一种空间分配模式都对应待布物的一种放置方式，也就是卫星舱布局的一个解；在蚁群劳动分工中，蚂蚁选择哺育、筑巢、防御或觅食的行为完成任务分配，在卫星舱布局中，待布物选择固定、平移、交换或跳跃的动作完成空间分配；蚂蚁在劳动分工机制下选择恰当的行为完成任务分配，将待布物看作蚂蚁，将动作看作行为，结合卫星舱布局的特点，设计定制化的劳动分工机制，即可实现卫星舱布局的空间分配。

所述基于蚁群劳动分工的布局方法的步骤为：

(3.1)根据卫星舱布局的特点定义占位动作：对待布物C_i而言，执行固定动作指保持其当前位置不变，执行平移动作指在其当前位置附近移动，执行交换动作指与另一随机选择的待布物C_j互换位置，执行跳跃动作指将其重新放置到容器内的其他位置处；即：设当前格局为则

执行固定动作后的格局为

执行平移动作后的格局为其中，为平移向量；

执行交换动作后的格局为其中，为与待布物C_i相似的待布物C_j的位置；

执行跳跃动作后的格局为其中，为当前格局中的一个空位点；

(3.2)根据占位动作的特点定义环境刺激：固定动作的环境刺激为平移、交换和跳跃三种动作的环境刺激为：其中，E_i表示待布物C_i的挤压弹性势能，f₁表示势能-刺激转换系数；

(3.3)根据待布物的特点定义响应阈值：待布物位置的优劣通过自身的弹性势能来度量，待布物C_i对应固定动作的响应阈值为：待布物C_i对应平移、交换和跳跃三种动作的响应阈值为：其中，f₂表示势能-阈值转换系数；

(3.4)根据蚁群劳动分工的刺激-响应原理设计待布物的空间位置占据方式：待布物C_i执行固定动作的概率为：其中，S_固定表示固定动作的环境刺激，表示固定动作的响应阈值；

待布物C_i执行平移动作的概率为：其中，S_平移表示平移动作的环境刺激，表示平移动作的响应阈值；

待布物C_i执行交换动作的概率为：其中，S_交换表示交换动作的环境刺激，表示交换动作的响应阈值；

待布物C_i执行跳跃动作的概率为：其中，S_跳跃表示跳跃动作的环境刺激，表示跳跃动作的响应阈值。

所述步骤(3.1)中待布物C_i的平移向量的求解方法为：考虑到最小化容器半径的目标要求，平移时应朝向容器的中心，可通过容器中心吸引待布物来实现；考虑到待布物之间、待布物与容器之间的非干涉约束，平移时应远离容器内的拥挤区域，可通过受挤压的待布物排斥其他待布物来实现：容器C₀对待布物C_i的吸引力为待布物C_j对圆形待布物C_i的排斥力为其中，α，β分别表示引力系数和斥力系数，E_j为待布物C_j的弹性势能，E为整个布局的弹性势能，v_ji＝(x_i-x_j,y_i-y_j)为待布物C_j指向待布物C_i的向量，则待布物C_i的平移向量为

所述步骤(3.1)中交换动作只允许发生在半径相近的圆形待布物之间，相近圆形待布物的判断方法为：将所有圆形待布物按半径大小排序，令Type_i表示圆形待布物C_i的类型；若|Type_i－Type_j|≤L，则待布物C_i和圆形待布物C_j的半径相近，其中，L表示相似性范围；

所述步骤(3.1)中跳跃动作中空位点的确定方法为：在容器C₀内随机生成一个点，若该点不在任一圆形待布物内，则其为一个空位点；将圆形容器C₀四等分，在每一个区域随机产生20个空位点，待布物C_i最终将跳跃到干涉量最小的空位点处。

所述步骤(3.3)中，考虑到平移、交换、跳跃的动作方式以及对布局造成的变动程度不同，对响应阈值做进一步区分：根据半径将圆形待布物分为大、中、小三个类型，其中较大圆形待布物的半径大于r_max为最大圆形待布物的半径，较小圆形待布物的半径小于其余的为半径适中的圆形待布物；

若待布物C_i为半径大于的较大圆形待布物，响应阈值分别为

若待布物C_i为半径小于大于的适中圆形待布物，响应阈值分别为

若待布物C_i为半径小于的较小圆形待布物，则响应阈值

所述设计环境刺激和响应阈值的更新规则方法为：在蚁群中，在学习因素作用下，当个体执行某一任务时，与之对应的响应阈值降低；在遗忘因素作用下，当个体未执行某一任务时，与之对应的响应阈值增加；

(3.5.1)环境刺激与整个布局的弹性势能有关，响应阈值与待布物的弹性势能有关；待布物执行某一占位动作后，若布局得到改进，则根据定义更新环境刺激和响应阈值，并进一步减小响应阈值；若布局未得到改进，则保持环境刺激不变，并增加响应阈值；

(3.5.2)若待布物连续执行多次占位动作后，布局仍未得到改进，则减小固定动作的环境刺激，增加平移、交换、跳跃三种动作的环境刺激；

所述设计并行占位动作执行方式的方法为：优先逐个选择待布物执行占位动作，在搜索到局部最优解以后，进行一次并行搜索，即选择若干个待布物同时执行占位动作；

所述设计格局更新准则的方法为：逐个选择待布物执行占位动作时，采用贪婪接收准则，即只接受改进的布局；同时选择若干个待布物执行占位动作时，采用无条件接收准则，即始终接受新布局为当前布局。

所述步骤四中初始化格局的方法为：容器C₀中心坐标为原点(0,0)，分别在x轴[-R,R]范围内和y轴[-R,R]范围内随机生成n个圆形待布物的坐标为(x₁,y₂)…(x_i,y_i)…(x_n,y_n)，初始格局为计算初始格局X的弹性势能E(X)，利用梯度下降法优化弹性势能E(X)，得到弹性势能最小格局X’；

采用经验法初始化算法参数：初始化容器半径R＝(R^upper+R^lower)/2，其中容器半径上限R^upper满足π*R^upper*R^upper＝1.5*Ω，容器半径下限R^lower满足π*R^lower*R^lower＝0.5*Ω，Ω为所有圆形待布物的面积之和；初始化圆形待布物的相似集合Similar，将待布物按照半径从小到大进行排序，确定各待布物的序号，且待布物C_i的相似集合Similar_i中的待布物C_j满足条件：|Type_i－Type_j|≤L；初始化布局的整体势能E(X)、势能-刺激转换系数f₁、势能-阈值转换系数f₂、引力系数α、斥力系数β和相似性范围L的范围；判断停止条件：R^upper－R^lower≤10^-6；

对待布物C_i执行刺激-响应方式下的占位动作的方法为：令概率随机生成一个随机数random，确定待布物C_i所执行的动作：

如果则圆形待布物C_i执行固定动作，其位置保持不变；

如果则圆形待布物C_i执行平移动作；容器C₀对待布物C_i的吸引力为待布物C_j对待布物C_i的排斥力为其中，v_ji＝(x_i-x_j,y_i-y_j)为C_j指向C_i的向量，则C_i平移时的位移量为得到新格局

如果则待布物C_i执行交换动作；即从圆形待布物C_i的相似集合Similar_i中随机挑选一个元素C_j互换位置，得到新格局

如果则圆形待布物C_i执行跳跃动作；即将圆形容器四等分，在每一个区域随机产生20个空位点，将待布物C_i试放到所有空位点处，并计算相应的弹性势能，选择弹性势能最小的空位点(x_i’,y_i’)作为待布物C_i的跳跃点，得到新格局

对于新格局X_new，计算梯度信息，利用梯度下降法得到弹性势能最小格局X_new’；如果E(X_new’)<10^-20，令X’＝X_new’，improve＝0，转更新容器半径；如果E(X_new’)<E(X’)，令X’＝X_new’，improve＝0，更新环境刺激，更新响应阈值，进一步的，如果新布局是由待布物C_i执行某一动作得到，则减小相应的响应阈值；否则，improve＝improve+1，增大相应的响应阈值，执行刺激-响应方式下的占位动作；

如果improve＝n，则减小固定动作的环境刺激，同时增大平移、交换和跳跃三种动作的环境刺激；如果improve＝2n，则选取相对弹性势能较大的前个圆形待布物，同时按照刺激-响应方式执行占位动作，得到新格局X_new；接着对新格局X_new计算梯度信息，利用梯度下降法得到弹性势能最小格局X_new’，并令X’＝X_new’，转更新容器半径；

更新容器半径：如果improve＝0，则R^upper＝R，R＝(R^upper+R^lower)/2；如果improve＝2n，则R^lower＝R，R＝(R^upper+R^lower)/2，improve＝0。

所述步骤五更新更新容器半径、更新环境刺激和响应阈值的方法为：(5.1)将初始格局中的待布物按照相对弹性势能大小排序，依照此顺序逐个选择待布物，根据刺激-响应方式计算待布物执行固定、平移、交换、跳跃动作的概率，选择概率最大的占位动作进行格局变换，接着利用梯度下降法优化格局，采用贪婪接收准则更新格局，并更新环境刺激和响应阈值；

(5.2)若当前格局连续多次未得到更新，选择若干个相对弹性势能较大的待布物，根据刺激-响应方式同时执行占位动作进行格局变换，接着利用梯度下降法优化格局，采用无条件接收准则更新格局，并更新环境刺激和响应阈值；

(5.3)采用二分法动态调整容器半径R，具体过程为：R＝(R^upper+R^lower)/2，其中，R^upper为容器半径R的上限，R^lower为容器半径R的下限；若得到可行解，则R^upper＝R，否则R^lower＝R；重复上述过程，直至上限容器半径R^upper与下限容器半径R^lower充分接近。

所述弹性势能最小格局X’的求解方法为：计算圆形待布物C_i与圆形待布物C_j之间的干涉量D_ij，以及待布物C_i与待布物C_j之间的挤压弹性势能E_ij＝(D_ij)²，i∈{1,2,…,n}；计算圆形待布物C_i与容器C₀之间的干涉量D_i0，以及待布物C_i与容器C₀之间的挤压弹性势能E_i0＝(D_i0)²；则圆形待布物C_i的弹性势能格局X的弹性势能

计算圆形待布物C_i受到圆形待布物C_j的弹力F_ij以及圆形待布物C_i受到容器C₀的弹力F_i0，则圆形待布物C_i受到的弹性合力弹性势能E(X)在点(x_i,y_i)处的负梯度方向即为圆形待布物C_i所受弹性合力F_i的方向；利用梯度下降法优化E(X)，得到弹性势能最小格局X’。

与现有技术相比，本发明的有益效果：

(1)将卫星舱布局抽象为空间分配问题，进而为卫星舱布局乃至其他装填问题的求解提供了新思路，即基于分配求解的思路；

(2)继承了蚁群劳动分工的特性，能有效克服已有方法的不足。比如，蚁群劳动分工在动态环境下的柔性分配能有效克服已有方法普适性差的不足，蚁群劳动分工的快速响应特性能有效克服已有方法收敛速度慢的不足，蚁群劳动分工下的高效任务分配能有效克服已有方法容易陷入局部最优的不足

(3)具有方法简单、控制参数少、易于实现等特点。采用该方法得到的布局方案利用率高，且完全满足卫星舱的平衡性能约束，可进一步推广应用于其他装填、下料等布局问题。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明卫星舱旋转承载板上装填物的布局示意图，其中，(a)为三维布局图，(b)为二维布局图。

图2为待布物之间、待布物与容器之间的允许干涉示意图，其中，(a)为待布物之间的示意图，(b)为待布物与容器之间的示意图。

图3为本发明蚁群劳动分工和卫星舱布局之间的映射关系图。

图4为本发明的流程图。

图5为本发明得到的最优布局结果图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有付出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

如图1所示，一种基于蚁群劳动分工的卫星舱布局方法，其步骤如下：

步骤一：在传统布局问题数学模型的基础上，建立卫星舱布局的数学模型，通过平移策略和干涉策略，将卫星舱布局由多目标带约束优化问题转化为单目标无约束优化问题。

卫星舱布局问题描述：在一个带自旋的返回式卫星舱内要布置若干个仪器设备，称仪器设备为待布物，卫星舱为容器。卫星舱布局要求容器半径和系统静不平衡量尽可能小，此外待布物之间、待布物与容器之间还必须满足互不干涉的约束。考虑一个具有n个圆形待布物和圆形容器的卫星舱，其中圆形待布物为质量分布均匀的圆柱体，则卫星舱布局可简化为二维圆形装填问题，如图1所示。

卫星舱布局问题建模：设圆形容器C₀的初始半径为R，容器C₀的中心为坐标原点(0,0)，圆形待布物C_i的半径为r_i、质量为m_i、质心坐标为(x_i,y_i)，i∈{1,2,…,n}，n为圆形待布物的数量，则代表一个圆形待布物的布局方案。根据卫星舱布局要求，建立如下多目标带约束数学模型：

且

其中，R(X)指当前布局X下所有待布物的最小外包络圆半径，J(X)指当前布局X下整个系统的静不平衡量。

平移策略：将卫星舱系统的质心平移到容器的中心，各待布物也做相应的平移，即此时，据此，建立如下单目标带约束数学模型：

且

干涉策略：将待布物和容器均视为弹性物体，令E_ij表示待布物C_i与待布物C_j之间的挤压弹性势能，D_ij表示待布物C_i与待布物C_j之间的干涉量，则挤压弹性势能E_ij＝(D_ij)²，干涉量则挤压弹性势能E_ij为0时，待布物C_i与待布物C_j之间无干涉，如图2(a)所示。同理，令挤压弹性势能E_i0表示待布物C_i与容器C₀之间的挤压弹性势能，D_i0表示待布物C_i与容器C₀之间的干涉量，挤压弹性势能E_i0＝(D_i0)²，干涉量则挤压弹性势能E_i0为0时，待布物C_i与容器C₀之间无干涉，如图2(b)所示。当整个系统的弹性势能为0时，就得到一个合法布局X。上述问题可转化为固定容器半径R下，系统的弹性势能最小化问题，找到最优解后缩小半径继续搜索，如此便可逐渐逼近最小半径。据此，建立如下单目标无约束数学模型

其中，E_i表示待布物C_i的挤压弹性势能。

步骤二：从空间的角度出发，建立蚁群劳动分工与卫星舱布局之间的映射关系，将卫星舱布局抽象为空间分配问题，提出基于蚁群劳动分工的布局方法。

卫星舱布局的空间分配特性：任何物体都占据着一定的空间。从空间的角度来看，卫星舱布局的一个解决方案就是待布物在容器内占据着不同的空间，将待布物装入容器等同于将待布物所占的空间装入容器所占的空间。据此，卫星舱布局可视为将容器空间合理有效地分配给给定的待布物。每一种空间分配模式都对应待布物的一种放置方式，也就是卫星舱布局的一个解。

蚁群劳动分工和卫星舱布局之间的映射关系：在蚁群劳动分工中，不同的个体执行不同的任务完成任务分配。对个体而言，执行不同的任务可以看作是采取不同的行为。在卫星舱布局中，不同的待布物占据不同的空间完成空间分配。对待布物而言，通常会执行固定、平移、交换和跳跃等动作来调整其在容器内所占的位置，不同的动作通常对应容器内不同的空间。综上，蚂蚁选择哺育、筑巢、防御、觅食等行为完成任务分配，待布物选择固定、平移、交换、跳跃等动作完成空间分配，如图3所示。

基于蚁群劳动分工的求解思路：蚂蚁在劳动分工机制下选择恰当的行为完成任务分配，将待布物看作蚂蚁，将动作看作行为，结合卫星舱布局的特点，设计定制化的劳动分工机制，即可实现卫星舱布局的空间分配。

步骤三：设计固定、平移、交换和跳跃四种占位动作，根据占位动作的特点定义环境刺激，根据待布物的特点定义响应阈值，根据蚁群劳动分工的刺激-响应原理设计待布物的空间位置占据方式；更进一步，设计环境刺激和响应阈值的更新规则、并行占位动作执行方式、不同格局变换策略下的格局更新准则。

(3.1)根据卫星舱布局的特点定义占位动作：假设当前格局为对待布物C_i而言，执行固定动作指保持其当前位置不变，执行平移动作指在其当前位置附近移动，执行交换动作指与另一随机选择的待布物C_j互换位置，执行跳跃动作指将其重新放置到容器内的其他位置处。则

(3.1.1)执行固定动作后的格局为

(3.1.2)执行平移动作后的格局为

其中，为平移向量。考虑到最小化容器半径的目标要求，平移时应朝向容器的中心，可通过容器中心吸引待布物来实现。考虑到待布物之间、待布物与容器之间的非干涉约束，平移时应远离容器内的拥挤区域，可通过受挤压的待布物排斥其他待布物来实现。容器C₀对圆形待布物C_i的吸引力可定义为圆形待布物C_j对圆形待布物C_i的排斥力可定义为其中，α，β分别表示引力系数和斥力系数，E_j为待布物C_j的弹性势能，E为整个布局的弹性势能，v_ji＝(x_i-x_j,y_i-y_j)为待布物C_j指向待布物C_i的向量，则待布物C_i平移时的位移量为

(3.1.3)执行交换动作后的格局为

其中，为与待布物C_i相似的待布物C_j的位置。经验表明，交换半径相同的圆形待布物不会改变当前格局，交换半径相差很大的圆形待布物会严重破坏当前格局，交换半径相近的圆形待布物能够在基本不破坏当前格局的情况下获得某些改进。相似圆形待布物的定义如下：将所有圆形待布物按半径大小排序，令Type_i表示圆形待布物C_i的类型；若|Type_i－Type_j|≤L，则认为圆形待布物C_i和圆形待布物C_j的半径相近，L表示相似性范围。在这里，交换动作只允许发生在半径相近的圆形待布物之间。

(3.1.4)执行跳跃动作后的格局为

其中，为当前格局中的一个空位点。经验表明，将圆形待布物C_i在容器C₀内随机放置具有盲目性，而且很容易与其他圆形待布物C_j产生干涉。相比之下，将圆形待布物C_i放置在容器C₀内未被占用的区域(或者空位点处)更有前景，可以尽量减少与其他待布物之间的干涉。空位点的确定方法如下：在容器C₀内随机生成一个点，若该点不在任一圆形待布物内，则其为一个空位点。将圆形容器四等分，在每一个区域随机产生20个空位点，圆形待布物C_i最终将跳跃到干涉量最小的空位点处。

(3.2)根据占位动作的特点定义环境刺激。在蚁群中，环境刺激是蚂蚁个体采取不同行为的外部驱动力。刺激越大，与行为对应的任务的紧迫性越强。根据图3的蚁群劳动分工和卫星舱布局之间的映射关系，对应圆形待布物的四种动作有四种不同的刺激。固定动作的目的是为了保持已找到的合适位置，而平移、交换和跳跃三种动作的目的是为了寻找更好的位置。据此，为固定动作定义一个刺激，为平移、交换和跳跃三种动作定义同一个刺激。

(3.2.1)当布局在最优解附近时，一般需要较小的变动，此时固定动作的刺激应该比较大。具体的，当布局在最优解附近时，整个布局的弹性势能较小，当前布局中大部分圆形待布物已经找到了合适的位置，圆形待布物感知到的保持位置不变的刺激较大。据此，定义固定动作的环境刺激为：其中，E_i表示待布物C_i的挤压弹性势能，f₁表示势能-刺激转换系数。

(3.2.2)当布局远离最优解时，一般需要较大的变动，此时平移、交换和跳跃三种动作的刺激应该比较大。具体的，当布局远离最优解时，整个布局的弹性势能较大，当前布局中大部分圆形待布物之间存在干涉，圆形待布物感知到的调整位置的刺激较大。据此，定义平移、交换、跳跃三种动作的环境刺激为：

(3.3)根据待布物的特点定义响应阈值。在蚁群中，响应阈值是决定蚂蚁个体响应刺激而采取相应行为的倾向性的一个内部变量。阈值越小，采取相应行为的倾向性越强。据此，每个待布物都有四个阈值分别对应固定、平移、交换和跳跃四种动作。

(3.3.1)当圆形待布物找到一个好位置时，其选择保持位置不变的倾向性大，而选择平移、交换或跳跃的倾向性小。当圆形待布物没有找到一个好位置时，其选择平移、交换或跳跃的倾向性大，而选择保持位置不变的倾向性小。因此，圆形待布物的响应阈值与其所处的位置有关。圆形待布物位置的优劣可通过自身的弹性势能来度量，定义圆形待布物C_i对应固定动作的响应阈值为：其中，E_i表示待布物C_i的挤压弹性势能，f₂表示势能-阈值转换系数。

圆形待布物C_i对应平移、交换和跳跃三种动作的响应阈值为：

(3.3.2)考虑到平移、交换、跳跃的动作方式以及对布局造成的变动程度不同，需要对响应阈值做进一步区分。平移动作对布局造成的变动最小，其次是跳跃动作，最后是交换动作。按照由近到远的搜索方式，圆形待布物C_i的响应阈值一般应满足实验观察发现，小圆经常位于多个大圆所围成的空隙中，即小圆适合填缝。因此，半径较小的圆形待布物C_i的响应阈值一般应满足实验观察还发现，大圆适合交换，尤其在布局比较紧凑时，交换大圆通常会找到一个更好的位置。因此，半径较大的圆形待布物C_i的响应阈值一般应满足

根据半径将圆形待布物分为大、中、小三个类型，其中较大圆形待布物的半径大于r_max为最大圆形待布物的半径，较小圆形待布物的半径小于其余的为半径适中的圆形待布物。

若待布物C_i为半径较大的圆形待布物，则响应阈值

若待布物C_i为半径适中的圆形待布物，则响应阈值

若待布物C_i为半径较小的圆形待布物，则响应阈值

(3.4)根据蚁群劳动分工的刺激-响应原理设计待布物的空间位置占据方式。在蚁群中，当任务的环境刺激超过蚂蚁个体的响应阈值时，蚂蚁个体执行任务的概率高；反之，执行任务的概率低。假设任务的刺激为S，蚂蚁的阈值为θ，则蚂蚁执行任务的概率为环境刺激越大，响应概率越大；响应阈值越小，响应概率越大。

(3.4.1)根据蚁群劳动分工的刺激-响应方式，圆形待布物C_i执行固定动作的概率为：

其中，S_固定表示固定动作的环境刺激，表示固定动作的响应阈值。

(3.4.2)根据蚁群劳动分工的刺激-响应方式，圆形待布物C_i执行平移动作的概率为：

其中，S_平移表示平移动作的环境刺激，表示平移动作的响应阈值。

(3.4.3)根据蚁群劳动分工的刺激-响应方式，圆形待布物C_i执行交换动作的概率为：

其中，S_交换表示交换动作的环境刺激，表示交换动作的响应阈值。

(3.4.4)根据蚁群劳动分工的刺激-响应方式，圆形待布物C_i执行跳跃动作的概率为：

其中，S_跳跃表示跳跃动作的环境刺激，表示跳跃动作的响应阈值。

(3.5)结合刺激-响应原理和卫星舱布局的特点，设计环境刺激和响应阈值的更新规则。在蚁群中，一旦任务被执行，刺激强度会降低；反之，刺激强度会升高。在学习因素作用下，当个体执行某一任务时，与之对应的阈值降低；在遗忘因素作用下，当个体未执行某一任务时，与之对应的阈值增加。

(3.5.1)环境刺激与整个布局的弹性势能有关，响应阈值与待布物的弹性势能有关。待布物执行某一占位动作后，若布局得到改进，则根据定义更新环境刺激和响应阈值，并进一步减小响应阈值；若布局未得到改进，则保持环境刺激不变，并增加响应阈值。

(3.5.2)若待布物连续执行多次占位动作后，布局仍未得到改进，则减小固定动作的环境刺激，增加平移、交换、跳跃三种动作的环境刺激。

(3.6)设计并行占位动作执行方式，作为串行搜索的补充。优先逐个选择待布物执行占位动作，在搜索到局部最优解以后，进行一次并行搜索。即选择若干个待布物同时执行占位动作，目的是在不完全破坏当前格局拓扑结构的前提下，跳出局部最优陷阱。

(3.7)设计格局更新准则。逐个选择待布物执行占位动作时，采用贪婪接收准则，即只接受改进的布局；同时选择若干个待布物执行占位动作时，采用无条件接收准则，即始终接受新布局为当前布局。

步骤四：初始化算法参数，随机生成初始格局。

初始化格局：随机生成n个圆形待布物的坐标(x₁,y₂)…(x_i,y_i)…(x_n,y_n)，利用梯度下降法最小化整体弹性势能。对每个待布物而言，其所受弹性合力的方向即为梯度下降的方向。

初始化算法参数：算法中的参数涉及占位动作等根据启发式信息定义的变量，采用经验法设置参数的取值。

步骤五：采用步骤二得到的基于蚁群劳动分工的布局方法求解卫星舱布局问题，更新容器半径，循环求解过程，直到满足停止条件。

(5.1)将初始格局中的待布物按照相对弹性势能大小排序，依照此顺序逐个选择待布物，根据刺激-响应方式计算待布物执行固定、平移、交换、跳跃动作的概率，选择概率最大的占位动作进行格局变换，接着利用梯度下降法优化格局，采用贪婪接收准则更新格局，并更新环境刺激和响应阈值。

(5.2)若当前格局连续多次未得到更新，选择若干个相对弹性势能较大的待布物，根据刺激-响应方式同时执行占位动作进行格局变换，接着利用梯度下降法优化格局，采用无条件接收准则更新格局，并更新环境刺激和响应阈值。

(5.3)采用二分法动态调整容器半径R，具体过程为：R＝(R^upper+R^lower)/2，其中，R^upper为容器半径R的上限，R^lower为容器半径R的下限；若得到可行解，则R^upper＝R，否则R^lower＝R；重复上述过程，直至上限容器半径R^upper与下限容器半径R^lower充分接近。

步骤六：输出最终布局结果，包括容器半径、待布物坐标和布局结果图。

具体实施例：

应用本发明提出的基于蚁群劳动分工的卫星舱布局方法，获得能容纳n个互不相嵌放置的圆形待布物的最小容器以及对应的布局方案。考虑一个包含40个圆形待布物的算例，各待布物的半径分别为r＝[106,112,98,105,93,103,,82,93,117,81,89,92,109,104,115,110,114,89,82,120,108,86,93,100,102,106,111,107,109,91,111,91,111,91,108,114,118,85,87,98]，质量为m＝[11,12,9,11,8,10,6,8,13,6,7,8,11,10,13,12,12,7,6,14,11,7,8,10,10,11,12,11,11,8,12,8,12,8,11,12,13,7,7,9]。注意到，在本发明方法所包含的六个主要步骤中，前三个步骤是本发明方法的基础和前提，主要涉及一些概念性的描述和定义。在具体实施过程中以后三个步骤为主，可参照图4所示流程进行求解。一种基于蚁群劳动分工的卫星舱布局方法的实施步骤如下：

步骤1：初始化算法参数

初始化容器半径R＝(R^upper+R^lower)/2，其中容器半径上限R^upper满足π*R^upper*R^upper＝1.5*Ω，容器半径下限R^lower满足π*R^lower*R^lower＝0.5*Ω，Ω为所有圆形待布物的面积之和。

初始化圆形待布物的大小类型Size，根据圆形待布物的半径大小将其划分为大、中、小三个类型。具体的，找到最大圆形待布物的半径r_max，若圆形待布物C_i的半径满足则Size_i＝big；若圆形待布物C_i的半径满足则Size_i＝midium；若圆形待布物C_i的半径满足则Size_i＝small。

初始化圆形待布物的相似集合Similar。将圆形待布物按照半径从小到大进行排序，确定各待布物的序号。比如r₁＝5，r₂＝5，r₃＝15，r₄＝10，则Type₁＝1，Type₂＝1，Type₃＝3，Type₄＝2。圆形待布物C_i的相似集合Similar_i中的元素C_j满足条件：|Type_i－Type_j|≤L。

考虑到计算精度，当布局的整体势能E(X)<10^-20时，认为找到当前半径下的最优布局。势能-刺激转换系数f₁、势能-阈值转换系数f₂、引力系数α、斥力系数β和相似性范围L分别设置为10⁵、10⁵、200、0.02、3。

步骤2：随机生成初始格局

令容器中心坐标为原点(0,0)，分别在x轴[-R,R]范围内和y轴[-R,R]范围内随机生成40个点，作为初始格局X＝(x₁,y₁,x₂,y₂,…,x₄₀,y₄₀)。计算格局X的弹性势能E(X)，利用梯度下降法优化弹性势能E(X)，得到弹性势能最小格局X’。

具体的，如图2所述，计算圆形待布物C_i与圆形待布物C_j之间的干涉量D_ij，以及待布物C_i与待布物C_j之间的挤压弹性势能E_ij＝(D_ij)²，i∈{1,2,…,n}；计算圆形待布物C_i与容器C₀之间的干涉量D_i0，以及待布物C_i与容器C₀之间的挤压弹性势能E_i0＝(D_i0)²；则圆形待布物C_i的弹性势能格局X的弹性势能

接着，计算圆形待布物C_i受到圆形待布物C_j的弹力F_ij，以及圆形待布物C_i受到容器C₀的弹力F_i0，则圆形待布物C_i受到的弹性合力弹性势能E(X)在点(x_i,y_i)处的负梯度方向即为圆形待布物C_i所受弹性合力F_i的方向，在此基础上，利用梯度下降法优化E(X)，得到弹性势能最小格局X’。

步骤3：刺激-响应求解方式

(3.1)对于格局X’，根据整体势能E(X’)计算固定、平移、交换和跳跃四种动作的环境刺激：

S_平移＝S_交换＝S_跳跃＝f_i×E(X’)。

(3.2)对于格局X’，根据各圆形待布物C_i的弹性势能计算其对应固定、平移、交换和跳跃四种动作的响应阈值：

若Size_i＝big，

若Size_i＝midium，则

若Size_i＝small，则

(3.3)对于格局X’，计算每个圆形待布物C_i的相对弹性势能E_i/r_i。

(3.4)对所有圆形待布物按照相对弹性势能从大到小进行排序，根据该序列，依次对待布物C_i执行刺激-响应方式下的占位动作。

首先，分别计算圆形待布物C_i执行四种动作的概率：

然后，令概率随机生成一个随机数random，在此随机数的基础上，确定圆形待布物C_i所执行的动作：

如果则圆形待布物C_i执行固定动作，其位置保持不变。

如果则圆形待布物C_i执行平移动作。具体的，容器C₀对圆形待布物C_i的吸引力为圆形待布物C_j对圆形待布物C_i的排斥力为其中，v_ji＝(x_i-x_j,y_i-y_j)为C_j指向C_i的向量，则C_i平移时的位移量为得到新格局X_new＝(x₁,y₁,…,x_i+σ_x,y_i+σ_y,…,x₄₀,y₄₀)。

如果则圆形待布物C_i执行交换动作。具体的，从圆形待布物C_i的相似集合Similar_i中随机挑选一个元素C_j互换位置，得到新格局X_new＝(x₁,y₁,…,x_j,y_j,…,x_i,y_i,…,x₄₀,y₄₀)。

如果则圆形待布物C_i执行跳跃动作。具体的，将圆形容器四等分，在每一个区域随机产生20个空位点。如果一个点到所有圆形待布物的圆心的距离都大于该圆形待布物的半径，则该点就是一个空位点。将圆形待布物C_i试放到所有空位点处，并计算相应的弹性势能。选择弹性势能最小的空位点(x_i’,y_i’)作为圆形待布物C_i的跳跃点，得到新格局X_new＝(x₁,y₁,…,x_i’,y_i’,…,x₄₀,y₄₀)。

(3.5)对于新格局X_new，根据步骤2的方法计算梯度信息，利用梯度下降法得到弹性势能最小格局X_new’。

如果E(X_new’)<10^-20，令X’＝X_new’，improve＝0，转步骤4。

如果E(X_new’)<E(X’)，令X’＝X_new’，improve＝0，根据步骤(3.1)更新环境刺激，根据步骤(3.2)更新响应阈值，如果新布局是由圆形待布物C_i执行某一动作得到，则进一步减小相应的响应阈值到原来的一半，转步骤(3.3)；否则，improve＝improve+1，增大相应的响应阈值到两倍，转步骤(3.4)。

如果improve＝n(这里n取40)，即连续n次布局没有得到改进，则减小固定动作的环境刺激到原来的一半，同时增大平移、交换和跳跃三种动作的环境刺激到原来的两倍，转步骤(3.4)。

如果improve＝2n(这里n取40)，即连续2n次布局没有得到改进，则选取相对弹性势能较大的前(这里n取40)个圆形待布物，同时按照刺激-响应方式执行占位动作，得到新格局X_new。接着对新格局X_new，根据步骤2的方法计算梯度信息，利用梯度下降法得到弹性势能最小格局X_new’，并令X’＝X_new’，转步骤4。

步骤4：更新容器半径

如果improve＝0，则R^upper＝R，R＝(R^upper+R^lower)/2。

如果improve＝2n，则R^lower＝R，R＝(R^upper+R^lower)/2，improve＝0。

步骤5：判断停止条件

如果R^upper－R^lower≤10^-6，转步骤6；否则转步骤3。

步骤6：输出最终容器半径R、待布物的质心坐标(x_i,y_i)和布局结果图。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。