In this paper the optimization of additively decomposed discrete functions
is investigated. For these functions genetic algorithms have exhibited a po
or performance. First the schema theory of genetic algorithms is reformulat
ed in probability theory terms. A schema defines the structure of a margina
l distribution. Then the conceptual algorithm BEDA is introduced. BEDA uses
a Boltzmann distribution to generate search points. From BEDA a new algori
thm, FDA, is derived. FDA uses a factorization of the distribution. The fac
torization captures the structure of the given function. The factorization
problem is closely connected to the theory of conditional independence grap
hs. For the test functions considered, the performance of FDA-in number of
generations till convergence-is similar to that of a genetic algorithm for
the OneMax function. This result is theoretically explained.