求解等圆Packing问题的快速优化算法研究

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:zhoulinqin274385037
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
圆形Packing问题是一个典型的布局优化问题,也是一个有代表性的NP难度问题,NP难度问题是现代计算机科学中难于求解的一类问题,对于该类问题,目前尚不存在经典数学要求的既精确完整又快速有效的求解算法,设计高效非完整启发式算法对该类问题进行近似求解有着十分重要的实际意义。不同于国际上求解NP难度问题的已知流行算法,针对等圆Packing问题,找到了该问题的一个非常贴切的模拟大自然物质受力运动模型,采用拟物算法对其进行求解,实践证明,对于等圆Packing问题的求解,拟物算法是十分快速高效的。为了进一步提高拟物算法的效率,提出提前退出局部搜索策略、最优步长法策略等方法对拟物算法进行有效改进,提前退出局部搜索策略不断估算当前搜索路径成功的概率,如果概率太小,则提前终止对当前路径的局部搜索,可以节省大量的计算时间。最优步长法在搜索计算的过程中不断调整步长,以使计算获得较快的收敛速度。针对等圆Packing问题如何逃离“局部最小值陷阱”的问题,在拟物算法的基础上提出了“找最大空区域中心点方法”、“单点黑洞引力方法”等几种拟人策略,并将拟物算法和拟人策略结合起来,提出概率选择形式算法,该算法根据当前格局情况以概率形式选择某种具体拟人策略以逃离当前“局部最小值陷阱”。通过大量计算实验分析了概率选择形式算法在等圆Packing问题算法试金石上的表现。并将计算结果和国内外其他研究者对该问题的研究结果作了简单比较。
其他文献
随着科学技术的发展,计算机和信息技术全方位、多角度冲击着社会生活的各个层面,深刻地影响着全球政治、经济、法律以及人们的生活。与此同时,与计算机和网络相关的各类纠纷日渐
学位
随着Internet的不断发展,网络技术给人们的工作和生活带来种种便捷,但同时也带来许多安全威胁。在与攻击者不断斗争的过程中,众多安全机构研发了许多安全产品。然而传统的安全技
在P2P流媒体系统中,多播日益受到研究者的关注。多播的一个重要问题在于多播路径的确定,通常是构建一棵以源节点为根,包含所有参与多播节点的生成树。多播路由是系统中网络层
近年来,随着运动捕获技术的发展,大量的具有较强真实感的人体运动捕获数据被生成并广泛地应用于计算机动画制作的各个领域。但随之而起的问题是如何更方便、高效地利用运动捕
随着视频搜索技术的发展,基于内容的视频搜索近年来受到越来越多的学者关注。通用视频索引往往只使用视频图片的低层特征,对图片内容描述不够充分,搜索结果不太理想。为解决
主题搜索引擎是针对某一个行业的专业搜索引擎,是搜索引擎的细分和延伸,是对网页库中的某类专门的信息进行一次整合。其中的关键技术包括中文分词、主题爬虫、索引、分布式存
随着数据库和移动通信技术的飞速发展,用户需要在任何时候和任何地点都能通过网络获得信息。同时,用户对数据处理的需求不断提高,并且要求能够在限定时间内得到响应,与各种移
随着计算机和网络的发展,企业机房里的服务器数量也迅速地增长着,要方便、快捷地维护好这些服务器也变得越来越难。为了能方便机房管理员对服务器进行维护,研究和实现了一种
随着计算机技术和网络通讯技术的日益发展,大量数据涌到人们面前。如何有效地选择需要的信息成为了越来越突出的问题,数据挖掘技术就是顺应这种需要而发展起来。分类技术作为
近年来,随着人们生活质量水平的提高和计算机技术、通信技术及多媒体技术的发展,智能视频监控系统的应用日益广泛。但目前的智能视频监控系统大多是基于PC架构的,具有监控场景布