<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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</p></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

The island model as a Markov dynamic system

Department of Computer Science AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krakόw, Poland

Institute of Computer Science Jagiellonian University, ul. Łojasiewicza 6, 30-348 Krakόw, Poland

International Journal of Applied Mathematics and Computer Science

{"article-title":"The island model as a Markov dynamic system"}

Parallel multi-deme genetic algorithms are especially advantageous because they allow reducing the time of computations and can perform a much broader search...

The island model as a Markov dynamic system

Publié en ligne: 28 déc. 2012

Pages: 971 - 984

DOI: https://doi.org/10.2478/v10006-012-0072-z

This content is open access.