求解广义最小生成树问题的元启发式算法

针对广义最小生成树问题,设计了2种改进的元启发式算法来求解:单亲遗传模拟退火算法和改进的禁忌搜索算法。通过综合遗传算法和模拟退火算法的优点,提出了单亲遗传和模拟退火的混合算法,并设计了自适应选择法和自适应基因重组操作;在改进的禁忌搜索算法中,通过在2种邻域进行搜索来避免陷入局部最优。数值实验验证了算法的有效性。

多参数最小支撑树问题的复杂性和算法

建立了多参数最小支撑树问题 (RMST)的模型 ,并证明该问题是 NP-完全的。利用经典 Greedy算法 ,给出了该问题的一个近似算法 ,并分析了该近似算法的性能比 ,证明了所给出的界是紧的。

最小最大后悔支撑树问题

本文建立了最小最大后悔支撑树问题的模型 .利用划分问题 ,证明了该问题是 NP- C的 .然后利用两个已有的算法 ,给出了上下界估计 .最后对一种特殊情况 ,给出了一个启发式算法 。

度、半径约束最小生成树问题及其算法

提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果.

最小支撑树问题的三个算法

最小支撑树是指找图G的一棵权重最小的支撑树,探讨最小支撑树问题的三个算法(避圈法、破圈法、反圈法)及其时间复杂性,证明了反圈法的时间复杂性最优。

融合均值榜样的反向互学习水母搜索算法

为解决水母搜索算法(jellyfish search algorithm,JS)的洋流运动缺乏多样性、群内运动缺乏引导性、种群间信息无交流,造成搜索速度慢、稳定性差及易早熟的问题,构建了一种融合均值榜样的反向互学习水母搜索算法(oppositional-mutual learning jellyfish search algorithm based on mean-value example,OMLJS).首先在水母跟随洋流运动(全局搜索)部分,利用前两代水母的平均位置代替只考虑上一代水母的平均位置来引导水母个体的位置更新,提高算法的全局搜索能力;其次在水母的群内主动运动(局部搜索)部分,利用最优个体代替随机个体来引导水母进行更有效的搜索,加快算法的收敛速度;然后在水母进入下一次迭代前增加对水母种群进行动态反向互学习步骤,增加种群多样性及增强种群间的信息交流,达到互补另外两个策略,提高算法的整体优化性能.选用12个经典的基准测试优化函数,将OMLJS与5个对比算法从解的平均值、最优值及方差进行对比分析,并用于求解最小生成树问题,OMLJS能够更快地找到最小生成树.实验结果表明,OMLJS的收敛速度、求解精度明显提高.

一种基于最小路径的多播路由优化算法

信息物理融合系统(Cyber-Physical Systems,CPS)底层是传感器、控制器和执行器等异构节点构成的无线自组网络,不同节点之间需要通过通信网络传送给感兴趣目标节点,传统的无线自组织网络一般采用单播或广播技术,但是这些往往实时性不高,通信开销大,不利于在CPS中受限节点间通信.该文针对信息物理融合系统中无线多播路由问题构建网络模型,演化为最小路径问题,数学模型为约束Steiner最小树问题,并针对该NP难问题通过启发式算法求解,再通过贪婪思想构建一种最小路径多播路由算法.最后通过与uCast以及SenCast等经典的多播路由算法仿真比较,得出其算法在实时性以及能耗等方面性能优异.

基于DCMSTP问题的算法综述

DCMSTP(度限制最小生成树问题)是一个NP难问题,具有重要的实际应用价值。对于大规模的DCMSTP问题,至今还没有非常有效的求解方法。为此,本文对讨论了DCMSTP问题的数学模型和求解该问题的精确算法和启发式算法。

最小生成树DNA算法

为了改进粘贴模型,提出了用生化实验实现求解割集的计算方法,并基于该方法给出了最小生成树DNA算法.首次将分离实验扩展为基于分离板的分离实验和基于电泳技术的分离实验,所提出的最小生成树DNA算法打破了DNA计算的计算模式——用求解割集的最小边的方法逐步产生最小生成树.用该方法求解割集利用了分离实验运算的高度并行性,最小生成树DNA算法的时间复杂度是线性的,从而降低了算法的时间复杂度.

传感器网络中基于模拟退火算法的拓扑控制方案

为了研究符合网络生命期目标要求的传感器网络拓扑控制方案,针对传统方案所获拓扑的连通冗余度过高或结构健壮性较低等弊端,从理论上对拓扑需求进行了建模分析,最终转化模型为度约束最小生成树问题,并设计了一种模拟退火算法对该问题进行处理,进而提出了一种基于模拟退火算法的拓扑控制方案。通过实验对方案进行了性能分析和验证,结果表明该方案所获拓扑具有网络整体功耗低、结构健壮性高和节点间通信干扰可控的折衷特点,并能够有效地延长传感器网络生命期。

基于遗传算法的传感器网络拓扑控制研究

无线传感器网络的首要设计目标是延长网络生命期,网络的拓扑控制是实现这一目标的支撑基础。针对传统拓扑控制方案所获拓扑的连通冗余度高或结构健壮性低等弊端,将问题转化为多判据最小生成树模型,提出了一种基于遗传算法的拓扑控制方案。仿真实验结果表明,该方案可获得具有网络整体功耗低、结构健壮性高和节点间通信干扰小等特点的拓扑结构,因而能够有效地延长传感器网络生命期。

一个蚁群优化模型的期望性能分析

用蚁群优化求解组合优化问题时,信息素模型及其规则可能使问题的各组件之间的竞争失衡,从而有可能使蚁群搜索停滞在最差解。研究了蚁群优化求解k-最小生成树问题时的信息素模型及其更新规则对性能的影响,对原有的信息素模型作出了新的解释:直接表示k-最小生成树问题的边被选择的概率。基于新的信息素模型设计了一种新的解的构造过程,这种过程不仅产生可行解,也产生不可行解;同时研究了使用可行解和全部解更新信息素模型时算法的迭代期望质量随时间的增减情况,其结果表明,只使用可行解时迭代期望质量随时间连续降低,而使用全部解时算法最终收敛到最优解。为了使用全部解,定义不可行解的不可行量及扩展目标函数使可行解的目标值不变而不可行解的目标值大于任何一个可行解。