On the Investigation of Multimodal Evolutionary Algorithms Using Search Trajectory Networks
Thai Bao Tran, Ngoc Hoang Luong · Proceedings of the Genetic and Evolutionary Computation Conference · 2024
Evolutionary algorithms (EAs) are often employed to tackle multimodal optimization (MMO), offering the possibility to obtain multiple distinct optimal solutions in one run of the algorithm. Nevertheless, it is challenging to analyze the behaviors of multimodal EAs (MEAs) due to the synergies between the global stage (typically a niching method) and the local stage (typically a core search algorithm) that exist in most MEAs. While Search Trajectory Networks (STNs) are a helpful visualization tool to characterize the behaviors of EAs in approaching a single global optimum, naively applying STNs in MMO yields unintelligible resulting graphs. We here propose an STN variant adapted specifically for depicting the progress of MEAs when locating the set of all global optima. Using this multimodal STN, we carry out investigations for four MEAs created from the combinations of two global-stage mechanisms (i.e., uniform random restart and hill-valley clustering) and two local-stage algorithms (i.e., an evolution strategy and a Gaussian estimation-of-distribution algorithm). Visualization results on 20 functions of the CEC 2013 niching benchmark suite exhibit intrinsic capabilities of these MEAs, yielding interesting explanations for their performance. Source code is available at: https://github.com/ELO-Lab/MDSTN.