research-article

Evolutionary diversity optimisation for the traveling thief problem

Authors:

Adel Nikfarjam,

Frank NeumannAuthors Info & Claims

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 749 - 756

https://doi.org/10.1145/3512290.3528862

Published: 08 July 2022 Publication History

Abstract

There has been a growing interest in the evolutionary computation community to compute a diverse set of high-quality solutions for a given optimisation problem. This can provide the practitioners with invaluable information about the solution space and robustness against imperfect modelling and minor problems' changes. It also enables the decision-makers to involve their interests and choose between various solutions. In this study, we investigate for the first time a prominent multi-component optimisation problem, namely the Traveling Thief Problem (TTP), in the context of evolutionary diversity optimisation. We introduce a bi-level evolutionary algorithm to maximise the structural diversity of the set of solutions. Moreover, we examine the inter-dependency among the components of the problem in terms of structural diversity and empirically determine the best method to obtain diversity. We also conduct a comprehensive experimental investigation to examine the introduced algorithm and compare the results to another recently introduced framework based on the use of Quality Diversity (QD). Our experimental results show a significant improvement of the QD approach in terms of structural diversity for most TTP benchmark instances.

References

[1]

Bradley Alexander, James Kortman, and Aneta Neumann. 2017. Evolution of artistic image variants through feature based diversity optimisation. In GECCO. ACM, 171--178.

[2]

Mohammad Reza Bonyadi, Zbigniew Michalewicz, and Luigi Barone. 2013. The travelling thief problem: The first step in the transition from theoretical problems to realistic problems. In IEEE Congress on Evolutionary Computation. IEEE, 1037-- 1044.

[3]

Mohammad Reza Bonyadi, Zbigniew Michalewicz, Michal Roman Przybylek, and Adam Wierzbicki. 2014. Socially inspired algorithms for the travelling thief problem. In GECCO. ACM, 421--428.

[4]

Jakob Bossek, Aneta Neumann, and Frank Neumann. 2021. Breeding diverse packings for the knapsack problem by means of diversity-tailored evolutionary algorithms. In GECCO. ACM, 556--564.

[5]

Jakob Bossek and Frank Neumann. 2021. Evolutionary diversity optimization and the minimum spanning tree problem. In GECCO. ACM, 198--206.

[6]

Antoine Cully. 2020. Multi-Emitter MAP-Elites: Improving quality, diversity and convergence speed with heterogeneous sets of emitters. CoRR abs/2007.05352 (2020).

[7]

Anh Viet Do, Jakob Bossek, Aneta Neumann, and Frank Neumann. 2020. Evolving diverse sets of tours for the travelling salesperson problem. In GECCO. ACM, 681--689.

[8]

Anh Viet Do, Mingyu Guo, Aneta Neumann, and Frank Neumann. 2021. Analysis of evolutionary diversity optimisation for permutation problems. In GECCO. ACM, 574--582.

[9]

Matthew C. Fontaine, Ruilin Liu, Ahmed Khalifa, Jignesh Modi, Julian Togelius, Amy K. Hoover, and Stefanos Nikolaidis. 2021. Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network. In AAAI. AAAI Press, 5922--5930.

[10]

Matthew C. Fontaine, Julian Togelius, Stefanos Nikolaidis, and Amy K. Hoover. 2020. Covariance matrix adaptation for the rapid illumination of behavior space. In GECCO. ACM, 94--102.

[11]

Wanru Gao, Samadhi Nallaperuma, and Frank Neumann. 2021. Feature-Based Diversity Optimization for Problem Instance Classification. Evol. Comput. 29, 1 (2021), 107--128.

[12]

Alenrex Maity and Swagatam Das. 2020. Efficient hybrid local search heuristics for solving the travelling thief problem. Appl. Soft Comput. 93 (2020), 106284.

[13]

Yuichi Nagata and Shigenobu Kobayashi. 2013. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. INFORMS J. Comput. 25, 2 (2013), 346--363.

Digital Library

[14]

Aneta Neumann, Jakob Bossek, and Frank Neumann. 2021. Diversifying greedy sampling and evolutionary diversity optimisation for constrained monotone submodular functions. In GECCO. ACM, 261--269.

[15]

Aneta Neumann, Wanru Gao, Carola Doerr, Frank Neumann, and Markus Wagner. 2018. Discrepancy-based evolutionary diversity optimization. In GECCO. ACM, 991--998.

[16]

Aneta Neumann, Wanru Gao, Markus Wagner, and Frank Neumann. 2019. Evolutionary diversity optimization using multi-objective indicators. In GECCO. ACM, 837--845.

[17]

Adel Nikfarjam, Jakob Bossek, Aneta Neumann, and Frank Neumann. 2021. Computing diverse sets of high quality TSP tours by EAX-based evolutionary diversity optimisation. In FOGA. ACM, 9:1--9:11.

[18]

Adel Nikfarjam, Jakob Bossek, Aneta Neumann, and Frank Neumann. 2021. Entropy-based evolutionary diversity optimisation for the traveling salesperson problem. In GECCO. ACM, 600--608.

[19]

Adel Nikfarjam, Aneta Neumann, and Frank Neumann. 2021. On the Use of Quality Diversity Algorithms for The Traveling Thief Problem. CoRR abs/2112.08627 (2021).

[20]

Sergey Polyakovskiy, Mohammad Reza Bonyadi, Markus Wagner, Zbigniew Michalewicz, and Frank Neumann. 2014. A comprehensive benchmark set and heuristics for the traveling thief problem. In GECCO. ACM, 477--484.

