Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/136717
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Niching-based evolutionary diversity optimization for the traveling salesperson problem |
Author: | Do, A.V. Guo, M. Neumann, A. Neumann, F. |
Citation: | Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'22), 2022 / Fieldsend, J.E., Wagner, M. (ed./s), pp.684-693 |
Publisher: | Association for Computing Machinery |
Publisher Place: | Online |
Issue Date: | 2022 |
ISBN: | 9781450392372 |
Conference Name: | The Genetic and Evolutionary Computation Conference (GECCO) (9 Jul 2022 - 13 Jul 2022 : virtual online) |
Editor: | Fieldsend, J.E. Wagner, M. |
Statement of Responsibility: | Anh Viet Do, Mingyu Guo, Aneta Neumann, Frank Neumann |
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. |
Keywords: | Traveling Salesperson Problem; niching; evolutionary diversity optimization |
Rights: | © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM |
DOI: | 10.1145/3512290.3528724 |
Grant ID: | http://purl.org/au-research/grants/arc/DP190103894 http://purl.org/au-research/grants/arc/FT200100536 |
Published version: | https://dl.acm.org/doi/proceedings/10.1145/3512290.3528724 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.