A study on meme propagation in multimemetic algorithms

Rafael Nogueras; Carlos Cotta

International Journal of Applied Mathematics and Computer Science (2015)

  • Volume: 25, Issue: 3, page 499-512
  • ISSN: 1641-876X

Abstract

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

How to cite

top

Rafael Nogueras, and Carlos Cotta. "A study on meme propagation in multimemetic algorithms." International Journal of Applied Mathematics and Computer Science 25.3 (2015): 499-512. <http://eudml.org/doc/271765>.

@article{RafaelNogueras2015,
abstract = {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.},
author = {Rafael Nogueras, Carlos Cotta},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {memetic algorithms; spatial structure; meme propagation},
language = {eng},
number = {3},
pages = {499-512},
title = {A study on meme propagation in multimemetic algorithms},
url = {http://eudml.org/doc/271765},
volume = {25},
year = {2015},
}

TY - JOUR
AU - Rafael Nogueras
AU - Carlos Cotta
TI - A study on meme propagation in multimemetic algorithms
JO - International Journal of Applied Mathematics and Computer Science
PY - 2015
VL - 25
IS - 3
SP - 499
EP - 512
AB - 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.
LA - eng
KW - memetic algorithms; spatial structure; meme propagation
UR - http://eudml.org/doc/271765
ER -

References

top
  1. Alba, E. (2005). Parallel Metaheuristics: A New Class of Algorithms, Wiley-Interscience, Hoboken, NJ. Zbl1094.90052
  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. Zbl0963.68164
  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. Zbl0982.68516
  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. Zbl1211.90006
  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. Zbl1028.68752
  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. Zbl1060.68101
  15. Hoos, H. and Stützle, T. (2004). Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA. Zbl1126.68032
  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. Zbl1071.92027
  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. Zbl1074.68064
  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. Zbl1288.90133
  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. Zbl1089.68114
  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. 

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.