Preventing Premature Convergence in a Simple EDA via Global Step Size Setting

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F08%3A03145842" target="_blank" >RIV/68407700:21230/08:03145842 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Preventing Premature Convergence in a Simple EDA via Global Step Size Setting

Original language description

When a simple real valued estimation of distribution algorithm (EDA) with Gaussian model and maximum likelihood estimation of parameters is used, it converges prematurely even on the slope of the fitness function. The simplest way of preventing prematureconvergence by multiplying the variance estimate by a constant factor k each generation is studied. Recent works have shown that when increasing the dimensionality of the search space, such an algorithm becomes very quickly unable to traverse the slopeand focus to the optimum at the same time. In this paper it is shown that when isotropic distributions with Gaussian or Cauchy distributed norms are used, the simple constant setting of $k$ is able to ensure a reasonable behaviour of the EDA on the slopeand in the valley of the fitness function at the same time.

Czech name

Předčasná konvergence v jednoduchém EDA a globální nastavení velikosti kroku

Czech description

Pokud použijeme jednoduchý algoritmus EDA v reálné oblasti společně s maximálně věrohodnými odhady parametrů pravděpodobnostního modelu, algoritmus předčasně zkonverguje, a to dokonce i na svahu účelové funkce. Nejjednodušším způsobem, jak zabránit tomuto jevu, je vynásobit odhad rozptylu konstantním faktorem k každou generaci. Výzkumy z nedávné doby ovšem ukázaly, že při zvyšování dimenze prostoru takto upravený algoritmus ztrácí schopnost efektivně procházet svahy účelové funkce a zároveň se zaměřovatna okolí optimálních řešení. Tento článek ukazuje, že při použití izotopických rozdělení s normami vektorů rozdělenými podle Gaussova nebo Cauchyho rozdělení tento efekt nenastává a lze u nich najít takovou hodnotu faktoru k, která zajistí rozumné chování algoritmu na svahu i v údolí účelové funkce.

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Parallel Problem Solving from Nature - PPSN X

ISBN

978-3-540-87699-1

ISSN

0302-9743

e-ISSN

—

Number of pages

10

Pages from-to

—

Publisher name

Springer

Place of publication

Heidelberg

Event location

Dortmund

Event date

Sep 13, 2008

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—