Evolutionary computation for expensive optimization: A survey

The term 'Expensive optimization problem' (EOP) refers to any problem that requires expensive or even unaffordable costs to evaluate candidate solutions. These problems exist in many significant real-world applications.

On the one hand, the "expensive cost" can refer that an evaluation itself that requires abundant time, money and so on. On the other hand, the "expensive cost" is a relative concept rather than an absolute concept in many real-world problems.

For instance, when encountering emergencies like epidemics or natural disasters, transportation and dispatching can be urgent for supporting daily operations and saving lives, where the time cost of optimization will become too expensive to accept at this time.

Solving EOPs more efficiently has become increasingly essential across many fields. However, due to the expensive cost of evaluating candidate solutions, EOP is difficult for optimization algorithms to assist with.

Evolutionary computation (EC) has been widely adopted to solve EOPs, leading to a fast-growing research field. In general, EC is a type of optimization methodology that is inspired by biological evolution and live organism characteristics. Commonly seen EC algorithms include evolutionary algorithms (EAs) like genetic algorithms (GAs) and differential evolution (DE), as well as swarm intelligence algorithms like particle swarm optimization (PSO) and ant colony optimization (ACO).

Using the idea of "survival of the fittest" from natural evolution, EC algorithms generate new individuals via corresponding evolutionary operators and select individuals with better fitness as a new population for the next generation. Based on this method, EC algorithms can find a satisfactory solution efficiently without the need for gradient information, which is very suitable for solving real-world problems.

To date, various researches into EC for EOP have been conducted and achieved considerable success. However, the work of EC for EOP is still dispersed in the literature and remains to be consolidated in a systematic manner. Therefore, given the rapid and important advancements of EC for EOP, it is essential to review these advancements in order to synthesize and understand previous research findings.

For this purpose, this paper attempts to provide a systematic and comprehensive survey to completely review and analyze how to enable and develop EC algorithms for tackling difficult EOPs efficiently. In addition, to present the review more concisely and clearly, this paper selects and cites related work by considering their sources, publication years, impact, and the coverage of different aspects of the topic surveyed in this paper.

Overall, the main contributions of this paper are given as follows:

Firstly, this paper mathematically analyzes the total expensive cost of using EC for solving EOPs. Then, based on the analysis, this paper further gives three directions for reducing the total cost: Problem approximation and substitution, algorithm design and enhancement, and parallel and distributed computation. This paper is the first that derives the potential research directions by analyzing the total expensive cost of using EC for solving EOPs.

Secondly, a systematic taxonomy is introduced to systematically and structurally review the existing works according to their efforts in the above-pointed directions for solving EOPs efficiently. The taxonomy contains four parts. The first part, problem approximation and substitution, includes problem simplification, fitness approximation, constraint approximation, and multi-fidelity substitution.

The second part, algorithm design and enhancement, introduces optimization framework and paradigm, novel operators, fitness inheritance, and hybrid algorithms and configurations.

The third part, parallel and distributed computation, considers accelerations for approximation and optimizations.

The fourth part, real-world applications, is about the real-world.

In each part, existing related works are further classified and introduced. Therefore, such a systematic taxonomy can offer a better understanding of why and how EC algorithms have been used to solve EOPs efficiently and provide references to help researchers in various fields to solve EOPs more efficiently.

Thirdly, this paper explores and discusses some future research areas and open problems related to the use of EC to tackle EOPs. Five potential future directions from three levels (i.e., theory-method-application level) are considered and discussed in this paper: Deeper theoretical analysis, larger search diversity, more adaptive configuration and control, better knowledge learning and utilization, further test on different problems.