Evolutionary Computation for Expensive Optimization: A Survey

Distributed Differential Evolution With Adaptive Resource Allocation

Distributed differential evolution (DDE) is an efficient paradigm that adopts multiple populations for cooperatively solving complex optimization problems. However, how to allocate fitness evaluation (FE) budget resources among the distributed multiple populations can greatly influence the optimization ability of DDE. Therefore, this article proposes a novel three-layer DDE framework with adaptive resource allocation (DDE-ARA), including the algorithm layer for evolving various differential evolution (DE) populations, the dispatch layer for dispatching the individuals in the DE populations to different distributed machines, and the machine layer for accommodating distributed computers. In the DDE-ARA framework, three novel methods are further proposed. First, a general performance indicator (GPI) method is proposed to measure the performance of different DEs. Second, based on the GPI, a FE allocation (FEA) method is proposed to adaptively allocate the FE budget resources from poorly performing DEs to well-performing DEs for better search efficiency. This way, the GPI and FEA methods achieve the ARA in the algorithm layer. Third, a load balance strategy is proposed in the dispatch layer to balance the FE burden of different computers in the machine layer for improving load balance and algorithm speedup. Moreover, theoretical analyses are provided to show why the proposed DDE-ARA framework can be effective and to discuss the lower bound of its optimization error. Extensive experiments are conducted on all the 30 functions of CEC 2014 competitions at 10, 30, 50, and 100 dimensions, and some state-of-the-art DDE algorithms are adopted for comparisons. The results show the great effectiveness and efficiency of the proposed framework and the three novel methods.

Progressive Learning Hill Climbing Algorithm with Energy-Map-Based Initialization for Image Reconstruction

Image reconstruction is an interesting yet challenging optimization problem that has several potential applications. The task is to reconstruct an image using a fixed number of transparent polygons. Traditional gradient-based algorithms cannot be applied to the problem since the optimization objective has no explicit expression and cannot be represented by computational graphs. Metaheuristic search algorithms are powerful optimization techniques for solving complex optimization problems, especially in the context of incomplete information or limited computational capability. In this paper, we developed a novel metaheuristic search algorithm named progressive learning hill climbing (ProHC) for image reconstruction. Instead of placing all the polygons on a blank canvas at once, ProHC starts from one polygon and gradually adds new polygons to the canvas until reaching the number limit. Furthermore, an energy-map-based initialization operator was designed to facilitate the generation of new solutions. To assess the performance of the proposed algorithm, we constructed a benchmark problem set containing four different types of images. The experimental results demonstrated that ProHC was able to produce visually pleasing reconstructions of the benchmark images. Moreover, the time consumed by ProHC was much shorter than that of the existing approach.

A Surrogate-Assisted Differential Evolution Algorithm for High-Dimensional Expensive Optimization Problems

The radial basis function (RBF) model and the Kriging model have been widely used in the surrogate-assisted evolutionary algorithms (SAEAs). Based on their characteristics, a global and local surrogate-assisted differential evolution algorithm (GL-SADE) for high-dimensional expensive problems is proposed in this article, in which a global RBF model is trained with all samples to estimate a global trend, and then its optima is used to significantly accelerate the convergence process. A local Kriging model prefers to select points with good predicted fitness and great uncertainty, which can effectively prevent the search from getting trapped into local optima. When the local Kriging model finds the best solution so far, a reward search strategy is executed to further exploit the local Kriging model. The experiments on a set of benchmark functions with dimensions varying from 30 to 200 are conducted to evaluate the performance of the proposed algorithm. The experimental results of the proposed algorithm are compared to four state-of-the-art algorithms to show its effectiveness and efficiency in solving high-dimensional expensive problems. Besides, GL-SADE is applied to an airfoil optimization problem to show its effectiveness.

Compressed-Encoding Particle Swarm Optimization with Fuzzy Learning for Large-Scale Feature Selection

Particle swarm optimization (PSO) is a promising method for feature selection. When using PSO to solve the feature selection problem, the probability of each feature being selected and not being selected is the same in the beginning and is optimized during the evolutionary process. That is, the feature selection probability is optimized from symmetry (i.e., 50% vs. 50%) to asymmetry (i.e., some are selected with a higher probability, and some with a lower probability) to help particles obtain the optimal feature subset. However, when dealing with large-scale features, PSO still faces the challenges of a poor search performance and a long running time. In addition, a suitable representation for particles to deal with the discrete binary optimization problem of feature selection is still in great need. This paper proposes a compressed-encoding PSO with fuzzy learning (CEPSO-FL) for the large-scale feature selection problem. It uses the N-base encoding method for the representation of particles and designs a particle update mechanism based on the Hamming distance and a fuzzy learning strategy, which can be performed in the discrete space. It also proposes a local search strategy to dynamically skip some dimensions when updating particles, thus reducing the search space and reducing the running time. The experimental results show that CEPSO-FL performs well for large-scale feature selection problems. The solutions obtained by CEPSO-FL contain small feature subsets and have an excellent performance in classification problems.

Multi-objective multi-criteria evolutionary algorithm for multi-objective multi-task optimization

Evolutionary multi-objective multi-task optimization is an emerging paradigm for solving multi-objective multi-task optimization problem (MO-MTOP) using evolutionary computation. However, most existing methods tend to directly treat the multiple multi-objective tasks as different problems and optimize them by different populations, which face the difficulty in designing good knowledge transferring strategy among the tasks/populations. Different from existing methods that suffer from the difficult knowledge transfer, this paper proposes to treat the MO-MTOP as a multi-objective multi-criteria optimization problem (MO-MCOP), so that the knowledge of all the tasks can be inherited in a same population to be fully utilized for solving the MO-MTOP more efficiently. To be specific, the fitness evaluation function of each task in the MO-MTOP is treated as an evaluation criterion in the corresponding MO-MCOP, and therefore, the MO-MCOP has multiple relevant evaluation criteria to help the individual selection and evolution in different evolutionary stages. Furthermore, a probability-based criterion selection strategy and an adaptive parameter learning method are also proposed to better select the fitness evaluation function as the criterion. By doing so, the algorithm can use suitable evaluation criteria from different tasks at different evolutionary stages to guide the individual selection and population evolution, so as to find out the Pareto optimal solutions of all tasks. By integrating the above, this paper develops a multi-objective multi-criteria evolutionary algorithm framework for solving MO-MTOP. To investigate the proposed algorithm, extensive experiments are conducted on widely used MO-MTOPs to compare with some state-of-the-art and well-performing algorithms, which have verified the great effectiveness and efficiency of the proposed algorithm. Therefore, treating MO-MTOP as MO-MCOP is a potential and promising direction for solving MO-MTOP.