The island model as a Markov dynamic system

• Autorzy: Robert Schaefer , Aleksander Byrski , Maciej Smołka
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2012
• Tom: 22
• Numer: 4
• Strony: 971-984

Daty

wydano

2012

otrzymano

2011-11-23

poprawiono

2012-05-19

Twórcy

autor

Robert Schaefer

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

autor

Aleksander Byrski

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

autor

Maciej Smołka

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

Bibliografia

• Alba, E. and Tomassini, M. (2002). Parallelism and evolutionary algorithms, IEEE Transactions on Evolutionary Computation 6(5): 443-462.
• 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.
• 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.
• 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.
• Billingsley, P. (1995). Probability and Measure, Wiley-Interscience, Hoboken, NJ.
• Brabazon, A. and O'Neill, M. (2006). Biologically Inspired Algorithms for Financial Modeling, Springer Verlag, Berlin/Heidelberg.
• 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.
• 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.
• Cantú-Paz, E. (1995). A summary of research on parallel genetic algorithms, IlliGAL Report No. 95007, University of Illinois, Chicago, IL.
• Cantú-Paz, E. (2000). Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA.
• 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.
• Diekert, V. and Rozenberg, G. (1995). The Book of Traces, World Scientific, Singapore.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• Hennessy, M. (1988). Algebraic Theory of Processes, The MIT Press, Cambridge, MA.
• 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.
• 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.
• Horst, R. and Pardalos, P. (1995). Handbook of Global Optimization, Kluwer, Norwell, MA.
• Iosifescu, M. (1980). Finite Markov Processes and Their Applications, John Wiley & Sons, Alphen aan den Rijn.
• 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.
• Kowalczuk, Z. and Białaszewski, T. (2006). Niching mechanisms in evolutionary computations, International Journal of Applied Mathematics and Computer Science 16(1): 59-84.
• Kushner, H. (1971). Introduction to Stochastic Control, Rinehart and Winston, Holt.
• 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.
• 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.
• Liekens, A. (2005). Evolution of Finite Populations in Dynamic Environments, Ph.D. thesis, Technische Universiteit Eindhoven, Eindhoven.
• Mahfoud, S. (1991). Finite Markov chain models of an alternative selection strategy for the genetic algorithm, Complex Systems 7(2): 155-170.
• 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.
• 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.
• 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.
• 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.
• 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.
• Nagylaki, T. (1979). The island model with stochastic migration, Genetics 91(1): 163-76.
• Nix, A.E. and Vose, M.D. (1992). Modeling genetic algorithms with Markov chains, Annals of Mathematics and Artificial Intelligence 5(1): 79-88.
• 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.
• Peterson, J.L. (1981). Petri Net Theory and the Modeling of Systems, Prentice Hall, Upper Saddle River, NJ.
• Potter, M.A. and De Jong, K.A. (2000). Cooperative coevolution: An architecture for evolving coadapted subcomponents, Evolutionary Computation 8(1): 1-29.
• Rinnoy Kan, A. and Timmer, G. (1987). Stochastic global optimization methods, Mathematical Programming 39: 27-56.
• Rudolph, G. (1994). Massively parallel simulated annealing and its relation to evolutionary algorithms, Evolutionary Computation 1(4): 361-383.
• 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.
• 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.
• 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).
• 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.
• Schaefer, R. and Telega, H. (2007). Foundation of Global Genetic Optimization, Studies in Computational Intelligence, Vol. 74, Springer Verlag, Berlin/Heidelberg/New York, NY.
• Schmitt, L.M. (2001). Theory of genetic algorithm, Theoretical Computer Science 259(1): 1-61.
• Skolicki, Z. (2007). An Analysis of Island Models In Evolutionary Computation, Ph.D. thesis, George Mason University, Fairfax, VA.
• 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.
• 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.
• 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.
• Tomassini, M. (2005). Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time, Natural Computing Series, Springer, Berlin/Heidelberg.
• Vose, M. (1998). The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA.
• Vose, M. and Liepins, G. (1991). Punctuated equilibria in genetic search, Complex Systems 5: 31-44.
• 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.
• 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.
• Wolpert, D.H. and Macready, W.G. (1997). No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation 1(1): 67-82.
• 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.

Identyfikatory

DOI

10.2478/v10006-012-0072-z