计算机应用 ›› 2010, Vol. 30 ›› Issue (11): 2898-2901.

• 人工智能 • 上一篇    下一篇

基于蚁群算法的带平衡约束矩形布局问题的启发式求解

季美1,肖人彬2   

  1. 1. 华中科技大学控制科学与工程系
    2. 华中科技大学
  • 收稿日期:2010-05-05 修回日期:2010-06-24 发布日期:2010-11-05 出版日期:2010-11-01
  • 通讯作者: 季美
  • 基金资助:
    教育部博士点基金

Ant colony optimization and heuristic algorithms for rectangle layout optimization problem with equilibrium constraints

  • Received:2010-05-05 Revised:2010-06-24 Online:2010-11-05 Published:2010-11-01
  • Contact: JI Mei

摘要: 以卫星舱布局问题作为研究背景,求解了带平衡约束的矩形布局问题。采用启发式策略设计了分区域分步布局法,该策略将圆形卫星舱承重板分成4个区域,分区域同步进行布局。当所布矩形和区域都确定时,采用最左最底填充策略进行布局。该方法通过不干涉约束,使布局紧凑,通过控制系统质心的位置,使系统保持平衡。在启发式策略的基础上,设计了蚁群算法搜索优化定位次序,从而得到优化的布局。数值仿真结果表明,该布局方法具有优良的计算性能。

关键词: 矩形布局, 平衡约束, 启发式策略, 蚁群算法

Abstract: Taking the problem of satellite module layout as research background, this paper discussed the problem of Rectangle Layout Optimization with Equilibrium Constraint (RLOEC). These works designed a sub-regional distribution strategy through heuristic strategies. This strategy divided the circular container into four regions, which were layout synchronized. When the layout rectangle and the area were decided, the Bottom Left Fill (BLF) strategy was used to layout the rectangle. The heuristic algorithm made the output layout compact by the geometry constraints and balanced by controlling the mass center of the system. On the basis of the heuristic strategy, an Ant Colony Optimization (ACO) algorithm was developed to search for the optimal positioning order and then the optimal layout. The simulation results show that the proposed method has good computation performance.

Key words: rectangle layout optimization, balance constraint, heuristic strategy, Ant Colony Optimization (ACO) algorithm