Addressing the traveling salesperson problem with frequency fitness assignment and hybrid algorithms

Liang, Tianyu; Wu, Zhize; Lässig, Jörg; van den Berg, Daan; Thomson, Sarah L.; Weise, Thomas

Abstract

The traveling salesperson problem (TSP) is one of the most iconic hard optimization tasks. With frequency fitness assignment (FFA), a new approach to optimization has recently been proposed: instead of directing the search towards better solutions, the optimization process prefers those with rarely encountered objective values. FFA can be plugged into existing algorithms and can improve their performance on some problems that are hard for them. However, problems like the TSP, where the number of possible objective values (here: tour lengths) is high, cause the performance of FFA-based algorithms to deteriorate. We choose 56 symmetric instances from TSPLib as a testbed for our experiments. We plug FFA both into the (1+1) EA and simulated annealing (SA) and obtain the FEA and FSA, respectively. We find that the resulting FEA substantially outperforms the (1+1) EA and that FSA can reach the global optima more often than SA within our computational budget. We propose two ways to hybridize FFA and traditional optimization in a round-robin scheme where objective function evaluations are alternatingly assigned to both components. The FFA-based parts of the algorithms sometimes send a solution over to the traditional-optimization-based ones. This can lead to further performance improvements. In particular, the hybrids combining simulated annealing with the FEA solve most problems and find close-to-optimal solutions on other instances. Even for several instances with many possible different objective values, which are therefore not suited to FFA, hybrids combining FFA and traditional objective-guided optimization algorithms can offer substantial performance improvements.

Citation

Liang, T., Wu, Z., Lässig, J., van den Berg, D., Thomson, S. L., & Weise, T. (2024). Addressing the traveling salesperson problem with frequency fitness assignment and hybrid algorithms. Soft Computing, 28, 9495–9508. https://doi.org/10.1007/s00500-024-09718-8

• Journal Article Type: Article
• Acceptance Date: Jan 24, 2024
• Online Publication Date: Jul 11, 2024
• Publication Date: 2024
• Deposit Date: May 3, 2024
• Publicly Available Date: Jul 12, 2025
• Print ISSN: 1432-7643
• Electronic ISSN: 1433-7479
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 28
• Pages: 9495–9508
• DOI: https://doi.org/10.1007/s00500-024-09718-8
• Public URL: http://researchrepository.napier.ac.uk/Output/3634808