论文标题
进化多样性优化和最小跨越树问题
Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem
论文作者
论文摘要
在进化计算的领域，根据术语进化多样性优化，近年来，针对给定优化问题的各种高质量解决方案集的计算已经获得了动力。对多样性优化基线进化算法的工作原理的理论见解仍然很少见。在本文中，我们在多样性优化的背景下研究了众所周知的最小跨越树问题（MST），其中人口多样性是通过成对边缘重叠的总和来衡量的。理论结果提供了有关MST多样性优化问题的适应性景观的见解，指出即使对于$μ= 2 $ fitness Plateaus（恒定长度）的人群，也可以达到多种设备，但可以在多项式时间内计算多样性的集合。我们通过一系列实验来补充我们的理论结果，以实验不受约束和约束的情况，在这些情况下，所有解决方案都需要实现最小的质量阈值。我们的结果表明，简单的$（μ+1）$ - EA可以有效地计算出高质量的跨越树木的多样化人群。
In the area of evolutionary computation the calculation of diverse sets of high-quality solutions to a given optimization problem has gained momentum in recent years under the term evolutionary diversity optimization. Theoretical insights into the working principles of baseline evolutionary algorithms for diversity optimization are still rare. In this paper we study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization where population diversity is measured by the sum of pairwise edge overlaps. Theoretical results provide insights into the fitness landscape of the MST diversity optimization problem pointing out that even for a population of $μ=2$ fitness plateaus (of constant length) can be reached, but nevertheless diverse sets can be calculated in polynomial time. We supplement our theoretical results with a series of experiments for the unconstrained and constraint case where all solutions need to fulfill a minimal quality threshold. Our results show that a simple $(μ+1)$-EA can effectively compute a diversified population of spanning trees of high quality.
