最大独立集和最小弱顶点覆盖问题求解及其应用研究

来源 :江南大学 | 被引量 : 0次 | 上传用户:suzengbiao
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
全局优化问题,特别是组合优化问题,是科学研究与工程计算中最基本的问题之一,这类问题的求解一直是算法研究领域的热点问题。全局优化方法一般分为确定型和随机型方法,确定型方法在数学理论上较为完善,但难以应用,而传统的随机型方法对于复杂的全局优化问题又难以解决,这时启发式算法的引入使得随机型方法和整个全局优化方法得到了新的发展,尤其是元启发式算法。蚁群优化算法(Ant Colony Optimization,简称ACO)作为一种新的元启发式算法,具有分布式计算、自组织、正反馈以及贪心启发等特点,使其能够成功解决许多NP-hard组合优化问题。ACO算法作为一种全局搜索算法,其全局优化性能的优劣在很大程度上与参数的正确选择有关。但由于ACO算法参数之间的关联性,使得最优参数组合成为一个极其复杂的优化问题,目前还没有形成完善的理论依据,一般都是根据经验来确定参数值。而禁忌搜索算法(Tabu Search,简称TS)以其灵活的禁忌表和相应的禁忌准则来避免重复迂回搜索,具有强大的全局优化性能。所以为弥补ACO算法易出现停滞现象和陷入局部最优这一缺陷,本文将ACO算法与TS算法组合起来,提出了基于禁忌搜索的蚁群优化算法(Tabu Search Based Ant Colony Optimization,简称TSBACO),并将该算法用于求解最大独立集问题。实验表明:禁忌搜索策略的引入,不仅提高了TSBACO算法的全局优化性能而且还提高了搜索效率。为了增强超大规模集成电路(VLSI)系统运行时的可靠性与稳定性,需要在电路设计中引入容错技术增强系统的容错能力。在VLSI阵列的容错技术中,一般有冗余法和降阶法两种重构方法,这两种方法都属于NP-hard问题。本文是通过冗余法来解决这一问题的,根据阵列中缺陷单元的分布情况,构造相应的矛盾图模型,将阵列的重构问题转化为求解矛盾图的独立集问题。通过TSBACO算法对矛盾图的独立集进行求解且使得所求独立集大小恰为缺陷单元个数,找出合理的补偿通道来完成阵列的重构问题。实验分析表明该重构方法是简单有效的。为进一步验证TSBACO算法在求解组合优化问题方面的实用性和有效性,本文将其应用于网络流量测量中的有效测量点选择问题。通过对图论中最小顶点覆盖模型的研究,网络流量测量点选择问题可以抽象为最小弱顶点覆盖问题,而求解该问题是一个NP-hard问题,于是本文又提出了一种求解最小弱顶点覆盖问题的TSBACO算法。比较现有的求解算法,实验结果表明:本文提出的TSBACO算法能够发现更小的弱顶点覆盖集,且具有更好的可扩展性,是网络流量测量中的一种有效测量点选择算法。
其他文献
城市供水设施是一个具有复杂的空间和非空间信息的纵横交错的巨大网络,行业中存在着地上地下资产难以管理维护等问题。本文简述了GIS的发展历史和GIS的技术体系,利用SuperMap的
传统的财务管理系统发挥计算机系统的处理能力,降低财务管理工作强度,使财务部门及其他部门的预算信息充分沟通,确保学校资金能够科学、合理的使用,大大提高财务人员的工作水平和
在一个P2P文件共享系统中,终端用户节点(Peer)通过Internet完成文件交换。一个P2P文件共享系统,需要解决两个方面的问题:文件搜索和文件传送。由于P2P系统本身的分布式存储特
云计算门户是云计算平台的人机交互入口,它能聚合原有门户网站的信息资源,支持各种移动平台终端和浏览器的访问。用户可通过云计算门户与原有门户网站的交互,实现原有门户网站数
由于城市地下管线的增多和各大城市地铁建设的加快,道路塌陷的事故越来越多的发生在我们的生活中,逐渐成为城市生活中一个看不到的隐患,随时对人民的生活产生着威胁。人们对城市
人脸验证是计算机识别领域非常活跃的研究课题,它包括三个主要技术环节,即预处理、人脸特征提取和分类器设计。人脸特征提取又称为人脸表述,是在低维特征空间内对原高维空间
随着数据时代的到来,各行各业所产生的数据呈指数级增长,数据的多样性和爆发式增长给数据存储和传输带来了巨大压力,严重阻碍了高性能计算在科学领域的运用和发展。数据压缩一直
目前,能否有效解决在软件项目开发及维护过程中出现的各种各样的问题已成为影响软件项目成败的重要因素,因此,有必要结合现代项目管理知识和企业问题管理模式对软件项目问题进行
随着我国经济建设的快速发展,国家对基础设施建设投入逐步增大。与此同时,大型工程项目中各种复杂的项目信息、数据需要动态管理,以实现各成员之间的资源共享、任务分配、协