一种新的求解度约束最小生成树的遗传算法 被引量：6

1

作者 来卫国 李鸥 程军 《计算机仿真》 CSCD 2008年第8期162-165,共4页

染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能。提出了基于过程控制的生成树编码方法——PC编码。PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向... 染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能。提出了基于过程控制的生成树编码方法——PC编码。PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向量控制算法的运行过程,从而得到唯一生成树。为了求解度约束最小生成树(DCMST)问题,在D-Prim算法的基础上,设计了过程可控的度约束生成树构造PC-Prim算法。给出了以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法。仿真结果表明遗传算法求解精度和运行时间均优于参与其他算法。 展开更多

关键词 度约束 最小生成树 遗传算法 过程控制

在线阅读 下载PDF 职称材料

基于混合遗传算法求解CMST问题 被引量：1

2

作者 曲润涛 韩兵 席裕庚 《通信学报》 EI CSCD 北大核心 1999年第10期31-35,共5页

ＣＭＳＴ （Ｃｏｎｓｔｒａｉｎｅｄ Ｍｉｎｉｍ ｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅ）是通信网络拓扑结构设计中经常遇到的问题，一般解决此问题采用启发式方法，本文提出了使用混合遗传算法求解ＣＭＳＴ问题的新算法。

关键词 遗传算法 启发式方法 CMST 通信网

在线阅读 下载PDF 职称材料

基于蚂蚁搜索度约束最小生成树的改进算法 被引量：3

3

作者 赵玲 刘三阳 《计算机仿真》 CSCD 2006年第10期164-166,198,共4页

针对度约束最小生成树问题,对基本的蚁群算法进行改进。提出了度信息的概念来改进转移概率,保证算法获得可行解;同时采用基于度的禁忌表这种数据结构来表示度约束生成树,并与深度优先搜索的思想结合,保证得到树的连通性;将遗传算法中的... 针对度约束最小生成树问题,对基本的蚁群算法进行改进。提出了度信息的概念来改进转移概率,保证算法获得可行解;同时采用基于度的禁忌表这种数据结构来表示度约束生成树,并与深度优先搜索的思想结合,保证得到树的连通性;将遗传算法中的变异特征引入蚁群算法,对生成树进行局部优化。不仅提高算法的效率,而且避免早熟收敛。通过数值试验验证新算法的可行性,并与其他算法进行比较,取得了良好的效果。 展开更多

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

在线阅读 下载PDF 职称材料

基于prüfer数的遗传算法求解度约束最小树问题 被引量：2

4

作者 牧云志 周根贵 《计算机工程与应用》 CSCD 北大核心 2008年第12期53-56,共4页

度约束最小树问题属于NP-完全问题,是一类比较难解的问题,但在现实中具有非常重要的应用价值。探讨了如何将基于prüfer数的遗传算法应用于该问题,并给出了相应的算法。采用C语言和MATLAB的混合编程实现该算法,数值分析的结果显示... 度约束最小树问题属于NP-完全问题,是一类比较难解的问题,但在现实中具有非常重要的应用价值。探讨了如何将基于prüfer数的遗传算法应用于该问题,并给出了相应的算法。采用C语言和MATLAB的混合编程实现该算法,数值分析的结果显示了遗传算法求解该问题的有效性及其应用价值。 展开更多

关键词 prüfer数 遗传算法 最小生成树 度约束

在线阅读 下载PDF 职称材料

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

5

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

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

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

在线阅读 下载PDF 职称材料

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

6

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

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

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

在线阅读 下载PDF 职称材料

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

7

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

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

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

在线阅读 下载PDF 职称材料

基于遗传算法度约束的最小生成树问题的研究 被引量：1

8

作者 董军 关凤岩 吕宗宝 《淮北煤炭师范学院学报（自然科学版）》 2005年第1期10-13,共4页

探讨了如何将遗传算法应用于度约束的最小生成树问题,并给出了相应的算法.实验结果表明,这种用遗传算法解决度约束的最小生成树问题是有效的.

关键词 度约束 最小生成树 遗传算法 实验结果

在线阅读 下载PDF 职称材料

多约束应用层组播的算法研究

9

作者 来卫国 侯惠峰 李鸥 《计算机工程与应用》 CSCD 北大核心 2007年第19期10-12,共3页

研究了基于组播服务节点(MSN)的两层应用层组播网络,提出了度和时延联合约束的最小生成树问题(DDCMST问题),并给出了求解该问题的启发式算法——DD-Prim算法。为了进一步提高求解的精度,在该算法中引入了偏置向量,得到了BDD-PRIM算法,... 研究了基于组播服务节点(MSN)的两层应用层组播网络,提出了度和时延联合约束的最小生成树问题(DDCMST问题),并给出了求解该问题的启发式算法——DD-Prim算法。为了进一步提高求解的精度,在该算法中引入了偏置向量,得到了BDD-PRIM算法,并将其作为染色体编码的译码器应用到遗传算法中。仿真结果证明了遗传算法的有效性。 展开更多

关键词 多约束 组播 最小生成树 遗传算法

在线阅读 下载PDF 职称材料

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

10

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

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

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

在线阅读 下载PDF 职称材料

度、直径约束最小生成树问题及其算法 被引量：2

11

作者 石磊 冯祖针 杨建强 《云南民族大学学报（自然科学版）》 CAS 2012年第4期295-297,共3页

提出了度、直径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法,其时间复杂性为O(mn).分析和实例实验表明,该算法有良好的效果.

关键词 最小生成树 启发式算法 度约束 直径约束

在线阅读 下载PDF 职称材料

度、半径约束最小生成树问题及其算法 被引量：2

12

作者 石磊 冯祖针 +1 位作者 杨建强 龙瑶 《沈阳大学学报（自然科学版）》 CAS 2012年第4期63-65,73,共4页

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

关键词 最小生成树问题 启发式算法 度约束 半径约束

在线阅读 下载PDF 职称材料

求解度限制最小生成树问题的启发式遗传搜索算法 被引量：4

13

作者 王励成 孙麟平 《系统工程理论与实践》 EI CSCD 北大核心 2003年第5期103-107,112,共6页

提出了求解度限制最小生成树问题的启发式遗传搜索算法 ,通过大量的数值试验验证其可行性 ;最后对此算法做了适当推广 ,并给出了用它求解 TSP及

关键词 遗传算法 启发式搜索 度限制最小生成树

原文传递

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

14

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

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

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

原文传递

度约束最小生成树问题概述

15

作者 郭仁杰 《阴山学刊（自然科学版）》 2014年第2期8-10,共3页

度约束最小生成树问题是经典的组合优化难题。本文对度约束最小生成树问题进行了综述,介绍了研究背景、数学模型及相关概念,并对该问题的求解算法进行了分类总结。

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

原文传递