一种基于遗传算法的度约束最小生成树求解方法

《基于遗传算法的直径限制最小生成树问题的研究》篇一一、引言最小生成树问题（Minimum Spanning Tree Problem，MST问题）是图论中的经典问题之一，主要目标是在加权连通图中找到一个子图，它是一个生成树且权重和最小。

随着现代信息技术和计算科学的飞速发展，对图的生成算法要求日益严格。

直径限制最小生成树问题（Diameter-Constrained Minimum Spanning Tree Problem，DCMST问题）作为其扩展问题，在通信网络、传感器网络、生物信息学等领域有着广泛的应用。

本文将针对基于遗传算法的直径限制最小生成树问题进行研究。

二、遗传算法概述遗传算法是一种模拟自然进化过程的搜索算法，通过模拟生物进化过程中的选择、交叉和变异等操作，对问题进行优化求解。

遗传算法具有全局搜索能力强、适用于大规模空间搜索等特点，因此在解决复杂优化问题上具有显著优势。

三、DCMST问题描述DCMST问题是在MST问题的基础上增加了直径限制的约束条件。

即在给定的连通图中找到一个生成树，该生成树的权重和最小，且其直径不超过给定的阈值。

该问题在许多实际场景中具有重要应用价值，如通信网络的拓扑设计、传感器网络的部署等。

四、基于遗传算法的DCMST问题求解针对DCMST问题，本文提出一种基于遗传算法的求解方法。

首先，将连通图中的边看作基因，生成树的权值作为个体适应度；然后，通过选择、交叉和变异等操作，生成新的树结构并计算适应度；最后，经过多次迭代，找到满足直径限制且权值最小的生成树。

五、实验与分析为验证本文提出的算法的有效性，我们进行了大量实验。

实验结果表明，该算法在求解DCMST问题上具有较高的效率和准确性。

与传统的启发式算法相比，遗传算法在解决此类问题时能够得到更好的解空间探索能力。

同时，该算法也具有较好的稳定性和鲁棒性，在不同规模的图上均能取得良好的效果。

六、结论与展望本文针对基于遗传算法的直径限制最小生成树问题进行了深入研究。

求最小生成树问题,常用的方法最小生成树（Minimum Spanning Tree）问题是一个经典的图论问题，其涉及到给定一个加权无向图，求其最小的生成树。

在实际问题中，求解最小生成树问题非常重要。

例如，最小生成树问题被广泛应用于网络设计、电路布线、机器学习等众多领域。

本文将介绍求解最小生成树问题的常用方法，包括Kruskal算法、Prim算法和Boruvka算法。

我们将详细介绍这些算法的原理和步骤，并给出各种算法的优缺点和适用情况。

1. Kruskal算法Kruskal算法是一种基于贪心策略的算法。

它首先将所有边按照权重大小排序，然后从小到大遍历边。

对于每个边，如果它连接了两个不同的连通块，则将这两个连通块合并成一个。

重复这个过程，直到所有的边都被考虑完。

最终的联通块就构成了最小生成树。

Kruskal算法具有简单、高效、容易实现的特点。

它的时间复杂度为O(E log E)，其中E为边的数量。

Kruskal 算法的实现需要使用并查集。

Kruskal算法的优点是它是一种局部最优的策略，因此它能够在众多情况下得到最优解。

另外，它能够处理稀疏图和稠密图，因为它不需要全局访问图的结构。

2. Prim算法Prim算法也是一种基于贪心策略的算法。

它从一个任意的节点开始，不断加入与已经加入的节点相邻的最短边，直到所有节点都被加入。

这个过程类似于将一个连通块逐渐扩张为最小生成树。

Prim算法的时间复杂度为O(E log V)，其中E为边的数量，V为节点的数量。

Prim算法的实现需要使用堆数据结构来进行边的最短距离的管理。

Prim算法的优点是它比Kruskal算法更加容易实现和理解。

另外，Prim算法能够处理不连通图，因为它从任意一个节点开始加入边。

此外，Prim算法也能够处理含有负权重的边的图。

3. Boruvka算法Boruvka算法是一种基于分治策略的算法。

