History-Based Topological Speciation for Multimodal Optimization

Abstract 

Evolutionary algorithms integrating various niching techniques have been widely 
used to find multiple optima of an optimization problem. In recent years, an increasing 
amount of research has been focused on the design and application of speciation-based 
niching techniques. These techniques rely on speciation to partition a population into 
subpopulations (species) such that each occupies a different region of attraction (niche) 
on the fitness landscape. Existing speciation methods are either distance-based or 
topology-based. Topology-based methods are more flexible and have fewer assumptions than 
distance-based methods. However, existing topology-based methods all require sampling and 
evaluating new individuals in order to capture the landscape topography. This incurs additional 
fitness evaluations (FEs), which is a drawback, especially when the FE budget is limited. 
In this paper, a new topology-based speciation method named history-based topological 
speciation (HTS) is proposed. It relies exclusively on search history to capture the landscape 
topography and, therefore, does not require any additional FEs to be performed. To the best 
of our knowledge, HTS is the only parameter-free speciation method at the moment. Both theoretical 
and empirical analyses have been conducted. Theoretical analysis shows that HTS incurs acceptable 
computational overhead. In the experimental study, HTS outperformed existing topology-based methods 
on benchmark functions in up to 32-D space and with as many as 50 optima, and the time overhead 
was practically negligible if a single FE took seconds.