History-Based Topological Speciation For Evolutionary Multimodal Optimization

A great many real-world optimization problems are multimodal, containing more than one optimum. Facing these problems, it is usually more beneficial to obtain multiple optima than just obtaining a single global optimum. Multimodal optimization refers to the search for multiple optima of a problem. Evolutionary algorithms are a family of nature-inspired black-box optimization methods, and have been widely used in multimodal optimization, leading to evolutionary multimodal optimization. Speciation is a fundamental technique in evolutionary multimodal optimization. By partitioning a population into a set of species, speciation enables evolutionary algorithms to work at the higher species level, performing species-wise operations, rather than being restricted to single individuals. Many evolutionary multimodal optimization algorithms are based on this technique. The speciation algorithm employed is expected to have a significant impact on the performance of these algorithms. It is therefore of great importance to conduct research on developing high-performance speciation algorithms.The crucial task and difficulty in speciation is to determine whether two individuals are of the same species. Existing algorithms mainly divides into two categories, namely distance-based and topology-based. Distance-based algorithms base the decision on the distance between the two individuals. They rely on a difficult-to-tune niche radius parameter, and have strong assumptions on the fitness landscape of the target problem. An advantage of distance-based algorithms is that they do not require sampling new points in the solution space and therefore incur no extra fitness evaluation cost. Topology-based algorithms, on the other hand, perform the task by referring to the topography of the fitness landscape. They do not require the niche radius parameter, and impose weaker assumptions on the fitness landscape. However, all existing topology-based algorithms rely on sampling new points to capture the landscape topography, and hence incur extra fitness evaluation cost. Fitness evaluations are crucial resources in evolutionary algorithms. Reducing fitness evaluation consumption of the speciation process is expected to have a positive effect on the overall performance of the evolutionary algorithm.This thesis investigates the topology-based algorithm that costs no extra fitness evaluations. Evolutionary algorithms are based on stochastic sampling and produce a considerable amount of search history during their execution. This fact suggests the idea of capturing landscape topography by using search history alone. To this end, existing topology-based algorithms are first explained from the novel perspective of point sequences, and the crucial task and difficulty in realizing this idea is reduced to the construction of an approximate sequence that consists solely of evaluated history points. This task is formally formulated as a constrained combinatorial optimization problem. A specialized divide-and-conquer algorithm is then designed to solve the problem in an efficient manner. Finally, a new History-Based Topological Speciation (HTS) algorithm that costs no extra fitness evaluations is obtained.This thesis elaborates on the design and implementation of HTS in full detail and presents a thorough theoretical analysis of its time and space complexity. To demonstrate the efficacy of this newly proposed algorithm, comparative experiments with a number of existing speciation algorithms were conducted. Experimental setup and results are reported. In the experiments, HTS significantly outperformed existing topology-based algorithms. Last but not least, HTS is the only parameter-free speciation algorithm at the moment and is readily available in practice.