没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
将拟物方法与邻域搜索过程结合,得到求解不等圆Packing问题的拟物型邻域搜索算法(QP-NS) .拟物方法用于连续优化,可从任一初始格局收敛至对应的局部最优格局;邻域搜索过程迭代地将当前格局替换为其邻域中的最优格局,直至无法继续改进当前格局为止.QP- NS可在不严重破坏当前格局的前提下稳定地改进当前格局,鲁棒性较强.基于14个国际公开算例的计算实验表明:QP-NS可在60 s内改进10个算例的此前最优解,并与其余4个算例的此前最优解持平.
资源推荐
资源详情
资源评论
第40卷 第4期
2012年 4月
华 中 科 技 大 学 学 报 (自 然 科 学 版)
J .Huazhong Univ .of Sci .& Tech .(Natural Science Edition)
Vol .40 No .4
Apr . 2012
收稿日期 2011‐04‐01 .
作者简介 黄文奇(1938‐) ,男 ,教授 ,E‐mail :wqhuang@ mail .hust .edu .cn .
基金项目 国家自然科学基金资助项目 (60773194 ,61070235) .
不 等 圆 Packing 问 题 的 拟 物 型 邻 域 搜 索 算 法
黄文奇 付樟华 许如初
(华中科技大学计算机科学与技术学院 ,湖北 武汉 430074)
摘要 将拟物方法与邻域搜索过程结合 ,得到求解不等圆 Packing 问题的拟物型邻域搜索算法 (QP‐NS) .拟
物方法用于连续优化 ,可从任一初始格局收敛至对应的局部最优格局 ;邻域搜索过程迭代地将当前格局替换
为其邻域中的最优格局 ,直至无法继续改进当前格局为止 .QP‐NS 可在不严重破坏当前格局的前提下稳定地
改进当前格局 ,鲁棒性较强 .基于 14 个国际公开算例的计算实验表明 :QP‐NS 可在 60 s 内改进 10 个算例的
此前最优解 ,并与其余 4 个算例的此前最优解持平 .
关键词 NP 难问题 ;拟物方法 ;组合优化 ;装填问题 ;启发式 ;邻域搜索
中图分类号 TP301 .5 ;TP301 .6 文献标志码 A 文章编号 1671‐4512(2012)04‐0001‐04
Neighborhood search algorithm associated with Quasi‐
p
hysical
method for solving unequal circle Packing problem
H uan
g
W en
q
i Fu Zhan
g
hua X u Ruchu
(School of Computer Science and Technology ,Huazhong University of
Science and Technology ,Wuhan 430074 ,China)
Abstract A hybrid meta‐heuristic algorithm called QP‐NS was developed ,which consisted of a Quasi‐
p
hysical method and a neighborhood search procedure ,to solve the two‐dimensional unequal circle
p
acking problem .The Quasi‐
p
hysical method was used to obtain a local optimal configuration from an
initial configuration .The neighborhood search procedure iteratively updated the incumbent configura‐
tion with its best neighboring configuration until the stop criterion was met .T he proposed approach
was very robust ,because the high‐
q
uality solutions had much more opportunity to be accepted than
low‐
q
uality ones .Experiments results show that QP‐NS produces very competitive results with re‐
spect to the results reported by previous literature ,in terms of both solution quality and runtime .For
14 representative instances taken from the literature ,QP‐NS succeeds in improving 10 best known re‐
sults and matching all the left 4 best know n results within 60 s .
Key words NP‐hard problem ; Quasi‐
p
hysical (QP ) method ; combinatory optimization ;
p
acking
p
roblem ;heuristic ;neighborhood search (NS)
圆形 Packing 问题是一类典型的 NP 难问
题 ,具有重要的理论价值 ,并在无线通信 、材料切
割 、轮船运输 、航天器设计等领域有着广泛的应用
背景 .圆形 Packing 问题的一般形式为 :给定若干
个半径已知的圆形(或球形)物体 ,要求将其互不
重叠地置入一个特定形状的大容器中 ,使得空间
利用率尽可能高
[1]
.本课题研究大容器为圆形时
的二维不等圆 Packing 问题(简称不等圆 Packing
问题) ,希望能设计出高性能的求解算法 .
现有的不等圆 Packing 问题求解算法几乎均
为启发式算法 ,并可大致分为 2 大类 :a .基于构
造规则的构造型算法 ;b .基于连续优化方法和格
资源评论
weixin_38633157
- 粉丝: 5
- 资源: 968
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 共创在线考试系统(JSP+SERVLET)130223.rar
- 俄罗斯方块(java+applet)130228.rar
- 会员管理系统(struts+hibernate+spring)130226.rar
- 会员管理系统(struts+hibernate+spring).rar
- 基于J2EE在分布式环境下的底层结构(外文翻译+文献综述).rar
- 基于JSP的畅想空间电子商务系统.rar
- 基于JSP的网上购物系统的设计与实现(源代码+论文).rar
- 基于JSP的房产中介系统的设计与实现(源代码+论文).rar
- 基于JSP电子商务系统?(论文).rar
- 基于jsp的新闻发布系统(论文).rar
- 基于matlab的数字图像分割技术研究及实现(论文).rar
- 基于jsp网上书店(源代码+论文).rar
- 计算器(java+applet)130228.rar
- 家庭理财系统(java+applet)130227.rar
- 教材订购系统(jsp+servlet+mysql).rar
- 教材订购系统(jsp+servlet+mysql)130226.rar
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功