Working principles of binary differential evolution

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. 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 leads to a very good performance in the situation where the decision variables have a differently strong influence on the result, in particular, when the target is not to find the optimal solution, but only a good one. Overall, our results indicate that BDE is an interesting optimization paradigm having characteristics significantly different from the classic evolutionary algorithms or EDAs.