Particle algorithms for optimization on binary spaces
Schäfer, Christian (2013), Particle algorithms for optimization on binary spaces, ACM Transactions on Modeling and Computer Simulation, 23, 1. http://dx.doi.org/10.1145/2414416.2414424
TypeArticle accepté pour publication ou publié
Journal nameACM Transactions on Modeling and Computer Simulation
MetadataShow full item record
Abstract (EN)We propose a general sequential Monte Carlo approach for optimization of pseudo-Boolean objective functions. There are three aspects we particularly address in this work. First, we give a unified approach to stochastic optimization based on sequential Monte Carlo techniques, including the cross-entropy method and simulated annealing as special cases. Secondly, we point out the need for auxiliary sampling distributions, that is parametric families on binary spaces, which are able to reproduce complex dependency structures. We discuss some known and novel binary parametric families and illustrate their usefulness in our numerical experiments. Finally, we provide numerical evidence that particle-driven optimization algorithms yield superior results on strongly multimodal optimization problems while local search heuristics outperform them on easier problems.
Subjects / KeywordsSequential Monte Carlo; Cross-entropy method; Simulated annealing; Binary parametric families; Unconstrained binary optimization
Showing items related by title and author.