Asymptotic guarantee of success for multi-agent memetic systems

• Autorzy: Byrski A. , Schaefer R. , Smołka M. , Cotta C.
• Języki publikacji: EN

Abstrakty

EN

The paper introduces a stochastic model for a class of population-based global optimization meta-heuristics, that generalizes existing models in the following ways. First of all, an individual becomes an active software agent characterized by the constant genotype and the meme that may change during the optimization process. Second, the model embraces the asynchronous processing of agent’s actions. Third, we consider a vast variety of possible actions that include the conventional mixing operations (e.g. mutation, cloning, crossover) as well as migrations among demes and local optimization methods. Despite the fact that the model fits many popular algorithms and strategies (e.g. genetic algorithms with tournament selection) it is mainly devoted to study memetic algorithms. The model is composed of two parts: EMAS architecture (data structures and management strategies) allowing to define the space of states and the framework for stochastic agent actions and the stationary Markov chain described in terms of this architecture. The probability transition function has been obtained and the Markov kernels for sample actions have been computed. The obtained theoretical results are helpful for studying metaheuristics conforming to the EMAS architecture. The designed synchronization allows the safe, coarse-grained parallel implementation and its effective, sub-optimal scheduling in a distributed computer environment. The proved strong ergodicity of the finite state Markov chain results in the asymptotic stochastic guarantee of success, which in turn imposes the liveness of a studied metaheuristic. The Markov chain delivers the sampling measure at an arbitrary step of computations, which allows further asymptotic studies, e.g. on various kinds of the stochastic convergence.

Słowa kluczowe

EN

computational multi-agent systems; asymptotic analysis; global optimization; parallel evolutionary algorithms; Markov chain modeling

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2013
• Tom: Vol. 61, nr 1
• Strony: 257--278
• Opis fizyczny: Bibliogr. 65 poz., rys., tab.

Twórcy

autor

Byrski A.

autor

Schaefer R.

autor

Smołka M.

autor

Cotta C.

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

Bibliografia

