Evolutionary Computation for Expensive Optimization Problems: A Survey

Tuesday - August 15 2023, 18:01 UTC - 1 year ago

This paper provides a systematic and comprehensive survey to review and analyze enabling and developing EC algorithms for tackling difficult Expensive Optimization Problems (EOPs), mathematically analyzing the total expensive cost and providing three potential research directions for reducing this cost. This paper also provides a taxonomy for summarizing the state-of-the-art advances in EC for EOPs from various perspectives, as well as a comprehensive overview of various key enabling technologies for EC for solving EOPs, and identifies and analyzes the common challenges and open issues in EC for EOPs.

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 exbasis.

Secondly, this paper provides a taxonomy for summarizing the state-of-the-art advances in EC for EOPs from various perspectives, as well as a comprehensive overview of various key enabling technologies for EC for solving EOPs.

Thirdly, this paper identifies and analyzes the common challenges and open issues in EC for EOPs, as well as emerging trends and hot topics in this field.