The island model as a Markov dynamic system

2012
journal article
article
18
dc.abstract.enParallel 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.en
dc.contributor.authorSchaefer, Robertpl
dc.contributor.authorByrski, Aleksanderpl
dc.contributor.authorSmołka, Maciejpl
dc.date.accessioned2014-08-19T05:32:32Z
dc.date.available2014-08-19T05:32:32Z
dc.date.created2012pl
dc.date.issued2012pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number4pl
dc.description.physical971-984pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume22pl
dc.identifier.doi10.2478/v10006-012-0072-zpl
dc.identifier.eissn2083-8492pl
dc.identifier.issn1641-876Xpl
dc.identifier.projectROD UJ / Ppl
dc.identifier.urihttp://ruj.uj.edu.pl/xmlui/handle/item/526
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 3.0 Polska*
dc.rights.licenceCC-BY-NC-ND
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/pl/legalcode*
dc.share.typeotwarte czasopismo
dc.subtypeArticlepl
dc.titleThe island model as a Markov dynamic systempl
dc.title.journalInternational Journal of Applied Mathematics and Computer Sciencepl
dc.typeJournalArticlepl
dspace.entity.typePublication
dc.abstract.enen
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.
dc.contributor.authorpl
Schaefer, Robert
dc.contributor.authorpl
Byrski, Aleksander
dc.contributor.authorpl
Smołka, Maciej
dc.date.accessioned
2014-08-19T05:32:32Z
dc.date.available
2014-08-19T05:32:32Z
dc.date.createdpl
2012
dc.date.issuedpl
2012
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.numberpl
4
dc.description.physicalpl
971-984
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
22
dc.identifier.doipl
10.2478/v10006-012-0072-z
dc.identifier.eissnpl
2083-8492
dc.identifier.issnpl
1641-876X
dc.identifier.projectpl
ROD UJ / P
dc.identifier.uri
http://ruj.uj.edu.pl/xmlui/handle/item/526
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights*
Udzielam licencji. Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 3.0 Polska
dc.rights.licence
CC-BY-NC-ND
dc.rights.uri*
http://creativecommons.org/licenses/by-nc-nd/3.0/pl/legalcode
dc.share.type
otwarte czasopismo
dc.subtypepl
Article
dc.titlepl
The island model as a Markov dynamic system
dc.title.journalpl
International Journal of Applied Mathematics and Computer Science
dc.typepl
JournalArticle
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
1
Views per month
Views per city
Ashburn
1
Downloads
schaefer_byrski_smolka_the_island_model_as_a_markov_dynamic_system_2012.pdf
20
schaefer_byrski_smolka_the_island_model_as_a_markov_dynamic_system_2012.odt
6