基于禁忌搜索平衡性能约束的圆形装填问题的布局方法

摘要

本发明公布了一种基于禁忌搜索平衡性能约束的圆形装填问题的布局方法，属于航天器布局方案设计研究领域。本发明方法包括，首先采用拟物策略和罚函数法将带平衡性能约束的圆形装填问题转化为无约束的优化问题；然后从任一随机初始布局出发，应用基于自适应步长的梯度法进行极小化优化计算；为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索，采用了禁忌搜索的策略。在禁忌搜索的过程中，对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进。本发明的优点在于布局具有很高的面积利用率，较快的速度，同时能更好地实现平衡性能约束，并可推广应用于其他布局优化问题的求解。

主权项

1.一种航天器布局领域中基于禁忌搜索平衡性能约束的圆形装填问题的布局方法，其特征在于包含以下步骤：(1)将所有n个圆形待布物C_i和圆形容器C₀都想象为光滑的弹性实体，按照拟物策略和罚函数法，将带平衡性能约束的圆形装填转化为下面的无约束优化：$\min \mathrm{imizeU}\left(X\right)=\underset{i=0}{\overset{n-1}{\Sigma }}\underset{j=i+1}{\overset{n}{\Sigma }}{d}_{\mathrm{ij}}^2+l[{\left(\underset{i=1}{\overset{n}{\Sigma }}{m}_i{x}_i\right)}^2+{\left(\underset{i=1}{\overset{n}{\Sigma }}{m}_i{y}_i\right)}^2]$这里$d_{\mathrm{ij}}=d_{\mathrm{ji}}=\max (0,r_i+r_j-\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2})$是圆形待布物C_i和C_j之间的嵌入深度，是圆形待布物C_i与圆形容器C₀之间的嵌入深度；r_i和m_i分别表示圆形待布物C_i的半径和质量，r₀为圆形容器C₀的半径；(x_i,y_i)为圆形待布物C_i的圆心即质心坐标；X＝(x₁,y₁,x₂,y₂,…,x_n,y_n)表示布局的一个方案，也就是一个格局；l为惩罚项系数，是一个小的正数；i,j=1,2,3,…,n，i≠j；(2)随机给出初始布局；(3)基于当前圆形容器C₀，使用禁忌搜索算法对当前初始布局进行布局的全局优化；(4)采用二分法对圆形容器的半径r₀进行设置，对于新半径的圆形容器，重新执行禁忌搜索算法进行布局的全局优化，此过程重复执行直到满足二分法的结束条件；(5)输出最优圆形容器的半径r₀和最优布局的图形；所述禁忌搜索算法如下：(3.1)邻域格局的产生：(3.1.1)挑出当前格局X中势能半径比E_i/r_i最大的圆形待布物C_i，其中表示第i个圆形待布物C_i所受到的其他n-1个圆形待布物和圆形容器C₀施加于它的挤压弹性势能之和；(3.1.2)将圆形待布物C_i在圆形容器内随机“试做”10个动作得到当前格局X的基于圆形待布物C_i的候选邻域N(X，C_i)，再从候选邻域N(X，C_i)中挑选一个最佳候选邻域格局X¹；其中动作为：对于当前格局X＝(x₁,y₁，…,x_i,y_i,...,x_n,y_n)，称将势能半径比E_i/r_i最大的圆形待布物C_i放在圆形容器内的空位点即圆形容器的空白区域内的一点上的手续为一个动作；“试做”是指C_i只是暂时放置，一旦计算出C_i放在该位置的挤压弹性势能后就将C_i从该位置移走；邻域格局为：对于当前格局X＝(x₁,y₁，…,x_i,y_i,...,x_n,y_n)，称X′=(x₁,y₁，…,x′_i,y′_i,...,x_n,y_n)是X的一个邻域格局，这里(x′_i,y′_i)是第i个圆形待布物C_i做一个动作后得到的新的圆心坐标；候选邻域定义为：对于当前格局X＝(x₁,y₁，…,x_i,y_i,...,x_n,y_n)，若C_i是势能半径比最大的圆形待布物，称将C_i在圆形容器内“试做”10个随机动作得到的10个邻域格局为X的基于C_i的候选邻域，记为N(X，C_i)；(3.1.3)对于最佳候选邻域格局X¹，调用基于自适应步长的梯度法GM(X¹)进行细粒度的布局调整，得到格局X²；其中自适应步长是指在梯度法迭代中，如果新产生格局的能量值小于或等于前一格局的能量值，则梯度法按步长h继续迭代；如果新产生的格局的能量值大于前一格局的能量值，则令步长h=h×0.8；(3.1.4)重复步骤(3.1.2)至(3.1.4)直到格局X²被接受或循环次数达到5次；其中步骤(3.1.4)中所述格局X²被接受的判断原则为：i)若前一格局X中被挑出需要做动作的圆形待布物C_i是禁忌对象，且将其做动作并执行梯度法后得到的格局X²的能量U(X²)小于当前最优格局的能量U_opt时，则修改禁忌表中各对象的任期和当前最优格局，同时采用藐视准则，即无视C_i的禁忌属性，将C_i强行解禁，并接受X²为当前格局；ii)如果C_i是禁忌对象，且将其做动作并执行梯度法后得到的格局X²的能量U(X²)不小于U_opt，则不接受X²为当前格局，此时，恢复X为当前格局；iii)如果C_i不是禁忌对象，但将C_i做动作并执行梯度法后得到的格局X²的能量U(X²)小于前一格局X的能量U(X)，则仍然接受X²为当前格局，同时修改禁忌表中各对象的任期，释放任期为0的对象；若此时该格局X²的能量U(X²)小于当前最优格局的能量U_opt，则进一步将X²更新为当前最优格局；iv)如果C_i不是禁忌对象，且将C_i做动作并执行梯度法后得到的格局X²的能量U(X²)不小于前一格局X的能量U(X)，则不接受X²为当前格局，此时，恢复X为当前格局；(3.2)如果步骤(3.1)中循环次数达到5次，则将圆形待布物C_i设置为禁忌对象并加入禁忌表中，令C_i的势能半径比为0；(3.3)重复步骤(3.1)-(3.3)直到下列条件之一成立时，禁忌搜索算法就结束：(a)算法找到问题minimize U(X)的全局最优解；(b)迭代步数t＞10⁵。