The Dynamic Travelling Thief Problem: Benchmarks and Performance of Evolutionary Algorithms

• URL: http://arxiv.org/abs/2004.12045v3
• Date: Tue, 15 Sep 2020 01:10:59 GMT
• Title: The Dynamic Travelling Thief Problem: Benchmarks and Performance of Evolutionary Algorithms
• Authors: Ragav Sachdeva, Frank Neumann, Markus Wagner
• Abstract summary: 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.
• Score: 12.973161516101806
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many real-world optimisation problems involve dynamic and stochastic components. While problems with multiple interacting components are omnipresent in inherently dynamic domains like supply-chain optimisation and logistics, most research on dynamic problems focuses on single-component problems. With this article, we define 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.

Related papers

• 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)
• Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance [47.42067405054353]
  Multi-objective learning (MOL) problems often arise in emerging machine learning problems. One of the critical challenges in MOL is the potential conflict among different objectives during the iterative optimization process. Recent works have developed various dynamic weighting algorithms for MOL such as MGDA and its variants.
  arXiv  Detail & Related papers  (2023-05-31T17:31:56Z)
• On the Impact of Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem [13.026567958569965]
  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.
  arXiv  Detail & Related papers  (2023-05-30T11:39:49Z)
• 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)
• 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)
• 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)
• 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)
• 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.