度约束最小生成树(DCMST)的竞争决策算法 被引量：21

1

作者 宁爱兵 马良 《系统工程学报》 CSCD 北大核心 2005年第6期630-634,共5页

度约束最小生成树是网络设计和优化中的一个NP难题,介绍了一种基于竞争造就优化和决策左右结果的新型算法———竞争决策算法,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法,经过数据测试... 度约束最小生成树是网络设计和优化中的一个NP难题,介绍了一种基于竞争造就优化和决策左右结果的新型算法———竞争决策算法,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法,经过数据测试和验证,并与其它算法的结果进行了比较,得到了较好的结果. 展开更多

关键词 度约束最小生成树 竞争决策算法 竞争力函数 决策函数

在线阅读 下载PDF 职称材料

一种求解度约束最小生成树问题的优化算法 被引量：5

2

作者 王竹荣 张九龙 崔杜武 《软件学报》 EI CSCD 北大核心 2010年第12期3068-3081,共14页

为求解大规模结点度约束最小生成树问题，提出一种带有嫁接和剪接算子操作的优化算法．通过借鉴花草果树种植技术，建立一种以基本遗传算子为基础、带有加速和调节算子作为激励的进化计算体系；嫁接以一种贪婪的思想加速搜索，按收益最... 为求解大规模结点度约束最小生成树问题，提出一种带有嫁接和剪接算子操作的优化算法．通过借鉴花草果树种植技术，建立一种以基本遗传算子为基础、带有加速和调节算子作为激励的进化计算体系；嫁接以一种贪婪的思想加速搜索，按收益最大化原则进行剪接．对可能陷入局部极值引起冲突的现象及冲突检测的方法进行分析，并提出了冲突的若干解决方法．针对DCMST问题求解中的复杂性，提出了几种有效的嫁接和剪接的策略，并对算法的收敛性和计算复杂度进行了分析．通过该算法对结点数为50-500之间的Euclidean问题和按均匀随机方式产生的non—Euclidean度约束最小生成树问题进行求解与现有文献的实验结果对比表明，该方法在求解最好解的精度和收敛速度上均有一定的优势． 展开更多

关键词 度约束最小生成树 遗传算法 嫁接 剪接

在线阅读 下载PDF 职称材料

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

3

作者 帅训波 马书南 《曲阜师范大学学报（自然科学版）》 CAS 2010年第1期55-58,共4页

度约束最小生成树是一个NP问题.提出了应用基于分段编码遗传算法求解度约束最小生成树的方法,给出了算法设计、算法描述和实例分析,并且对遗传操作产生的非法染色体进行修正.经过数据测试验证,该求解方法是可行的,与其它算法相比较,有... 度约束最小生成树是一个NP问题.提出了应用基于分段编码遗传算法求解度约束最小生成树的方法,给出了算法设计、算法描述和实例分析,并且对遗传操作产生的非法染色体进行修正.经过数据测试验证,该求解方法是可行的,与其它算法相比较,有着较好的求解效果. 展开更多

关键词 度约束最小生成树 遗传算法 分段编码 染色体修正

在线阅读 下载PDF 职称材料

度约束最小生成树的元胞竞争决策算法 被引量：2

4

作者 熊小华 宁爱兵 《上海第二工业大学学报》 2011年第3期207-213,共7页

度约束最小生成树(Degree-Constrained Minimum Spanning Tree,简记DCMST)是网络设计和优化中的一个经典的组合优化难题。竞争决策算法是一种特别适合于求解组合优化难题的新型算法。为了提高求解DCMST问题的求解精度,将元胞自动机的邻... 度约束最小生成树(Degree-Constrained Minimum Spanning Tree,简记DCMST)是网络设计和优化中的一个经典的组合优化难题。竞争决策算法是一种特别适合于求解组合优化难题的新型算法。为了提高求解DCMST问题的求解精度,将元胞自动机的邻居演化原理和竞争决策算法相结合——元胞竞争决策算法来求解DCMST;为了提高算法的效率,分析了度约束最小生成树问题的数学性质并利用这些性质对问题实现降阶。降阶过程会有效降低问题处理的规模。为了验证算法的性能,采用Delphi 7.0实现算法,经过数据测试和验证,并与其他算法的结果进行比较,证明了算法的有效性。 展开更多

关键词 竞争决策算法 元胞自动机 度约束最小生成树 降阶

在线阅读 下载PDF 职称材料

遗传算法在度约束最小生成树问题中的应用 被引量：1

5

作者 田小梅 龚静 《湖南环境生物职业技术学院学报》 CAS 2009年第3期1-4,共4页

