带静不平衡约束的正交矩形布局问题的启发式模拟退火算法

摘要

With the background of the satellite module layout, the orthogonal rectangle packing problem with static non-equilibrium constraints is studied. By drawing lessons from quasiphysical strategy and defining embedded computing formula between each two rectangles, and between the rectangle and the circular container, this problem is converted into an unconstrained optimization problem. By incorporating heuristic configuration update strategies, local search strategy based on the gradient method and the simulated annealing algorithm with global optimization, a heuristic simulated annealing algorithm for orthogonal rectangle packing problem with static non-equilibrium constraints is put forward. The heuristic configuration update strategies in this algorithm produce new configurations and jump out of trap. The gradient method is searched for lower-energy minima near newly generated configurations. In addition, in the process of layout optimization, a static non-equilibrium penalty term on the basis of the extrusive elastic energy is introduced. Subsequently, by adopting the translation of the center of mass, the static non-equilibrium constraints of the whole system can be satisfied. The experimental results show that the proposed algorithm is an effective algorithm for solving the orthogonal rectangle packing problem with static non-equilibrium constraints.%以卫星舱布局为背景，研究一类带静不平衡约束的正交矩形布局问题。借鉴拟物策略，定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式，将该问题转变为无约束的优化问题。通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合，提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法。算法中的启发式格局更新策略产生新格局和跳坑，梯度法搜索新格局附近能量更低的格局。另外，在布局优化过程中，通过在挤压弹性势能的基础上增加静不平衡量惩罚项，并采用质心平移的方法，使布局系统的静不平衡量达到约束要求。实验表明，文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法。