Niching-based Evolutionary Diversity Optimization for the Traveling
Salesperson Problem
- URL: http://arxiv.org/abs/2201.10316v2
- Date: Tue, 19 Apr 2022 03:41:53 GMT
- Title: Niching-based Evolutionary Diversity Optimization for the Traveling
Salesperson Problem
- Authors: Anh Viet Do, Mingyu Guo, Aneta Neumann, Frank Neumann
- Abstract summary: We consider the problem of finding a set of tours to a traveling salesperson problem (TSP) instance maximizing diversity, while satisfying a given cost constraint.
This study aims to investigate the effectiveness of applying niching to maximize diversity rather than simply maintaining it.
- Score: 17.268191781480745
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we consider the problem of finding a set of tours to a
traveling salesperson problem (TSP) instance maximizing diversity, while
satisfying a given cost constraint. This study aims to investigate the
effectiveness of applying niching to maximize diversity rather than simply
maintaining it. To this end, we introduce a 2-stage approach where a simple
niching memetic algorithm (NMA), derived from a state-of-the-art for
multi-solution TSP, is combined with a baseline diversifying algorithm. The
most notable feature of the proposed NMA is the use of randomized
improvement-first local search instead of 2-opt. Our experiment on TSPLIB
instances shows that while the populations evolved by our NMA tend to contain
clusters at tight quality constraints, they frequently occupy distant basins of
attraction rather than close-by regions, improving on the baseline
diversification in terms of sum-sum diversity. Compared to the original NMA,
ours, despite its simplicity, finds more distant solutions of higher quality
within less running time, by a large margin.
Related papers
- Balancing Pareto Front exploration of Non-dominated Tournament Genetic Algorithm (B-NTGA) in solving multi-objective NP-hard problems with constraints [0.0]
The paper presents a new balanced selection operator applied to the proposed Balanced Non-dominated Tournament Genetic Algorithm (B-NTGA)
The proposed B-NTGA is investigated on two benchmark multi- and many-objective optimization real-world problems, like Thief Traveling Problem and Multi-Skill Resource-Constrained Project Scheduling Problem.
The results of experiments show that B-NTGA has a higher efficiency and better performance than state-of-the-art methods.
arXiv Detail & Related papers (2024-10-08T05:34:13Z) - Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization [9.838618121102053]
In real-world applications, users often favor structurally diverse design choices over one high-quality solution.
This paper presents a fresh perspective on this challenge by considering the problem of identifying a fixed number of solutions with a pairwise distance above a specified threshold.
arXiv Detail & Related papers (2024-08-29T09:55:55Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
We introduce a novel greedy-style subset selection algorithm for batch acquisition.
Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
arXiv Detail & Related papers (2024-06-21T05:57:08Z) - 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) - 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) - Permutation Invariant Policy Optimization for Mean-Field Multi-Agent
Reinforcement Learning: A Principled Approach [128.62787284435007]
We propose the mean-field proximal policy optimization (MF-PPO) algorithm, at the core of which is a permutation-invariant actor-critic neural architecture.
We prove that MF-PPO attains the globally optimal policy at a sublinear rate of convergence.
In particular, we show that the inductive bias introduced by the permutation-invariant neural architecture enables MF-PPO to outperform existing competitors.
arXiv Detail & Related papers (2021-05-18T04:35:41Z) - Niching Diversity Estimation for Multi-modal Multi-objective
Optimization [9.584279193016522]
Niching is an important and widely used technique in evolutionary multi-objective optimization.
In MMOPs, a solution in the objective space may have multiple inverse images in the decision space, which are termed as equivalent solutions.
A general niching mechanism is proposed to make standard diversity estimators more efficient when handling MMOPs.
arXiv Detail & Related papers (2021-01-31T05:23:31Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
arXiv Detail & Related papers (2020-06-12T00:32:21Z) - Hybrid Adaptive Evolutionary Algorithm for Multi-objective Optimization [0.0]
This paper proposed a new Multi-objective Algorithm as an extension of the Hybrid Adaptive Evolutionary algorithm (HAEA) called MoHAEA.
MoHAEA is compared with four states of the art MOEAs, namely MOEA/D, pa$lambda$-MOEA/D, MOEA/D-AWA, and NSGA-II.
arXiv Detail & Related papers (2020-04-29T02:16:49Z) - dMFEA-II: An Adaptive Multifactorial Evolutionary Algorithm for
Permutation-based Discrete Optimization Problems [6.943742860591444]
We propose the first adaptation of the recently introduced Multifactorial Evolutionary Algorithm II (MFEA-II) to permutation-based discrete environments.
The performance of the proposed solver has been assessed over 5 different multitasking setups.
arXiv Detail & Related papers (2020-04-14T14:42:47Z) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space.
Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
arXiv Detail & Related papers (2020-02-17T20:21:20Z)
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.