Particle Algorithms for Optimization on Binary Spaces

DOI10.1145/2414416.2414424zbMATH Open1386.65166arXiv1111.0574OpenAlexW2137091798MaRDI QIDQ4635211FDOQ4635211

Christian Schäfer

Publication date: 16 April 2018

Published in: ACM Transactions on Modeling and Computer Simulation (Search for Journal in Brave)

Abstract: We discuss a unified approach to stochastic optimization of pseudo-Boolean objective functions based on particle methods, including the cross-entropy method and simulated annealing as special cases. We point out the need for auxiliary sampling distributions, that is parametric families on binary spaces, which are able to reproduce complex dependency structures, and illustrate their usefulness in our numerical experiments. We provide numerical evidence that particle-driven optimization algorithms based on parametric families yield superior results on strongly multi-modal optimization problems while local search heuristics outperform them on easier problems.

Full work available at URL: https://arxiv.org/abs/1111.0574

Recommendations

• Binary accelerated particle swarm algorithm (BAPSA) for discrete optimization problems
• Particle Filtering Framework for a Class of Randomized Optimization Algorithms
• An improved binary particle swarm optimization for discrete optimization problems
• On a practical implementation of particle methods
• Particle methods for statistical inference and design optimization
• Particle methods for stochastic optimal control problems
• The discrete dynamical functional particle method for solving constrained optimization problems

zbMATH Keywords

simulated annealingsequential Monte Carlo methodscross-entropy methodpseudo-Boolean optimizationbinary parametric families

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical optimization and variational techniques (65K10) Stochastic particle methods (65C35)

Cited In (1)

• Space mapping-based optimization with the macroscopic limit of interacting particle systems

This page was built for publication: Particle Algorithms for Optimization on Binary Spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635211)