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