Metaheuristics for Expensive Optimization

An optimisation problem is said to be expensive if assessing the interest of a candidate solution requires access to very significant resources, or resources that are difficult to mobilise. Such problems severely penalise optimisation methods for finding one or more satisfactory solutions to the problem in a reasonable time or, more generally, with reasonable resources. Traditionally, metaheuristics are used to solve complex problems for which no more efficient classical solution methods are known. Most of these problems are characterised by many dimensions, many conflicting objectives, many constraints, or by evaluation functions based on a large amount of data or which cannot be computed automatically. This leads to expensive optimisation. Focusing on population-based metaheuristics, we present three main classes of strategies for reducing the overall cost of the optimisation process, namely reducing the cost of evaluation, accelerating the convergence of the metaheuristic and increasing the computational resources. We adopt and illustrate these strategies on very different real-world application problems such as content-based image retrieval, image signal processor parameterisation, or gene regulatory network modelling, all of which are considered to be complex and expensive problems. However, we show that reducing one type of cost often leads to an increase in another type of cost, and that it is necessary to combine different strategies, paying particular attention to the cost of the strategy itself. We argue that the future of expensive optimisation lies in the integration of multiple reduction strategies, taking into account a variety of potential costs such as time, material, human, financial and environmental resources. To this end, we advocate the use of a multi-objective optimisation approach, in which each cost is associated with a distinct objective, in order to avoid or at least control cost transfers.