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) - 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) - Automatically Learning Compact Quality-aware Surrogates for Optimization
Problems [55.94450542785096]
Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values.
Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making.
We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
arXiv Detail & Related papers (2020-06-18T19:11:54Z) - 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.