• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Symposium Series on Computational Intelligence >A pareto-beneficial sub-tree mutation for the multi-criteria minimum spanning tree problem
【24h】

A pareto-beneficial sub-tree mutation for the multi-criteria minimum spanning tree problem

机译：多准则最小生成树问题的对等子树变异

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

While finding minimum-cost spanning trees (MST) in undirected graphs is solvable in polynomial time, the multi-criteria minimum spanning tree problem (mcMST) is NP-hard. Interestingly, the mcMST problem has not been in focus of evolutionary computation research for a long period of time, although, its relevance for real world problems is easy to see. The available and most notable approaches by Zhou and Gen as well as by Knowles and Corne concentrate on solution encoding and on fairly dated selection mechanisms. In this work, we revisit the mcMST and focus on the mutation operators as exploratory components of evolutionary algorithms neglected so far. We investigate optimal solution characteristics to discuss current mutation strategies, identify shortcomings of these operators, and propose a sub-tree based operator which offers what we term Pareto-beneficial behavior: ensuring convergence and diversity at the same time. The operator is empirically evaluated inside modern standard evolutionary meta-heuristics for multi-criteria optimization and compared to hitherto applied mutation operators in the context of mcMST.
机译：虽然可以在多项式时间内解决在无向图中找到最小代价生成树（MST）的问题，但多准则最小生成树问题（mcMST）是NP难的。有趣的是，尽管很容易看到mcMST问题，但长期以来它一直不是进化计算研究的重点。 Zhou和Gen以及Knowles和Corne可用和最著名的方法集中于解决方案编码和过时的选择机制。在这项工作中，我们将重新探讨mcMST，并将重点放在突变算子上，将其作为迄今为止被忽略的进化算法的探索性组成部分。我们调查最佳解决方案特征，以讨论当前的变异策略，找出这些算子的缺点，并提出一个基于子树的算子，该算子提供了我们所说的帕累托有益行为：同时确保收敛和多样性。在多标准优化的现代标准进化元启发式方法中，根据经验对算子进行了评估，并与迄今为止在mcMST中应用的变异算子进行了比较。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号