Abstract  Fitness functions of binary strings (pseudo-boolean functions) canbe represented as polynomials over a set of boolean variables. Weshow that any such function has a unique best approximation in thelinear span of any subset of polynomials. For example, there is aunique best linear approximation and a unique best quadraticapproximation. The error of an approximation here isroot-mean-squared error. If all the details of the function to beapproximated are known, then the approximation can be calculateddirectly. Of more practical importance, we give a method for usingsampling to estimate the coefficients of the approximation, anddescribe its limitations.