论文标题
多目标最小跨越树问题的进化算法的运行时分析
Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem
论文作者
论文摘要
进化算法（EAS）是通常执行无偏见的通用问题解决者。这是合理的，并且在黑盒子方案中是可取的。对于组合优化问题，通常给出更多有关最佳解决方案结构的知识，可以通过有偏见的搜索操作员来利用。我们考虑单目标和多目标版本中的最小跨越树（MST）问题，并引入一个有偏见的突变，该突变更加强调低级统治数的低等级边缘的选择。我们介绍示例图，其中有偏见的突变可以显着加快预期运行时，直到找到（帕累托 - 最佳解决方案）。另一方面，如果重边是最佳解决方案的一部分，我们证明偏差可能导致指数运行时。但是，在单瞄准设置中的一般图上，我们表明，在每个步骤中决定无偏见或偏见的边缘选择的组合突变算子，如果情况有利，则在最坏的情况下表现出多项式上限 - 无偏突变 - 在最坏的情况下，并从偏见中受益。
Evolutionary algorithms (EAs) are general-purpose problem solvers that usually perform an unbiased search. This is reasonable and desirable in a black-box scenario. For combinatorial optimization problems, often more knowledge about the structure of optimal solutions is given, which can be leveraged by means of biased search operators. We consider the Minimum Spanning Tree (MST) problem in a single- and multi-objective version, and introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We present example graphs where the biased mutation can significantly speed up the expected runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate that bias can lead to exponential runtime if heavy edges are necessarily part of an optimal solution. However, on general graphs in the single-objective setting, we show that a combined mutation operator which decides for unbiased or biased edge selection in each step with equal probability exhibits a polynomial upper bound -- as unbiased mutation -- in the worst case and benefits from bias if the circumstances are favorable.