遗传算法是一类借鉴自然界生物种群"自然选择、优胜劣汰"进化过程的启发式随机搜索优化算法,具通用性好、鲁棒性强等特点,被广泛地应用于通信网络设计领域,如度约束最小生成树问题.通过讨论遗传算法在度约束最小生成树问题中... 遗传算法是一类借鉴自然界生物种群"自然选择、优胜劣汰"进化过程的启发式随机搜索优化算法,具通用性好、鲁棒性强等特点,被广泛地应用于通信网络设计领域,如度约束最小生成树问题.通过讨论遗传算法在度约束最小生成树问题中的应用,并对遗传算法在应用时存在的问题和挑战提出了见解.参17. 展开更多

关键词 遗传算法 约束最小生成树 度约束最小生成树

在线阅读 下载PDF 职称材料

求解度约束最小生成树问题的自适应遗传算法

6

作者 田小梅 郑金华 《衡阳师范学院学报》 2005年第3期19-22,共4页

在遗传算法中一个关键问题是必须采取措施保持种群多样性,防止算法出现早熟收敛。本文提出了一种基于父个体相似度的自适应遗传算法,使用新的自适应遗传操作策略以保持种群多样性。将新算法用于求解图的度约束最小生成树问题,实验结果... 在遗传算法中一个关键问题是必须采取措施保持种群多样性,防止算法出现早熟收敛。本文提出了一种基于父个体相似度的自适应遗传算法,使用新的自适应遗传操作策略以保持种群多样性。将新算法用于求解图的度约束最小生成树问题,实验结果表明本方法到比不使用父个体相似度信息的普通遗传算法权值更低的度约束最小生成树。 展开更多

关键词 相似度 最小生成树 度约束最小生成树

在线阅读 下载PDF 职称材料

求解度约束最小生成树的改进ACS算法 被引量：3

7

作者 王志杰 全惠云 《计算机工程》 CAS CSCD 北大核心 2009年第21期195-196,199,共3页

针对蚂蚁系统算法求解度约束最小生成树时收敛速度慢和早熟问题,提出一种改进的蚁群系统算法UDA-ACS。该算法在保留蚁群系统算法优点的基础上,通过增大能见度的影响力、采用动态负反馈机制和赋予不同初始信息素的方法解决上述问题。理... 针对蚂蚁系统算法求解度约束最小生成树时收敛速度慢和早熟问题,提出一种改进的蚁群系统算法UDA-ACS。该算法在保留蚁群系统算法优点的基础上,通过增大能见度的影响力、采用动态负反馈机制和赋予不同初始信息素的方法解决上述问题。理论分析和实验结果证明,该算法的求解质量和速度比蚂蚁系统算法更优越。 展开更多

关键词 蚂蚁系统算法 度约束最小生成树 蚁群系统算法

在线阅读 下载PDF 职称材料

求解度约束最小生成树的单亲遗传算法 被引量：14

8

作者 宋海洲 《系统工程理论与实践》 EI CSCD 北大核心 2005年第4期61-66,共6页

　提出了求解度约束最小生成树问题的单亲遗传算法.该算法首先利用Prufer数对生成树进行编码;然后精心地设计了一个随机地产生初始种群的方法,用这种方法产生的初始种群,不会含有任何不可行解;在遗传操作中只使用选择和变异操作,共设计... 　提出了求解度约束最小生成树问题的单亲遗传算法.该算法首先利用Prufer数对生成树进行编码;然后精心地设计了一个随机地产生初始种群的方法,用这种方法产生的初始种群,不会含有任何不可行解;在遗传操作中只使用选择和变异操作,共设计了三种变异操作,其中两种变异操作均不会产生不可行解,只有一种变异操作可能会产生不可行解,需要作树的度的检查和修改;这样就大大的降低了不可行解产生的机会,从而提高了遗传算法的效率;而且只使用变异算子,有效的避免了早熟收敛现象的产生;通过大量的数值试验,表明该算法简单,高效,收敛率高;最后对此算法做了适当推广,并给出了用它求解TSP问题的具体步骤和实例. 展开更多

关键词 单亲遗传算法 度约束最小生成树 度 变异

原文传递

基于度约束最小生成树的域间路由恢复算法 被引量：3

9

作者 王禹 张连成 +1 位作者 张宏涛 郭毅 《北京邮电大学学报》 EI CAS CSCD 北大核心 2020年第4期113-119,共7页

