动作空间带平衡约束圆形Packing问题的拟物求解算法

发布时间：2017-10-30 11:03

  本文关键词：动作空间带平衡约束圆形Packing问题的拟物求解算法

  更多相关文章： NP难度 圆形Packing 拟物 动作空间 平衡约束

【摘要】：对于一个以卫星舱内设备布局为背景的具有NP难度的全局优化问题——带平衡约束的圆形Packing问题,提出了基于动作空间的拟物求解算法.在拟物下降遇到局部极小点的陷阱时,如何找到当前格局下的最空闲空间以使搜索过程跳到更有前景的区域去是设计跳坑策略的一个关键难点.借鉴求解矩形Packing问题中动作空间的概念,通过化"圆"为"方",将不规则的空闲空间近似为一系列规则的矩形空间,从而有效地解决了此难点.另外,将拟物法与提前中止、粗精调和自适应步长这3个拟人辅助策略相结合,以提高势能下降的效率.对3组共13个代表性算例的计算结果及与国内外代表性算法的比较表明,所提格局的外包络圆半径多为最小或次小,且在部分算例上找到了有更小外包络圆半径的格局,总体计算结果较好,且静不平衡量的精度较高.
【作者单位】： 华中科技大学计算机科学与技术学院;
【关键词】： NP难度 圆形Packing 拟物 动作空间 平衡约束
【基金】：国家自然科学基金(61173180,61272014)~~
【分类号】：TP301.6
【正文快照】： 圆形Packing问题是高复杂度典型的NP难度问题,在无线通信、航空航天及交通运输等领域均有着广泛的应用.随着问题规模的增大,问题的解空间呈指数级膨胀,使得精确算法的求解时间过长而不适于实际应用.国内外研究者多采用启发式方法求解此类问题,如拟物算法[1,2]、禁忌算法[3,4]

【相似文献】

中国期刊全文数据库 前1条

1 黄文奇,赵孝武;求解正交数组问题的拟物拟人算法[J];计算机研究与发展;2002年02期

中国博士学位论文全文数据库 前1条

1 赵孝武;求解正交表问题的拟物拟人方法[D];中国科学院软件研究所;2001年

中国硕士学位论文全文数据库 前3条

1 杨辰凯;求解带平衡约束的圆形Packing问题的拟物拟人算法[D];华中科技大学;2013年

2 苏梅瑞;基于密度扩散策略的纯粹拟物算法研究与应用[D];华中科技大学;2008年

3 付樟华;求解等圆packing问题的拟物拟人算法[D];华中科技大学;2007年

，

本文编号：1117380