【摘 要】
：
随着信息技术的发展,各类复杂网络层出不穷,识别网络中的关键节点可以在一定程度上帮助了解网络特性,维护网络的结构和功能。关键节点问题（CNP）是NP难组合优化问题,对该问题的研究有着重要的理论价值和应用价值。关键节点问题在于移除图中的某些节点,使得剩余图满足预定义的连通性度量。目前针对CNP问题的算法存在运行时间较久或迭代较多、准确性不够的问题,仍需要进一步的改进与研究。针对6类CNP问题中关注较多
论文部分内容阅读
随着信息技术的发展,各类复杂网络层出不穷,识别网络中的关键节点可以在一定程度上帮助了解网络特性,维护网络的结构和功能。关键节点问题（CNP）是NP难组合优化问题,对该问题的研究有着重要的理论价值和应用价值。关键节点问题在于移除图中的某些节点,使得剩余图满足预定义的连通性度量。目前针对CNP问题的算法存在运行时间较久或迭代较多、准确性不够的问题,仍需要进一步的改进与研究。针对6类CNP问题中关注较多的CNP2b（又叫做CC-CNP）问题,本文基于局部搜索算法和遗传策略进行了研究探索,主要创新性及贡献如下:（1）提出了一种求解关键节点问题的多阶段局部搜索算法MSLS（a multistage local search algorithm for critical node problem）。该算法采用的两种关键性技术为“循环删点”和禁忌搜索FIFO原则。“循环删点”过程通过贪婪法不断删点,直到当前解不满足可行解的条件;“换点”过程通过禁忌搜索选择剩余图中优先级最高的一个点加入当前解。实验结果表明:禁忌搜索策略相较于随机加点可以更好地提升解质量,加快运算速度;MSLS局部搜索算法相较于最新的两种局部搜索算法求解质量更优,在真实网络图上求解速度更快。（2）提出了一种结合遗传算法（GA）和上述多阶段局部搜索算法MSLS的GAMSLS（a genetic algorithm with a multistage local search algorithm for critical node problem）算法。该算法整体采用遗传算法框架,基于MSLS局部搜索算法对初始解进行提升,并创新性地将节点数目减少这一操作放在交叉过程实现,同时采用新的更新策略更新种群。最后在三类不同的网络图上与最新的基准算法进行了对比,证明了GAMSLS算法的有效性。
其他文献
近年来,海洋环境保护、资源的开发利用等需求越来越高,水下无线传感器网络作为探索和利用海洋的关键技术之一,也成为了一个研究热点。而水下传感器网络节点的位置信息是网络能够有效工作的关键之一。水下环境由于水流等因素比陆地环境更为复杂,且由于射频信号在水下传输衰减过大,不能用于水下信息的中长距离传输,只能考虑水声,因此,陆地无线传感器网络的技术不能直接应用于水下传感器网络。水下节点定位的主要问题:一是节点
图像匹配通过特征检测和描述,寻找不同图像的相同区域,从而完成识别、配准和检索等任务。本文主要针对无人机视觉导航任务,传统图像匹配方法SIFT在困难条件下（如图像模糊）匹配性能不足等问题开展研究。考虑到基于卷积神经网络（CNN）的学习型描述子具有更大的描述区域以及对困难条件的强适应能力,与SIFT手工设计描述子性能互补。本文基于传统和深度特征相结合的SIFT-HardNet方法,针对SIFT-Har
非聚焦模糊区域检测是为了检测图像中非聚焦模糊区域和聚焦清晰区域,是一种像素级任务,在自动聚焦、图像恢复等计算机视觉领域有着广泛的应用。近年来,深度卷积神经网络在非聚焦模糊检测任务中展示出了强大的特征提取能力,取得了很大的进展。然而,大多数基于卷积神经网络的方法总是依赖于昂贵的像素级标签。为了降低标签成本,本文提出利用框级标签完成像素级的非聚焦模糊检测任务。框级标签能够提供非聚焦区域大致位置的线索,
深层抗滑稳定分析是重力坝抗震计算中的一项重要内容,采用有限元方法进行深层抗滑稳定计算需要在计算模型中预先设置滑动面,当重力坝坝基深层存在多个缓倾角和软弱结构面时,不仅整个有限元模型建模和网格剖分将面对较大的困难,而且会面临局部单元质量降低的问题。本文提出了一种基于BP神经网络的重力坝深层抗滑稳定有限元分析方法。该方法无需在有限元计算模型中设置滑动面,结合BP神经网络算法根据坝基深层空间应力关系拟合
六足机器人作为一类高冗余、多自由度的足式机器人,在适应性、可靠性、运动性能等方面具有其他类型机器人无法比拟的优势,但是过于复杂的非线性结构为六足机器人运动控制与步态规划研究带来了挑战。为了保证六足机器人运动控制的准确性,提高六足机器人环境适应能力,进而实现六足机器人完全自主行走,六足机器人的步态规划与控制问题成为近十年来足式机器人研究领域的关键问题。本文首先对六足机器人国内外研究现状进行了分析,从
移动通信和互联网技术的普及给人们通信生活带来极大便利的同时,也使得通信隐私问题越来越受关注,以隐蔽安全通信为目的的信息隐藏技术研究也越来越多,作为其对抗技术,信息隐藏分析技术的研究也愈受重视。随着近年来深度学习与图像信息隐藏分析技术的结合,信息隐藏分析检测性能越来越好,但目前深度信息隐藏分析模型研究主要集中于数据匹配条件下性能提升,本文面向数据源失配场景和模型效率提升,进行了以下方面的研究:在空域
时间序列模型运用数据信息开展系统状态的预测与分析,在工业、经济和医疗等诸多领域取得了广泛的应用。随着建模数据规模和复杂程度的日益加剧,人们希望时间序列模型不仅能够预测未来时刻的信息,还能提供考察对象在某一时间段内的变化趋势,进而对模型结果提供一定的语义解释。本文将使用信息粒化技术探讨时间序列数据的粒度表示、区间时间序列的建模和预测结果的评估等内容,主要工作包括:首先,运用信息粒化技术将时间序列数据
21世纪以来,随着计算机运算能力的大幅度提高,神经网络在诸如土木工程、生物学、图像识别等多种领域中得到了越来越多的重视。近些年,众多行业和领域在机器学习研究中也投入了越来越多的精力和资金,在作为世界经济发展的支柱型行业之一的建筑与土木工程领域中,传统计算技术正在与机器学习算法相融合,从而推动技术进步和基础产业的升级换代。另一方面,比例边界有限元方法作为一种新发展的半解析计算科学,其与机器学习的结合
交通标志检测技术是目标检测领域的一个热点和难点。实际场景中,道路街景复杂多样,交通标志在整张图片中的占比非常小,在进行特征提取时交通标志自身的特征往往会被周围的背景和其他小尺寸目标,例如广告牌等物体不断稀释,导致实际场景中检测效果较差。另外,交通标志检测系统通常搭载在智能汽车等移动平台上,需要在极低时延内对前方标志做出快速准确地识别,而现有方法很难在检测精度和检测速度上做到均衡。针对上述问题,本文
智能决策是人工智能领域的重要发展方向之一,可在博弈环境中基于强化学习方法来实现。传统强化学习方法中一般将参与交互的其他智能体即对手看作环境的一部分,由于未考虑对手的行为特征,可能会导致误判而影响决策结果。因此对博弈中参与交互的对手进行建模成为研究的一个热点问题。当前的对手建模技术多数都着眼于固定的对手策略,而在现实中的对手策略通常是动态变化的。采取动态策略的对手智能体在博弈时,其策略的变化会导致智