[21]

Nemanja Rakicevic, Antoine Cully, and Petar Kormushev. 2021. Policy manifold search: exploring the manifold hypothesis for diversity-based neuroevolution. In GECCO. ACM, 901--909.

[22]

Kirby Steckel and Jacob Schrum. 2021. Illuminating the space of beatable lode runner levels produced by various generative adversarial networks. In GECCO Companion. ACM, 111--112.

[23]

Tamara Ulrich and Lothar Thiele. 2011. Maximizing population diversity in single-objective optimization. In GECCO. ACM, 641--648.

[24]

Markus Wagner. 2016. Stealing Items More Efficiently with Ants: A Swarm Intelligence Approach to the Travelling Thief Problem. In ANTS Conference (Lecture Notes in Computer Science), Vol. 9882. Springer, 273--281.

[25]

Mohamed El Yafrani and Belaïd Ahiod. 2015. Cosolver2B: An eficient local search heuristic for the Travelling Thief Problem. In AICCSA. IEEE Computer Society, 1--5.

[26]

Mohamed El Yafrani and Belaïd Ahiod. 2018. Efficiently solving the Traveling Thief Problem using hill climbing and simulated annealing. Inf. Sci. 432 (2018), 231--244.

[27]

Enrico Zardini, Davide Zappetti, Davide Zambrano, Giovanni Iacca, and Dario Floreano. 2021. Seeking quality diversity in evolutionary co-design of morphology and control of soft tensegrity modular robots. In GECCO. ACM, 189--197.

[28]

Wiem Zouari, Inès Alaya, and Moncef Tagina. 2019. A new hybrid ant colony algorithms for the traveling thief problem. In GECCO (Companion). ACM, 95--96.

Cited By

Nikfarjam ANeumann ANeumann F(2024)On the Use of Quality Diversity Algorithms for the Travelling Thief ProblemACM Transactions on Evolutionary Learning and Optimization10.1145/36411094:2(1-22)Online publication date: 8-Jun-2024
https://dl.acm.org/doi/10.1145/3641109
Gounder SNeumann FNeumann ALi XHandl J(2024)Evolutionary Diversity Optimisation for Sparse Directed Communication NetworksProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654184(1237-1245)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654184
Antipov DNeumann ANeumann FLi XHandl J(2024)A Detailed Experimental Analysis of Evolutionary Diversity Optimization for OneMinMaxProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654082(467-475)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654082
Show More Cited By

Recommendations

Niching-based evolutionary diversity optimization for the traveling salesperson problem
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

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 ...
On the use of quality diversity algorithms for the traveling thief problem
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. There is an inter-dependency between the sub-problems, making it impossible to solve such a problem by focusing on only one component. The ...
Co-evolutionary Diversity Optimisation for the Traveling Thief Problem
Parallel Problem Solving from Nature – PPSN XVII
Abstract
Recently different evolutionary computation approaches have been developed that generate sets of high quality diverse solutions for a given optimisation problem. Many studies have considered diversity 1) as a mean to explore niches in behavioural ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

July 2022

1472 pages

ISBN:9781450392372

DOI:10.1145/3512290

Editor:
Jonathan E. Fieldsend
University of Exeter
,
General Chair:
Markus Wagner
The University of Adelaide

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Australian Research Council
South Australian Government

Conference

GECCO '22

Sponsor:

SIGEVO

GECCO '22: Genetic and Evolutionary Computation Conference

July 9 - 13, 2022

Massachusetts, Boston

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
122
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)5

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nikfarjam ANeumann ANeumann F(2024)On the Use of Quality Diversity Algorithms for the Travelling Thief ProblemACM Transactions on Evolutionary Learning and Optimization10.1145/36411094:2(1-22)Online publication date: 8-Jun-2024
https://dl.acm.org/doi/10.1145/3641109
Gounder SNeumann FNeumann ALi XHandl J(2024)Evolutionary Diversity Optimisation for Sparse Directed Communication NetworksProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654184(1237-1245)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654184
Antipov DNeumann ANeumann FLi XHandl J(2024)A Detailed Experimental Analysis of Evolutionary Diversity Optimization for OneMinMaxProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654082(467-475)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654082
Pathirage Don TNeumann ANeumann FLi XHandl J(2024)The Chance Constrained Travelling Thief Problem: Problem Formulations and AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654014(214-222)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654014
Antipov DNeumann ANeumann FSutton A(2024)Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) ProblemParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_2(19-35)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_2
Antipov DNeumann ANeumann F(2024)Local Optima in Diversity Optimization: Non-trivial Offspring Population is EssentialParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_12(181-196)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_12
Gadea Harder JNeumann ANeumann F(2024)Analysis of Evolutionary Diversity Optimisation for the Maximum Matching ProblemParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_10(149-165)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70071-2_10
Nikfarjam ARothenberger RNeumann FFriedrich TSilva SPaquete L(2023)Evolutionary Diversity Optimisation in Constructing Satisfying AssignmentsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590517(938-945)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590517
Neumann AGounder SYan XSherman GCampbell BGuo MNeumann FSilva SPaquete L(2023)Diversity Optimization for the Detection and Concealment of Spatially Defined Communication NetworksProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590405(1436-1444)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590405
Rodríguez DCruz-Duarte JOrtiz-Bayliss JAmaya I(2022)A Sequence-Based Hyper-Heuristic for Traveling ThievesApplied Sciences10.3390/app1301005613:1(56)Online publication date: 21-Dec-2022
https://doi.org/10.3390/app13010056
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents