Optimizing evolutionary computation with hierarchy-based fitness functions for improved performance and efficiency

Research often focuses on improving performance and efficiency at a lower cost than the current state-of-the-art; one approach, which has enjoyed some success, is the use of various hierarchical models, particularly when trying to improve the scaling ability of Evolutionary Algorithms (EAs). The central hypothesis of this thesis is that by implementing hierarchy in fitness functions, which are at the core of EAs, one can reduce computational costs and improve performance.

We initially develop a hierarchical system known as Pyramid, in which problems are decomposed into simpler versions that can be more easily solved, before scaling up to more difficult versions while reducing the population size. The scaling involves promoting high-performing individuals once they attain a certain threshold of fitness. A major research question in Pyramid is when to promote individuals to the next level (indicated by α), and another is how many individuals to promote (indicated by β). These choices were initially made arbitrarily.

As part of our analysis, we use a set of GA benchmark problems to demonstrate that Pyramid is capable of at least the same performance in terms of solution quality on these benchmarks but at a considerably lower cost in terms of the number of individuals evaluated.

Next, we improve Pyramid by introducing a refined threshold value of α to ensure that the top individuals are highly significantly better than the original population at the current level and making β less aggressive (to maintain a moderately sized population at the final level).

As an extension of Pyramid, we propose Hierarchical Multi-Objective Symbolic Regression (HMS), where multiple objectives are arranged hierarchically. HMS works on two levels. At the first level, a random population is evolved based on a single objective (accuracy), and when the promotional criterion, also referred to as α, is met, some members of the population are promoted to the next level, where another objective (complexity) is introduced. This new, smaller population subsequently evolves using Multi-Objective Optimization (MOO). Several complexity measures are tested along with performance (accuracy). HMS is validated using synthetic Symbolic Regression (SR) problems, benchmarked against state-of-the-art solutions, as demonstrated by the best paper presented at GECCO 2022, where the authors utilized similar problems for evaluation. The evolved models are either competitive with or better than models produced with standard approaches in terms of performance. In terms of size, the solutions are more efficient, lowering computational costs.

The hierarchical approaches we propose can benefit both GA and GP. Hierarchies are implemented from 2 to 5 levels, and the system is scalable to include more levels if needed. The performance is better or equal to the current state of the art, but our approaches are less computationally expensive.