Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC. Authors must sign a non-exclusive distribution agreement after article acceptance.
Cellular memetic algorithms
Keywords:
SAT problem, Cellular evolutionary algorithm, Memetic algorithmsAbstract
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.
Downloads
Download data is not yet available.
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, 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.
[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.
Downloads
Published
2005-12-01
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
Issue
Section
Original Articles
