位置:成果数据库 > 期刊 > 期刊详情页
基于粗精调技术的求解带平衡约束圆形Packing问题的拟物算法
  • ISSN号:0254-4164
  • 期刊名称:计算机学报
  • 时间:2013.6.15
  • 页码:1224-1234
  • 分类:TP301[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
  • 作者机构:[1]华中科技大学计算机科学与技术学院,武汉430074
  • 相关基金:本课题得到国家自然科学基金(61173180)、中央高校基本科研业务费(HUST:2010MS099)资助.
  • 相关项目:四维时空高效利用的装箱调度问题
中文摘要:

带平衡约束的圆形Packing问题是以卫星舱布局为背景的具有NP难度的布局优化问题.文中建立了此问题相应的数学模型,同时提出了两个新的物理模型,并受工艺加工过程中“粗精加工”现象的启发,提出了基于粗精调技术的拟物算法QPCFA.该算法既兼顾了搜索空间的多样性以利于全局搜索,又能对有前途的局部区域进行精细搜索以找到相应的局部最优解.同时,在计算过程中引入禁忌技术和跳坑策略,以提高算法的求解质量.对国际上11个代表性的算例进行了计算,QPCFA更新了其中7个算例的最好记录,其余4个与目前的最好记录基本持平,且与目前的最好结果相比在计算精度上均有较大的提高.

英文摘要:

The circles packing problem with constraints of equilibrium, as a two-dimensional packing problem with the background of satellite module layout design, is an NP hard layout op- timization problem. A mathematical model and two new physical models are established for this problem. And inspired by the process of coarse and fine adjustment in the industry, a Quasi- Physical algorithm based on Coarse and Fine Adjustment (QPCFA) is proposed. Not only can QPCFA keep the diversity of the searching space to facilitate the global search, but also it can do fine search in promising local areas to find the corresponding local optimal solutions. Moreover, the taboo method and the jump pit strategy are combined to improve the performance of this algo- rithm. Experiments on 11 representative instances show that QPCFA achieve new and better results on seven ones and matched the current best records on the other four. In addition, the calculation accuracy is improved considerably.

同期刊论文项目
期刊论文 38 会议论文 6
同项目期刊论文
期刊信息
  • 《计算机学报》
  • 北大核心期刊(2011版)
  • 主管单位:中国科学院
  • 主办单位:中国计算机学会 中国科学院计算技术研究所
  • 主编:孙凝晖
  • 地址:北京中关村科学院南路6号
  • 邮编:100190
  • 邮箱:cjc@ict.ac.cn
  • 电话:010-62620695
  • 国际标准刊号:ISSN:0254-4164
  • 国内统一刊号:ISSN:11-1826/TP
  • 邮发代号:2-833
  • 获奖情况:
  • 中国期刊方阵“双效”期刊
  • 国内外数据库收录:
  • 美国数学评论(网络版),荷兰文摘与引文数据库,美国工程索引,美国剑桥科学文摘,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊(2004版),中国北大核心期刊(2008版),中国北大核心期刊(2011版),中国北大核心期刊(2014版),中国北大核心期刊(2000版)
  • 被引量:48433