Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem

• URL: http://arxiv.org/abs/2207.14036v1
• Date: Thu, 28 Jul 2022 12:02:15 GMT
• Title: Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem
• Authors: Adel Nikfarjam, Aneta Neumann, Jakob Bossek, Frank Neumann
• Abstract summary: We introduce a co-evolutionary algorithm to simultaneously explore the two spaces for the multi-component traveling thief problem. Results show the capability of the co-evolutionary algorithm to achieve significantly higher diversity compared to the baseline evolutionary diversity algorithms from the the literature.
• Score: 11.590506672325668
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently different evolutionary computation approaches have been developed that generate sets of high quality diverse solutions for a given optimisation problem. Many studies have considered diversity 1) as a mean to explore niches in behavioural space (quality diversity) or 2) to increase the structural differences of solutions (evolutionary diversity optimisation). In this study, we introduce a co-evolutionary algorithm to simultaneously explore the two spaces for the multi-component traveling thief problem. The results show the capability of the co-evolutionary algorithm to achieve significantly higher diversity compared to the baseline evolutionary diversity algorithms from the the literature.

Related papers

• A Unified Algorithm Framework for Unsupervised Discovery of Skills based on Determinantal Point Process [53.86223883060367]
  We show that diversity and coverage in unsupervised option discovery can indeed be unified under the same mathematical framework. Our proposed algorithm, ODPP, has undergone extensive evaluation on challenging tasks created with Mujoco and Atari.
  arXiv  Detail & Related papers  (2022-12-01T01:40:03Z)
• Computing High-Quality Solutions for the Patient Admission Scheduling Problem using Evolutionary Diversity Optimisation [10.609857097723266]
  We adapt the evolutionary diversity optimisation for a real-world problem, namely patient admission scheduling. We introduce an evolutionary algorithm to achieve structural diversity in a set of solutions subjected to the quality of each solution.
  arXiv  Detail & Related papers  (2022-07-28T14:26:45Z)
• Evolutionary Diversity Optimisation for The Traveling Thief Problem [11.590506672325668]
  We introduce a bi-level evolutionary algorithm to maximise the structural diversity of the set of solutions. We empirically determine the best method to obtain diversity. Our experimental results show a significant improvement of the QD approach in terms of structural diversity for most TTP benchmark instances.
  arXiv  Detail & Related papers  (2022-04-06T10:13:55Z)
• Diversity Enhancement via Magnitude [7.005458308454871]
  We use the recently developed theory of magnitude to construct a gradient flow and similar notions that systematically manipulate finite subsets of Euclidean space to enhance their diversity. We demonstrate diversity enhancement on benchmark problems using leading algorithms, and discuss extensions of the framework.
  arXiv  Detail & Related papers  (2022-01-25T01:38:53Z)
• 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)
• What can phylogenetic metrics tell us about useful diversity in evolutionary algorithms? [62.997667081978825]
  Phylogenetic diversity metrics are a class of metrics popularly used in biology. We find that, in most cases, phylogenetic metrics behave meaningfully differently from other diversity metrics.
  arXiv  Detail & Related papers  (2021-08-28T06:49:14Z)
• 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)
• Expressivity of Parameterized and Data-driven Representations in Quality Diversity Search [111.06379262544911]
  We compare the output diversity of a quality diversity evolutionary search performed in two different search spaces. A learned model is better at interpolating between known data points than at extrapolating or expanding towards unseen examples.
  arXiv  Detail & Related papers  (2021-05-10T10:27:43Z)
• 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)
• Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
  We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
  arXiv  Detail & Related papers  (2021-04-10T13:52:27Z)
• Quality and Diversity in Evolutionary Modular Robotics [1.290382979353427]
  In Evolutionary Robotics a population of solutions is evolved to optimize robots that solve a given task. Quality Diversity algorithms try to overcome premature convergence by introducing additional measures that reward solutions for being different.
  arXiv  Detail & Related papers  (2020-08-05T13:08:14Z)

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.