主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
刘景发,刘思妤.带静不平衡约束的矩形装填问题的启发式算法.软件学报,2018,29(2):283-298
带静不平衡约束的矩形装填问题的启发式算法
Heuristic Algorithm for the Rectangular Packing Problem with Static Non-Equilibrium Constraint
投稿时间:2016-09-01  修订日期:2017-01-10
DOI:10.13328/j.cnki.jos.005252
中文关键词:  静不平衡约束  Wang-Landau抽样算法  启发式策略  卫星舱布局
英文关键词:static non-equilibrium  Wang-Landau sampling algorithm  heuristic strategy  layout of satellite module
基金项目:国家自然科学基金(61373016);江苏省"六大人才高峰"项目(DZXX-041);国家社会科学基金(16ZDA047)
作者单位E-mail
刘景发 江苏省网络监控工程中心(南京信息工程大学), 江苏 南京 210044
南京信息工程大学 计算机与软件学院, 江苏 南京 210044 
 
刘思妤 江苏省网络监控工程中心(南京信息工程大学), 江苏 南京 210044
南京信息工程大学 计算机与软件学院, 江苏 南京 210044 
siyu544708079@163.com 
摘要点击次数: 1438
全文下载次数: 1176
中文摘要:
      卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性.解决这类问题最大的挑战在于需要优化的目标函数具有大量被高能势垒分隔开的局部极小值点.Wang-Landau(WL)抽样算法是一种改进的蒙特卡罗方法,已被成功地运用于蛋白质结构预测等优化问题.以卫星舱布局优化问题为背景,将WL抽样算法引入矩形装填问题的求解.针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走.为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,就执行梯度法进行局部搜索.通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法.在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.为了改进算法的搜索效率,还提出了改进的有限圆族法,用于装填物之间的干涉性判断和干涉量计算.通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利