低速拒绝服务攻击对于域间路由系统造成威胁,已有失效恢复算法未能有效解决恢复拓扑计算的时间复杂度高和节点聚合控制等问题,为此,提出一种基于度约束最小生成树的失效恢复算法.通过设计基础迁移子算法和复杂迁移子算法,在满足度约束... 低速拒绝服务攻击对于域间路由系统造成威胁,已有失效恢复算法未能有效解决恢复拓扑计算的时间复杂度高和节点聚合控制等问题,为此,提出一种基于度约束最小生成树的失效恢复算法.通过设计基础迁移子算法和复杂迁移子算法,在满足度约束的条件下根据遭袭路由系统生存拓扑构建新的恢复拓扑,并针对上述两类迁移子算法,分别提出关键点选择子算法,用于判定和计算迁移过程所需的关键节点.理论分析和仿真实验结果证明,该算法生成的恢复拓扑在有效控制节点度的同时,具有较优的性能. 展开更多

关键词 域间路由系统 失效恢复 度约束最小生成树 时间复杂度 节点聚合控制

原文传递

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

10

作者 刘林峰 刘业 《通信学报》 EI CSCD 北大核心 2006年第9期71-77,共7页

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

关键词 无线传感器网络 拓扑控制 度约束最小生成树问题 模拟退火算法

在线阅读 下载PDF 职称材料

绿色通信下的矿井优化路由算法 被引量：2

11

作者 徐恒 王建平 +1 位作者 李奇越 罗国军 《电子测量与仪器学报》 CSCD 北大核心 2018年第8期148-156,共9页

随着人类对矿石能源的长期依赖,世界各地都在开采地下矿山,地下开采往往具有一定的危险性,因此许多地下矿山建立了自组织网络,用来管理与获取来自矿工和其他地方的传感器节点的信息。例如矿工位置、巷道环境参数等,在矿难发生时可以及... 随着人类对矿石能源的长期依赖,世界各地都在开采地下矿山,地下开采往往具有一定的危险性,因此许多地下矿山建立了自组织网络,用来管理与获取来自矿工和其他地方的传感器节点的信息。例如矿工位置、巷道环境参数等,在矿难发生时可以及时地对矿工采取救援措施。由于移动传感器节点的电源采用具有容量限制的电池供给,因此基于绿色通信的井下网络是降低网络能耗和延长其寿命的有效方法。为了减少网络的能量消耗,应考虑所有对生命周期有负面影响的因素。研究中引入了度约束最小生成树,以考虑所有异构因素,并为下一步评估分配权重。然后,引入遗传算法对网络中的传感器节点进行分簇,并根据若干异构因素来平衡能量消耗。基于仿真结果的比较,优化路由算法用于地下矿山绿色通信可以有效降低网络能耗,延长网络寿命。 展开更多

关键词 绿色通信 地下矿山 度约束最小生成树 遗传算法 异构网络

在线阅读 下载PDF 职称材料

启发式交叉求解TSP问题的混合遗传算法 被引量：6

12

作者 宋海洲 《系统工程学报》 CSCD 北大核心 2005年第6期625-629,共5页

在给出度约束最小生成树的快速生成方法的基础上,设计了一种启发式交叉求解TSP问题的混合遗传算法.该算法在交叉操作的设计上,与其他遗传算法有本质的不同,该交叉操作是在不违反度约束和不形成圈的前提下,每次从父代基因所拥有的边中加... 在给出度约束最小生成树的快速生成方法的基础上,设计了一种启发式交叉求解TSP问题的混合遗传算法.该算法在交叉操作的设计上,与其他遗传算法有本质的不同,该交叉操作是在不违反度约束和不形成圈的前提下,每次从父代基因所拥有的边中加入权最小的边,从而形成子代.利用该算法得到了TSP CHN144问题迄今为止最好的解. 展开更多

关键词 TSP 遗传算法 初始种群 度约束最小生成树

在线阅读 下载PDF 职称材料

无线光通信网络拓扑形成问题研究

13

作者 程朴 覃慧玲 《舰船电子工程》 2018年第5期143-145,共3页

无线光通信网络初始化过程中,面临着通信对象的优选和节点度的限制。将该问题通过图论中的度约束最小生成树模型来进行表达,并引入度约束最小生成树的一种近似快速算法来加以求解。通过实例证明,该模型和求解算法能够解决网络的拓扑形... 无线光通信网络初始化过程中,面临着通信对象的优选和节点度的限制。将该问题通过图论中的度约束最小生成树模型来进行表达,并引入度约束最小生成树的一种近似快速算法来加以求解。通过实例证明,该模型和求解算法能够解决网络的拓扑形成问题。 展开更多

