A study on meme propagation in multimemetic algorithms

Nogueras, R. ; Cotta, C.

International Journal of Applied Mathematics and Computer Science, Tome 25 (2015) no. 3, pp. 499-512.

Résumé

Multimemetic algorithms (MMAs) are a subclass of memetic algorithms in which memes are explicitly attached to genotypes and evolve alongside them. We analyze the propagation of memes in MMAs with a spatial structure. For this purpose we propose an idealized selecto-Lamarckian model that only features selection and local improvement, and study under which conditions good, high-potential memes can proliferate. We compare population models with panmictic and toroidal grid topologies. We show that the increased takeover time induced by the latter is essential for improving the chances for good memes to express themselves in the population by improving their hosts, hence enhancing their survival rates. Experiments realized with an actual MMA on three different complex pseudo-Boolean functions are consistent with these findings, indicating that memes are more successful in a spatially structured MMA, rather than in a panmictic MMA, and that the performance of the former is significantly better than that of its panmictic counterpart.

Détail

Keywords: memetic algorithm, spatial structure, meme propagation
Mots-clés : algorytm memetyczny, struktura przestrzenna

Bibliographie

[1] Alba, E. (2005). Parallel Metaheuristics: A New Class of Algorithms, Wiley-Interscience, Hoboken, NJ.

[2] Alba, E. and Luque, G. (2004). Growth curves and takeover time in evolutionary algorithms, in K. Deb (Ed.), GECCO 2004, Lecture Notes in Computer Science, Vol. 3102, Springer-Verlag, Berlin/Heidelberg, pp. 864–876.

[3] Cantu-Paz, E. (2000). Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA.

[4] Chakhlevitch, K. and Cowling, P. (2008). Hyperheuristics: Recent developments, in C. Cotta, M. Sevaux and K. Sörensen (Eds.), Adaptive and Multilevel Metaheuristics, Studies in Computational Intelligence, Vol. 136, Springer-Verlag, Berlin/Heidelberg, pp. 3–29.

[5] Chen, X. and Ong, Y.-S. (2012). A conceptual modeling of meme complexes in stochastic search, IEEE Transactions on Systems, Man, and Cybernetics, Part C 42(5): 612–625.

[6] Chen, X., Ong, Y.-S., Lim, M.-H. and Tan, K.C. (2011). A multi-facet survey on memetic computation, IEEE Transactions on Evolutionary Computation 15(5): 591–607.

[7] Cowling, P., Kendall, G. and Soubeiga, E. (2008). A hyperheuristic approach to schedule a sales submit, in E. Burke and W. Erben (Eds.), PATAT 2000, Lecture Notes in Computer Science, Vol. 2079, Springer-Verlag, Berlin/Heidelberg, pp. 176–190.

[8] Dawkins, R. (1976). The Selfish Gene, Clarendon Press, Oxford.

[9] Deb, K. and Goldberg, D.E. (1993). Analyzing deception in trap functions, in L.D. Whitley (Ed.), Second Workshop on Foundations of Genetic Algorithms,Morgan Kaufmann, San Francisco, CA, pp. 93–108.

[10] Dorronsoro, B. and Alba, E. (2008). Cellular Genetic Algorithms, Operations Research/Computer Science Interfaces, Vol. 42, Springer, New York, NY.

[11] Giacobini, M., Alba, E. and Tomassini, M. (2003). Selection intensity in asynchronous cellular evolutionary algorithms, in E. Cantú-Paz et al. (Eds.), Genetic and Evolutionary Computation Conference, GECCO 2003, Lecture Notes in Computer Science, Vol. 2723, Springer-Verlag, Berlin/Heidelberg, pp. 955–966.

[12] Giacobini, M., Tomassini, M., Tettamanzi, A. and Alba, E. (2005). Selection intensity in cellular evolutionary algorithms for regular lattices, IEEE Transactions on Evolutionary Computation 9(5): 489–505.

[13] Goldberg, D.E., Deb, K. and Horn, J. (1992). Massive multimodality, deception, and genetic algorithms, Parallel Problem Solving from Nature, PPSN II, Elsevier, Brussels, pp. 37–48.

[14] Hart, W., Krasnogor, N. and Smith, J. (2005). Recent Advances in Memetic Algorithms, Studies in Fuzziness and Soft Computing, Vol. 166, Springer-Verlag, Berlin/Heidelberg, pp. 3–27.

[15] Hoos, H. and Stützle, T. (2004). Stochastic Local Search: Foundations Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA.

[16] Karcz-Dulęba, I. (2004). Time to the convergence of evolution in the space of population states, International Journal of Applied Mathematics and Computer Science 14(3): 279–287.

[17] Krasnogor, N. (2004). Self generating metaheuristics in bioinformatics: The proteins structure comparison case, Genetic Programming and Evolvable Machines 5(2): 181–201.

[18] Krasnogor, N., Blackburne, B., Burke, E. and Hirst, J. (2002). Multimeme algorithms for protein structure prediction, in J. Merelo et al. (Eds.), Parallel Problem Solving From Nature VII, Lecture Notes in Computer Science, Vol. 2439, Springer, Berlin, pp. 769–778.

