Object structure

Creator:

Schaefer, Robert ; Byrski, Aleksander ; Smołka, Maciej

Contributor:

Cordón, Oskar - ed. ; Kazienko, Przemysław - ed.

Title:

The island model as a Markov dynamic system

Subtitle:

Hybrid and Ensemble Methods in Machine Learning

Group publication title:

AMCS, Volume 22 (2012)

Subject and Keywords:

genetic algorithms ; asymptotic analysis ; global optimization ; parallel evolutionary algorithms ; Markov chain modeling

Abstract:

Parallel multi-deme genetic algorithms are especially advantageous because they allow reducing the time of computations and can perform a much broader search than single-population ones. However, their formal analysis does not seem to have been studied exhaustively enough. In this paper we propose a mathematical framework describing a wide class of island-like strategies as a stationary Markov chain. ; Our approach uses extensively the modeling principles introduced by Vose, Rudolph and their collaborators. An original and crucial feature of the framework we propose is the mechanism of inter-deme agent operation synchronization. It is important from both a practical and a theoretical point of view. ; We show that under a mild assumption the resulting Markov chain is ergodic and the sequence of the related sampling measures converges to some invariant measure. The asymptotic guarantee of success is also obtained as a simple issue of ergodicity. Moreover, if the cardinality of each island population grows to infinity, then the sequence of the limit invariant measures contains a weakly convergent subsequence. ; The formal description of the island model obtained for the case of solving a single-objective problem can also be extended to the multi-objective case.

Publisher:

Zielona Góra: Uniwersytet Zielonogórski

Date:

2012

Resource Type:

artykuł

DOI:

10.2478/v10006-012-0072-z

Pages:

971-984

Source:

AMCS, Volume 22, Number 4 (2012) ; click here to follow the link

Language:

eng

Rights:

Biblioteka Uniwersytetu Zielonogórskiego