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

以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法.

求解二维正交矩形布局问题的动态填空启发式算法

为更高效解决二维正交矩形布局问题,建立该问题的数学模型,改进BL算法规则;为寻找布局过程中的空余平面,建立了新颖的图形矩阵化理论。最后提出一种动态填空(DFB)启发式算法,制定了四条动态调整机制,结合遗传算法对该问题进行求解。大量算例测试显示,DFB算法可达到100%的平面利用率,极大地提高了BL算法的效率,并且可以适用于大规模布局问题。