Using a Markov network as a surrogate fitness function in a genetic algorithm

Citation

Brownlee A, Regnier-Coudert O, McCall J & Massie S (2010) Using a Markov network as a surrogate fitness function in a genetic algorithm. In: 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010. 2010 IEEE Congress on Evolutionary Computation (CEC), Barcelon, 18.07.2010-23.07.2010. Piscataway, NJ: IEEE. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5586548&abstractAccess=no&userType=inst; https://doi.org/10.1109/CEC.2010.5586548

Abstract
Surrogate models of fitness have been presented as a way of reducing the number of fitness evaluations required by an evolutionary algorithm. This is of particular interest with expensive fitness functions where the cost of building the model is outweighed by the saving of using fewer function evaluations. In this paper we show how a Markov network model can be used as a surrogate fitness function in a genetic algorithm. We demonstrate this applied to a number of well-known benchmark functions and although the results are good in terms of function evaluations the model-building overhead requires a substantially more expensive fitness function to be worthwhile. We move on to describe a fitness function for feature selection in Case-Based Reasoning, which is considerably more expensive than the other benchmark functions we used. We show that for this problem using the surrogate offers a significant decrease in total run time compared to a GA using the true fitness function.