A Convexity-Aware Memetic Framework

Abstract Evolutionary algorithms (EAs) have been successful in addressing black-box optimization problems, making them suitable for tackling a wide range of real-world optimization challenges. However, they take much evaluation cost to find the optimal solutions when dealing with problems that involve expensive fitness evaluation functions, which is common in modern systems that involve big data and require hours or even days of simulation. To explore a large search space efficiently, a memetic algorithm can be tailored for a specific EA by combining it with a local search method. This paper presents a general convexity-aware memetic framework (CA-MF) that can be applied to arbitrary EAs. Since the populations of an EA tend to accumulate in the basin of attraction of the landscape, CA-MF employs a partial population from the two most recent generations of the EA to approximate local areas with a computational geometry method based on convex hulls. When a convex-like local landscape is identified, the EA will be switched to local search with a certain probability to accelerate the convergence to a possibly local minimum, saving the computational resources for further global exploration of the EA. To evaluate the performance of CA-MF, it was applied to three different types of EAs, namely CMA-ES, GA, and L-SHADE, and tested on 14 fitness functions as well as real-world applications. The experimental results demonstrate that CA-MF has a generic capacity to enhance the abilities of EAs and outperforms the state-of-the-art memetic framework APrMF. Additionally, the performance analysis of CA-MF is discussed with four local search methods and different parameter configurations. It also shows competitive performance compared with the state of the art method IPOP-CMA-ES.