  We conduct a first fundamental analysis of the working principles of binary
differential evolution (BDE), an optimization heuristic for binary decision
variables that was derived by Gong and Tuson (2007) from the very successful
classic differential evolution (DE) for continuous optimization. We show that
unlike most other optimization paradigms, it is stable in the sense that
neutral bit values are sampled with probability close to $1/2$ for a long time.
This is generally a desirable property, however, it makes it harder to find the
optima for decision variables with small influence on the objective function.
This can result in an optimization time exponential in the dimension when
optimizing simple symmetric functions like OneMax. On the positive side, BDE
quickly detects and optimizes the most important decision variables. For
example, dominant bits converge to the optimal value in time logarithmic in the
population size. This enables BDE to optimize the most important bits very
fast. Overall, our results indicate that BDE is an interesting optimization
paradigm having characteristics significantly different from classic
evolutionary algorithms or estimation-of-distribution algorithms (EDAs).
  On the technical side, we observe that the strong stochastic dependencies in
the random experiment describing a run of BDE prevent us from proving all
desired results with the mathematical rigor that was successfully used in the
analysis of other evolutionary algorithms. Inspired by mean-field approaches in
statistical physics we propose a more independent variant of BDE, show
experimentally its similarity to BDE, and prove some statements rigorously only
for the independent variant. Such a semi-rigorous approach might be interesting
for other problems in evolutionary computation where purely mathematical
methods failed so far.
