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.
@article{bwmeta1.element.bwnjournal-article-amcv25i3p499bwm,
author = {Rafael Nogueras and Carlos Cotta},
title = {A study on meme propagation in multimemetic algorithms},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {25},
year = {2015},
pages = {499-512},
zbl = {1322.90120},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv25i3p499bwm}
}
Rafael Nogueras; Carlos Cotta. A study on meme propagation in multimemetic algorithms. International Journal of Applied Mathematics and Computer Science, Tome 25 (2015) pp. 499-512. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv25i3p499bwm/
[000] Alba, E. (2005). Parallel Metaheuristics: A New Class of Algorithms, Wiley-Interscience, Hoboken, NJ. | Zbl 1094.90052
[001] 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.
[002] Cantu-Paz, E. (2000). Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA. | Zbl 0963.68164
[003] 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.
[004] 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.
[005] 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.
[006] 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. | Zbl 0982.68516
[007] Dawkins, R. (1976). The Selfish Gene, Clarendon Press, Oxford.
[008] 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.
[009] Dorronsoro, B. and Alba, E. (2008). Cellular Genetic Algorithms, Operations Research/Computer Science Interfaces, Vol. 42, Springer, New York, NY. | Zbl 1211.90006
[010] 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. | Zbl 1028.68752
[011] 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.
[012] 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.
[013] 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. | Zbl 1060.68101
[014] Hoos, H. and Stützle, T. (2004). Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA. | Zbl 1126.68032
[015] 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. | Zbl 1071.92027
[016] Krasnogor, N. (2004). Self generating metaheuristics in bioinformatics: The proteins structure comparison case, Genetic Programming and Evolvable Machines 5(2): 181-201.
[017] 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.
[018] Krasnogor, N. and Gustafson, S. (2004). A study on the use of “self-generation” in memetic algorithms, Natural Computing 3(1): 53-76. | Zbl 1074.68064
[019] 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.
[020] 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.
[021] 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.
[022] 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.
[023] Neri, F. and Cotta, C. (2012). Memetic algorithms and memetic computing optimization: A literature review, Swarm and Evolutionary Computation 2: 1-14.
[024] Neri, F., Cotta, C. and Moscato, P. (2012). Handbook of Memetic Algorithms, Studies in Computational Intelligence, Vol. 379, Springer-Verlag, Berlin/Heidelberg.
[025] 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.
[026] 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.
[027] 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.
[028] Ong, Y.-S. and Keane, A. (2004). Meta-Lamarckian learning in memetic algorithms, IEEE Transactions on Evolutionary Computation 8(2): 99-110.
[029] Ong, Y.-S., Lim, M.-H. and Chen, X. (2010). Memetic computation-past, present and future, IEEE Computational Intelligence Magazine 5(2): 24-31.
[030] 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.
[031] 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.
[032] 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.
[033] 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. | Zbl 1288.90133
[034] Schönfisch, B. and de Roos, A. (1999). Synchronous and asynchronous updating in cellular automata, BioSystems 51(3): 123-143.
[035] 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.
[036] 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.
[037] 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.
[038] Tomassini, M. (2005). Spatially Structured Evolutionary Algorithms, Natural Computing Series, Springer-Verlag, Berlin/Heidelberg. | Zbl 1089.68114
[039] 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.
[040] Wilcoxon, F. (1945). Individual comparisons by ranking methods, Biometrics 1(6): 80-83.