Evolutionary computation for expensive optimization: a survey

Expensive optimization problem (EOP) refers to the problem that requires expensive or even unaffordable costs to evaluate candidate solutions, which widely exist in many significant real-world applications. On the one hand, the “expensive cost” can refer that the evaluation itself 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 the emergencies like epidemics outbreaks or natural disasters, transportation and dispatching can be urgent for supporting daily operations and saving lives, where the time cost of optimization in normal situations will become too expensive to accept at this time. Therefore, with the progress of real-world society and the emerging issues like the smart cities, the internet of things, and the big data era, solving EOPs more efficiently has become increasingly essential for prospering various fields.

However, due to the expensive cost of evaluating candidate solutions, EOP is difficult for optimization algorithms to search for a satisfactory solution. For this aim, 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 algorithm (EA) like genetic algorithm (GA) and differential evolution (DE), and swarm intelligence algorithms like particle swarm optimization (PSO) and ant colony optimization (ACO). With 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 into the next generation. Based on this, 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 give previous research findings and references to help develop relevant research fields. 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 cover 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. It is supposed that 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; and 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. This can encourage and support the broadening and deepening of research in the related fields.

This work was supported by National Key Research and Development Program of China, the Outstanding Youth Science Foundation, National Natural Science Foundations of China, the Key-Area Research and Development of Guangdong Province, Guangdong Natural Science Foundation Research Team, and National Research Foundation of Korea.

See the article:

Evolutionary Computation for Expensive Optimization: A Survey

http://doi.org/10.1007/s11633-022-1317-4