Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem

• URL: http://arxiv.org/abs/2010.10913v2
• Date: Tue, 27 Apr 2021 12:38:45 GMT
• Title: Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem
• Authors: Jakob Bossek, Frank Neumann
• Abstract summary: We study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization. We show that a simple $(mu+1)$-EA can effectively compute a diversified population of spanning trees of high quality.
• Score: 13.264683014487376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\mu=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 $(\mu+1)$-EA can effectively compute a diversified population of spanning trees of high quality.

Related papers

• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax [13.026567958569965]
  We study how the GSEMO algorithm with additional diversity-enhancing enhancements optimize a diversity of its population on a bi-objective benchmark problem OneMin. We prove that it finds a population with optimal diversity in expected time $O(n2)$, when the problem size $n$ is odd. For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes.
  arXiv  Detail & Related papers  (2023-07-14T09:43:29Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  We study the scenario of components that are independent and normally distributed. We introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem.
  arXiv  Detail & Related papers  (2021-09-13T09:24:23Z)
• An Analysis of Phenotypic Diversity in Multi-Solution Optimization [118.97353274202749]
  We show that multiobjective optimization does not always produce much diversity, multimodal optimization produces higher fitness solutions, and quality diversity is not sensitive to genetic neutrality. An autoencoder is used to discover phenotypic features automatically, producing an even more diverse solution set with quality diversity.
  arXiv  Detail & Related papers  (2021-05-10T10:39:03Z)
• Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem [11.590506672325668]
  We employ a population diversity measure, called the high-order entropy measure, in an evolutionary algorithm to compute a diverse set of high-quality solutions for the Traveling Salesperson Problem. We show significant improvements compared to a recently proposed edge-based diversity optimisation approach when working with a large population of solutions or long segments.
  arXiv  Detail & Related papers  (2021-04-28T02:36:14Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  We present techniques that produce optimal decision trees over a variety of objectives. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
  arXiv  Detail & Related papers  (2020-06-15T19:00:11Z)
• Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem [0.0]
  This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem. We define devolutionary algorithms as the process of reaching a feasible solution by devolving a population of super-optimal unfeasible solutions over time. We show how classical evolutionary concepts, such as crossing, mutation and fitness can be adapted to aim at reaching an optimal or close-to-optimal solution.
  arXiv  Detail & Related papers  (2020-04-18T13:27:28Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.