Cellular memetic algorithms

• Autores: Enrique Alba Torres , Bernabé Dorronsoro Díaz , Hugo Alfredo Alfonso
• Localización: Journal of Computer Science and Technology, ISSN-e 1666-6038, Vol. 5, Nº. 4, 2005 (Ejemplar dedicado a: Sixteenth Issue), págs. 257-263
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen

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

• Referencias bibliográficas
  • References [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,...
  • [4] E. Alba and B. Dorronsoro, “The exploration/exploitation tradeoff in dynamic cellular evolutionary algorithms,” IEEE TEC, vol. 9, no....
  • [5] E. Alba, B. Dorronsoro, M. Giacobini, and M. Tomasini, “Decentralized cellular evolutionary algorithms,” in Handbook of Bioinspired Algorithms...
  • [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,...
  • [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,...
  • [9] J. Gottlieb, E. Marchiori, and C. Rossi, “Evolutionary algorithm for the satisfiability problem,” Evolutionary Computation, vol. 10, no....
  • [10] T. Back, A.E. Eiben, and M.E. Vink, “A superior evolutionary ¨ algorithm for 3-SAT,” in 7th Conf. on Evolutionary Programming. 1998,...
  • [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,”...
  • [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....
  • [17] B. Selman, H. Kautz, and B. Cohen, “Noise strategies for improving local search,” in 22th Nat. Conf. on Artificial Intelligence, California,...
  • [18] D. McAllester, B. Selman, and H. Kautz, “Evidence for invariants in local search,” in 14th Nat. Conf. on Artificial Intelligence, Providence,...
  • [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,...