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

• 作者: 何琨 杨辰凯 黄文奇 黄梦龙
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: NP难度 圆形Packing 拟物 动作空间 平衡约束
• 年，卷（期）: 2016,（9）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 2218-2229
• 页数: 12页
• 分类号: TP301
• 字数: 8964字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.004848

摘要

对于一个以卫星舱内设备布局为背景的具有NP难度的全局优化问题——带平衡约束的圆形Packing问题提出了基于动作空间的拟物求解算法.在拟物下降遇到局部极小点的陷阱时,如何找到当前格局下的最空闲空间以使搜索过程跳到更有前景的区域去是设计跳坑策略的一个关键难点.借鉴求解矩形Packing问题中动作空间的概念通过化“圆”为“方”,将不规则的空闲空间近似为一系列规则的矩形空间,从而有效地解决了此难点.另外,将拟物法与提前中止、粗精调和自适应步长这3个拟人辅助策略相结合,以提高势能下降的效率.对3组共13个代表性算例的计算结果及与国内外代表性算法的比较表明,所提格局的外包络圆半径多为最小或次小,且在部分算例上找到了有更小外包络圆半径的格局,总体计算结果较好,且静不平衡量的精度较高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄文奇	华中科技大学计算机科学与技术学院	88	1090	21.0	27.0
2	何琨	华中科技大学计算机科学与技术学院	31	263	10.0	16.0
3	杨辰凯	华中科技大学计算机科学与技术学院	1	4	1.0	1.0
4	黄梦龙	华中科技大学计算机科学与技术学院	1	4	1.0	1.0