Cellular memetic algorithms


  • Enrique Alba Torres Department of Computer Science, University of Malaga, Spain
  • Bernabé Dorronsoro Department of Computer Science, University of Malaga, Spain
  • Hugo Alfonso National University of La Pampa, General Pico, La Pampa, Argentina


SAT problem, Cellular evolutionary algorithm, Memetic algorithms


This work is focussed on the development and analysis of a new class of algorithms, called cellular memetic algorithms (cMAs), which will be evaluated here on the satisfiability problem (SAT). For describing a cMA, we study the effects of adding specific knowledge of the problem to the fitness function, the crossover and mutation operators, and to the local search step in a canonical cellular genetic algorithm (cGA). Hence, the proposed cMAs are the result of including these hybridization techniques in different structural ways into a canonical cGA. We conclude that the performance of the cGA is largely improved by these hybrid extensions. The accuracy and efficiency of the resulting cMAs are even better than those of the best existing heuristics for SAT in many cases.


Download data is not yet available.


[1] E. Cantu-Paz, ´ Efficient and Accurate Parallel Genetic Algorithms, vol. 1 of Book Series on GAs and EC, Kluwer, 2000.
[2] E. Alba and M. Tomassini, “Parallelism and evolutionary algorithms,” IEEE TEC, vol. 6, no. 5, pp. 443–462, 2002.
[3] E. Alba and J.M. Troya, “Improving Flexibility and Efficiency by Adding Parallelism to Genetic Algorithms,” Statistics and Computing, vol. 12, no. 2, pp. 91–114, 2002.
[4] E. Alba and B. Dorronsoro, “The exploration/exploitation tradeoff in dynamic cellular evolutionary algorithms,” IEEE TEC, vol. 9, no. 2, pp. 126–142, April 2005.
[5] E. Alba, B. Dorronsoro, M. Giacobini, and M. Tomasini, “Decentralized cellular evolutionary algorithms,” in Handbook of Bioinspired Algorithms and Applications. 2005, CRC Press.
[6] H.A. Kautz and B. Selman, “Planning as satisfiability,” in European Conf. on Artificial Intelligence, 1992, pp. 359–363.
[7] R. Reiter and A. Mackworth, “A logical framework for depiction and image interpretation,” Artifitial Intelligence, vol. 41(3), pp. 123–155, 1989.
[8] K.A. De Jong and W.M. Spears, “Using genetic algorithm to solve NP-complete problems,” in 3rd ICGA, James D. Schaffer, Ed. 1989, pp. 124–132, Morgan Kaufmann.
[9] J. Gottlieb, E. Marchiori, and C. Rossi, “Evolutionary algorithm for the satisfiability problem,” Evolutionary Computation, vol. 10, no. 2, pp. 35–50, Spring 2002.
[10] T. Back, A.E. Eiben, and M.E. Vink, “A superior evolutionary ¨ algorithm for 3-SAT,” in 7th Conf. on Evolutionary Programming. 1998, Vol. 1477 of LNCS, pp. 125–136, Springer.
[11] A.E. Eiben and J.K. van der Hauw, “Solving 3-SAT with adaptive genetic algorithms,” in IEEE CEC97, 1997, pp. 81–86.
[12] G. Folino, C. Pizzuti, and G. Spezzano, “Combining cellular genetic algorithms and local search for solving satisfiability problems,” in IEEE Int. Conf. Tools with AI, 1998, pp. 192–198.
[13] E. Alba, B. Dorronsoro, and H. Alfonso, “Cellular memetic algorithms evaluated on SAT,” in CACIC, 2005, vol. CD 1.
[14] S.A. Cook, “The complexity of theorem-proving procedures,” ACM Symp. on the Theory of Computing, pp. 151–158, 1971.
[15] M. Garey and D. Johnson, Computers and Intractability: a Guide to the Theory of NP-completeness, Freeman, 1979.
[16] J. Gottlieb and N. Voss, “Representations, fitness functions and genetic operators for the satisfiability problem,” in Artificial Evolution. 1998, LNCS, pp. 55–68, Springer.
[17] B. Selman, H. Kautz, and B. Cohen, “Noise strategies for improving local search,” in 22th Nat. Conf. on Artificial Intelligence, California, 1994, pp. 337–343, AAAI Press.
[18] D. McAllester, B. Selman, and H. Kautz, “Evidence for invariants in local search,” in 14th Nat. Conf. on Artificial Intelligence, Providence, RI, 1997, pp. 321–326.
[19] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, “Optimization by simulated annealing,” Science, vol. 4598, pp. 671–680, 1983.
[20] P. Moscato, Handbook of Applied Optimization, chapter Memetic Algorithms, Oxford University Press, 2000.
[21] D.G. Mitchell, B. Selman, and H.J. Levesque, “Hard and easy distributions for SAT problems,” in 10th Nat. Conf. on Artificial Intelligence, California, 1992, pp. 459–465.




How to Cite

Alba Torres, E., Dorronsoro, B., & Alfonso, H. (2005). Cellular memetic algorithms. Journal of Computer Science and Technology, 5(04), p. 257–263. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/845



Original Articles