Tips & Tricks: Handling expensive evaluation functions in Evolutionary Computation

Evolutionary algorithms (EA) have become very popular for solving complex optimization / data based modeling problems as, generally, they are fairly robust, easy to use and able to produce high quality results.

A common problem in real-word applications is the fact that the evaluation/fitness function employed by this type of algorithms is quite expensive (time-wise or even financially) to evaluate. As such, when taking into consideration the restrictions imposed on the running time of the EA, only a limited amount of fitness evaluations can be performed and this usually has a huge impact on the quality of the obtained solutions.

The approaches that have been proposed by scientific literature to deal with this problem roughly fall within two main categories:

• surrogate approximation - construct a new (faster to evaluate) expression of the objective function based on previous input to output mappings obtained using the original (expensive) evaluation function.
• evolutionary approximation - reduce the number of expensive fitness evaluations performed during the run by trying to estimate the fitness of an individual without using the costly evaluation function by combining information from other similar individuals that have already been evaluated and, if available, information regarding parameter sensitivity.

Two of the most common methods for surrogate approximation are based on neural networks (NNs) or support vector machines (SVMs). The idea behind the approach is quite simple: when having a sufficient number of individual fitness evaluations (i.e. sampling data), try to train a NN or a SVM model that can approximate reasonably well the actual expensive fitness evaluation function. The quality of the approximation depends a lot on the complexity and roughness of the search space, on the amount of sampling data and of course on the choice of NN or SVM kernel. After the surrogate NN or SVM model has been trained we can use it to perform a lot of inexpensive but relatively accurate fitness evaluations during parts, or even during the entire run of the EA.

Evolutionary approximation is based on the fact that, for most search spaces, two individuals that share many common features also tend to have a similar fitness value. For example, if in an EA's individuals are coded by a real parameter vector containing 15 values and one individual has 14 values that match exactly the values of an individual that has been evaluate 3 generations before and the 15 value is only slightly different, we can approximate the fitness of the current individual with that of its ancestor. This is a very brute approximation, that can be extended and refined (i.e. using advanced similarity metrics, interpolation, variable correlation information, local mappings, etc) according to the concrete problem at hand.

Hybrid strategies are also worth mentioning. One idea could be to use the surrogate models especially in the middle stages of the EA run and then to switch back to the original fitness evaluation function at the the very end stages of the run, when precision is of the utmost importance.