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.
@article{bwmeta1.element.bwnjournal-article-amcv22z4p971bwm,
author = {Robert Schaefer and Aleksander Byrski and Maciej Smo\l ka},
title = {The island model as a Markov dynamic system},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {22},
year = {2012},
pages = {971-984},
zbl = {1288.90133},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv22z4p971bwm}
}
Robert Schaefer; Aleksander Byrski; Maciej Smołka. The island model as a Markov dynamic system. International Journal of Applied Mathematics and Computer Science, Tome 22 (2012) pp. 971-984. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv22z4p971bwm/
[000] Alba, E. and Tomassini, M. (2002). Parallelism and evolutionary algorithms, IEEE Transactions on Evolutionary Computation 6(5): 443-462.
[001] Aparicio, J., Correia, L. and Moura-Pires, F. (1999). Populations are multisets-plato, in W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela and R.E. Smith (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, Florida, USA, 13-17 July 1999, Vol. 2, Morgan Kaufmann, San Francisco, CA, pp. 1845-1850.
[002] Bäck, T., Fogel, D. and Michalewicz, Z. (2000). Evolutionary Computation: Basic Algorithms and Operators, Vols. 1 and 2, Institute of Physics Publishing, Bristol/Philadelphia, PA. | Zbl 0973.68197
[003] Back, T., Hammel, U. and Schwefel, H.-P. (1997). Evolutionary computation: Comments on the history and current state, IEEE Transactions on Evolutionary Computation 1(1): 3-17.
[004] Billingsley, P. (1995). Probability and Measure, Wiley-Interscience, Hoboken, NJ. | Zbl 0822.60002
[005] Brabazon, A. and O'Neill, M. (2006). Biologically Inspired Algorithms for Financial Modeling, Springer Verlag, Berlin/Heidelberg.
[006] Buckley, F., Nicol, S. and Pollett, P. (2010). Preface to the selected papers on modeling and control of metapopulation networks, Ecological Modeling 221(21): 2512-2514.
[007] Byrski, A. and Schaefer, R. (2009). Stochastic model of evolutionary and immunological multi-agent systems: Mutually exclusive actions, Fundamenta Informaticae 95(2-3): 263-285. | Zbl 1209.68557
[008] Cantú-Paz, E. (1995). A summary of research on parallel genetic algorithms, IlliGAL Report No. 95007, University of Illinois, Chicago, IL.
[009] Cantú-Paz, E. (2000). Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA. | Zbl 0963.68164
[010] Davis, T.E. and Principe, J.C. (1991). A simulated annealing like convergence theory for the simple genetic algorithm, Proceedings of the 4th International Conference on Genetic Algorithms, San Diego, CA, USA, pp. 174-181.
[011] Diekert, V. and Rozenberg, G. (1995). The Book of Traces, World Scientific, Singapore.
[012] Droste, S., Jansen, T. and Wegener, I. (1998a). On the optimization of unimodal functions with the (1+1) evolutionary algorithm, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, Amsterdam, The Netherlands, pp. 13-22.
[013] Droste, S., Jansen, T. and Wegener, I. (1998b). A rigorous complexity analysis of the (1+1) evolutionary algorithm for separable functions with Boolean inputs, Evolutionary Computation 6(2): 185-196.
[014] Gajda, E., Schaefer, R. and Smołka, M. (2010). Evolutionary multiobjective optimization algorithm as a Markov system, Proceedings of the 11th International Conference on Parallel Problem Solving from Nature, PPSN XI, Kraków, Poland, pp. 617-626.
[015] Goldberg, D.E. and Segrest, P. (1987). Finite Markov chain analysis of genetic algorithms, Proceedings of the 2nd International Conference on Genetic Algorithms on Genetic Algorithms and Their Application, Cambridge, MA, USA, pp. 1-8.
[016] Gordon, V., Whitley, D. and Bohn, A. (1992). Data flow parallelism in genetic algorithms, in R. Manner and B. Manderick (Eds.), Parallel Problem Solving from Nature 2, Elsevier Science, Amsterdam, pp. 553-542.
[017] Grochowski, M., Schaefer, R. and Uhruski, P. (2004). Diffusion based scheduling in the agent-oriented computing systems, in R. Wyrzykowski, J. Dongarra, M. Paprzycki and J. Waśniewski (Eds.), Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, Vol. 3019, Springer, Berlin/Heidelberg, pp. 97-104. | Zbl 1128.68334
[018] Harik, G., Cantú-Paz, E., Goldberg, D.E. and Miller, B.L. (1999). The gambler's ruin problem, genetic algorithms, and the sizing of populations, Evolutionary Computation 7(3): 251-253.
[019] Hennessy, M. (1988). Algebraic Theory of Processes, The MIT Press, Cambridge, MA. | Zbl 0744.68047
[020] Hewitt, C., Bishop, P. and Steiger, R. (1973). A universal modular ACTOR formalism for artificial intelligence, Proceedings of the 3rd International Joint Conference on Artificial Intelligence, Stanford, CA, USA, pp. 235-245.
[021] Horn, J. (1993). Finite Markov chain analysis of genetic algorithms with niching, Proceedings of the 5th International Conference on Genetic Algorithms, UrbanaChampaign, IL, USA, pp. 110-117.
[022] Horst, R. and Pardalos, P. (1995). Handbook of Global Optimization, Kluwer, Norwell, MA. | Zbl 0805.00009
[023] Iosifescu, M. (1980). Finite Markov Processes and Their Applications, John Wiley & Sons, Alphen aan den Rijn. | Zbl 0436.60001
[024] Kołodziej, J. and Xhafa, F. (2011). Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids, International Journal of Applied Mathematics and Computer Science 21(2) 243-257, DOI: 10.2478/v10006-011-0018-x.
[025] Kowalczuk, Z. and Białaszewski, T. (2006). Niching mechanisms in evolutionary computations, International Journal of Applied Mathematics and Computer Science 16(1): 59-84. | Zbl 1334.90212
[026] Kushner, H. (1971). Introduction to Stochastic Control, Rinehart and Winston, Holt. | Zbl 0293.93018
[027] Lässig, J. and Sudholt, D. (2010). General scheme for analyzing running times of parallel evolutionary algorithms, in R. Schaefer, C. Cotta, J. Kołodziej and G. Rudolph (Eds.), Proceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part I, Springer-Verlag, pp. 234-243.
[028] Li, C. and Yang, S. (2008). An island based hybrid evolutionary algorithm for optimization, in X. Li, M. Kirley, M. Zhang, D.G. Green, V. Ciesielski, H.A. Abbass, Z. Michalewicz, T. Hendtlass, K. Deb, K.C. Tan, J. Branke and Y. Shi (Eds.), SEAL, Lecture Notes in Computer Science, Vol. 5361, Springer, Berlin/Heidelberg, pp. 180-189.
[029] Liekens, A. (2005). Evolution of Finite Populations in Dynamic Environments, Ph.D. thesis, Technische Universiteit Eindhoven, Eindhoven.
[030] Mahfoud, S. (1991). Finite Markov chain models of an alternative selection strategy for the genetic algorithm, Complex Systems 7(2): 155-170. | Zbl 0807.92016
[031] Manderick, B. and Spiessens, P. (1989). Fine-grained parallel genetic algorithms, in J. Schaffer (Ed.), Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kauffman, San Francisco, CA, p. 428.
[032] Mesghouni, K., Hammadi, S. and Borne, P. (2004). Evolutionary algorithms for job-shop scheduling, International Journal of Applied Mathematics and Computer Science 14(1): 91-103. | Zbl 1171.90402
[033] Milner, R. (1990). Functions as processes, in M. Paterson (Ed.), Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 443, Springer, Berlin/Heidelberg, pp. 167-180. | Zbl 0766.68036
[034] Mühlenbein, H. (1989). Parallel genetic algorithms, population genetic and combinatorial optimization, in J. Schaffer, (Ed.), Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kauffman, San Francisco, CA, pp. 416-421.
[035] Mühlenbein, H. (1992). How genetic algorithms really work: Mutation and hillclimbing, in R. Männer and B. Manderick (Eds.), Proceedings of PPSN '92, Elsevier, Amsterdam, pp. 15-26.
[036] Nagylaki, T. (1979). The island model with stochastic migration, Genetics 91(1): 163-76.
[037] Nix, A.E. and Vose, M.D. (1992). Modeling genetic algorithms with Markov chains, Annals of Mathematics and Artificial Intelligence 5(1): 79-88. | Zbl 1034.68534
[038] Paredis, J. (1998). Coevolutionary algorithms, in T. Bäck, D. Fogel and Z. Michalewicz (Eds.), Handbook of Evolutionary Computation, 1st Suppl., IOP Publishing/Oxford University Press, Bristol/Oxford.
[039] Peterson, J.L. (1981). Petri Net Theory and the Modeling of Systems, Prentice Hall, Upper Saddle River, NJ. | Zbl 0461.68059
[040] Potter, M.A. and De Jong, K.A. (2000). Cooperative coevolution: An architecture for evolving coadapted subcomponents, Evolutionary Computation 8(1): 1-29.
[041] Rinnoy Kan, A. and Timmer, G. (1987). Stochastic global optimization methods, Mathematical Programming 39: 27-56. | Zbl 0634.90066
[042] Rudolph, G. (1994). Massively parallel simulated annealing and its relation to evolutionary algorithms, Evolutionary Computation 1(4): 361-383.
[043] Rudolph, G. (1997). Stochastic processes (Chapter B.2.2), Models of stochastic convergence (Chapter B.2.3), in T. Bäck, D.B. Fogel and Z. Michalewicz (Eds.), Handbook of Evolutionary Computations, Oxford University Press, Oxford.
[044] Rudolph, G. (2006). Takeover time in parallel populations with migration, Proceedings of the 2nd International Conference on Bioinspired Optimization Methods and Their Applications (BIOMA 2006), Ljubljana, Slovenia, pp. 63-72.
[045] Schaefer, R., Byrski, A., Kołodziej, J. and Smołka, M. (2012). An agent-based model of hierarchic genetic search, Computers and Mathematics with Applications, DOI: 10.1016/j.camwa.2012.02.052, (accepted). | Zbl 1268.68141
[046] Schaefer, R., Byrski, A. and Smołka, M. (2009). Stochastic model of evolutionary and immunological multi-agent systems: Parallel execution of local actions, Fundamenta Informaticae 95(2-3): 325-348. | Zbl 1214.68410
[047] Schaefer, R. and Telega, H. (2007). Foundation of Global Genetic Optimization, Studies in Computational Intelligence, Vol. 74, Springer Verlag, Berlin/Heidelberg/New York, NY.
[048] Schmitt, L.M. (2001). Theory of genetic algorithm, Theoretical Computer Science 259(1): 1-61. | Zbl 0972.68133
[049] Skolicki, Z. (2007). An Analysis of Island Models In Evolutionary Computation, Ph.D. thesis, George Mason University, Fairfax, VA.
[050] Skolicki, Z. and de Jong, K. (2004). Improving evolutionary algorithms with multi-representation island models, 8th International Conference on Parallel Problem Solving from Nature, PPSN, Birmingham, UK, pp. 420-429.
[051] Suzuki, J. (1993). A Markov Chain Analysis on a Genetic Algorithm, in S. Forrest (Ed.), Proceedings of the 5th International Conference on Genetic Algorithms, UrbanaChampaign, IL, USA, June 1993, Morgan Kaufmann, San Francisco, CA, pp. 146-154.
[052] Terzo, O. Mossucca, L., Cucca, M. and Notarpietro R. (2011). Data intensive scientific analysis with grid computing, International Journal of Applied Mathematics and Computer Science 21(2): 219-228, DOI: 10.2478/v10006-011-0016-z.
[053] Tomassini, M. (2005). Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time, Natural Computing Series, Springer, Berlin/Heidelberg. | Zbl 1089.68114
[054] Vose, M. (1998). The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA. | Zbl 0952.65048
[055] Vose, M. and Liepins, G. (1991). Punctuated equilibria in genetic search, Complex Systems 5: 31-44. | Zbl 0764.68149
[056] Whitley, D. (1992). An executable model of a simple genetic algorithm, in L.D. Whitley (Ed.), Foundations of Genetic Algorithms 2, Morgan Kaufmann, San Francisco, CA, pp. 45-62.
[057] Whitley, W.D., Rana, S.B. and Heckendorn, R.B. (1997). Island model genetic algorithms and linearly separable problems, in D. Corne and J.L. Shapiro (Eds.), Selected Papers from the AISB Workshop on Evolutionary Computing, Springer-Verlag, London, pp. 109-125.
[058] Wolpert, D.H. and Macready, W.G. (1997). No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation 1(1): 67-82.
[059] Wood, G.R. and Zabinsky, Z.B. (2002). Stochastic adaptive search, in P.M. Pardalos and H.E. Romeijn (Eds.), Handbook of Global Optimization, Vol. 2, Kluwer, Norwell, MA. | Zbl 1050.90536