Genetic Algorithms for solving combinatorial problems

Abstract

[EN] The boolean satisfiability problem is a very important problem in computer science, affecting a great variety of fields, this work attempts to study how well genetic algorithms perform when applied to the SAT problem in comparison with some popular existing SAT solvers. In order to study the genetic algorithms, the effects of the different genetic operators are analyzed through experimental evaluation, using this analysis the best performing genetic algorithms are selected for comparison with the SAT solvers. The experiments performed indicate that hybrid genetic algorithms outperform pure genetic algorithms and local search algorithms, such as the SAT solvers analyzed, outperform them both when applied to SAT problems.

[ES] El problema de satisfacibilidad booleana es un problema muy importante en el campo de la informatica ya que afecta a una gran variedad de campos, este trabajo intenta estudiar el comportamiento de los algoritmos aplicados a problemas SAT para luego compararlos con algunos de los solucionadores SAT existentes más populares. Para poder estudiar el comportamiento del algoritmo genético, se analizan los efectos de los distintos operadores genéticos a partir de la evaluación experimental, utilizando dicho análisis se seleccionan los mejores algoritmos genéticos para compararlos con los solucionadores SAT. Los experimentos llevados a cabo indican que los algoritmos genéticos hibridos funcionan mejor que los algoritmos genéticos puros y los algoritmos de busqueda local, como los solucionadores SAT analizados, funcionan mejor que ambos a la hora de solucionar problemas SAT.

[CA] El problema de satisfacibilidad booleana és un problema molt important en el camp de la informatica ja que afecta a una gran varietat de camps, este treball intenta estudiar com es comporten el algoritmes genetics aplicats a problemes SAT per a despres compararlos amb alguns dels solucionadors SAT existents més populars. Per a poder estudiar el comportament de l’algoritme genètic, s’analitzen els efectes dels distints operadors genètics a partir de l’avaluació experimental, utilitzant la dit anàlisi se seleccionen els millors algoritmes genètics per a comparar-los amb els solucionadors SAT. Els experiments duts a terme indiquen que els algoritmes genètics híbrids funcionen millor que els algoritmes genètics purs i els algoritmes de cerca local, com els solucionadors SAT analitzats, funcionen millor que ambdós a l’hora de solucionar problemes SAT.