Zhang, Hang; Rowe, Jonathan E. Best approximations of fitness functions of binary strings. (English) Zbl 1074.68668 Nat. Comput. 3, No. 1, 113-124 (2004). Summary: Fitness functions of binary strings (pseudo-boolean functions) can be represented as polynomials over a set of boolean variables. We show that any such function has a unique best approximation in the linear span of any subset of polynomials. For example, there is a unique best linear approximation and a unique best quadratic approximation. The error of an approximation here is root-mean-squared error. If all the details of the function to be approximated are known, then the approximation can be calculated directly. Of more practical importance, we give a method for using sampling to estimate the coefficients of the approximation, and describe its limitations. Cited in 2 Documents MSC: 68W05 Nonnumerical algorithms 68T05 Learning and adaptive systems in artificial intelligence Keywords:approximation; fitness function; pseudo-boolean function PDFBibTeX XMLCite \textit{H. Zhang} and \textit{J. E. Rowe}, Nat. Comput. 3, No. 1, 113--124 (2004; Zbl 1074.68668) Full Text: DOI