[19] Krasnogor, N. and Gustafson, S. (2004). A study on the use of “self-generation” in memetic algorithms, Natural Computing 3(1): 53–76.

[20] Krasnogor, N. and Smith, J. (2005). A tutorial for competent memetic algorithms: Model, taxonomy, and design issues, IEEE Transactions on Evolutionary Computation 9(5): 474–488.

[21] Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms, Caltech Concurrent Computation Program, Report 826, California Institute of Technology, Pasadena, CA.

[22] Moscato, P. (1999). Memetic algorithms: A short introduction, in D. Corne, M. Dorigo and F. Glover (Eds.), New Ideas in Optimization, McGraw-Hill, Maidenhead, pp. 219–234.

[23] Moscato, P. and Cotta, C. (2010). A modern introduction to memetic algorithms, in M. Gendreau and J.-Y. Potvin (Eds.), Handbook of Metaheuristics, International Series in Operations Research Management Science, Vol. 146, Springer, New York, NY, pp. 141–183.

[24] Neri, F. and Cotta, C. (2012). Memetic algorithms and memetic computing optimization: A literature review, Swarm and Evolutionary Computation 2: 1–14.

[25] Neri, F., Cotta, C. and Moscato, P. (2012). Handbook of Memetic Algorithms, Studies in Computational Intelligence, Vol. 379, Springer-Verlag, Berlin/Heidelberg.

[26] Neri, F., Tirronen, V., Kärkkäinen, T. and Rossi, T. (2007). Fitness diversity based adaptation in multimeme algorithms: A comparative study, IEEE Congress on Evolutionary Computation, CEC 2007, Singapore, pp. 2374–2381.

[27] Nogueras, R. and Cotta, C. (2013). Analyzing meme propagation in multimemetic algorithms: Initial investigations, Proceedings of the 2013 Federated Conference on Computer Science and Information Systems, Cracow, Poland, pp. 1013–1019.

[28] Norman, M. and Moscato, P. (1989). A competitive and cooperative approach to complex combinatorial search, Proceedings of the 20th Informatics and Operations Research Meeting, Buenos Aires, Argentina, pp. 3.15–3.29.

[29] Ong, Y.-S. and Keane, A. (2004). Meta-Lamarckian learning in memetic algorithms, IEEE Transactions on Evolutionary Computation 8(2): 99–110.

[30] Ong, Y.-S., Lim, M.-H. and Chen, X. (2010). Memetic computation-past, present and future, IEEE Computational Intelligence Magazine 5(2): 24–31.

[31] Ong, Y.-S., Lim, M.-H., Zhu, N. and Wong, K.-W. (2006). Classification of adaptive memetic algorithms: A comparative study, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 36(1): 141–152.

[32] Rudolph, G. and Sprave, J. (1995). A cellular genetic algorithm with self-adjusting acceptance threshold, 1st IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, London, UK, pp. 365–372.

[33] Sarma, J. and De Jong, K. (1997). An analysis of local selection algorithms in a spatially structured evolutionary algorithm, in T. Bäck (Ed.), 7th International Conference on Genetic Algorithms, Morgan Kaufmann, San Francisco, CA, pp. 181–186.

[34] Schaefer, R., Byrski, A. and Smołka, M. (2012). The island model as a Markov dynamic system, International Journal of Applied Mathematics and Computer Science 22(4): 971–984, DOI: 10.2478/v10006-012-0072-z.

[35] Schönfisch, B. and de Roos, A. (1999). Synchronous and asynchronous updating in cellular automata, BioSystems 51(3): 123–143.

[36] Smith, J.E. (2007). Coevolving memetic algorithms: A review and progress report, IEEE Transactions on Systems, Man, and Cybernetics, Part B 37(1): 6–17.

[37] Smith, J.E. (2008). Self-adaptation in evolutionary algorithms for combinatorial optimisation, in C. Cotta, M. Sevaux and K. Sörensen (Eds.), Adaptive and Multilevel Metaheuristics, Studies in Computational Intelligence, Vol. 136, Springer, Berlin/Heidelberg, pp. 31–57.

[38] Smith, J.E. (2012). Self-adaptative and coevolving memetic algorithms, in F. Neri, C. Cotta and P. Moscato (Eds.), Handbook of Memetic Algorithms, Studies in Computational Intelligence, Vol. 379, Springer-Verlag, Berlin/Heidelberg, pp. 167–188.

[39] Tomassini, M. (2005). Spatially Structured Evolutionary Algorithms, Natural Computing Series, Springer-Verlag, Berlin/Heidelberg.

[40] Watson, R.A., Hornby, G.S. and Pollack, J.B. (1998). Modeling building-block interdependency, in A. Eiben, T. Back, M. Schoenauer and H.-P. Schwefel (Eds.), Parallel Problem Solving from Nature, PPSN V, Lecture Notes in Computer Science, Vol. 1498, Springer-Verlag, Berlin/Heidelberg, pp. 97–106.

[41] Wilcoxon, F. (1945). Individual comparisons by ranking methods, Biometrics 1(6): 80–83.