Entropy, Search Trajectories, and Explainability for Frequency Fitness Assignment

Thomson, Sarah L; Ochoa, Gabriela; van den Berg, Daan; Liang, Tianyu; Weise, Thomas

Abstract

Local optima are a menace that can trap optimisation processes. Frequency fitness assignment (FFA) is an concept aiming to overcome this problem. It steers the search towards solutions with rare fitness instead of high-quality fitness. FFA-based algorithms have shown promise in the literature, but their behaviour is not well understood. We take a first step in this direction by seeking to explain FFA behaviour and performance for the first time. In particular, we attempt to understand the difference in how FFA-based algorithms navigate the space when compared with a standard objective-guided algorithm which incorporates diversification: simulated annealing (SA). As a testbed for these investigations, a set of quadratic assignment problem (QAP) benchmark instances designed to be difficult for metaheuristics is used. A statistical analysis of trajectory behaviours for FFA-based algorithms is conducted. Additionally, we consider and compare the fitness distributions encountered by each algorithm, as well their respective proficiency on the problems. The findings help to explain FFA performance behaviours, and show that FFA explores more widely and consistently than SA. It is hoped that the explanatory approach adopted in this study serves as an example and inspires further similar investigations into how --- and why --- FFA-assisted optimisation works.

Citation

Thomson, S. L., Ochoa, G., van den Berg, D., Liang, T., & Weise, T. (2024, September). Entropy, Search Trajectories, and Explainability for Frequency Fitness Assignment. Presented at Parallel Problem Solving from Nature (PPSN 2024), Hagenberg, Austria

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Parallel Problem Solving from Nature (PPSN 2024)
• Start Date: Sep 14, 2024
• End Date: Sep 18, 2024
• Acceptance Date: May 31, 2024
• Online Publication Date: Sep 7, 2024
• Publication Date: 2024
• Deposit Date: Jun 5, 2024
• Publicly Available Date: Sep 8, 2025
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Pages: 377-392
• Series Title: Lecture Notes in Computer Science
• Series Number: 15148
• Series ISSN: 0302-9743
• Book Title: Parallel Problem Solving from Nature – PPSN XVIII
• ISBN: 9783031700545
• DOI: https://doi.org/10.1007/978-3-031-70055-2_23
• Keywords: frequency fitness assignment; quadratic assignment problem; fitness landscape
• Public URL: http://researchrepository.napier.ac.uk/Output/3677804
• External URL: https://ppsn2024.fh-ooe.at/