Scalability of using Restricted Boltzmann Machines for Combinatorial Optimization
Estimation of Distribution Algorithms (EDAs) require flexible probability models that can be efficiently learned and sampled. Restricted Boltzmann Machines (RBMs) are generative neural networks with these desired properties. We integrate an RBM into an EDA and evaluate the performance of this system in solving combinatorial optimization problems with a single objective. We assess how the number of fitness evaluations and the CPU time scale with problem size and with problem complexity. The results are compared to the Bayesian Optimization Algorithm, a state-of-the-art EDA. Although RBM-EDA requires larger population sizes and a larger number of fitness evaluations, it outperforms BOA in terms of CPU times, in particular if the problem is large or complex. RBM-EDA requires less time for model building than BOA. These results highlight the potential of using generative neural networks for combinatorial optimization.
Code (0)
등록된 구현이 없습니다.
Tasks
Bayesian OptimizationCombinatorial OptimizationCPUSimilar Papers 제목 키워드 기반
Transductive Boltzmann Machines
We present transductive Boltzmann machines (TBMs), which firstly achieve transductive learning of the Gibbs distribution. While exact learning of the Gibbs distribution is impossible by the family of existing Boltzmann m…
Transductive LearningLogically Synthesized, Hardware-Accelerated, Restricted Boltzmann Machines for Combinatorial Optimization and Integer Factorization
The Restricted Boltzmann Machine (RBM) is a stochastic neural network capable of solving a variety of difficult tasks such as NP-Hard combinatorial optimization problems and integer factorization. The RBM architecture is…
Combinatorial OptimizationCombining Learned Representations for Combinatorial Optimization
We propose a new approach to combine Restricted Boltzmann Machines (RBMs) that can be used to solve combinatorial optimization problems. This allows synthesis of larger models from smaller RBMs that have been pretrained,…
Combinatorial OptimizationRelaxations for inference in restricted Boltzmann machines
We propose a relaxation-based approximate inference algorithm that samples near-MAP configurations of a binary pairwise Markov random field. We experiment on MAP inference tasks in several restricted Boltzmann machines. …
Effective Method for Inverse Ising Problem under Missing Observations in Restricted Boltzmann Machines
Restricted Boltzmann machines (RBMs) are energy-based models analogous to the Ising model and are widely applied in statistical machine learning. The standard inverse Ising problem with a complete dataset requires comput…