它首先将所有的节点看作单独的连通块，然后每个连通块都选择当前权重最小的边加入。

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.21, No.12, December 2010, pp.3068−3081 doi: 10.3724/SP.J.1001.2010.03713 Tel/Fax: +86-10-62562563© by Institute of Software, the Chinese Academy of Sciences. All rights reserved.∗一种求解度约束最小生成树问题的优化算法王竹荣+, 张九龙, 崔杜武(西安理工大学计算机科学与工程学院,陕西西安 710048)Optimization Algorithm for Solving Degree-Constrained Minimum Spanning Tree ProblemWANG Zhu-Rong+, ZHANG Jiu-Long, CUI Du-Wu(School of Computer Science and Engineering, Xi’an University of Technology, Xi’an 710048, China)+ Corresponding author: E-mail: wangzhurong@Wang ZR, Zhang JL, Cui DW. Optimization algorithm for solving degree-constrained minimum spanningtree problem. Journal of Software, 2010,21(12):3068−3081. /1000-9825/3713.htmAbstract: To solve the degree-constrained spanning minimum tree (DCMST) problems with a large scale of nodes,an optimization algorithm based on grafting and pruning operator is proposed. Learning from the flower plantingtechniques, this paper establishes, an evolutionary computation framework containing accelerating and adjustingoperators based on conventional genetic operators. The grafting and pruning are performed by a greedy strategy andgain maximization respectively. The collision caused by possible local minima is analyzed and detected, and severalmethods dealing with the collision are discussed. To tackle the complexity of DCMST problems, some strategies ofgrafting and pruning are proposed. The convergence of the proposed algorithm and the computation complexity areanalyzed. For DCMST problems of Euclidean and uniform random non-Euclidean instances from 50 to 500 nodes,the experiments show that the quality and convergence rate of the proposed method are the best compared with theknown results.Key words: DCMST; genetic algorithm; grafting; pruning摘要: 为求解大规模结点度约束最小生成树问题,提出一种带有嫁接和剪接算子操作的优化算法.通过借鉴花草果树种植技术,建立一种以基本遗传算子为基础、带有加速和调节算子作为激励的进化计算体系;嫁接以一种贪婪的思想加速搜索,按收益最大化原则进行剪接.对可能陷入局部极值引起冲突的现象及冲突检测的方法进行分析,并提出了冲突的若干解决方法.针对DCMST问题求解中的复杂性,提出了几种有效的嫁接和剪接的策略,并对算法的收敛性和计算复杂度进行了分析.通过该算法对结点数为50~500之间的Euclidean问题和按均匀随机方式产生的non-Euclidean度约束最小生成树问题进行求解.与现有文献的实验结果对比表明,该方法在求解最好解的精度和收敛速度上均有一定的优势.关键词: 度约束最小生成树;遗传算法;嫁接;剪接中图法分类号: TP301文献标识码: A度约束最小生成树(degree-constrained minimum spanning tree,简称DCMST)问题是一类难解的NP-hard问∗ Supported by the National Natural Science Foundation of China under Grant No.60873035 (国家自然科学基金)Received 2009-02-12; Revised 2009-04-27; Accepted 2009-07-29王竹荣 等:一种求解度约束最小生成树问题的优化算法 3069 题[1],它在通信网络、电力线网络、计算机网络、大规模集成电路等方面都有重要的应用[2,3].一直以来,对它的研究引起国内外许多学者的关注.Narula 与Ho 最早提出一种分枝限界法(a branch and bound algorithm),该算法可以得到较小规模DCMST 问题的最佳解.Caccetta 等人提出了一种求解DCMST 问题的分枝和剪切算法(a branch and cut algorithm)[4].Andrade 等人提出了基于双重解信息的Lagrangian 算法[5].Behle 等人在标准分枝和剪切算法的基础上,利用0/1整型规划中的问题分离原则,提出了一种优先的分枝和剪切算法(a primal branch-and-cut algorithm)[6].近些年来,许多学者对以遗传算法、免疫算法[7]为代表的进化计算方法进行研究并取得广泛的应用.其中,一些学者利用进化计算方法开展对DCMST 问题求解.例如,Zhou 和Gen 首先提出利用遗传算法的途径求解DCMST 问题,文中采用一种pr üfer 计数来表示一棵生成树的编码方法[8].Knowles 等人设计了一种包含边结点权重信息的动态表结构的编码方法(the randomized primal method,简称RPM),是将其与多点爬山(multistart hillclimbing,简称MHC)、模拟退火(simulated annealing,简称SA)和遗传算法(GA)相结合的优化方法[3].Raidl 等人对最优解中包含低权重边的频次进行统计分析,推导出结点数为20~100的DCMST 问题边的权重及其在最优解中出现的概率公式,并以该概率作为执行变异操作边的选取依据的(1+1)-EA 算法[9].Soak 等人提出一种由子图边的结点组成的数字序列的编码方式(the edge-window-decoder),设计了几种按不同策略遍历子图边结点的算子(TCR)来构建生成树的算法[10].其他的方法如蚁群算法[11]、粒子流算法[12]等,均从不同方面取得了一定成效.不同的DCMST 问题可分为两大类,即non-Euclidean DCMST 和Euclidean DCMST 完全图问题.对这两大类约束最小生成树问题求解的复杂性,不同的文献有不同的看法.多数文献作者认为,按均匀随机方式产生的non-Euclidean 问题要比Euclidean 问题的求解更为复杂;与之相反,文献[10]的作者倾向Euclidean 问题的求解更具有挑战性.通过大量的实验测试及分析,我们认为,以均匀随机方法生成non-Euclidean 图例的DCMST 问题具有更大的变化性和多样性,使得这类问题解的结构及求解的难易性具有更大的变化性.一方面,这类问题的Prim 解对应的度值通常大于5,且在度为3时问题的最好解与Prim 算法解的比值随不同的问题或分布范围有所不同.一些文献证实,Euclidean 图例的DCMST 问题对应Prim 解的度最大为5,且在度值为3或4时最好解与Prim 算法解的比值在一定的范围内.当度为3时,该指标的界限值在不同的文献分别为5/3,1.5和1.402[13].文献[14]作者猜测性地认为,该指标界限值能进一步减小到 1.103.另一方面,对均匀随机方式产生分布在某一区间的non-Euclidean 问题,随着结点数增加,其解的复杂度逐渐降低.主要表现在:当结点数增大到某一值后,该类问题不再是一个难求的NP-hard 问题,较多情形下能以几乎1的概率构造出一棵度值为3的最小生成树,使其与Prim 算法得到的无约束生成树(对应的度值一般大于10)具有相同目标值.通过反复的编程测试及对存在问题的分析,我们发展了基于度排列的编码方法[1],通过利用度维关系,不需经过完全解码就能求出及利用待考察结点的关联结点及构成边的权重信息;结合花草果树的人工种植和培育技术,提出一种带有嫁接及剪接算子的遗传算法(a genetic algorithm with grafting and pruning operators,简称GPOGA).通过将该算法用于对DCMST 问题进行求解,与现有文献提供的实验数据的对比说明,本文算法在得到最好解精度以及算法的诸多性能指标均有很大提高.1 DCMST 的数学模型假设G =(V ,E )为网图,其中:V ={v 1,v 2,…,v n }是结点的有限集合,n =|V |为结点总数;E ={e 1,e 2,…,e m }是G 中边的集合,m 为边的总数.设1{,...,,...,|}i t i S v v v v V V ′′′′=∈⊆且|S |≥1;设T 为图G 的所有满足度约束的生成树的集合, 因此,对DCMST 问题求解就是寻找G 的一棵生成树,这里用一个向量x 表示,x ∈T ,使其满足给定的度约束并使对应边权重w ij (一般指边长或费用,本文以下均指边长)之和为最小值.DCMST 的数学模型可描述如下:3070Journal of Software 软件学报 V ol.21, No.12, December 2010111111||1||111 min{() |}subject to 1 1, 1,2,..., ||1, , 2(1)n n ij ij ij i j i n n ij i j i i c S S ij i j i i i z w x x x n d d i n x S i j d n −==+−==+−==+==×∈=−=S −∈=×−∑∑∑∑∑∑≤≤≤x x {0,1}, ,1,2,...,n ij x i j n⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪∈=⎩∑ (1) 上述数学模型由DCMST 问题的优化目标函数及约束构成,其中:第1个约束为生成树包含不同结点的n −1条边;第2个约束为每个结点应满足的度约束条件,d c 为给定的度约束值;第3个约束表示生成树无环路;第4个约束为所有结点的度值和;第5个约束当x ij =1时,由结点〈v i ,v j 〉构成的边是生成树的一条边.2 GPOGA 算法体系2.1 GPOGA 算法思想在对与排序或路径长度有关的组合优化问题的求解中,广泛使用一项被称为邻域搜索(local search)的策 略[15].其基本思想是,在算子的搜索过程中,应充分利用相邻结点的路径长度信息,使结点或边交换后的收益最大.文献[15]指出,邻域搜索为获取NP-hard 问题的高精度解提供一种有效和可靠的途径.在类似问题的求解中,邻域搜索策略成为检验一个算子或算法是否具有高效性的基本前提.但应看到,它的基本出发点是利用一种贪婪思想,极有可能加速算法陷入局部最优.文献[9]的作者也指出,在对DCMST 问题的求解中,较小权重的边以较大的概率被选取参与变异操作很可能使算法以更大的概率陷入局部最优.我们发现,当使用local search 策略使算法陷入局部最优或消除非正常态时,一般会出现一种称为冲突的现象.而对冲突的检测和处理,成为本文算法要解决的一个关键问题.因此,从算子的作用看,如果将带local search 的算子归结为一种加速算子,则算法应包含另一种算子,本文称它为调整算子.其作用是双重的:一方面,它对出现的非正常态进行及时处理,使得当算法陷入局部最优时,能对这种情形进行有效的检测,并使其以较大的几率跳出;另一方面,它同样包含local search,使算子的搜索具有更高的效率.为便于叙述,以下先给出与本文算法相关的几个概念.本文所指的树(生成树)是指一棵非空树(n >1,除根结点之外的元素被分为m (m >0)个不相交的集合T 1,T 2,…, T m ,其中每一个集合T i (1≤i ≤m )又是一棵树,称为根结点的子树,文中称每棵子树为树的一条分支.在本文算法的嫁接和剪接操作中,当树发生变化时,指以待考察结点为根结点的整条分支的移动.定义1(收益和代价). 对一棵(生成)树T 1,若将某结点的一条分枝移至另一结点作为其一条分枝后产生的生成树为T 2,考察分枝移动前后生成树的边长和的变化,则定义收益(gain)和代价(cost)分别为111121111()()n n n n ij ij ij ij i j i i j i 2gain f T f T w x w x −−==+==+=−=×−×∑∑∑∑ (2) 112211111()()n n n n ij ij ij iji j i i j i cost f T f T w x w x −−==+==+1=−=×−×∑∑∑∑ (3) 公式(2)与公式(3)中,1212,ij ij x T x T ∈∈. 定义2(嫁接). 从(生成)树中选取具有某种优良特性的分枝(嫁接枝)接入到待考察结点中,以形成更好生成树个体(指收益大于0)的过程称为嫁接.定义3(剪接). 将(生成)树中的某一分枝(剪接枝)接入到另一位置,以形成可行个体或更好生成树的过程称为剪接.王竹荣等:一种求解度约束最小生成树问题的优化算法30712.2 嫁接算子及策略2.2.1 嫁接算子的构造嫁接算子操作可分为两步:1) 根据结点及其关联结点的边长信息,选择具有优良品质的嫁接枝;2) 将选择的嫁接枝重新接入,以形成更好的生成树个体,即嫁接后收益大于0.如何选取具有优良品质的嫁接枝,是嫁接操作的关键所在.要选取一条有效的嫁接枝,需解决以下两个关键问题:1) 有效利用边结点及其关联结点的边长信息.为了使嫁接及剪接操作更为有效,对各结点按其关联结点构成边的长度进行排序,并将排序结果保存在指针变量pnodesortdis中.2) 求任意结点的父结点及子结点关系.本文采用基于度的排列的编码方法,有关编码方法见文献[1].为此,设计了通过利用度维关系查找某一结点的父结点函数FindPareNode(par1,par2)及其子结点的函数FindChildNode(par1,par2),par1,par2为算法所需参数,它们在较好情形下的时间复杂度均为O(1),在最坏情形下的时间复杂度为O(n).FindPareNode的基本思想是,从当前位置向前扫描,记录扫描过的结点的度值,根据扫描过的结点与度值的关系计算出其父结点位置,其伪码描述如下:算法1(检索某一结点位置nodepos的父结点位置parvpos算法).Begin初始化参数:degreesum=0, counter=0, parvpos=nodepos;根据输入的个体individual,得到其结点维individual.chrom1和度维individual.chrom2;if parvpos=1 thenreturn 1;end ifparvpos=parcpos−1, counter=counter+1;degreesum=degreesum+individual.chrom2[parvpos];if parv>1 then degreesum=degreesum−1;while degreesum<counter doparvpos=parcpos−1,counter=counter+1;degreesum=degreesum+individual.chrom2[parvpos];if parv>1 then degreesum=degreesum−1;end while返回parvpos;End按收益优先及度约束控制嫁接策略执行嫁接操作,算法的伪码描述如下:算法2(嫁接算法).Begin设置所有结点使用标志变量pflagnodeuse为0;初始化参数contrpara=d c, i=1, k=1, bflaggrafting=false;while i≤n do设置counter=0,结点i对应结点序号的标志pflagnodeuse为1;由pnodesortdis得到与i关联的第k个结点序号inodeassono,并计算关联边长nodedis;while counter<contrpara && k≤n do求出inodeassono的父结点assoparenodeno及边长assonodedis;计算边交换后收益gain=nodedis−assonodedis;if inodeassono不是i的子结点且gain>0 then选择以inodeassono代表的分枝选,bflaggrafting=true;end ifif bflaggrafting=true then3072Journal of Software 软件学报 V ol.21, No.12, December 2010执行嫁接操作;counter =counter +1,将inodeassono 的标志pflagnodeuse 变为1,bflaggrafting =flase ;end ifk =k +1;求得与i 关联的第k 个结点序号inodeassono 及位置inodeassopos 及关联边长nodedis ;end whilei =i +1;end whileEnd2.2.2 嫁接策略为使嫁接操作能够处理不同情形的DCMST 问题,本文提出以下几种嫁接策略,它们分别是:1) 收益优先嫁接策略对考察结点,若所选关联结点分枝移至考察结点前后收益大于0,则该分枝可选为嫁接枝.按该策略执行嫁接,操作简便,且总体效果较好.其缺点是,嫁接后某些结点的分枝数可能大大超过给定的度约束值,从而增加剪接的负担.2) 无度约束最优嫁接策略对考察结点,选取与其具有最小边长的关联结点作为嫁接枝.按该策略执行嫁接,在理想的情形下,通过该策略可生成一棵无度约束的最小生成树.其缺点主要有:1) 针对给定某一度约束值d c ,若通过Prim 算法得到的无约束生成树对应的度值与d c 相差较大,该控制策略往往不能取得好的效果;2) 增加算法陷入局部最优解的 概率.3) 度约束控制嫁接策略对考察结点新加入的分枝进行控制,一般不超过给定的度约束值d c .按该策略执行嫁接,可使嫁接后的生成树基本满足度约束要求.4) 双重信息嫁接策略对考察结点,在判断某一结点代表的分枝是否作为嫁接枝时,应将边长信息(决定收益)和位置次序关系信息(决定优先关系)同时进行分析.也就是说,某一结点代表的分枝移动到考察结点后,即使收益不如其他的分枝,但考虑其位置次序关系,应优先将该分枝选为嫁接枝.由于在嫁接中需要同时考察边长及位置次序关系,如果处理恰当,则可有效提高算法的求解精度和收敛速度.5) 概率选择嫁接策略文献[9]给出了当最大结点数为100时,第r 条边选择的概率值近似为/2((1)/)(/(1)1)r r q n n n n =−−−,n 为 结点数,r (1≤r ≤m )为按边长排序分配的序号,m 为边的总数.考虑到本文算法中嫁接算子的作用与文献[9]变异算子作用的差异,本文的处理方法是按边长排序:针对每一结点的边长信息设定一个阈值,当边长大于或等于该阈值时,其分配概率为0;当边长小于给定的阈值时,按边长或以边长排列分配位置次序,然后分别计算关联结点代表的分枝对应的概率值.以下分别对它们的概率进行分析.当按边长分配概率时,对考察结点i =1,2,…,n ,设给定的阈值为r i ,设与i 关联的某一结点j 构成的边长为len (i ,j ),定义len (i ,j )与r i 的距离dis (len (i ,j ),r i )为dis (len (i ,j ),r i )=r i −len (i ,j ) (4)因此,结点j 代表的分枝的选择概率为 1,0, (,)(,)|(,), (,)(,)i iij i i n k k ilen i j r r len i j p len i k r len i j r len i k =≠⎧⎪−⎪=<⎨⎪⎪⎩∑≥< (5) 当按以边长排列分配位置次序时,对考察结点i =1,2,…,n ,设给定的阈值为r i .由公式(4),计算出与i 关联的结王竹荣 等:一种求解度约束最小生成树问题的优化算法 3073 点j 构成的边长为len (i ,j )与r i 的距离dis (len (i ,j ),r i ),对dis (len (i ,j ),r i )按递减排序,以确定与i 关联的结点j 构成的边的位置次序rank (i ,j ),分别对它们分配1,2,…,m 值.则结点j 代表的分枝的选择概率为 1,0, (,)1(,) , (,)(1(,))i ij i m k k ilen i j r m rank i j p len i j r m rank i k =≠⎧⎪+−⎪=<⎨⎪+−⎪⎩∑当≥当 (6)公式(5)和公式(6)中,j =1,2,…,n 且j ≠i .在上述策略中,策略1)~策略4)属于稳定控制策略,策略5)属于非稳定控制策略.在算法设计中,嫁接操作在一般情形采用上述策略1)和策略3)就能取得较好的效果;当求解一些复杂及特殊情形的DCMST 问题,选择交替使用策略2)、策略4)或策略5).2.3 剪接算子及策略2.3.1 剪接算子构造嫁接时产生的生成树可能包含某些结点不满足度约束以及具有较差属性分枝的情形,均要进行剪接操作. 判断一条分枝是否在当前位置具有最(较)差属性的依据为下列两种情形之一:1) 若该分枝移动到另一关联结点的收益最(较)大;2) 若所有考察的分枝分别移动收益均小于0,则指移动后代价最小的分枝.算法3以一棵生成树子结点分枝进行修剪为例说明剪接操作的程序流程,算法的伪码描述如下:算法3(剪接算法).Begin初始化剪接参数,设置iprunflag ,iprunneedflag 为false ,设置初始位置i =1;while i ≤n do取当前结点度值nodegree ;if nodegree 大于给定的度约束值degreecons then iprunflag =true ;求解i 的子结点,结果保存在指针变量pichild 中;while pichild 非空 do寻找具有最差属性的子结点selectchildnode 分枝if 收益为大于0且iprunflag 为false thenif 检测无冲突 then iprunneedflag =true ;else if 冲突能有效解决iprunneedflag =true ;end ifif iprunflag or iprunneedflag 为true then 执行剪接操作,改变剪接标志;else break;if 剪接插入位置小于当前位置 then 指针回溯;取当前位置度值nodedegree ;if nodedegree ≤degreecons then iprunflag =flase ;end whilei =i +1;end whileEnd在剪接过程中,可能遇到的一个关键问题是冲突.在图1和图2的示例中,不失一般性,假定给定度约束值为3.由于序号为6的结点有4条分枝,必须剪去结点6的一条分枝.假定已检测到结点7代表的分枝具有最差的属性,而结点7与除结点6以外的最佳关联结点是结点3,那么将结点7代表的分枝插入到结点3之后就可以.这一插入过程未引起新的不满足度约束的情形,即不会引起冲突,其操作如图1所示.但是,如果结点7与除结点6之外只与结点4结合具有最好的特性,这时将引起新的冲突,因为结点4已有3条分枝,不能再插入新的分枝,否则引起新的不满足约束的情形发生,此时称插入后引起了新的冲突.其操作如图2所示.3074Journal of Software 软件学报 V ol.21, No.12, December 2010Fig.1 No collision emerges after inserting the branch denoted by node 7 as a new branch of node 3,the new associated edge is denoted by the dash line图1 将结点7代表的分枝插入到结点3之后未引起冲突,虚线为新构建的一条关联边245319678453219 6Fig.2 A collision emerges after inserting the branch denoted by node 7 as a new branch of node 4,the new associated edge is denoted by the dash line图2 将结点7代表的分枝插入到结点4之后引起冲突,虚线为新构建的一条关联边定义4(冲突及冲突检测). 在对消除不满足约束情形进行剪接或对具有较差属性的分枝进行剪接操作,若引起新的不满足约束的情形称为冲突;将发现这一冲突现象的过程称为冲突检测.定义5(冲突解决).1) 当冲突出现时,若冲突能在遍历一个或若干个结点后按收益最大化原则完全解决,称冲突能在与问题规模无关的常数内解决,此时冲突解决的时间复杂度为O (1).2) 当冲突出现时,若冲突能在遍历所有结点分枝后可按收益最大化原则完全解决,称冲突能在与问题规模相关的线性关系内解决,此时冲突解决的最坏时间复杂度为O (n ).3) 当冲突出现时,若冲突在遍历所有结点后仍无法按收益最大化原则完全解决,称冲突只能在与问题规模相关的非线性关系内解决,此时冲突解决的时间复杂度为多项式时间或指数时间.由定义5可知,当冲突出现时,若冲突能在O (1)和O (n )时间内解决,称冲突能完全解决.尽管冲突的多项式时间解决和指数时间解决有很大的区别,但冲突的多项式时间解决的循环递归将导致冲突的指数时间解决情形出现,为简化处理过程,称这两种情形为冲突不能完全解决.定义6(冲突的简化解决). 当冲突出现时,按收益较大化或代价较小化原则寻求在至多与问题规模相关的线性关系时间内解决该冲突的过程,称为冲突的简化解决.定义7(冲突的有效解决). 当冲突出现时,按收益较大化原则寻求在至多与问题规模相关的线性关系时间内解决该冲突的过程,称为冲突的有效解决.定义8(冲突的退化解决). 当冲突出现时,按代价最(较)小化的原则寻求在至多与问题规模相关的线性关系时间内解决该冲突的过程,称为冲突的退化解决.在冲突的解决过程中,使用了一种向前搜索的机制,这种机制能对已确定的边在考虑冲突存在及冲突解决中根据收益和代价进行重新评价,以确定相应的冲突解决方案.王竹荣等:一种求解度约束最小生成树问题的优化算法30752.3.2 剪接策略在剪接过程中,由于某些策略与嫁接策略的思想类似,因而对它们仅作简要说明,分别如下:1) 收益优先剪接策略对考察结点的所有分枝,若所选分枝移至另一结点位置后收益大于0且未引起不能有效解决的冲突,则该分枝可选为剪接枝,执行剪接操作.2) 双重信息剪接策略对考察结点的所有分枝,在判断某一分枝是否作为剪接枝时,应将边长信息和位置次序关系信息同时进行分析.3) 退化剪接策略当不满足度约束时,若在剪接中出现不能有效解决的冲突,只能按代价最(较)小化原则进行剪接.2.4 GPOGA体系在基本遗传算法体系的基础上,结合嫁接和剪接算子,形成GPOGA算法,其伪码描述如下:算法4(GPOGA).Begin随机初始化种群P(0),t=0;计算P(0)中个体的适应值并按适应值排序;while 计算代数t≤max(gen) doj=0;while 新产生个体j<N do根据个体的适应值随机从当代种群中选择两个父个体,设为oldindi1和oldindi2;执行杂交操作CrossOver(oldindi1,oldindi2),将产生的新个体保存在newpop[j],newpop[j+1]中;执行变异操作Mutation(newpop[j]),Mutation(newpop[j+1]),同时,将两个新个体复制到临时种群变量数组temp1[j]和temp1[j+1]中;执行嫁接操作Grafting(newpop[j]),Grafting (newpop[j+1]);执行剪接操作pruning(newpop[j]),pruning(newpop[j+1]);计算并评价temp1[j],temp1[j+1],newpop[j],newpop[j+1],oldindi1及oldindi2的目标值,选择两个较好的个体复制到newpop[j]及newpop[j+1]中;j=j+2;end while计算新种群newpop的目标值、适应值并排序,同时将oldpop最好个体替换newpop中最差个体;将newpop种群中个体复制到oldpop中,调整其目标值、适应值及顺序;t=t+1;end while记录及输出结果.End在算法中采用的选择策略称为(μ+λ+λ),即将随机选择的两个父个体、由基本遗传算子——杂交及变异后产生的新个体及经嫁接和剪接后产生的新个体共同参与竞争,以选择两个较好的个体进入下一代种群空间.上述算法,根据情形也可采用基于适应值概率的转盘式选择策略.3076Journal of Software 软件学报 V ol.21, No.12, December 2010)3 算法分析3.1 算法的收敛性分析本文算法中,若考虑遗传算子的作用及精英选择策略,则算法是以概率1收敛到所求问题的最优解.单独从嫁接和剪接算子的作用来看,它们只是在一定程度上加速或减缓算法的收敛速度.考虑其综合效果,嫁接和剪接操作只能是加速算法的收敛速度,否则,得到的解被原有父个体替换而被抛弃.因此,本文算法以概率1收敛到问题的全局最优解.详细的证明过程可参考文献[16]的有关定理和结论.在对DCMST 问题求解时,由于嫁接和剪接算子均使用local search 策略以及嫁接和剪接策略的差异,它们在一定程度上可能使算法陷于局部最优;当陷于局部最优时,要跳出这种状态一般会出现冲突,本算法可以有效检测冲突,并提出了若干有效的解决方法.综合考虑本文算法各遗传算子的作用,与没有加入嫁接和剪接算子的情形相比,算法具有更强的寻优能力,同时算法获得问题最好解的概率增大.3.2 算法的时间复杂度分析该算法每一代计算主要由杂交、变异、嫁接、剪接及评价5部分组成.假定结点数大小为n ,种群规模为N ,度约束值为d c ,则杂交操作的时间复杂度为O (N ×n 2),变异操作的时间复杂度为O (N ×n 2),嫁接操作的最坏时间复杂度为O (N ×n 3).而在剪接操作中,考虑到树、回溯和冲突解决的最坏情形,其最坏时间复杂度为O (N ×(n × (n −1−d c )×n ×n )),而评价的时间复杂度为O (N ×n ×d c ),因此在一代运算中,算法的最差时间复杂度为2233243()()()()((1)( (2).c c c c T n O N n O N n O N n O N n n d O N n d O N n N n d N n N n d =×+×+×+××−−+××=××+××+×−××在本文所讨论的结点规模范围内,N 的取值与n 无关,度约束值d c 一般为常数3,因此,T (n )=O (2×N ×n 2+N ×n +N ×n 4−N ×n 3×d c )≈O (n 4).通过对测试用例计算时间的曲线拟合及分析,可得出本文算法的平均时间复杂度为O (n a ),2.5<a <3.0.我们认为,在算法中由于增加嫁接和剪接算子操作,虽然算法的最坏计算复杂度理论值可达O (n 4).但这一过程没有破坏模式定理和隐含并行性定理,上述两定理在本文算法中的基本遗传算子(杂交与变异算子)及新算子中均发挥作用.所不同的是,由于增加了知识的作用及冲突的解决,使得新算子由一种近似随机的搜索变成一种在知识指导下按一定方向进行的搜索.另一方面,评价算法性能的一个重要指标是评价次数,通过对non-Euclidean 和Euclidean 两大类测试问题的实验分析,本文算法在得到所求问题相同解精度解的评价次数均远低于相关文献给出的数据.即使考虑在一代中计算代价(或计算时间)的增加量,本文算法对所求问题的求解精度和收敛速度方面都有较大提高.4 实验及分析为了验证本文所提算法GPOGA 在求解DCMST 问题的有效性和正确性,我们在VC 环境下采用C/C++编程,某些图形曲线根据计算数据由Matlab 绘制输出.在对实验数据进行比较和分析时,本文采用以下几个指标作为对通过算法得到所求DCMST 问题的最好解的精度和算法的性能进行评价的依据,它们分别是:评价(次)数(evalutions)[1];最好解偏差(best-gap);平均最好解偏差(average-best gap).首先,我们对一个经典的9结点完全图DCMST 问题进行求解,该问题在度为3时的最好解为2 256[1].遗传操作基本参数设置与对比文献[3,9]所给参数设置基本相同.为避免随机性影响,我们进行了1 000轮测试.得到的实验结果为:在度约束为3时的最好解为2 256,最小收敛代数为1,最大收敛代数为5,平均收敛代数为1.52;算法在1 000轮测试中均收敛到2 256,即算法得到该问题最优解的概率为100%.这一测试结果,无论从算法的收敛速度还是算法收敛到最优解的概率均优于相关文献提供的实验数据.4.1 Non-Euclidean 图例DCMST 问题测试我们参照有关文献所提方法设计了一个专用的随机数生成器,该生成器按均匀随机方式产生[10,100]之间。

《基于单亲遗传算法的度约束最小生成树问题研究》篇一一、引言度约束最小生成树问题（Degree-Constrained Minimum Spanning Tree Problem, DC-MST）是图论领域中一个重要的研究课题。

该问题主要关注在给定图上寻找满足特定度约束条件的生成树，同时要求生成树的权值之和最小。

近年来，随着网络规模的不断扩大和复杂性的增加，度约束最小生成树问题在通信网络、生物信息学、社交网络等领域得到了广泛的应用。

传统的求解方法如贪心算法、动态规划等在处理大规模问题时往往效率较低，因此，寻找更高效的算法成为了一个重要的研究方向。

本文将探讨基于单亲遗传算法的度约束最小生成树问题的求解方法。

二、单亲遗传算法概述遗传算法是一种模拟自然进化过程的搜索算法，通过模拟生物进化过程中的选择、交叉和变异等操作，在解空间中寻找最优解。

单亲遗传算法是遗传算法的一种变种，其特点是在交叉操作中只涉及到一个父代个体，通过变异和选择操作来产生新的个体。

这种算法在处理组合优化问题时具有较高的效率。

三、度约束最小生成树问题描述度约束最小生成树问题是在给定图上寻找满足特定度约束条件的生成树。

其中，图的节点表示网络中的实体，边表示实体之间的连接关系，边的权值表示连接的代价。

度约束条件是指每个节点的连接数量有一个上限或下限的限制。

问题的目标是找到一个生成树，使得树中所有边的权值之和最小，同时满足给定的度约束条件。

四、基于单亲遗传算法的度约束最小生成树问题求解针对度约束最小生成树问题，本文提出了一种基于单亲遗传算法的求解方法。

具体步骤如下：1. 初始化种群：随机生成一定数量的初始解作为种群，每个解表示一个生成树。

2. 适应度函数设计：根据问题的特点，设计适应度函数。

适应度函数应能反映生成树的权值之和以及满足度约束条件的程度。

3. 选择操作：根据适应度函数的值，选择出优秀的个体进入下一代。

4. 交叉操作：在选中的个体中进行单亲交叉操作，生成新的个体。

遗传算法最小生成树遗传算法什么是遗传算法？遗传算法（Genetic Algorithm，GA）是一种基于生物进化思想的随机化搜索优化方法。

它通过模拟自然界中的进化过程，对问题进行求解。

遗传算法的原理1.个体编码：将问题转换为染色体编码的形式。

2.初始种群：随机生成初始种群。

3.适应度函数：根据问题定义适应度函数，用来评估每个个体的优劣程度。

4.选择操作：按照适应度大小选择部分个体作为下一代的父代。

5.交叉操作：对父代进行交叉操作，生成新的后代。

6.变异操作：对后代进行变异操作，增加种群多样性。

7.重复执行步骤4-6，直到满足终止条件。

遗传算法的优缺点优点：1.全局搜索能力强，可以在大规模搜索空间中找到最优解或次优解；2.适用范围广泛，可以处理多种类型和形式的问题；3.具有较好的并行性和可扩展性；4.易于实现和使用。

缺点：1.需要大量计算资源和时间；2.结果不一定是最优解或次优解；3.对问题的建模需要较高的技能和经验。

最小生成树什么是最小生成树？最小生成树（Minimum Spanning Tree，MST）是一种用来解决带权无向图连通性问题的算法。

它通过在图中选择一些边，使得这些边组成一个树，并且这个树包含所有节点，并且权值之和最小。

最小生成树的原理1.首先，将图中所有边按照权值从小到大排序。

2.从第一条边开始，依次遍历每条边：①如果这条边连接的两个节点不在同一个连通分量中，则将这条边加入最小生成树中；②如果这条边连接的两个节点已经在同一个连通分量中，则不加入最小生成树中。

3.重复执行步骤2，直到所有节点都被包含在最小生成树中。

最小生成树的优缺点优点：1.可以保证所得到的解是全局最优解；2.算法简单易行；3.适用范围广泛。

缺点：1.只适用于带权无向图；2.对于稠密图而言，时间复杂度比较高；3.对于动态变化的图而言，需要重新计算整个最小生成树。

《基于遗传算法的直径限制最小生成树问题的研究》篇一一、引言在图论中，最小生成树问题是一个经典且重要的组合优化问题。

该问题通常涉及在一个带权图中寻找一棵包含所有节点的树，使得这棵树的权值之和（即所有边的权重之和）最小。

而在实际的应用场景中，常常存在一些特定的限制条件，例如直径限制。

直径限制最小生成树问题就是在满足生成树的直径不超过某一特定值的前提下，寻找权值和最小的生成树。

近年来，随着人工智能和优化算法的不断发展，遗传算法作为一种全局搜索优化算法，在解决复杂组合优化问题中表现出强大的优势。

本文将基于遗传算法对直径限制最小生成树问题进行深入研究，旨在寻找更高效的求解方法和优化策略。

二、遗传算法概述遗传算法是一种模拟自然进化过程的搜索算法，通过模拟生物进化过程中的选择、交叉和变异等操作，在解空间中寻找最优解。

在解决最小生成树问题时，遗传算法可以通过编码生成树为染色体，将边权作为染色体上基因的编码，通过进化操作逐步寻找最优解。

三、基于遗传算法的直径限制最小生成树问题研究1. 问题建模在直径限制最小生成树问题中，我们需要将图中的节点和边进行编码，形成染色体。

每个染色体代表一棵生成树，其基因值（即边的权重）决定了生成树的权值和及直径。

我们通过设定一个阈值作为直径限制条件，筛选出满足条件的生成树。

2. 编码与初始化在遗传算法中，我们需要将生成树进行编码，以便于进行后续的选择、交叉和变异操作。

常用的编码方式包括实数编码、二进制编码等。

在初始化阶段，我们随机生成一定数量的初始解（即生成树），形成初始种群。

3. 选择操作选择操作是遗传算法中的重要步骤，其目的是从当前种群中选择出优秀的个体，使其有机会产生后代。

在直径限制最小生成树问题中，我们可以通过比较生成树的权值和及直径来选择优秀的个体。

常用的选择策略包括轮盘赌选择、锦标赛选择等。

4. 交叉操作交叉操作是通过交换两个个体的部分基因来产生新的个体。

在直径限制最小生成树问题中，我们可以通过交换两个生成树的边来产生新的生成树。

《基于遗传算法的直径限制最小生成树问题的研究》篇一一、引言最小生成树问题（Minimum Spanning Tree Problem，MST问题）是图论中一项经典问题，常用于描述网络的拓扑结构优化问题。

其中，基于边权最小化且生成的树是无向图中最小生成树的要求是关键。

然而，在某些特定场景下，如通信网络、电力系统等，我们往往需要考虑到网络的直径限制，即网络中任意两点间最短路径的最大长度。

这导致传统的最小生成树算法无法满足需求，因此，基于直径限制的最小生成树问题逐渐成为了研究的热点。

本篇论文旨在探索基于遗传算法的直径限制最小生成树问题的解决方法。

二、遗传算法介绍遗传算法（Genetic Algorithm）是一种启发式搜索算法，模拟自然选择与生物进化的进化论思想。

它通过模拟生物进化过程中的选择、交叉、变异等操作，在搜索空间中寻找最优解。

遗传算法具有全局搜索能力强、易于并行化等优点，适用于解决复杂优化问题。

三、直径限制最小生成树问题描述直径限制最小生成树问题是在MST问题的基础上增加了一个新的约束条件：所求的生成树的直径不能超过某个预定的值。

在现实应用中，这一限制对于网络稳定性、延迟等方面具有重要影响。

该问题的求解不仅需要满足生成树的边权之和最小，还需要满足网络直径的限制条件。

四、基于遗传算法的解决方案为解决基于直径限制的最小生成树问题，我们设计了一种基于遗传算法的求解策略。

主要步骤包括：1. 编码：将解空间中的解编码为遗传算法的染色体。

每个染色体代表一个可能的生成树结构。

2. 初始化：随机生成一定数量的初始染色体作为种群的初始解。

3. 选择：根据染色体的适应度选择优秀的个体进入下一代。

适应度函数设计为生成树的边权之和与直径的加权和，以平衡最小化边权和与满足直径限制的需求。

4. 交叉：通过交叉操作产生新的染色体，增加种群的多样性。

5. 变异：对染色体进行随机变异操作，以引入新的基因组合和结构。

6. 迭代：重复选择、交叉和变异操作，直到满足终止条件（如达到最大迭代次数或适应度达到预设阈值）。

基于DNA计算的遗传算法解决最小生成树问题
韩世芬
【期刊名称】《鄂州大学学报》
【年(卷),期】2008(15)2
【摘要】给出了最小生成树问题(MST)的一个基于混合DNA计算的遗传算法模型.在该模型中.为了对最小生成树的解进行编码和解码,通过引入DNA计算,提出了一种最小生成树问题的改进遗传算法编码方案,该方案吸收了DNA计算和遗传算法的优点,具有固定的长度.为了搜索需要的最佳编码.引入遗传算法搜索技术,并给出了自适应的交叉算子和变异算子.最后,根据最小生成树问题的特点.通过实例仿真验证了所提出的基于DNA计算的遗传算法的有效性.
【总页数】3页(P22-24)
【作者】韩世芬
【作者单位】鄂州大学,计算机系,湖北,鄂州,436000
【正文语种】中文
【中图分类】TP319
【相关文献】
1.基于遗传算法度约束的最小生成树问题的研究 [J], 董军;关凤岩;吕宗宝
2.遗传算法在度约束最小生成树问题中的应用 [J], 田小梅;龚静
3.基于模糊费用最小生成树问题的算法设计 [J], 罗世亮
4.求解度约束最小生成树问题的自适应遗传算法 [J], 田小梅;郑金华
5.基于Prim算法的度约束最小生成树问题研究 [J], 孙小军
因版权原因，仅展示原文概要，查看原文内容请购买。

最小生成树克鲁斯卡尔算法
最小生成树克鲁斯卡尔算法是一种基于贪心思想的图论算法，主
要用于解决图的最小生成树问题。

该算法精简高效，在实际应用中广
泛使用。

最小生成树问题是指，在一个带权无向图中，选取一些边，使得
它们组成一棵树，且这棵树的所有边的权值之和最小。

这个问题可以
用克鲁斯卡尔算法来解决。

克鲁斯卡尔算法的思想是，首先将所有边按照权值从小到大排序，依次将每条边加入到已选的边集合中，如果加入该边后形成了环路，
则不选择该边。

最终生成的边集合就是该图的最小生成树。

这个算法的时间复杂度为O(ElogE)，其中E为边数。

虽然速度不
如其他复杂度更快的算法，但克鲁斯卡尔算法的代码简洁易懂，并且
适用于边数较小的图，正因为如此，在实际应用中它的使用非常广泛。

在大型计算机网络中，最小生成树算法常用于广域网的拓扑设计
问题。

在城市交通规划中，也可以应用最小生成树算法，来设计更加
合理的交通路线。

需要注意的是，最小生成树仅仅是起到了将所有节点连接起来的
作用，它并不保证任意两个节点之间都有最短路径。

如果需要求解两
点间的最短路径问题，需要使用单源最短路径算法，如Dijkstra算法
和Bellman-Ford算法等。

总之，最小生成树克鲁斯卡尔算法在实际应用中扮演着重要的角色，尤其在计算机网络和城市规划领域的应用非常广泛。

学习并掌握这个算法，对于解决实际问题具有重要的指导意义。

《基于遗传算法的直径限制最小生成树问题的研究》篇一一、引言在图论中，最小生成树问题是一个经典的优化问题，其目标是在给定的连通图中找到一棵包含所有节点的树，且所有边的权重之和最小。

在实际应用中，尤其是网络设计、无线通信和电路设计等领域，往往存在对树形结构的直径有所限制的场景。

这种带直径限制的最小生成树问题（D-MST，Diameter-constrained Minimum Spanning Tree）的研究具有很高的实用价值。

本文将主要探讨基于遗传算法的直径限制最小生成树问题的研究。

二、问题描述在给定的连通图中，我们不仅要找到权重和最小的生成树，还需要满足树的直径不超过某一预定值。

直径是指树中任意两个节点之间最长路径的边数或权重之和。

D-MST问题是一个NP难问题，传统的优化算法往往难以在合理的时间内找到最优解。

因此，需要寻找一种能够快速寻找近似最优解的算法。

三、遗传算法介绍遗传算法是一种模拟自然进化过程的优化算法，通过模拟生物进化过程中的选择、交叉和变异等操作，寻找问题的最优解。

在解决D-MST问题时，我们可以将每个生成树看作一个个体，其编码方式可以采用二进制编码或实数编码等方式表示。

通过不断迭代进化，最终得到满足直径限制的最小生成树。

四、算法设计1. 编码方式：采用实数编码方式表示每个生成树的边权值。

2. 初始化种群：随机生成一定数量的初始解作为种群。

3. 适应度函数：定义适应度函数为生成树的边权之和与直径的加权和。

这样可以在优化边权和的同时考虑直径的限制。

4. 选择操作：根据适应度函数的值选择优秀的个体进入下一代。

5. 交叉操作：对选中的个体进行交叉操作，生成新的个体。

6. 变异操作：对新的个体进行随机扰动，增加种群的多样性。

7. 终止条件：达到最大迭代次数或适应度函数值满足要求时停止迭代。

五、实验结果与分析我们通过多个测试用例对基于遗传算法的D-MST问题进行实验验证。

实验结果表明，该算法能够在较短的时间内找到满足直径限制的近似最优解。

基于遗传算法的最小生成树算法
周荣敏;买文宁;雷延峰
【期刊名称】《郑州大学学报（工学版）》
【年(卷),期】2002(023)001
【摘要】以图论和遗传算法为基础,提出了一种求最小生成树的改进遗传算法.该算法采用二进制编码表示最小树问题,用深度优先搜索算法进行图的连通性判断,并设计出相应的适应度函数、单亲换位算子和单亲逆转算子以及四种控制性进化策略,以提高算法执行速度和进化效率.与Kruskal 算法相比,该算法能在一次遗传进化过程中获得一批最小生成树,适合于解决不同类型的最小树问题.
【总页数】4页(P45-48)
【作者】周荣敏;买文宁;雷延峰
【作者单位】郑州大学环境与水利学院,河南,郑州,450002;郑州大学环境与水利学院,河南,郑州,450002;郑州大学环境与水利学院,河南,郑州,450002
【正文语种】中文
【中图分类】O157.6
【相关文献】
1.基于最小生成树算法和改进遗传算法的配电网络综合优化 [J], 王磊;庄园
2.基于DNA计算的遗传算法解决最小生成树问题 [J], 韩世芬
3.基于改进遗传算法的最小生成树算法 [J], 刘志成;钱建刚
4.一种基于遗传算法的度约束最小生成树求解方法 [J], 帅训波;马书南
5.基于遗传算法的广义最小生成树求解与应用 [J], 段渊
因版权原因，仅展示原文概要，查看原文内容请购买。

基于Prim算法的度约束最小生成树问题研究孙小军【摘要】Based on the Prim algorithm,a algorithm is designed to solve a kind of the degree-constrained Mini-mum spanning tree problem.With the given node being maximum degree assured by this algorithm,it comes out the minimum spanning tree of the given node under the maximum degree constraint in the network.Finally,according to simulation comparison between the algorithm and classical Glove-klingman algorithm,it is verified that the algorithm is an effective method in solving the minimum spanning tree under the maximum degree constraint about a given node.%针对一类度约束最小生成树问题，基于传统最小生成树问题的Prim算法，设计了一种求解算法。

该算法在保证网络中指定节点的度不变的前提下，构造了网络关于指定节点的最大度最小生成树。

与经典的 Glove-klingman算法进行了仿真比较，结果表明，该算法是求解度约束最小生成树问题的一种有效算法。

【期刊名称】《内蒙古师范大学学报（自然科学汉文版）》【年(卷),期】2016(045)004【总页数】4页(P445-448)【关键词】度约束;最大度最小生成树;Prim算法;Glove-klingman算法【作者】孙小军【作者单位】宝鸡文理学院数学与信息科学学院，陕西宝鸡 721013【正文语种】中文【中图分类】TP301.6最小生成树问题[1]是组合优化中一个有重要理论意义和应用价值的经典问题.该问题历史悠久,它是在寻求电力线网络的最优经济布局时,由Boruvka[2]于1926年首次提出,随后被用于解决网络优化、运筹学等领域的相关问题,在交通运输、城市规划、经济管理、通讯与网络技术、计算机科学与信息技术等领域也得到了广泛应用,同时衍生出了众多研究分支,度约束最小生成树(Degree-constrained Minimum Spanning Tree,DCMST)问题[3]就是其中一种重要的扩展类型.DCMST问题的概念最早由Narula等[4]提出,他们还设计了一种分枝限界法求解较小规模DCMST问题的最佳解.2001年Caccetta等[5]提出一种求解DCMST问题的分枝和剪切算法; 2006年Andrade等[6]提出了基于双重解信息的Lagrangian 算法; 2007年Behle等[7]利用0-1整型规划中的问题分离原则,提出一种优先的分枝和剪切算法; 2008年焦森林[8]基于最小生成树问题的避圈法和权矩阵法,设计了最大度最小生成树问题的两种求解算法; 2010年袁卫东[9]提出一种基于Dijkstra 算法求解最大度最小生成树问题的方法.近些年来,人们开始把具有全局优化性、通用性且适合并行处理等特点的智能优化算法用于求解DCMST 问题[10-13].然而,大量应用实例及实验数据显示,这些算法虽然有着传统优化算法不可比拟的优势,但也存在易早熟收敛、后期震荡、局部寻优能力弱等不足.本文针对一类度约束最小生成树问题,结合问题特征,提出一种基于Prim算法的求解算法.该算法在保证网络G中指定节点v0的度不变的前提下,在|V|-|VG(v0)|-1个特殊的边割中,每次选取每个边割的一条权最小的边,最终构造出G关于指定节点v0的最大度最小生成树.定义1[8] 设G(V,E,W)是一个简单连通无向网络,v0∈V是G中指定的一个节点,k 为给定的一个正整数.如果T是G的一个支撑树且dT(v0)=k,则称T为网络G关于节点v0的k度限制支撑树.定义2[8] 设G(V,E,W)是一个简单连通无向网络,v0∈V是G中指定的一个节点.在G的所有支撑树中,使得v0的度最大且整个支撑树的权最小的那些支撑树称为网络G关于节点v0的最大度最小生成树.定理1[8] 设G(V,E,W)是一个简单连通无向网络,v0∈V是G中指定的一个节点,则网络G关于节点v0的最大度最小生成树T′一定存在,且dT′(v0)=dG(v0) (其中dT′(v0)表示节点v0在T′中的度,dG(v0)表示节点v0在G中的度).定理2[14] 设C和分别是图G的圈和补圈,则(mod 2).在简单连通无向网络G=G(V,E,W)中,V={v1,v2,…,vn}是节点的有限集合,E是边的有限集合,W=(wi j)n×n表示网络的权矩阵,其中wi j=wj i,wi i=+∞ (i,j=1,2,…,n); 若vivj∈E,wi j=w(vivj),否则wi j=+∞.并设各节点的度约束为bi (i=1,2,…,n),则DCMST问题的数学模型[15]为mins.t.其中,变量为集合S中所含图G的节点个数,约束(1)为节点的度限制,约束(2)和(3)保证所得的是一棵生成树.上述模型中,当某个bi<n-1,其余bi≥n-1时,即为本文要讨论的单点度约束最小生成树问题.3.1 算法思想和步骤在保证网络G中指定节点v0的度不变的前提下,结合Prim算法,在|V|-|VG(v0)|-1个特殊的边割中,每次选取每个边割的一条权最小的边,构成G的一个权最小的支撑树,即为G关于指定节点v0的最大度最小生成树.Step 0 求VG(v0),EG(v0).其中VG(v0)表示G中与v0相邻的点集,EG(v0)表示G 中与v0关联的边集.令.Step 1 若Sk=V,结束,得到Tk为G的最大度最小生成树; 否则转Step 2.Step 2 求].若Ø,则停止,G中不存在关于v0的最大度支撑树; 否则,选取.令,转Step 1.3.2 算法的证明定理3 由本文算法得到的Tk为原网络G关于指定节点的最大度最小生成树.证明算法是在保证简单连通无向网络G中指定节点v0的度不变的前提下,结合Prim算法思想求解得到G的支撑树的,所以最终得到的Tk一定是G的最大度支撑树.下证Tk也是G的最大度最小生成树.设Ω是G的一个边割,e 0是Ω中权最小的边,令ζ(e 0)={T|T是G的最大度支撑树且e 0∈E(T)}.先证G中存在一个最大度最小生成树T′,使e 0∈E(T′).事实上,任取G 的一个最大度最小生成树T*,若e 0∈E(T*),取T′=T*; 若e 0∉E(T*),选取G中关于T*的基本圈C(e 0).由定理2,存在e′∈E(C(e 0))∩Ω,e′≠e 0.因为e′∈Ω,e 0是Ω中权最小的边,则w(e 0)≤w(e′).令T′=T*+e 0-e′,则w(T′)≤w(T*),即T′是G的一个最大度最小生成树,且e 0∈E(T′),所以T′∈ζ(e 0).又当Tk是ζ(e 0)中权最小的最大度支撑树时,w(Tk)≤w(T′).由于Tk是G的最大度支撑树,T′是G的最大度最小生成树,因此Tk是G的最大度最小生成树.3.3 应用实例某公司在A地区设有2个代理商,通常由物流将产品配送给各代理商后,再由代理商将产品配送到该地区各销售点.但公司发现,如果只由代理商直接供货,不仅配送费用高,而且会出现供应不及时、断货现象.为了适应市场的实际供求形势,更好地服务各销售点,公司允许各销售点之间可以相互供货.现有一批产品由公司配送给代理商后,试问如何配送才能使总的配送费用最少.公司、代理商及销售点之间的配送网络G 如图1所示,其中节点v0表示公司,节点v1,v2表示代理商,节点v3,v4,v5表示销售点,图中的权值表示各节点之间的配送费用.图1是一个简单连通无向网络,该问题即为求网络G关于节点v0的最大度最小生成树.第一次迭代:Step 1 由于S0≠V,转Step 2;}.取w(v1v3)=min }.经过3次迭代后,S3=V,结束,得到的T3即为G的最大度最小生成树,如图2所示.3.4 仿真实验为了更好地对本文算法的性能进行分析,使用美国Salama博士提出的Waxman随机拓扑生成器进行仿真实验.该拓扑生成器产生的随机网络具备仿真网络要求的特性,在算法性能研究中被广泛使用.具体使用时可以通过调整参数的取值,使之更接近真实网络.仿真实验的硬件平台为Inter Core处理器,主频2.0 GHz,内存1 G.对网络G的最小生成树T中的dT(v0)与dG(v0)相差较大的情形,通过拓扑生成器生成8个最大度不同的连通网络,并利用本文算法和Glove-klingman算法计算其最大度最小生成树,两种算法的运行时间见表1.表1数据显示,对网络G的最小生成树T中的dT(v0)与dG(v0)相差较大的情形,随着指定节点最大度的增加,与Glove-klingman算法相比,本文算法的运算速度有明显的提高.另外对网络G的最小生成树T中的dT(v0)与dG(v0)接近且边稀疏的情形,仿真实验出现了Glove-klingman算法优于本文算法的结果,这表明对于边稠密的网络,本文算法较Glove-klingman算法更有效.本文讨论了一类度约束最小生成树问题,在分析其数学模型的基础上,结合Prim算法,设计了一种求解该问题的精确算法.利用Waxman随机网络模型进行的仿真结果显示,相比经典的Glove-klingman算法,该算法对边稠密的网络更有效.但由于DCMST问题本身是一类难解的NP-hard问题,当问题规模太大时,采用精确算法对其求解的效率往往不理想,甚至很难得到问题的最优解.因此,有效结合精确算法和智能优化算法的优势,设计求解DCMST问题的高效算法具有重要的实际意义和应用价值.【相关文献】[1] Ahuja R K,Magnanti T L,Orlin J B. Network Flows:Theory,Algorithms,and Applications [M]. Beijing:Mechanical Industry Press,2005:510-536.[2] Graham R,Hell P. On the History of the Minmum Spanning Tree Problem [J]. Annimals of the History of Computing 1985,7(1):43-57.[3] Gen M,Cheng R W. Genetic Algorithms and Engineering Optimization [M]. Beijing:Tsinghua University Press,2004.[4] Narula S C,Ho C A. Degree-constrained minimum spanning tree [J]. Computers and Operations Research,1980,7(4):239-249.[5] Caccetta L,Hill S P. A branch and cut method for the degree-constrained minimum spanning tree problem [J]. Networks,2001,37(2):74-83.[6] Andrade R,Lucena A,Maculan N. Using Lagrangian dual information to generate degree constrained spanning trees [J]. Discrete Applied Mathematics,2006,154(5):703-717.[7] Behle M,Jünger M,Liers F. A primal branch-and-cut algorithm for the degree-constrained minimum spanning tree problem [C]// Demetrescu C. LNCS 4525.Berlin,Heidelberg,New York: Springer-Verlag,2007:379- 392.[8] 焦森林. 度约束最小生成树算法 [D]. 西安:西安电子科技大学数学与统计学院,2008.[9] 袁卫东. 一类度约束最小生成树问题的Dijkstra算法 [J]. 科学技术与工程,2010,10(8):1898-1891.[10] Almeida A M D,Martins P,Souza M C D. Min-degree constrained minimum spanning tree problem:complexity,properties,and formulations [J]. International Transactions in Operational Research,2012,19(3):323-352.[11] Bui T N,Deng X,Zmcic C M. An improved ant-based algorithm for the degree-constrained minimum spanning tree problem [J]. Evolutinary Computation IEEE Transactions on,2012,16(2):266-278.[12] Torkestani J A. Degree constrained minimum spanning tree problem:a learning automata approach [J]. Journal of Supercomputing,2013,64(1):226-249.[13] 孙小军. 模糊权值网络最小生成树问题研究 [J]. 内蒙古师范大学学报:自然科学汉文版,2015,44(4):435-438.[14] 谢政. 网络算法与复杂性理论 [M]. 长沙:国防科技大学出版社,2003.[15] 王竹荣,张九龙,崔杜武. 一种求解度约束最小生成树问题的优化算法 [J]. 软件学报,2010,21(12):3068-3081.。

