Co-evolutionary Diversity Optimisation for the Traveling Thief Problem
Pages 237 - 249
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 space (quality diversity) or 2) to increase the structural differences of solutions (evolutionary diversity optimisation). In this study, we introduce a co-evolutionary algorithm to simultaneously explore the two spaces for the multi-component traveling thief problem. The results show the capability of the co-evolutionary algorithm to achieve significantly higher diversity compared to the baseline evolutionary diversity algorithms from the literature.
References
[1]
Bossek, J., Neumann, A., Neumann, F.: Breeding diverse packings for the knapsack problem by means of diversity-tailored evolutionary algorithms. In: GECCO, pp. 556–564. ACM (2021)
[2]
Bossek, J., Neumann, F.: Evolutionary diversity optimization and the minimum spanning tree problem. In: GECCO, pp. 198–206. ACM (2021)
[3]
Chagas, J.B.C., Wagner, M.: A weighted-sum method for solving the bi-objective traveling thief problem. CoRR abs/2011.05081 (2020)
[4]
Clune, J., Mouret, J., Lipson, H.: Summary of “the evolutionary origins of modularity”. In: GECCO (Companion), pp. 23–24. ACM (2013)
[5]
Cully, A., Mouret, J.: Behavioral repertoire learning in robotics. In: GECCO, pp. 175–182. ACM (2013)
[6]
Do, A.V., Bossek, J., Neumann, A., Neumann, F.: Evolving diverse sets of tours for the travelling salesperson problem. In: GECCO, pp. 681–689. ACM (2020)
[7]
Do, A.V., Guo, M., Neumann, A., Neumann, F.: Analysis of evolutionary diversity optimisation for permutation problems. In: GECCO, pp. 574–582. ACM (2021)
[8]
Doerr, B., Doerr, C.: Optimal parameter choices through self-adjustment: applying the 1/5-th rule in discrete settings. In: GECCO Companion, pp. 1335–1342 (2015)
[9]
Gao W, Nallaperuma S, and Neumann F Feature-based diversity optimization for problem instance classification Evol. Comput. 2021 29 1 107-128
[10]
Lehman J and Stanley KO Abandoning objectives: evolution through the search for novelty alone Evol. Comput. 2011 19 2 189-223
[11]
Nagata Y and Kobayashi S A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem INFORMS J. Comput. 2013 25 2 346-363
[12]
Neumann, A., Antipov, D., Neumann, F.: Coevolutionary Pareto diversity optimization. CoRR arXiv:2204.05457 (2022), accepted as full paper at GECCO 2022
[13]
Neumann, A., Bossek, J., Neumann, F.: Diversifying greedy sampling and evolutionary diversity optimisation for constrained monotone submodular functions. In: GECCO, pp. 261–269. ACM (2021)
[14]
Neumann, A., Gao, W., Doerr, C., Neumann, F., Wagner, M.: Discrepancy-based evolutionary diversity optimization. In: GECCO, pp. 991–998. ACM (2018)
[15]
Neumann, A., Gao, W., Wagner, M., Neumann, F.: Evolutionary diversity optimization using multi-objective indicators. In: GECCO, pp. 837–845. ACM (2019)
[16]
Neumann, A., Szpak, Z.L., Chojnacki, W., Neumann, F.: Evolutionary image composition using feature covariance matrices. In: GECCO, pp. 817–824 (2017)
[17]
Nikfarjam, A., Bossek, J., Neumann, A., Neumann, F.: Computing diverse sets of high quality TSP tours by EAX-based evolutionary diversity optimisation. In: FOGA, pp. 9:1–9:11. ACM (2021)
[18]
Nikfarjam, A., Bossek, J., Neumann, A., Neumann, F.: Entropy-based evolutionary diversity optimisation for the traveling salesperson problem. In: GECCO, pp. 600–608. ACM (2021)
[19]
Nikfarjam, A., Neumann, A., Neumann, F.: On the use of quality diversity algorithms for the traveling thief problem. CoRR abs/2112.08627 (2021)
[20]
Nikfarjam, A., Neumann, A., Neumann, F.: Evolutionary diversity optimisation for the traveling thief problem. CoRR abs/2204.02709 (2022)
[21]
Polyakovskiy, S., Bonyadi, M.R., Wagner, M., Michalewicz, Z., Neumann, F.: A comprehensive benchmark set and heuristics for the traveling thief problem. In: GECCO, pp. 477–484. ACM (2014)
[22]
Pugh JK, Soros LB, and Stanley KO Quality diversity: a new frontier for evolutionary computation Front. Robot. AI 2016 3 40
[23]
Pugh, J.K., Soros, L.B., Szerlip, P.A., Stanley, K.O.: Confronting the challenge of quality diversity. In: GECCO, pp. 967–974. ACM (2015)
[24]
Toth P Dynamic programming algorithms for the zero-one knapsack problem Computing 1980 25 1 29-45
[25]
Ulrich, T., Thiele, L.: Maximizing population diversity in single-objective optimization. In: GECCO, pp. 641–648. ACM (2011)
Recommendations
On the use of quality diversity algorithms for the traveling thief problem
GECCO '22: Proceedings of the Genetic and Evolutionary Computation ConferenceIn 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 ...
Evolutionary diversity optimisation for the traveling thief problem
GECCO '22: Proceedings of the Genetic and Evolutionary Computation ConferenceThere 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 ...
Entropy-based evolutionary diversity optimisation for the traveling salesperson problem
GECCO '21: Proceedings of the Genetic and Evolutionary Computation ConferenceComputing diverse sets of high-quality solutions has gained increasing attention among the evolutionary computation community in recent years. It allows practitioners to choose from a set of high-quality alternatives. In this paper, we employ a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2022
631 pages
ISBN:978-3-031-14713-5
DOI:10.1007/978-3-031-14714-2
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 10 September 2022
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in