求解多目标最小生成树的一种改进的非支配排序遗传算法

在改进的非支配排序遗传算法(NSGA-Ⅱ)的基础上,提出了一种基于生成树边集合编码求解多目标最小生成树问题的进化算法。通过快速非支配排序法,降低了算法的计算复杂度,引入保存精英策略,扩大采样空间。实验结果表明:对于多目标最小生成树问题,边集合编码具有较好的遗传性和局部性,而且基于边集合编码的进化算法在求解效率和解的质量方面都优于基于Pr(?)fer编码的进化算法。     

最小代价多播生成树的快速算法

本文针对MPH（Minimum Path Cost Heuristic）等多播最小生成树算法存在的问题，通过改进最短路径节点的搜寻过程，以较小的存储空间为代价，获得了计算效率很高的快速最小代价多播生成树算法FMPH（Fast Minimum Path Cost Heuristic），且获得多播生成树与MPH算法完全相同，随机网络模型的仿真结果表明：FMPH算法快速、稳定，是一种值得推广使用的高效算法。     

基于优先队列的最小生成树算法

本文提出一个获取连通网络是小生成树的算法。该算法采用一个优先队列组织各顶点集合，每次根据边的权值对队列头集合进行增长。由于对每个顶点的相关联边进行了按权值分级排序的预处理，算法获取具有。个预示e条边的无向连通网络的最小生成树的期望时间是O（e*loglogn）。     

通信网络架设中最小生成树问题的一种新算法

本文在Prim算法的基础上,结合最优二叉树的思想,提出了一种新的计算方法,将最小生成树的生成过程划分为几个连通子图的最小生成树生成过程,从而显著的提高算法效率。     

基于最小生成树的异构传感器网络抗共谋优化方案

基于EBS (Exclusion Basis Systems)的密钥管理协议,以安全性高、动态性和扩展性好,较适用于异构传感器网络,但却存在共谋问题。该文提出了一种基于MST (Minimum Spanning Tree)的密钥共谋问题优化方案。该方案利用Prim算法对由簇内感知节点所构成的无向连通图进行最小生成树求解,并对该树进行遍历,根据所得节点遍历顺序进行密钥的指派与分配,使得相邻节点间所含的密钥重叠程度增大,发生共谋的可能性得到降低。实验结果表明：同比于密钥随机分配方案与SHELL方案,所提方案有效提高了网络的抗捕获能力。     

基于生成树的mesh网虚环保护算法

波分复用(WDM)全光网是下一代骨干网的核心,网络的生存性问题是构建WDM全光网的关键技术之一。文章对网状拓扑中的虚环保护机制进行了研究,并对一种基于生成树的虚环构成算法进行了分析。基于生成树的虚环构成算法可应用于各种网状拓扑,具有良好的适应性,同时还避免了P-圈法中复杂的“Hamilton”环的搜索问题。     

基于改进遗传算法的配网无功优化

针对配电网无功优化问题进行研究。以配电网络有功网损最小为优化目标,使用连接权重将配电网中的有功网络损耗、电压稳定性、补偿设备投入容量等多目标优化变为单目标优化。利用具有全局搜索能力的免疫算法与遗传算法相结合,从而提高了遗传算法的稳定性和适应性。最后通过IEEE 14节点的配网无功优化实例对所研究的改进遗传算法的优化模型进行分析。研究结果表明,使用改进遗传算法后的有功损耗相比常规遗传算法下降了0.28 MW,损耗降低率提高了1.37%,并且迭代次数明显降低,提高了优化的速率。     

基于最小生成树的分簇协作频谱感知改进算法

为减少分簇过程中的时延,基于最小生成树的单向比较优势提出簇首快速推举方法,并提出改进的分簇协作频谱感知算法,分析了算法的时间复杂度。算法首先基于最小划分对所有次用户节点进行分簇,簇内节点根据设置的评价条件进行性能比较,推举簇首。由簇首进行本地簇内频谱检测,并上传检测结果,最后融合中心在簇首间实现协作的频谱检测。在瑞利信道条件下,仿真显示在大信噪比时,融合中心应用AND规则,系统具有较小的虚警率,所提算法检测性能优;小信噪比时,应用OR规则能扩展系统的有效检测区间,所提算法在满足系统要求的前提下检测性能较差,但簇内信道效率提高了n-1倍。     

基于最小生成树路由的电力线载波通信数据融合算法

电力线载波通信技术利用现有的电力传输网络进行数据传输,具有建设成本低,部署快速灵活等特点,被广泛用于局域网本地通信中。但当节点数过多或传输数据量过高时,如每个节点单独将数据传到调控中心,将会给整个通信系统带来巨大的数据量,同时降低通信效率,甚至造成通信拥塞。为降低传输数据量,节省通信传输资源,提升电力线载波接入网络的传输能力,本文提出了基于最小生成树传输路径的电力线载波通信数据融合算法。将所提算法与未使用融合算法带来的数据量进行对比,证明了所提算法的有效性。     

