Parallel and interacting stochastic approximation annealing algorithms for global optimisation

DOI10.1007/S11222-016-9663-0MaRDI QIDQ1703808zbMATH OpenOpenAlexFDO

Authors Georgios Karagiannis, Bledar A. Konomi, Guang Lin, Faming Liang

Publication date 7 March 2018

Published in Statistics and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.04876, http://dro.dur.ac.uk/22820/1/22820.pdf

zbMATH Keywords

simulated annealingprotein foldingstochastic approximation Monte Carlopopulation Markov chain Monte Carlostochastic optimisationnetwork learninglocal trap

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Applications of statistics to biology and medical sciences; meta analysis (62P10) Monte Carlo methods (65C05) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We present the parallel and interacting stochastic approximation annealing (PISAA) algorithm, a stochastic simulation procedure for global optimisation, that extends and improves the stochastic approximation annealing (SAA) by using population Monte Carlo ideas. The standard SAA algorithm guarantees convergence to the global minimum when a square-root cooling schedule is used; however the efficiency of its performance depends crucially on its self-adjusting mechanism. Because its mechanism is based on information obtained from only a single chain, SAA may present slow convergence in complex optimisation problems. The proposed algorithm involves simulating a population of SAA chains that interact each other in a manner that ensures significant improvement of the self-adjusting mechanism and better exploration of the sampling space. Central to the proposed algorithm are the ideas of (i) recycling information from the whole population of Markov chains to design a more accurate/stable self-adjusting mechanism and (ii) incorporating more advanced proposals, such as crossover operations, for the exploration of the sampling space. PISAA presents a significantly improved performance in terms of convergence. PISAA can be implemented in parallel computing environments if available. We demonstrate the good performance of the proposed algorithm on challenging applications including Bayesian network learning and protein folding. Our numerical comparisons suggest that PISAA outperforms the simulated annealing, stochastic approximation annealing, and annealing evolutionary stochastic approximation Monte Carlo especially in high dimensional or rugged scenarios.

Recommendations

• Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule
• Parallel simulated annealing algorithms in global optimization
• Multiple-try simulated annealing algorithm for global optimization
• Parallel continuous simulated annealing for global optimization simulated annealing^∗
• Parallel MCMC methods for global optimization

Cites work

• scientific article; zbMATH DE number 3986503 (Why is no real title available?)
• scientific article; zbMATH DE number 46578 (Why is no real title available?)
• scientific article; zbMATH DE number 3497315 (Why is no real title available?)
• scientific article; zbMATH DE number 1471711 (Why is no real title available?)
• scientific article; zbMATH DE number 194544 (Why is no real title available?)
• A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems
• Advanced Markov chain Monte Carlo methods. Learning from past samples.
• Annealing evolutionary stochastic approximation Monte Carlo for global optimization
• Annealing stochastic approximation Monte Carlo algorithm for neural network training
• Auxiliary Variable Methods for Markov Chain Monte Carlo with Applications
• Beitrag zur Theorie des Ferromagnetismus
• Convergence of adaptive direction sampling
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Equation of state calculations by fast computing machines
• General hit-and-run Monte Carlo sampling for evaluating multidimensional integrals
• Learning Bayesian networks for discrete data
• Learning Causal Bayesian Network Structures From Experimental Data
• Monte Carlo sampling methods using Markov chains and their applications
• Optimization by simulated annealing
• Real-Parameter Evolutionary Monte Carlo With Applications to Bayesian Mixture Models
• Simulated annealing process in general state space
• Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule
• Stochastic Approximation in Monte Carlo Computation
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• The Bayesian Choice
• The parallel genetic algorithm as function optimizer
• Very fast simulated re-annealing
• Weak Convergence Rates of Population Versus Single-Chain Stochastic Approximation MCMC Algorithms

Cited in

(5)

• Stochastic annealing for synthesis under uncertainty
• Annealing Optimization for Progressive Learning With Stochastic Approximation
• Annealing adaptive search, cross-entropy, and stochastic approximation in global optimization
• Multiple-try simulated annealing algorithm for global optimization
• Parallel continuous simulated annealing for global optimization simulated annealing^∗

This page was built for publication: Parallel and interacting stochastic approximation annealing algorithms for global optimisation

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