带静不平衡约束的矩形装填问题的启发式算法
作者:
作者单位:

作者简介:

刘景发(1972-),男,湖南衡阳人,博士,教授,博士生导师,CCF高级会员,主要研究领域为NP难度问题现实求解,多目标优化,智能计算,生物信息计算;刘思妤(1993-),女,硕士生,主要研究领域为高性能智能计算.

通讯作者:

刘思妤,E-mail:siyu544708079@163.com

中图分类号:

TP301

基金项目:

国家自然科学基金(61373016);江苏省"六大人才高峰"项目(DZXX-041);国家社会科学基金(16ZDA047)


Heuristic Algorithm for the Rectangular Packing Problem with Static Non-Equilibrium Constraint
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61373016); Six Talent Peaks Project of Jiangsu Province (DZXX-041); National Social Science Foundation of China (16ZDA047)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性.解决这类问题最大的挑战在于需要优化的目标函数具有大量被高能势垒分隔开的局部极小值点.Wang-Landau(WL)抽样算法是一种改进的蒙特卡罗方法,已被成功地运用于蛋白质结构预测等优化问题.以卫星舱布局优化问题为背景,将WL抽样算法引入矩形装填问题的求解.针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走.为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,就执行梯度法进行局部搜索.通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法.在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.为了改进算法的搜索效率,还提出了改进的有限圆族法,用于装填物之间的干涉性判断和干涉量计算.通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法.

    Abstract:

    Layout design of satellite module is not only a complex coupling system design problem but also a special optimization problem. It is considered to be NP-hard. The most challenge of solving this problem is that the objective function to be optimized is characterized by a multitude of local minima separated by high-energy barriers. The Wang-Landau (WL) sampling method is an improved Monte Carlo method, which has been successfully applied to solve the protein structure prediction and other optimization problems. Taking satellite layout design as case study, this paper introduces the WL sampling method to solve the rectangular packing problem. In order to guide the WL sampling algorithm to random walk effectively in solution space, rectangular objects-oriented heuristic layout update strategies are proposed. To accelerate the search for the global optimal layout, the gradient method is executed for local search once the Monte-Carlo sweep produces a new layout. By incorporating the local search mechanism and heuristic layout update strategies into the WL sampling algorithm, a heuristic Wang-Landau sampling algorithm is constructed to solve the arbitrary rectangular packing problem with the static non-equilibrium constraint. By adding a static non-equilibrium penalty term on the basis of the extrusive elastic energy, and adopting the translation of the center of mass, the static non-equilibrium constraints of the whole system can be satisfied. Furthermore, to improve the efficiency of the algorithm significantly, an improved finite-circle method is presented to judge and calculate the overlapping depth among objects. The computational results of two sets of benchmarks consisting of ten representative instances from the literature show that the proposed packing algorithm is effective.

    参考文献
    相似文献
    引证文献
引用本文

刘景发,刘思妤.带静不平衡约束的矩形装填问题的启发式算法.软件学报,2018,29(2):283-298

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2016-09-01
  • 最后修改日期:2017-01-10
  • 录用日期:
  • 在线发布日期: 2017-03-23
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号