［摘要］Sollin 算法是一种非常适合于并行计算的求解最小生成树方法，但其较高时间复杂度抵消了并行计算带来的好处。

本文提出了一种递归的堆调整实现方法以及堆合并原则，解决了Sollin 算法在子树合并时快速找到连接两棵相邻子树的最短的边的问题，降低最小生成树求解的时间复杂度。

理论分析表明，该改进方法有效地将Sollin 算法的时间复杂度由O （n2log2n ）降低到了O （elog2n ）。

同时，根据边权重的分布情况不同，该算法并非必须遍历所有的边才能得到MST ，实际时间复杂度将优于O （elog2n ），最优可达O(n(log2n)2)。

［关键词］最小生成树;Sollin 算法；堆调整；递归方法；子树合并［中图分类号］TP18［文章标识码］A［文章编号］1671-5136(2015)02-0135-03［收稿日期］［基金项目］［作者简介］1.引言最小生成树算法被广泛应用于城市道路、管道、计算机传输网络建设规划以及电子线路设计中，如在n 个城市之间建立起互联网络光传输线路，由于光传输线路建设成本高昂且数据传输时间基本不受传输距离影响，故不会在每对城市之间建立起传输链路，而是根据城市之间建立链路的成本规划出总体建设成本最低的解决方案。

关于最小生成树的求解方法，比较经典的有Prim 算法、Kruskal 算法，这两种算法在教科书中被广泛引用[1-2]。

Sollin 算法[3]是一种结合了Prim 算法和Kruskal算法思想的一种最小生成树求解方法，其原理为：算法开始时，图中的n 个顶点视为一片森林，每个顶点视为一棵子树；每次通过找到连接两棵子树的最小[基金项目：国家自然科学基金项目（50875087）作者简介:殷雯（1983-），女（汉），湖南益阳人，硕士，主要研究方向为算法、数据挖掘；徐海军(1980－),男（汉），湖南永州人，系统分析员,硕士研究生,主要研究方向为柔性工作流、并行计算；马佩勋(1978－),男（汉）,湖南湘潭人,副教授，硕士研究生,主要研究方向为程序验证、数据挖掘；]邻边，实现子树的合并；直到所有子树合并成一棵树结束。