Faster convergence by means of fitness estimation

Evolutionary algorithms usually require a large number of objective function evaluations before converging to a good solution. However, many real-world applications allow for only very few objective function evaluations. To solve this predicament, one promising possibility seems to not evaluate every individual, but to just estimate the quality of some of the individuals. In this paper, we estimate an individuals fitness on the basis of previously observed objective function values of neighboring individuals. Two estimation methods, interpolation and regression, are tested and compared. The experiments show that by using fitness estimation, it is possible to either reach a better fitness level in the given time, or to reach a desired fitness level much faster (roughly half the number of evaluations) than if all individuals are evaluated.