Entropy, Search Trajectories, and Explainability for Frequency Fitness Assignment

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.