Local Optima Networks (LONs) and Search Trajectory Networks (STNs) for Noisy Combinatorial Problems
John Payne, N.A. Aishwaryaprajna, David J. Walker, Edward C. Keedwell · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2025
Evolutionary computation (EC) methods are effective optimisation algorithms, but their random nature and sensitivity to noise make their behaviour difficult to interpret, limiting real-world use. This paper introduces the novel visualisation tools Noisy Local Optima Networks (Noisy LONs) and Noisy Search Trajectory Networks (Noisy STNs) to illustrate algorithm behaviours and fitness landscapes affected by noise. We evaluated (1+1)-EA, UMDA, and PCEA on the OneMax and Knapsack combinatorial optimisation problems with additive Gaussian noise in fitness evaluations. Results show these visualisations can identify how noise affects algorithm performance, solution paths, and transitions between optima, aiding the explanation of why algorithms may succeed or fail in noisy environments. Further work should improve the clarity and scalability of visualisations to support application to a wider range of problems and noise types, as well as further investigate the predictive power of visualisation features.