Abstract
Evolutionary algorithms (EAs) have demonstrated remarkable success in tackling black-box optimization problems, making them suitable for addressing various real-world optimization challenges in engineering, computer science, finance, energy, and many other fields. Nevertheless, when the complexity of the objective problem increases, a single EA possesses inherent limitations in achieving better performance. This dissertation aims to explore general techniques for enhancing the capabilities of a single EA in two specific scenarios: 1) when the objective problems to be solved are a problem class, and 2) when the objective problem is a single problem but it is computationally expensive and requires an efficient search process. Consequently, two main techniques for combining multiple algorithms are introduced to adapt to these new scenarios.When dealing with a problem class, it is unlikely that a single algorithm is always the best for all types of optimization problems. Therefore, composing an algorithm portfolio can be beneficial as it leverages the individual strengths of different algorithms. With a wide range of algorithms available, there are numerous possibilities for combining them. This dissertation proposes a general approach for automatically constructing an algorithm portfolio based on a problem set taken from an unknown problem class with an unknown probability distribution. The method utilizes one problem set as training data to learn and identify an algorithm portfolio that is suitable for solving the underlying problem class. The portfolio is constructed by sequentially selecting and adding algorithms. Initially, the best-performing algorithm is determined based on its average rank in solving the training problem set. The most complementary algorithm is then selected using the Pearson correlation coefficient of fitness values at the first hitting time. This iterative process continues, adding more algorithms to the portfolio until no further improvement is achieved. The experimental results indicate the effectiveness of this approach in selecting well-cooperated algorithms, and the composed portfolio is shown to adapt well to different problem classes.
When it comes to solving a specific problem instance, especially in the case of modern black-box problems with expensive fitness evaluation functions, many EAs are not efficient enough due to the high number of function evaluations needed to find the optimal solution. To tackle this, memetic algorithms serve as the foundation for the second technique introduced in this dissertation, which combines an EA with a local search method, allowing for efficient exploration and exploitation of a large search space.
First, a general-purpose multi-dimensional convex landscape generator is introduced as the fundamental component of the memetic algorithm design. In principle, one can select a set of convex basis functions and use operations that preserve convexity to generate a family of convex functions, which inevitably introduces bias in favor of the basis functions. In this dissertation, a convex function generation method with no bias towards a specific analytical function form is proposed using convex hull, a computational geometric structure. This method enables the generation of arbitrary convex functions in multiple dimensions starting from a set of random points, which generalizes existing convex function benchmarks.
Using the multi-dimensional convex-hull-based landscape generator as a surrogate model, a hybrid CMA-ES algorithm with the localized search strategy of the BFGS algorithm is introduced. After running CMA-ES for some time, the populations of the two most recent iterations are collected to construct the convex approximation of the actual problem landscape. As the population converges to a landscape basin, the local landscape is approximated using the constructed convex surrogate model. The accuracy of the convex surrogate model is subsequently validated by the historical solutions and used to determine the probability of switching to a local search. Given BFGS's superior performance in handling unimodal optimization problems, this hybrid approach demonstrates its potential to accelerate the convergence process in finding the global optimum. In this study, we perform experiments on test functions from the BBOB benchmark. The experiments are conducted with a limited evaluation budget, and we introduce a novel method to evaluate the performance of algorithms. The new measurement compares the hitting time of the algorithm to reach a specific fitness value, which is determined by comparing the final solutions obtained by the two algorithms. The obtained results support the effectiveness of this method.
The surrogate-assisted algorithm is then extended as a general convexity-aware memetic framework (CA-MF) that can be applied to any EA. Constructing the convex approximation, when a convex-like local landscape is identified, the EA is switched to local search with a probability to accelerate the convergence to a local minimum, saving the computational resources for further global exploration of the EA. To evaluate the performance of CA-MF, it is applied to three different types of EAs, namely CMA-ES, GA, and L-SHADE, and tested on 14 fitness functions. By observing the convergence curves and comparing the fitness values at two special operating points, the experimental results demonstrate that CA-MF has a generic capacity to enhance the abilities of EAs and outperforms the state-of-the-art Approximate Probabilistic Memetic Framework (APrMF).
In summary, this doctoral dissertation investigates general techniques for enhancing the capabilities of EAs by combining multiple algorithms through the use of algorithm portfolios and memetic algorithm/framework structures. The intellectual proposition lies in the novel approaches, enhanced problem-solving, and performance comparisons. The dissertation introduces a new methodology for finding complementary algorithms in composing algorithm portfolios based on the fitness value at the first hitting time and correlation relationships. Additionally, it incorporates computational geometry methods to develop a convex function landscape generator and proposes a memetic algorithm and framework. These approaches offer a general way to extend the abilities of EAs, resulting in improved solution quality, faster convergence speed, and increased robustness. Comparative evaluations demonstrate the competitiveness and effectiveness of the proposed approaches.
| Date of Award | 6 May 2024 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Shiu Yin Kelvin YUEN (Supervisor) & Chi Wan SUNG (Co-supervisor) |