On the Impact of Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem

• URL: http://arxiv.org/abs/2305.18955v1
• Date: Tue, 30 May 2023 11:39:49 GMT
• Title: On the Impact of Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem
• Authors: Jakob Bossek, Aneta Neumann, Frank Neumann
• Abstract summary: We investigate the node weighted traveling salesperson problem (W-TSP) in dynamic settings. In the dynamic setting of the problem, items that have to be collected as part of a TSP tour change over time. Our first experimental investigations study the impact of such changes on resulting optimized tours.
• Score: 13.026567958569965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary algorithms have been shown to obtain good solutions for complex optimization problems in static and dynamic environments. It is important to understand the behaviour of evolutionary algorithms for complex optimization problems that also involve dynamic and/or stochastic components in a systematic way in order to further increase their applicability to real-world problems. We investigate the node weighted traveling salesperson problem (W-TSP), which provides an abstraction of a wide range of weighted TSP problems, in dynamic settings. In the dynamic setting of the problem, items that have to be collected as part of a TSP tour change over time. We first present a dynamic setup for the dynamic W-TSP parameterized by different types of changes that are applied to the set of items to be collected when traversing the tour. Our first experimental investigations study the impact of such changes on resulting optimized tours in order to provide structural insights of optimization solutions. Afterwards, we investigate simple mutation-based evolutionary algorithms and study the impact of the mutation operators and the use of populations with dealing with the dynamic changes to the node weights of the problem.

Related papers

• An Adaptive Metaheuristic Framework for Changing Environments [0.0]
  This paper introduces an Adaptive Metaheuristic Framework (AMF) designed for dynamic environments. AMF combines a dynamic representation of problems, a real-time sensing system, and adaptive techniques to navigate continuously changing optimization environments.
  arXiv  Detail & Related papers  (2024-04-18T13:47:53Z)
• Dual-Space Optimization: Improved Molecule Sequence Design by Latent Prompt Transformer [78.47949363282868]
  We propose the Dual-Space Optimization (DSO) method that integrates latent space sampling and data space selection to solve this problem. DSO iteratively updates a latent space generative model and a synthetic dataset in an optimization process that shifts the generative model and the synthetic data towards regions of desired property values. Our experiments demonstrate effectiveness of the proposed method, which sets new performance benchmarks across single-objective, multi-objective and constrained molecule design tasks.
  arXiv  Detail & Related papers  (2024-02-27T03:33:23Z)
• AbCD: A Component-wise Adjustable Framework for Dynamic Optimization Problems [49.1574468325115]
  Dynamic Optimization Problems (DOPs) are characterized by changes in the fitness landscape that can occur at any time and are common in real world applications. We develop a component-oriented framework for DOPs called Adjustable Components for Dynamic Problems (AbCD) Our results highlight existing problems in the DOP field that need to be addressed in the future development of algorithms and components.
  arXiv  Detail & Related papers  (2023-10-09T08:11:31Z)
• Multiobjective Evolutionary Component Effect on Algorithm behavior [0.04588028371034406]
  It is unknown what are the most influential components that lead to performance improvements. We apply this methodology to a tuned Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D) designed by the iterated racing (irace) configuration package. We compare the impact of the algorithm components in terms of their Search Trajectory Networks (STNs), the diversity of the population, and the anytime hypervolume values.
  arXiv  Detail & Related papers  (2023-07-31T16:02:56Z)
• Optimistic Active Exploration of Dynamical Systems [52.91573056896633]
  We develop an algorithm for active exploration called OPAX. We show how OPAX can be reduced to an optimal control problem that can be solved at each episode. Our experiments show that OPAX is not only theoretically sound but also performs well for zero-shot planning on novel downstream tasks.
  arXiv  Detail & Related papers  (2023-06-21T16:26:59Z)
• Reproducibility and Baseline Reporting for Dynamic Multi-objective Benchmark Problems [4.859986264602551]
  This paper focuses on the simulation experiments for parameters of DMOPs. A baseline schema for dynamic algorithm evaluation is introduced. We can establish the minimum capability required of purpose-built dynamic algorithms to be useful.
  arXiv  Detail & Related papers  (2022-04-08T15:50:17Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  We introduce a novel GP regression to incorporate the subgroup feedback. Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches. We execute our algorithm on two disparate social problems.
  arXiv  Detail & Related papers  (2021-07-07T03:57:22Z)
• EOS: a Parallel, Self-Adaptive, Multi-Population Evolutionary Algorithm for Constrained Global Optimization [68.8204255655161]
  EOS is a global optimization algorithm for constrained and unconstrained problems of real-valued variables. It implements a number of improvements to the well-known Differential Evolution (DE) algorithm. Results prove that EOSis capable of achieving increased performance compared to state-of-the-art single-population self-adaptive DE algorithms.
  arXiv  Detail & Related papers  (2020-07-09T10:19:22Z)
• Dynamic Regret of Policy Optimization in Non-stationary Environments [120.01408308460095]
  We propose two model-free policy optimization algorithms, POWER and POWER++, and establish guarantees for their dynamic regret. We show that POWER++ improves over POWER on the second component of the dynamic regret by actively adapting to non-stationarity through prediction. To the best of our knowledge, our work is the first dynamic regret analysis of model-free RL algorithms in non-stationary environments.
  arXiv  Detail & Related papers  (2020-06-30T23:34:37Z)
• The Dynamic Travelling Thief Problem: Benchmarks and Performance of Evolutionary Algorithms [12.973161516101806]
  This article defines a number of scenarios based on the Travelling Thief Problem to enable research on the effect of dynamic changes to sub-components. Our investigations of 72 scenarios and seven algorithms show that -- depending on the instance, the magnitude of the change, and the algorithms in the portfolio -- it is preferable to either restart the optimisation from scratch or to continue with the previously valid solutions.
  arXiv  Detail & Related papers  (2020-04-25T02:54:17Z)
• Dynamic Multi-objective Optimization of the Travelling Thief Problem [4.859986264602551]
  Investigation of detailed and complex optimisation problem formulations that reflect realistic scenarios is a burgeoning field of research. A growing body of work exists for the Travelling Thief Problem, including multi-objective formulations and comparisons of exact and approximate methods to solve it. Definition of dynamics within three areas of the TTP problem are addressed; in the city locations, availability map and item values. A combined approach that mixes solution generation methods to provide a composite population in response to dynamic changes provides improved performance in some instances for the different dynamic TTP formulations.
  arXiv  Detail & Related papers  (2020-02-07T06:33:05Z)

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.