第４０卷 第４期
２０１２年 ４月
华 中 科 技 大 学 学 报 （自 然 科 学 版）
Ｊ ．Ｈｕａｚｈｏｎｇ Ｕｎｉｖ ．ｏｆ Ｓｃｉ ．＆ Ｔｅｃｈ ．（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ）
Ｖｏｌ ．４０ Ｎｏ ．４
Ａｐｒ ． ２０１２
收稿日期 ２０１１‐０４‐０１ ．
作者简介 黄文奇（１９３８‐） ，男 ，教授 ，Ｅ‐ｍａｉｌ ：ｗｑｈｕａｎｇ＠ ｍａｉｌ ．ｈｕｓｔ ．ｅｄｕ ．ｃｎ ．
基金项目 国家自然科学基金资助项目 （６０７７３１９４ ，６１０７０２３５） ．
不 等 圆 Ｐａｃｋｉｎｇ 问 题 的 拟 物 型 邻 域 搜 索 算 法
黄文奇 付樟华 许如初
（华中科技大学计算机科学与技术学院 ，湖北 武汉 ４３００７４）
摘要 将拟物方法与邻域搜索过程结合 ，得到求解不等圆 Ｐａｃｋｉｎｇ 问题的拟物型邻域搜索算法 （ＱＰ‐ＮＳ） ．拟
物方法用于连续优化 ，可从任一初始格局收敛至对应的局部最优格局 ；邻域搜索过程迭代地将当前格局替换
为其邻域中的最优格局 ，直至无法继续改进当前格局为止 ．ＱＰ‐ＮＳ 可在不严重破坏当前格局的前提下稳定地
改进当前格局 ，鲁棒性较强 ．基于 １４ 个国际公开算例的计算实验表明 ：ＱＰ‐ＮＳ 可在 ６０ ｓ 内改进 １０ 个算例的
此前最优解 ，并与其余 ４ 个算例的此前最优解持平 ．
关键词 ＮＰ 难问题 ；拟物方法 ；组合优化 ；装填问题 ；启发式 ；邻域搜索
中图分类号 ＴＰ３０１ ．５ ；ＴＰ３０１ ．６ 文献标志码 Ａ 文章编号 １６７１‐４５１２（２０１２）０４‐０００１‐０４
Ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ａｓｓｏｃｉａｔｅｄ ｗｉｔｈ Ｑｕａｓｉ‐
ｐ
ｈｙｓｉｃａｌ
ｍｅｔｈｏｄ ｆｏｒ ｓｏｌｖｉｎｇ ｕｎｅｑｕａｌ ｃｉｒｃｌｅ Ｐａｃｋｉｎｇ ｐｒｏｂｌｅｍ
Ｈ ｕａｎ
ｇ
Ｗ ｅｎ
ｑ
ｉ Ｆｕ Ｚｈａｎ
ｇ
ｈｕａ Ｘ ｕ Ｒｕｃｈｕ
（Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ，Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ
Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ，Ｗｕｈａｎ ４３００７４ ，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ Ａ ｈｙｂｒｉｄ ｍｅｔａ‐ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ ＱＰ‐ＮＳ ｗａｓ ｄｅｖｅｌｏｐｅｄ ，ｗｈｉｃｈ ｃｏｎｓｉｓｔｅｄ ｏｆ ａ Ｑｕａｓｉ‐
ｐ
ｈｙｓｉｃａｌ ｍｅｔｈｏｄ ａｎｄ ａ ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｅａｒｃｈ ｐｒｏｃｅｄｕｒｅ ，ｔｏ ｓｏｌｖｅ ｔｈｅ ｔｗｏ‐ｄｉｍｅｎｓｉｏｎａｌ ｕｎｅｑｕａｌ ｃｉｒｃｌｅ
ｐ
ａｃｋｉｎｇ ｐｒｏｂｌｅｍ ．Ｔｈｅ Ｑｕａｓｉ‐
ｐ
ｈｙｓｉｃａｌ ｍｅｔｈｏｄ ｗａｓ ｕｓｅｄ ｔｏ ｏｂｔａｉｎ ａ ｌｏｃａｌ ｏｐｔｉｍａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｆｒｏｍ ａｎ
ｉｎｉｔｉａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ ．Ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｅａｒｃｈ ｐｒｏｃｅｄｕｒｅ ｉｔｅｒａｔｉｖｅｌｙ ｕｐｄａｔｅｄ ｔｈｅ ｉｎｃｕｍｂｅｎｔ ｃｏｎｆｉｇｕｒａ‐
ｔｉｏｎ ｗｉｔｈ ｉｔｓ ｂｅｓｔ ｎｅｉｇｈｂｏｒｉｎｇ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｕｎｔｉｌ ｔｈｅ ｓｔｏｐ ｃｒｉｔｅｒｉｏｎ ｗａｓ ｍｅｔ ．Ｔ ｈｅ ｐｒｏｐｏｓｅｄ ａｐｐｒｏａｃｈ
ｗａｓ ｖｅｒｙ ｒｏｂｕｓｔ ，ｂｅｃａｕｓｅ ｔｈｅ ｈｉｇｈ‐
ｑ
ｕａｌｉｔｙ ｓｏｌｕｔｉｏｎｓ ｈａｄ ｍｕｃｈ ｍｏｒｅ ｏｐｐｏｒｔｕｎｉｔｙ ｔｏ ｂｅ ａｃｃｅｐｔｅｄ ｔｈａｎ
ｌｏｗ‐
ｑ
ｕａｌｉｔｙ ｏｎｅｓ ．Ｅｘｐｅｒｉｍｅｎｔｓ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ＱＰ‐ＮＳ ｐｒｏｄｕｃｅｓ ｖｅｒｙ ｃｏｍｐｅｔｉｔｉｖｅ ｒｅｓｕｌｔｓ ｗｉｔｈ ｒｅ‐
ｓｐｅｃｔ ｔｏ ｔｈｅ ｒｅｓｕｌｔｓ ｒｅｐｏｒｔｅｄ ｂｙ ｐｒｅｖｉｏｕｓ ｌｉｔｅｒａｔｕｒｅ ，ｉｎ ｔｅｒｍｓ ｏｆ ｂｏｔｈ ｓｏｌｕｔｉｏｎ ｑｕａｌｉｔｙ ａｎｄ ｒｕｎｔｉｍｅ ．Ｆｏｒ
１４ ｒｅｐｒｅｓｅｎｔａｔｉｖｅ ｉｎｓｔａｎｃｅｓ ｔａｋｅｎ ｆｒｏｍ ｔｈｅ ｌｉｔｅｒａｔｕｒｅ ，ＱＰ‐ＮＳ ｓｕｃｃｅｅｄｓ ｉｎ ｉｍｐｒｏｖｉｎｇ １０ ｂｅｓｔ ｋｎｏｗｎ ｒｅ‐
ｓｕｌｔｓ ａｎｄ ｍａｔｃｈｉｎｇ ａｌｌ ｔｈｅ ｌｅｆｔ ４ ｂｅｓｔ ｋｎｏｗ ｎ ｒｅｓｕｌｔｓ ｗｉｔｈｉｎ ６０ ｓ ．
Ｋｅｙ ｗｏｒｄｓ ＮＰ‐ｈａｒｄ ｐｒｏｂｌｅｍ ； Ｑｕａｓｉ‐
ｐ
ｈｙｓｉｃａｌ （ＱＰ ） ｍｅｔｈｏｄ ； ｃｏｍｂｉｎａｔｏｒｙ ｏｐｔｉｍｉｚａｔｉｏｎ ；
ｐ
ａｃｋｉｎｇ
ｐ
ｒｏｂｌｅｍ ；ｈｅｕｒｉｓｔｉｃ ；ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｅａｒｃｈ （ＮＳ）
圆形 Ｐａｃｋｉｎｇ 问题是一类典型的 ＮＰ 难问
题 ，具有重要的理论价值 ，并在无线通信 、材料切
割 、轮船运输 、航天器设计等领域有着广泛的应用
背景 ．圆形 Ｐａｃｋｉｎｇ 问题的一般形式为 ：给定若干
个半径已知的圆形（或球形）物体 ，要求将其互不
重叠地置入一个特定形状的大容器中 ，使得空间
利用率尽可能高
［１］
．本课题研究大容器为圆形时
的二维不等圆 Ｐａｃｋｉｎｇ 问题（简称不等圆 Ｐａｃｋｉｎｇ
问题） ，希望能设计出高性能的求解算法 ．
现有的不等圆 Ｐａｃｋｉｎｇ 问题求解算法几乎均
为启发式算法 ，并可大致分为 ２ 大类 ：ａ ．基于构
造规则的构造型算法 ；ｂ ．基于连续优化方法和格
资源评论
