Symmetric-Approximation Energy-Based Estimation of Distribution (SEED): A Continuous Optimization Algorithm

Abstract

Estimation of Distribution Algorithms (EDAs) maintain and iteratively update a probabilistic model to tackle optimization problems. The Boltzmann Probability Distribution Function (Boltzmann-PDF) provides advantages when used in energy based EDAs. However, direct sampling from the Boltzmann-PDF to update the probabilistic model is unpractical, and several EDAs employ an approximation to the Boltzmann-PDF by means of a Gaussian distribution that is usually derived by the minimization of the Kullback-Leibler divergence (KL-divergence) computed between the Gaussian and the Boltzmann-PDFs. The KL-divergence measure is not symmetric, and this causes the Gaussian approximation to fail at correctly modeling the target function for the EDAs, because the parameters of the Gaussian are not optimally estimated. In this paper, we derive an approximation to the Boltzmann-PDF using Jeffreys' divergence (a symmetric measure) in lieu of the KL-divergence and thus improve the performance of the optimization algorithm. Our approach is termed Symmetric-approximation Energy-based Estimation of Distribution (SEED) algorithm. The SEED algorithm is experimentally compared under a univariate approach against two other EDAs (UMDAc and BUMDA) on several benchmark optimization problems. The results show that the SEED algorithm is more effective and more efficient than the other algorithms.

Keywords

• Boltzmann selection
• estimation of distribution algorithms
• Kullback-Leibler divergence
• J-divergence