关键词 无线光通信网络 拓扑形成 度约束最小生成树

在线阅读 下载PDF 职称材料

融合局部搜索策略求解DCMST的改进稳态遗传算法 被引量：3

14

作者 鞠成安 王妮娅 +2 位作者 HANZALA 张书凡 毛剑琳 《重庆邮电大学学报（自然科学版）》 CSCD 北大核心 2023年第5期935-942,共8页

针对目前遗传算法求解度约束最小生成树存在的求解质量不稳定、局部搜索不完全的问题,提出一种融合局部搜索策略求解度约束最小生成树(DCMST)的改进稳态遗传算法。提出服从边隶属度值的度约束初始生成树算法,用来提高初始种群的质量;在... 针对目前遗传算法求解度约束最小生成树存在的求解质量不稳定、局部搜索不完全的问题,提出一种融合局部搜索策略求解度约束最小生成树(DCMST)的改进稳态遗传算法。提出服从边隶属度值的度约束初始生成树算法,用来提高初始种群的质量;在局部搜索时引入禁忌搜索,防止相似解大量重复搜索;融合自适应变量和点替换的局部搜索方法,提升算法的局部搜索能力。仿真结果表明,提出的算法提高了初始解的质量,加快了算法的收敛速度,加强局部搜索从而提高了算法的求解质量,可获得较好的有效性与稳定性。 展开更多

关键词 度约束最小生成树 遗传算法 初始种群 禁忌搜索 局部搜索

在线阅读 下载PDF 职称材料

一种新型的无线传感器执行器网络协议

15

作者 孔鹏 余镇危 《微电子学与计算机》 CSCD 北大核心 2015年第12期8-11,16,共5页

针对无线传感器执行器网络节点能量消耗公平性的问题,提出了一种基于加权维诺图和度约束最小生成树的协议.协议基于加权维诺图的方法将网络分簇,每个簇由一个簇头执行器节点和一些传感器节点组成.协议将网络运行分成多个循环执行的回合... 针对无线传感器执行器网络节点能量消耗公平性的问题,提出了一种基于加权维诺图和度约束最小生成树的协议.协议基于加权维诺图的方法将网络分簇,每个簇由一个簇头执行器节点和一些传感器节点组成.协议将网络运行分成多个循环执行的回合,每个回合根据网络情况重新使用度约束最小生成树算法来计算路由路径.仿真结果显示协议可以提升网络节点剩余能量的公平性,延长网络寿命. 展开更多

关键词 无线传感器执行器网络 维诺图 度约束最小生成树

在线阅读 下载PDF 职称材料

基于Prüfer数的离散粒子群优化算法在TSP问题中的应用 被引量：1

16

作者 严坤妹 《福州大学学报（自然科学版）》 CAS 北大核心 2017年第1期147-150,共4页

通过引入Prüfer数编码、归一化运算、粒子的位置矩阵进行模糊化等操作,将连续型粒子群优化算法改造为离散化PSO.并通过构造旅行商问题的度约束最小生成树,利用DCMST的模糊离散粒子群算法求出最优解.采用TSP的测试实例进行仿真实验... 通过引入Prüfer数编码、归一化运算、粒子的位置矩阵进行模糊化等操作,将连续型粒子群优化算法改造为离散化PSO.并通过构造旅行商问题的度约束最小生成树,利用DCMST的模糊离散粒子群算法求出最优解.采用TSP的测试实例进行仿真实验,证明算法的有效性与实用性. 展开更多

关键词 旅行商问题 Prüfer数编码 粒子群优化算法 度约束最小生成树

在线阅读 下载PDF 职称材料

基于新的树编码方式用免疫遗传算法解决DCMST问题

17

作者 尉志青 《世界科技研究与发展》 CSCD 2009年第6期1063-1065,共3页

本文提出了一种新的树编码方式,可以方便地表达一棵树,简化了树在遗传算法中的编码表达。且新的树编码方式清楚地表达了边的信息,有利于疫苗的设计。此外,本文使用免疫遗传算法,有效地克服了传统遗传算法中解退化的现象。数值实验表明,... 本文提出了一种新的树编码方式,可以方便地表达一棵树,简化了树在遗传算法中的编码表达。且新的树编码方式清楚地表达了边的信息,有利于疫苗的设计。此外,本文使用免疫遗传算法,有效地克服了传统遗传算法中解退化的现象。数值实验表明,解的振荡相对于传统遗传算法减小了,且收敛速度更快。 展开更多

关键词 免疫遗传算法 度约束最小生成树 树编码

原文传递