The island model as a Markov dynamic system

Robert Schaefer; Aleksander Byrski; Maciej Smołka

International Journal of Applied Mathematics and Computer Science (2012)

  • Volume: 22, Issue: 4, page 971-984
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Robert Schaefer, Aleksander Byrski, and Maciej Smołka. "The island model as a Markov dynamic system." International Journal of Applied Mathematics and Computer Science 22.4 (2012): 971-984. <http://eudml.org/doc/244557>.

@article{RobertSchaefer2012,
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.},
author = {Robert Schaefer, Aleksander Byrski, Maciej Smołka},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {genetic algorithms; asymptotic analysis; global optimization; parallel evolutionary algorithms; Markov chain modeling},
language = {eng},
number = {4},
pages = {971-984},
title = {The island model as a Markov dynamic system},
url = {http://eudml.org/doc/244557},
volume = {22},
year = {2012},
}

TY - JOUR
AU - Robert Schaefer
AU - Aleksander Byrski
AU - Maciej Smołka
TI - The island model as a Markov dynamic system
JO - International Journal of Applied Mathematics and Computer Science
PY - 2012
VL - 22
IS - 4
SP - 971
EP - 984
AB - 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.
LA - eng
KW - genetic algorithms; asymptotic analysis; global optimization; parallel evolutionary algorithms; Markov chain modeling
UR - http://eudml.org/doc/244557
ER -

References

top
  1. Alba, E. and Tomassini, M. (2002). Parallelism and evolutionary algorithms, IEEE Transactions on Evolutionary Computation 6(5): 443-462. 
  2. 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. 
  3. 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. Zbl0973.68197
  4. 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. 
  5. Billingsley, P. (1995). Probability and Measure, Wiley-Interscience, Hoboken, NJ. Zbl0822.60002
  6. Brabazon, A. and O'Neill, M. (2006). Biologically Inspired Algorithms for Financial Modeling, Springer Verlag, Berlin/Heidelberg. 
  7. 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. 
  8. 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. Zbl1209.68557
  9. Cantú-Paz, E. (1995). A summary of research on parallel genetic algorithms, IlliGAL Report No. 95007, University of Illinois, Chicago, IL. 
  10. Cantú-Paz, E. (2000). Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA. Zbl0963.68164
  11. 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. 
  12. Diekert, V. and Rozenberg, G. (1995). The Book of Traces, World Scientific, Singapore. 
  13. 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. 
  14. 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. 
  15. 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. 
  16. 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. 
  17. 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. 
  18. 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. Zbl1128.68334
  19. 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. 
  20. Hennessy, M. (1988). Algebraic Theory of Processes, The MIT Press, Cambridge, MA. Zbl0744.68047
  21. 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. 
  22. 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. 
  23. Horst, R. and Pardalos, P. (1995). Handbook of Global Optimization, Kluwer, Norwell, MA. Zbl0805.00009
  24. Iosifescu, M. (1980). Finite Markov Processes and Their Applications, John Wiley & Sons, Alphen aan den Rijn. Zbl0436.60001
  25. 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. 
  26. Kowalczuk, Z. and Białaszewski, T. (2006). Niching mechanisms in evolutionary computations, International Journal of Applied Mathematics and Computer Science 16(1): 59-84. Zbl1334.90212
  27. Kushner, H. (1971). Introduction to Stochastic Control, Rinehart and Winston, Holt. Zbl0293.93018
  28. 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. 
  29. 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. 
  30. Liekens, A. (2005). Evolution of Finite Populations in Dynamic Environments, Ph.D. thesis, Technische Universiteit Eindhoven, Eindhoven. 
  31. Mahfoud, S. (1991). Finite Markov chain models of an alternative selection strategy for the genetic algorithm, Complex Systems 7(2): 155-170. Zbl0807.92016
  32. 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. 
  33. 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. Zbl1171.90402
  34. 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. Zbl0766.68036
  35. 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. 
  36. 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. 
  37. Nagylaki, T. (1979). The island model with stochastic migration, Genetics 91(1): 163-76. 
  38. Nix, A.E. and Vose, M.D. (1992). Modeling genetic algorithms with Markov chains, Annals of Mathematics and Artificial Intelligence 5(1): 79-88. Zbl1034.68534
  39. 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. 
  40. Peterson, J.L. (1981). Petri Net Theory and the Modeling of Systems, Prentice Hall, Upper Saddle River, NJ. Zbl0461.68059
  41. Potter, M.A. and De Jong, K.A. (2000). Cooperative coevolution: An architecture for evolving coadapted subcomponents, Evolutionary Computation 8(1): 1-29. 
  42. Rinnoy Kan, A. and Timmer, G. (1987). Stochastic global optimization methods, Mathematical Programming 39: 27-56. Zbl0634.90066
  43. Rudolph, G. (1994). Massively parallel simulated annealing and its relation to evolutionary algorithms, Evolutionary Computation 1(4): 361-383. 
  44. 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. 
  45. 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. 
  46. 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). Zbl1268.68141
  47. 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. Zbl1214.68410
  48. Schaefer, R. and Telega, H. (2007). Foundation of Global Genetic Optimization, Studies in Computational Intelligence, Vol. 74, Springer Verlag, Berlin/Heidelberg/New York, NY. 
  49. Schmitt, L.M. (2001). Theory of genetic algorithm, Theoretical Computer Science 259(1): 1-61. Zbl0972.68133
  50. Skolicki, Z. (2007). An Analysis of Island Models In Evolutionary Computation, Ph.D. thesis, George Mason University, Fairfax, VA. 
  51. 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. 
  52. 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. 
  53. 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. 
  54. Tomassini, M. (2005). Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time, Natural Computing Series, Springer, Berlin/Heidelberg. Zbl1089.68114
  55. Vose, M. (1998). The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA. Zbl0952.65048
  56. Vose, M. and Liepins, G. (1991). Punctuated equilibria in genetic search, Complex Systems 5: 31-44. Zbl0764.68149
  57. 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. 
  58. 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. 
  59. Wolpert, D.H. and Macready, W.G. (1997). No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation 1(1): 67-82. 
  60. 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. Zbl1050.90536

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.