\input zb-basic
\input zb-ioport
\iteman{io-port 00759418}
\itemau{Page, Scott E.}
\itemti{Covers: A theory of Boolean function decomposition.}
\itemso{Complex Syst. 8, No.1, 1-24 (1994).}
\itemab
Summary: We develop a theory of covers for functions defined over Boolean strings. Given a function, a cover is a decomposition, though not necessarily a partition, of the bits into subproblems that can be solved in parallel. In the paper, we formulate the notion of cover size, which equals the size of the largest subproblem in a decomposition for a particular function. Cover size is defined relative to a function's upper contour sets. An implication of cover theory is that a problem's difficulty, as measured by its cover size, necessarily decreases as the function value improves. We also show how cover theory lends insight to the performance of hillclimbing algorithms and genetic algorithms, and present data from simulations that support a covers-based explanation for genetic algorithm performance.
\itemrv{~}
\itemcc{}
\itemut{hillclimbing algorithms; genetic algorithm performance}
\itemli{}
\end