• [1] L. Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold Computer Library, New York, 1991.
• [2] P. Moscato, “On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms”, in TechnicalReport 826, California Institute of Technology, Pasadena, 1989.
• [3] W.E. Hart and R.K. Belew, “Optimizing an arbitrary function is hard for the genetic algorithm”, Proc. 4th Int. Conf. onGenetic Algorithms 4, 190-195 (1991).
• [4] D.H.Wolpert and W.G. Macready, “No free lunch theorems for optimization”, IEEE Trans. on Evol. Comp. 67 (1), CD-ROM (1997).
• [5] N. Krasnogor and J. Smith, “A tutorial for competent memetic algorithms: Model, taxonomy, and design issues”, IEEE Trans.on Evol. Comp. 9 (5), 474-488 (2005).
• [6] P. Moscato and C. Cotta, “A modern introduction to memetic algorithms”, in eds. M. Gendrau and J.-Y. Potvin, Handbook ofMetaheuristics, vol. 146, pp. 141-183, Springer, Berlin, 2010.
• [7] F. Neri, C. Cotta, and P. Moscato, Handbook of MemeticAlgorithms, Studies in Computational Intelligence, vol. 379, Springer-Verlag, Berlin, 2012.
• [8] N.J. Radcliffe and P.D. Surry, “Formal memetic algorithms”. in ed. T. Fogarty, Evolutionary Computing: AISB Workshop LectureNotes in Computer Science, vol. 865, pp. 1-16, Springer- Verlag, Berlin, 1994.
• [9] W.E. Hart, N. Krasnogor, and J.E. Smith, “Memetic evolutionary algorithms” in Recent Advances in Memetic AlgorithmsStudies in Fuzziness and Soft Computing, vol. 166, pp. 3-27, Springer-Verlag, Berlin, 2005.
• [10] F. Neri and C. Cotta. “Memetic algorithms and memetic computing optimization: a literature review”, Swarm and EvolutionaryComputation 2, 1-14 (2012).
• [11] M.G. Norman and P. Moscato, “A competitive and cooperative approach to complex combinatorial search”, in TechnicalReport 790, California Institute of Technology, Pasadena, 1989.
• [12] P. Moscato, “Memetic algorithms: a short introduction”, in New Ideas in Optimization, pp. 219-234, McGraw-Hill, Maidenhead, 1999.
• [13] P. Moscato and C. Cotta, “A gentle introduction to memetic algorithms”, in eds. F. Glover and G. Kochenberger, Handbookof Metaheuristics, pp. 105-144, Kluwer Academic Publishers, Boston, 2003.
• [14] Y.-S. Ong, M.-H. Lim, and X. Che, “Memetic computation - past, present & future”, IEEE Comp. Intel. Mag. 5 (2), 24-36 (2010).
• [15] W. Zhong, J. Liu, M. Xue, and Licheng Jiao, “A multiagent genetic algorithm for global numerical optimization”, IEEETrans. on Systems, Man, and Cybernetics B 34 (2), 1128-1141 (2004).
• [16] A.S.S.M. Barkat Ullah, R. Sarker, and C. Lokan, “An agentbased memetic algorithm (AMA) for nonlinear optimization with equality constraints”, Proc. 11th Congress on EvolutionaryComputation 1, 70-77 (2009).
• [17] G. Acampora, M. Gaeta, V. Loia, and A. Vitiello, “Multi-agent memetic computing for adaptive learning experiences”, 2010 Proc. IEEE Int. Conf.on Fuzzy Systems 1, 1-8 (2010).
• [18] N. Krasnogor, B.P. Blackburne, E.K. Burke, and J.D. Hirst, “Multimeme algorithms for protein structure prediction”, in ed. J.J. Merelo, Parallel Problem Solving From Nature VII of Lecture Notes in Computer Science, vol. 2439, pp. 769-778, Springer-Verlag, Berlin, 2002.
• [19] N. Krasnogor and S. Gustafson, “A study on the use of “selfgeneration in memetic algorithms”, Natural Computing 3, 53-76 (2004).
• [20] J.E. Smith, “Coevolving memetic algorithms: a review and progress report”, IEEE Trans. on Systems, Man, and Cybernetics B 37 (1), 6-17 (2007).
• [21] D. Hales, “Selfish memes and selfless agents-altruism in the swap shop”, Proc. Int. Conf. on Multi Agent Systems 1, 431-432 (1998).
• [22] A. Caponio and F. Neri, “Memetic algorithms in engineering and design”, in eds. F. Neri, C. Cotta, and P. Moscato, Handbookof Memetic Algorithms Studies in Computational Intelligence, vol. 379, pp. 241-260, Springer-Verlag, Berlin, 2012.
• [23] A. Długosz and T. Burczyński, “Multiobjective shape optimization of selected coupled problems by means of evolutionary algorithms”, Bull. Pol. Ac.: Tech. 60 (2), 205-222 (2012).
• [24] Ł. Chomatek and M. Rudnicki, “Application of genetically evolved neural networks to dynamic terrain generation”, Bull. Pol. Ac.: Tech. 59 (1), 3-8 (2011).
• [25] A. Byrski and M. Kisiel-Dorohinicki, “Immunological selection mechanism in agent-based evolutionary computation”, Proc. IIS: IIPWM ’05 Conf., Advances in Soft Computing 1, 411-415 (2005).
• [26] A. Byrski and M. Kisiel-Dorohinicki, “Agent-based evolutionary and immunological optimization”, Proc. ComputationalScience - ICCS 2007, 7th Int. Conf. 1, CD-ROM (2007).
• [27] L. Siwik and R. Dreżewski, “Agent-based multi-objective evolutionary algorithms with cultural and immunological mechanisms”, in Evolutionary Computation, pp. 541-556, In-Teh, London, 2009.
• [28] R. Dreżewski, “Co-evolutionary multi-agent system with speciation and resource sharing mechanisms”, Computing andInformatics 25 (4), 305-331 (2006).
• [29] R. Dreżewski, J. Sepielak, and L. Siwik, “Classical and agentbased evolutionary algorithms for investment strategies generation”, in Natural Computing in Computational Finance Studiesin Computational Intelligence, vol. 185, pp. 181-205, Springer- Verlag, Berlin, 2009.
• [30] A. Byrski, R. Dreżewski, L. Siwik, and M. Kisiel-Dorohinicki, “Evolutionary multi-agent systems”, The Knowledge EngineeringReview, (2013), to be published.
• [31] M. Vose, The Simple Genetic Algorithm: Foundations andTheory, MIT Press, Cambridge, 1998.
• [32] G. Rudolph, “Evolution strategies”, in Handbook of EvolutionaryComputations, Oxford University Press, Oxford, 1997.
• [33] G. Rudolph, “Models of stochastic convergence”, in Handbookof Evolutionary Computations, Oxford University Press, Oxford, 1997.
• [34] G. Rudolph, “Stochastic processes”, in Handbook of EvolutionaryComputations, Oxford University Press, Oxford, 1997.
• [35] P. Pardalos and E. Romeijn, in Handbook of Global Optimization, vol. 2, Kluwer Academic Publisher, Dortrecht, 2002.
• [36] R. Horst and P. Pardalos, Handbook of Global Optimization, Kluwer, Dortrecht, 1995.
• [37] A. Rinnoy Kan and G. Timmer, “Stochastic global optimization methods”, Mathematical Programming 39, 27-56 (1987).
• [38] T.E. Davis and J.C. Principe, “A simulated annealing like convergence theory for the simple genetic algorithm”, Proc. Fourth Int. Conf. on Genetic Algorithms 1, 174-181 (1991).
• [39] J. Suzuki, “A Markov chain analysis on a genetic algorithm”, Proc. 5th Int. Conf. on Genetic Algorithms, Urbana-Champaign 1, 146-154 (1993).
• [40] D.E. Goldberg and P. Segrest, “Finite Markov chain analysis of genetic algorithms”, Proc. 2nd ICGAG 1, 1-8 (1987).
• [41] S. Mahfoud, “Finite Markov chain models of an alternative selection strategy for the genetic algorithm”, Complex Systems 7, 155-170 (1991).
• [42] E. Alba and M. Tomassini, Parallelism and evolutionary algorithms, IEEE Trans. on Evolutionary Computation 6 (5), 443-462 (2002).
• [43] E. Cantú-Paz, Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, 2000.
• [44] F. Fernández de Vega, and E. Cantú-Paz, Parallel and DistributedComputational Intelligence, vol. 269, Springer, Berlin, 2010.
• [45] M. Tomassini, Spatially Structured Evolutionary Algorithms, Springer, Berlin, 2005.
• [46] X. Xu and H. He, “A theoretical model and convergence analysis of memetic evolutionary algorithms”, Advances in NaturalComputation. Lecture Notes in Computer Science 1, 1035-1043 (2005).
• [47] Y.-S. Ong, M.-H. Lim, N. Zhu, and K.-W. Wong, “Classification of adaptive memetic algorithms: a comparative study”, Systems, Man, and Cybernetics, IEEE Trans. on Cybernetics B 36 (1), 141-152 (2006).
• [48] G. Rudolph, “Convergence analysis of canonical genetic algorithms”, IEEE Trans. on Neural Networks 5 (1), 96-101 (1994).
• [49] Y.J. Cao and Q.H. Wu, “Convergence analysis of adaptive genetic algorithm”, Proc. Genetic Algorithms in EngineeringSystems: Innovations and Applications 1, 85-89 (1997).
• [50] K. Cetnarowicz, M. Kisiel-Dorohinicki/ and E. Nawarecki, “The application of evolution process in multi-agent world (MAW) to the prediction system”, Proc. on 2nd Int. Conf.on Multi-Agent Systems (ICMAS’96) 1, CD-ROM (1996).
• [51] A. Byrski and R. Schaefer, “Stochastic model of evolutionary and immunological multi-agent systems: mutually exclusive actions”, Fundamenta Informaticae 95 (2-3), 263-285 (2009).
• [52] R. Schaefer, A. Byrski, and M. Smołka, “Stochastic model of evolutionary and immunological multi-agent systems: parallel execution of local actions”, Fundamenta Informaticae 95 (2-3), 325-348 (2009).
• [53] A. Byrski, R. Schaefer, M. Smołka, and C. Cotta, “Asymptotic analysis of computational multi-agent systems”, Proc. 11th Int. Conf. on Parallel Problem Solving from Nature - PPSN XI 68, 475-484 (2011).
• [54] R. Schaefer, A. Byrski, and M. Smołka, “Island model as markov dynamic system”, Int. J. Applied Mathematics & ComputerScience 22 (4), 971-984 (2012).
• [55] R. Schaefer, A. Byrski, J. Kołodziej, and M. Smołka, “An agent-based model of hierarchic genetic search”, Computers& Mathematics with Applications (CAMWA) 64 (12), 3763-3776 (2012).
• [56] N.R. Jennings, K. Sycara, and M. Wooldridge, “A roadmap of agent research and development”, J. Autonomous Agents andMulti-Agent Systems 1 (1), 7-38 (1998).
• [57] N.R. Jennings and M.J. Wooldridge, “Software agents”, IEEReview 1, 17-20 (1996).
• [58] E. Cantú-Paz, “A summary of research on parallel genetic algorithms”, Report 95007, CD-ROM (1995).
• [59] M. Kisiel-Dorohinicki, “Agent-oriented model of simulated evolution”, in Theory and Practice of Informatics, vol. 2540, Springer-Verlag, Berlin, 2002.
• [60] A.S. Rao and M.P. Georgeff, “Bdi agents: from theory to practice”, Proc. First Int. Conf. on Multi-Agent Systems 1, 312-319 (1995).
• [61] K. G¨odel, “¨Uber formal unentscheidbare S¨atze der Principia Mathematica und verwandter Systeme I”, Monatsheft f ¨urMath. und Physik 38, 173-198 (1931).
• [62] Z. Michalewicz, Genetic Algorithms Plus Data StructuresEquals Evolution Programs, Springer-Verlag New York, 1994.
• [63] P. Billingsley, Probability and Measure, John Wiley and Sons, London, 1987.
• [64] M. Iosifescu, Finite Markov Processes and Their Applications John Wiley and Sons, London, 1980.
• [65] J. Digalakis and K. Margaritis, “An experimental study of benchmarking functions for evolutionary algorithms”, Int. J. Computer Mathemathics 79 (4), 403-416 2002.