Evolving Diverse Sets of Tours for the Travelling Salesperson Problem

• URL: http://arxiv.org/abs/2004.09188v2
• Date: Fri, 1 Oct 2021 07:28:54 GMT
• Title: Evolving Diverse Sets of Tours for the Travelling Salesperson Problem
• Authors: Anh Viet Do, Jakob Bossek, Aneta Neumann, Frank Neumann
• Abstract summary: We study the impact of using different diversity measures for a given set of tours and the ability of evolutionary algorithms to obtain a diverse set of high quality solutions. Our studies show that a large variety of diverse high quality tours can be achieved by using our approaches.
• Score: 14.171272631032522
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolving diverse sets of high quality solutions has gained increasing interest in the evolutionary computation literature in recent years. With this paper, we contribute to this area of research by examining evolutionary diversity optimisation approaches for the classical Traveling Salesperson Problem (TSP). We study the impact of using different diversity measures for a given set of tours and the ability of evolutionary algorithms to obtain a diverse set of high quality solutions when adopting these measures. Our studies show that a large variety of diverse high quality tours can be achieved by using our approaches. Furthermore, we compare our approaches in terms of theoretical properties and the final set of tours obtained by the evolutionary diversity optimisation algorithm.

Related papers

• Towards Multi-Objective High-Dimensional Feature Selection via Evolutionary Multitasking [63.91518180604101]
  This paper develops a novel EMT framework for high-dimensional feature selection problems, namely MO-FSEMT. A task-specific knowledge transfer mechanism is designed to leverage the advantage information of each task, enabling the discovery and effective transmission of high-quality solutions.
  arXiv  Detail & Related papers  (2024-01-03T06:34:39Z)
• 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)
• Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem [11.590506672325668]
  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.
  arXiv  Detail & Related papers  (2022-07-28T12:02:15Z)
• 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)
• Scaling up Search Engine Audits: Practical Insights for Algorithm Auditing [68.8204255655161]
  We set up experiments for eight search engines with hundreds of virtual agents placed in different regions. We demonstrate the successful performance of our research infrastructure across multiple data collections. We conclude that virtual agents are a promising venue for monitoring the performance of algorithms across long periods of time.
  arXiv  Detail & Related papers  (2021-06-10T15:49:58Z)
• 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)
• Portfolio Search and Optimization for General Strategy Game-Playing [58.896302717975445]
  We propose a new algorithm for optimization and action-selection based on the Rolling Horizon Evolutionary Algorithm. For the optimization of the agents' parameters and portfolio sets we study the use of the N-tuple Bandit Evolutionary Algorithm. An analysis of the agents' performance shows that the proposed algorithm generalizes well to all game-modes and is able to outperform other portfolio methods.
  arXiv  Detail & Related papers  (2021-04-21T09:28:28Z)
• Emergent Hand Morphology and Control from Optimizing Robust Grasps of Diverse Objects [63.89096733478149]
  We introduce a data-driven approach where effective hand designs naturally emerge for the purpose of grasping diverse objects. We develop a novel Bayesian Optimization algorithm that efficiently co-designs the morphology and grasping skills jointly. We demonstrate the effectiveness of our approach in discovering robust and cost-efficient hand morphologies for grasping novel objects.
  arXiv  Detail & Related papers  (2020-12-22T17:52:29Z)
• Towards Multimodal Response Generation with Exemplar Augmentation and Curriculum Optimization [73.45742420178196]
  We propose a novel multimodal response generation framework with exemplar augmentation and curriculum optimization. Our model achieves significant improvements compared to strong baselines in terms of diversity and relevance.
  arXiv  Detail & Related papers  (2020-04-26T16:29:06Z)

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.