Deep Boltzmann Machines in Estimation of Distribution Algorithms for Combinatorial Optimization
This work addresses combinatorial optimization for researchers in evolutionary computation, but it is incremental as it builds on existing neural network-based EDAs with mixed results.
The authors tackled the problem of improving Estimation of Distribution Algorithms (EDAs) for combinatorial optimization by integrating Deep Boltzmann Machines (DBMs) as flexible probability models, resulting in superior performance over the Bayesian Optimization Algorithm for difficult additively decomposable functions like concatenated deceptive traps of higher order, but with unreliable convergence for most other benchmarks and higher computational costs.
Estimation of Distribution Algorithms (EDAs) require flexible probability models that can be efficiently learned and sampled. Deep Boltzmann Machines (DBMs) are generative neural networks with these desired properties. We integrate a DBM into an EDA and evaluate the performance of this system in solving combinatorial optimization problems with a single objective. We compare the results to the Bayesian Optimization Algorithm. The performance of DBM-EDA was superior to BOA for difficult additively decomposable functions, i.e., concatenated deceptive traps of higher order. For most other benchmark problems, DBM-EDA cannot clearly outperform BOA, or other neural network-based EDAs. In particular, it often yields optimal solutions for a subset of the runs (with fewer evaluations than BOA), but is unable to provide reliable convergence to the global optimum competitively. At the same time, the model building process is computationally more expensive than that of other EDAs using probabilistic models from the neural network family, such as DAE-EDA.