主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
何琨,杨辰凯,黄梦龙,黄文奇.动作空间带平衡约束圆形Packing问题的拟物求解算法.软件学报,2016,27(9):2218-2229
动作空间带平衡约束圆形Packing问题的拟物求解算法
Quasi-Physical Algorithm Based on Action Space for Solving the Circles Packing Problem with Equilibrium Constraints
投稿时间:2014-02-18  修订日期:2014-04-17
DOI:10.13328/j.cnki.jos.004848
中文关键词:  NP难度  圆形Packing  拟物  动作空间  平衡约束
英文关键词:NP-hard  circle packing  quasi-physics  action space  equilibrium constraints
基金项目:国家自然科学基金(61173180,61272014)
作者单位E-mail
何琨 华中科技大学 计算机科学与技术学院, 湖北 武汉 430074 brooklet60@gmail.com 
杨辰凯 华中科技大学 计算机科学与技术学院, 湖北 武汉 430074  
黄梦龙 华中科技大学 计算机科学与技术学院, 湖北 武汉 430074  
黄文奇 华中科技大学 计算机科学与技术学院, 湖北 武汉 430074  
摘要点击次数: 856
全文下载次数: 1049
中文摘要:
      对于一个以卫星舱内设备布局为背景的具有NP难度的全局优化问题——带平衡约束的圆形Packing问题,提出了基于动作空间的拟物求解算法.在拟物下降遇到局部极小点的陷阱时,如何找到当前格局下的最空闲空间以使搜索过程跳到更有前景的区域去是设计跳坑策略的一个关键难点.借鉴求解矩形Packing问题中动作空间的概念,通过化“圆”为“方”,将不规则的空闲空间近似为一系列规则的矩形空间,从而有效地解决了此难点.另外,将拟物法与提前中止、粗精调和自适应步长这3个拟人辅助策略相结合,以提高势能下降的效率.对3组共13个代表性算例的计算结果及与国内外代表性算法的比较表明,所提格局的外包络圆半径多为最小或次小,且在部分算例上找到了有更小外包络圆半径的格局,总体计算结果较好,且静不平衡量的精度较高.
英文摘要:
      This paper proposes a Quasi-physical algorithm based on action space (QPAS) for an NP-hard global optimization problem-the circle packing problem with equilibrium constraints (CPPEC). The algorithm has important applications for the layout design of the satellite modules. A key issue in designing a good basin hopping strategy for CPPEC is how to find the most vacant areas such that the searching procedure can jump from a local minimum basin to a promising area. By borrowing the concept of "action space" proposed for the rectangular packing problem, the new algorithm approximates each circle as a rectangle and the irregular vacant areas are viewed approximately as regular rectangular areas. Consequently the most vacant areas can be found efficiently and accurately. In addition, three quasi-human strategies, namely early termination, coarse-to-fine and adaptive step length, are combined with the quasi-physical approach to speed up the potential energy descending process. Experiments are performed on 13 benchmark instances, and computational results demonstrate the high efficiency of the proposed approach. QPAS achieves the first or the second best results on most instances compared with other algorithms, and in some configurations, it has smaller container radius than the current best results. Meanwhile, QPAS obtains very small equilibrium deviations.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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