CRSGA: Cluster-Based Region Selection Genetic Algorithm Solving Multi-Objective Travelling Thief Problem
Łukasz P. Olech, Paweł B. Myszkowski, Konrad Gmyrek · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2025
The Travelling Thief Problem (TTP) is a multi-objective, combinatorial, NP-hard optimisation problem with constraints and interwoven objectives resembling real-world problems. This paper proposes a Cluster-Based Region Selection Genetic Algorithm (CRSGA) utilising clusterisation of individuals coupled with a 2-layer selection operator: (1) tournament density-based selection that favours regions with sparsely distributed individuals, for which (2) individuals from those clusters are selected into pairs for reproduction. CRSGA focuses on balancing the exploration and exploitation of clusters, improving the quality of the results. The performance of the CRSGA is investigated on 24 benchmark instances with varying complexity. CRSGA outperforms 5 state-of-the-art methods.