License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06061.9
URN: urn:nbn:de:0030-drops-5973
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/597/
Go to the corresponding Portal

Mühlenbein, Heinz ; Höns, Robin

The Factorized Distribution Algorithm and the Minimum Relative Entropy Principle

pdf-format:
06061.MuehlenbeinHeinz.Paper.597.pdf (0.3 MB)

Abstract

We assume that the function to be optimized is additively decomposed (ADF). Then the interaction graph $G_{ADF}$ can be used to compute exact or approximate factorizations. For many practical problems only approximate factorizations lead to efficient optimization algorithms. The relation between the approximation used by the FDA algorithm and the minimum relative entropy principle is discussed. A new algorithm is presented, derived from the Bethe-Kikuchi approach in statistical physics. It minimizes the relative entropy to a Boltzmann distribution with fixed $eta$. We shortly compare different factorizations and algorithms within the FDA software. We use 2-d Ising spin glass problems and Kaufman's n-k function as examples.

BibTeX - Entry

@InProceedings{muhlenbein_et_al:DagSemProc.06061.9,
  author =	{M\"{u}hlenbein, Heinz and H\"{o}ns, Robin},
  title =	{{The Factorized Distribution Algorithm and the Minimum Relative Entropy Principle}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--27},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/597},
  URN =		{urn:nbn:de:0030-drops-5973},
  doi =		{10.4230/DagSemProc.06061.9},
  annote =	{Keywords: Junction tree, minimum relative entropy, maximum likelihood, Bethe-Kikuchi approximation}
}

Keywords: Junction tree, minimum relative entropy, maximum likelihood, Bethe-Kikuchi approximation
Collection: 06061 - Theory of Evolutionary Algorithms
Issue Date: 2006
Date of publication: 07.07.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI