Evolutionary Algorithms and Multi-Objective Minimum Spanning Trees with Limited Distinct Weight Values
For researchers in evolutionary computation, this offers refined theoretical insights into a specific combinatorial optimization problem, but the results are incremental.
The paper provides theoretical runtime bounds for evolutionary algorithms on the multi-objective minimum spanning tree problem when edge weights have few distinct values, and validates these bounds experimentally.
Evolutionary algorithms have been used for a wide range of multi-objective combinatorial optimization problems. Despite practical success, theoretical results on the runtime of evolutionary algorithms for multi-objective combinatorial problems are rather limited. One classical problem that has been investigated is the multi-objective minimum spanning tree problem for which runtime bounds have been obtained to compute all extremal corner points of the Pareto front. With this paper, we provide some more detailed insights into the structure of the Pareto front when the edge weights take on a small number of distinct values. Based on these insights, we derive new runtime results for evolutionary multi-objective algorithms and complement our theoretical results with experimental investigations.