NDLI: Towards the geometry of estimation of distribution algorithms based on the exponential family

Please wait, while we are loading the content...

Analysis of evolutionary algorithms: from computational complexity analysis to algorithm engineering

On the behaviour of the (1,λ)-es for a simple constrained problem

Elementary bit string mutation landscapes

On the practicality of optimal output mechanisms for co-optimization algorithms

Handling expensive optimization with large noise

Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics

The logarithmic hypervolume indicator

Approximating the distribution of fitness over hamming regions

The role of selective pressure when solving symmetric functions in polynomial time

Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets

Analyzing the impact of mirrored sampling and sequential selection in elitist evolution strategies

Using markov-chain mixing time estimates for the analysis of ant colony optimization

Abstract convex evolutionary search

Faster black-box algorithms through higher arity operators

Non-uniform mutation rates for problems with unknown solution lengths

Adaptive population models for offspring populations and parallel evolutionary algorithms

On the movement of vertex fixed points in the simple GA

Simple max-min ant systems and the optimization of linear pseudo-boolean functions

Using multivariate quantitative genetics theory to assist in EA customization

Towards the geometry of estimation of distribution algorithms based on the exponential family

Convergence rates of SMS-EMOA on continuous bi-objective problem classes

Towards the geometry of estimation of distribution algorithms based on the exponential family

Content Provider	ACM Digital Library
Author	Malagò, Luigi Matteucci, Matteo Pistone, Giovanni
Abstract	In this paper we present a geometrical framework for the analysis of Estimation of Distribution Algorithms (EDAs) based on the exponential family. From a theoretical point of view, an EDA can be modeled as a sequence of densities in a statistical model that converges towards distributions with reduced support. Under this framework, at each iteration the empirical mean of the fitness function decreases in probability, until convergence of the population. This is the context of stochastic relaxation, i.e., the idea of looking for the minima of a function by minimizing its expected value over a set of probability densities. Our main interest is in the study of the gradient of the expected value of the function to be minimized, and in particular on how its landscape changes according to the fitness function and the statistical model used in the relaxation. After introducing some properties of the exponential family, such as the description of its topological closure and of its tangent space, we provide a characterization of the stationary points of the relaxed problem, together with a study of the minimizing sequences with reduced support. The analysis developed in the paper aims to provide a theoretical understanding of the behavior of EDAs, and in particular their ability to converge to the global minimum of the fitness function. The theoretical results of this paper, beside providing a formal framework for the analysis of EDAs, lead to the definition of a new class algorithms for binary functions optimization based on Stochastic Natural Gradient Descent (SNGD), where the estimation of the parameters of the distribution is replaced by the direct update of the model parameters by estimating the natural gradient of the expected value of the fitness function.
Starting Page	230
Ending Page	242
Page Count	13
File Format	PDF
ISBN	9781450306331
DOI	10.1145/1967654.1967675
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-01-05
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Stochastic relaxation Estimation of distribution algorithms Exponential family Stochastic natural gradient descent
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Information Geometry of the Gaussian Distribution in View of Stochastic Optimization

Natural Gradient Flow in the Mixture Geometry of a Discrete Exponential Family

Stochastic Natural Gradient Descent by estimation of empirical covariances

Intrinsic Geometry of Stochastic Gradient Descent Algorithms

An Estimation of Distribution Algorithm based on the Natural Gradient and the Boltzmann Distribution

MATHEMATICAL ENGINEERING TECHNICAL REPORTS Estimation of Exponential-Polynomial Distribution by Holonomic Gradient Descent

Information-based gain adaptation and gradient descent.

Gradient descent optimisation for ILC-based stochastic distribution control

Gibbs random sequences Bayes estimation based on stochastic relaxation

Towards the geometry of estimation of distribution algorithms based on the exponential family

Similar Documents

Information Geometry of the Gaussian Distribution in View of Stochastic Optimization

Natural Gradient Flow in the Mixture Geometry of a Discrete Exponential Family

Stochastic Natural Gradient Descent by estimation of empirical covariances

Intrinsic Geometry of Stochastic Gradient Descent Algorithms

An Estimation of Distribution Algorithm based on the Natural Gradient and the Boltzmann Distribution

MATHEMATICAL ENGINEERING TECHNICAL REPORTS Estimation of Exponential-Polynomial Distribution by Holonomic Gradient Descent

Information-based gain adaptation and gradient descent.

Gradient descent optimisation for ILC-based stochastic distribution control

Gibbs random sequences Bayes estimation based on stochastic relaxation

Towards the geometry of estimation of distribution algorithms based on the exponential family