求解最小支配集问题的禁忌遗传混合算法

将最小支配集问题转换为一系列判定问题k支配集问题,并提出一种禁忌遗传混合算法对k-DS问题进行求解。此算法将禁忌搜索算法和遗传算法两种启发式算法结合起来,互补不足。高效的邻域结构保证了算法的运行效率,禁忌策略防止算法过早陷入局部最优陷阱,遗传算法框架进一步增强了算法的疏散性。经过与现有求解最小支配集算法的结果进行分析比较,禁忌遗传混合算法的结果较其它算法更优。

最小支配集问题的活体分子计算模型

生物体内分子网络中信息的传输、储存、放大、整合等大量任务可以看成是一种生物分子计算过程.文中提出了一种活体分子计算模型,借助RNA干扰技术和乳糖操纵子调控模型,在细胞内构建了一个基因网络,用于求解图的最小支配集.该模型展示了利用生物体自身的信息处理能力进行计算的能力,在生物体内建立具有一定智能的分子机器,这将在计算科学、生物学、医学上有着深远的应用前景.

禁忌遗传算法求解最小支配集

如何寻找一个网络图的最小支配集是NP难题。分别设计了逆序启发式算法和禁忌搜索算法,并在此基础上提出了禁忌遗传算法(TSGA)用于求解最小支配集;将禁忌搜索和遗传算法结合起来,弥补了彼此的不足,既有效地避免了算法易陷入局部最优解的缺陷,又加快了算法的收敛速度。经对大量随机网络图的测试和对物流网络选址问题的求解,验证了TSGA算法的优越性。

基于最小支配集组簇的MF路由协议

为了进一步提高容延迟移动传感器网络中的数据投递率、降低平均延迟和能量消耗,提出一种改进的Message Ferry(MF)路由协议MF-MDS。该协议采用最小支配集对网络中的普通节点进行组簇。在NS-2上进行的仿真实验证明MF-MDS在投递率和平均延迟上明显优于传统的MF协议。

基于粗糙集的无向图最小支配集启发式算法

图的最小支配集在许多领域有广泛应用,但其求解是一个NP问题。针对现有近似求解算法的复杂度和精度有待改进的问题,基于粗糙集理论提出一种低复杂度、高精度的最小支配集启发式求解算法。首先,利用图的邻接矩阵构造诱导决策表,证明了图的最小支配集与其诱导决策表的最小属性约简等价。然后,提出一种启发式的最小支配集近似算法。该方法采用前向和后向搜索机制,有效提高了最小支配集求解的近似精度;采用累积策略计算诱导决策表的正域,有效降低了计算复杂度。最后,在公用数据集上与典型算法进行了实验对比分析,结果表明该算法在运行效率方面具有明显优势,能得到更高精度的近似最小支配集,且输出结果具有较好的稳定性。

一种求解最小支配集问题的置信传播算法

最小支配集问题(MDS)是图论中的一个重要问题,在网络资源配置中有广泛的应用。上述问题是一个NP难问题,传统的启发式算法求解最小支配集问题时速度慢,且易于陷入局部最优解。将上述问题原有的无向图转化为对应的因子图,基于因子图构建最小支配集问题的线性规划方程,将方程代入图模型(GM)中,设计了一种求解最小支配集问题的置信传播算法。当算法收敛时,获得每个节点取值的边缘概率,利用边缘概率高概率地决定最小支配集节点。在随机生成的无向图上进行数值实验,结果表明,算法有效。

求解最小支配集的线性混合整型规划算法

提出了一个高效的求解最小支配集问题的线性混合整数规划算法(MILP)。该算法主要针对最小支配集问题的特点建立整数规划模型,并通过Gurobi求解器进行优化求解。采用当前国际文献公开的共74个算例作为算法测试实验集,与FKW算法、传统的Grandoni算法以及改进的Grandoni算法进行比较。实验结果表明,该算法的计算效率明显优于其它的精确算法,且在所有算例上都能得到精确解。

最小支配阈值集问题的降阶回溯算法

图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出上界子算法、下界子算法和降阶子算法,并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR;最后,通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。

求解最小双连通支配集问题的变邻域禁忌搜索算法

针对经典NP难优化问题——最小双连通支配集问题,提出了一种元启发式求解算法——变邻域禁忌搜索算法。算法将原优化问题的求解转换为一系列判定问题——k双连通支配集问题的求解,使用两种邻域结构更加有效地覆盖解空间,同时使用扰动及禁忌机制帮助算法跳出局部最优陷阱。通过与现有文献中的精确算法、启发式算法在国际文献公开的38个双连通图算例上的实验对比,结果表明变邻域禁忌搜索算法能够有效求解最小双连通支配集问题,可求得所有公开算例的最优解,并且在稠密图中计算效率明显优先于其他算法。

