.png){kind=icon}
返回
An Evolutionary Algorithm Based on CMSA for Rooted Max Tree Coverage
.png){kind=icon}
PRE
AI
DOI：10.1109/TEVC.2024.3522012.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
根植最大树覆盖（MTC）问题在网络设计、车辆路径规划等领域的应用十分广泛。给定一个定义了非负边权值的图、一个作为根的顶点以及一个预算，该问题要求找到一棵包含根的树，使其总成本不超过预算，并最大化该树所覆盖的顶点数量。根植MTC问题属于NP难问题，并且存在常数因子近似算法。然而，现有的根植MTC近似算法非常复杂，难以在实际中实现。本文首次为根植MTC问题构建了一个多项式规模的混合整数线性规划（MILP）模型。在此基础上，我们基于近期提出的构建-合并-求解-自适应（CMSA）元启发式算法，开发了一种简单有效的根植MTC进化算法（称为CMSA-MTC）。实验结果表明，CMSA-MTC具有非常良好的实际性能。对于小规模实例，CMSA-MTC几乎总能找到最优解；对于大规模实例，CMSA-MTC在相同运行时间内找到的解优于CPLEX以及两种额外的贪心算法。
Keyword:
Construct
merge
solve
and adapt (CMSA)
combinatorial optimization
evolutionary algorithm
heuristic algorithm
max tree cover
期刊
IF:
12
论文数:
1.9K
被引数:
2.4W
.png){kind=icon}
查看更多内容