Can I read Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms - FOGA '11 - Approximating the distribution of fitness over hamming regions on EtoBox?

Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms - FOGA '11 - Approximating the distribution of fitness over hamming regions by Sutton, Andrew M.; Whitley, Darrell; Howe, Adele E. is a scholarly article available to read on EtoBox.

What is Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms - FOGA '11 - Approximating the distribution of fitness over hamming regions about?

The distribution of fitness values across a set of states sharply influences the dynamics of evolutionary processes and heuristic search in combinatorial optimization. In this paper we present a method for approximating the distribution of fitness values over Hamming regions by solving a linear programming problem that incorporates low order moments of the target function. These moments can be retrieved in polynomial time for select problems such as MAX-k-SAT using Walsh analysis. The method is applicable to any real function on binary strings that is epistatically bounded and discrete with asymptotic bounds on the cardinality of its codomain.We perform several studies on the ONE-MAX and MAXk-SAT domains to assess the accuracy of the approximation and its dependence on various factors. We show that the approximation can accurately predict the number of states within a Hamming region that have an improving fitness value.

Author

Sutton, Andrew M.; Whitley, Darrell; Howe, Adele E.

Publisher

ACM Press

Published

2011

Language

EN