基于SIR模型的最小支配集溯源研究

论文研究了在SIR模型基础上,通过有限的观测者定位谣言爆发来源的估计问题。出于对观测节点遍历性的考虑,论文利用贪婪算法求取图的最小支配集作为观测节点,通过观测节点记录感染信息,然后利用皮尔逊相关系数,计算每个候选节点到观测节点的最短路径和其感染时间序列之间的相关性,相关性最高的判定为源节点。最后在仿真实验中验证了算法的准确性。

区间图最小连通支配集问题的最优算法

针对区间图的最小连通支配集问题,设计简洁的线性算法。对该算法的时间、空间复杂度进行分析,并从实例和理论两方面验证其可行性和有效性。研究结果表明:该算法是线性的,即区间图上可在O(m+n)时间内找到一个最小连通支配集。

基于极大权的最小连通支配集启发式算法

Adhoc无线网络中基于最小连通支配集 (MCDS)的路由是一个引人瞩目的方法 ,文中提出了一种基于极大权的MCDS的启发式算法 ,确保了性能强的主机担任网关节点的角色 ,能更好的协调管理网络中其他的节点 ,从而保持MCDS的相对稳固性并为全网中的广播和路由操作提供一个高效的通信基础 .仿真结果表明 ,该算法能在保证生成权和极大的连通支配集的同时也确保它的极小性 。

移动Ad Hoc网络中最小连通支配集的分布式高效近似算法

提出了一种基于局部最大度数与节点标识号相结合的支配点选择方式,并基于该方式给出了一种计算移动AdHoc网络最小连通支配集的分布式近似算法CDSA,实验显示,CDSA算法生成的连通支配集比文献[3～5]所提出的WL、CBBA及MCDS算法更小。另外,CDSA是一种动态的和基于分布式的算法,因此它不但适用于移动AdHoc网络,也适用于一般网络中的最小连通支配集的近似计算问题。

一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题 ,设计有效的广播算法是一项重要的课题 .文中提出了一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明 .它只需要网络节点具有局部的网络状态信息 ,可伸缩性强 .通过此算法可以在网络中自动形成一个虚拟骨干网 ,从而可为网络中的广播和路由操作提供一个有效的通信基础 .模拟结果表明 ,文中提出的算法求得的连通支配集小 ,能较好地应用于一般网络以及移动自组网络中 .

用马尔科夫模型优化分布式最小连通支配集算法

为了提高无线传感器网络(WSNs)的能量利用效率、延长网络的生存时间,对基于极大独立集的最小连通支配集算法(MISB)进行优化,提出了一种新的算法.本文首先应用离散马尔科夫链为节点建立模型,并且根据模型预测节点的能量消耗;本算法进行多轮选举,每一轮开始时根据节点的度和能量选举支配点,依据模型预测的能量消耗决定本轮的运行时间,本轮运行结束时从新选举支配点,开始新一轮.仿真结果表明,本算法和原算法相比可以更好地平衡网络的能量消耗,提高全网的能量利用率,极大地延长网络的生存时间.

基于最小连通支配集的无线传感网拓扑构建研究

基于通信虚拟主干网的拓扑构建是关闭冗余节点,节省全网能耗的有效方法。该文将全连通网络环境下寻找最优虚拟主干网问题抽象转化成最小连通支配集求解问题(MCDS),并建立了基于混合整数规划的数学模型(NMIP-MCDS)。NMIP-MCDS在分析MCDS解的基础上,确定以令牌分发数与节点能耗乘积为目标的优化函数,通过令牌分发同时辅以全网能量负载均衡的方式,构建最优MCDS。仿真实验结果验证了NMIP-MCDS的有效性,并可进一步实际应用在中等规模的无线传感网中。

基于极大独立集的最小连通支配集的分布式算法

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.

一种求解最小连通支配集的高效近似算法

寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果.

分布式最小连通支配集启发式算法

针对Ad Hoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7.6opt+1.4,时间复杂度为O(△2),消息复杂度为O(n),比同类算法优秀。

能量均衡的最小连通支配集分布式算法

在无线传感器网络路由协议中,最小连通支配集构成的虚拟骨干网是缓解广播风暴的有效方法。现有算法在构造连通支配集时,通常只考虑支配集的规模,虽然获得了较小的支配集,但也造成虚拟骨干网生命周期较短等问题。为了有效解决该问题,提出了一种能量均衡的最小连通支配集分布式算法(EB-MCDS)。仿真实验结果表明,与现有算法相比,EB-MCDS算法有效的均衡了网络能量,延长了网络生命周期20%左右。