基于MST聚类的遥感图像变化检测

为了获取图像信息较完好的差异图像以及得到更 好的变化检测结果,提出了 一种基于最小生成树(MST)聚类的遥感图像变化检测算法。先利用归一化邻域比值法得到两 幅遥 感图像的差异图像;然后根据灰度差异直方图将像素分成变化、非变化和未确定3类, 针对未确定像素,利用未确定像素的纹理特征结合MST算法进行聚类;最后通过最优 目标函数将未确定像素区分为变化类和非变化类,得到最终图像变化检测结果。采用 两组数据验证算法的有效性:墨西哥数据的检测精度为99.01%,运行 时间为8.49s,撒 丁岛数据的检测精度为98.62%,运行时间为3.45s。实验结果表明,本文算法具有更高的检测精度和较短的运行时间。     

Solving minimum spanning tree problem with DNA computing

Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.     

Topology aggregation and decoding algorithms based on a minimum spanning tree in asymmetric multi-domain optical networks

In an optical network, the connections are generally bidirectional, but their QoS parameters in each direction may be not the same. In this paper, we propose an enhanced algorithm called Node Label Order First (NLOF), which can maintain asymmetrical information and guarantee availability of the compressed topology. Besides, a decoding algorithm to restore the compressed topology named Average Proportional point (AP) is also proposed, which not only retains the space complexity of the aggregation process but also improves the accuracy of the restored information. Simulation results show that combing NLOF with AP can balance the contradiction between space complexity of the aggregation algorithm and routing accuracy.     

基于改进粒子群算法的无线传感器网络覆盖优化

为了解决粒子群算法的无线传感器网络覆盖方法存在的容易出现局部收敛的问题,提出基于改进粒子群的无线传感器网络覆盖优化方法。分析基本粒子群算法进行无线传感器网络覆盖优化的过程,找出其存在的局部收敛问题,通过采用拟万有引力和库仑力两种拟物方案,在粒子速度进化过程中融入拟物力,对基本粒子群算法的速度修正过程实施优化,避免粒子群算法出现局部收敛问题,降低重复覆盖率,完成无线传感器网络覆盖优化。实验结果表明,改进粒子群算法具有更快的收敛效率,对无线传感网络的覆盖优化效果更好。     

结合均值漂移与最小生成树的图像分割算法

为了提高均值漂移(MS)分割算法的运行效率,提出了一种结合MS与最小生成树(MST)的图像分割方法,简称MS-MST方法。首先选取较小的空间带宽参数,以较快的速度对图像进行MS分割,得到过分割图像;然后,以过分割区域作为后续处理的基本单元,构造加权区域邻接图,运用MST算法对其进行合并,得到最终的分割结果。实验结果表明,本文算法在保证图像分割质量的前提下,大幅提高了经典MS算法的分割速度。     

RFID network planning based on improved brain storm optimization algorithm

In order to improve the service quality of radio frequency identification (RFID) systems, multiple objectives should be comprehensively considered. An improved brain storm optimization algorithm GABSO, which incorporated adaptive learning operator and golden sine operator into the original brain storm optimization (BSO) algorithm, was proposed to solve the problem of RFID network planning (RNP). GABSO algorithm introduces learning operator and golden sine operator to achieve a balance between exploration and development. Based on GABSO algorithm, an optimization model is established to optimize the position of the reader. The GABSO algorithm was tested on the RFID model and dataset, and was compared with other methods. The GABSO algorithm's tag coverage was increased by 9.62% over the Cuckoo search (CS) algorithm, and 7.70% over BSO. The results show that the GABSO algorithm could be successfully applied to solve the problem of RNP.     

基于进化规划求解最优通信生成树

本文分析了使用遗传算法求解最优通信生成树的缺陷,提出了基于进化规划求解最优通信生成树的新方法,并将这一方法扩展到有约束最优通信生成树问题。仿真结果验证了算法的有效性。     

A bi-criteria minimum spanning tree routing model for MPLS/overlay networks

The MPLS platform enables the implementation of advanced multipath and multicast routing schemes. This work develops and analyses the performance of a new bi-criteria minimum spanning tree model intended for routing broadcast messages in MPLS networks or constructing tree-based overlay networks. The aim of the model is to obtain spanning trees which are compromise solutions with respect to two important traffic engineering metrics: load balancing cost and average delay bound. An exact solution to the formulated bi-criteria optimization problem is presented, which is based on an algorithm that enables the computation of the set of supported non-dominated spanning trees. An application model and a set of experiments on randomly generated Internet type topologies will also be presented. Finally a network performance analysis of the model considering three network performance metrics will be shown.