Original title: Evoluční algoritmy v úloze booleovské splnitelnosti
Translated title: Evolutionary Algorithms in the Task of Boolean Satisfiability
Authors: Serédi, Silvester ; Vašíček, Zdeněk (referee) ; Sekanina, Lukáš (advisor)
Document type: Master’s theses
Year: 2013
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Cílem této diplomové práce je najít heuristiku řešící SAT problém pomocí evolučního algoritmu. Jsou zde uvedeny přístupy k řešení SAT problému a různé varianty k evolučním algoritmům, které jsou relevantní k danému tématu. Následně je popsaná implementace lineárního genetického programování hledající heuristiku pro řešení instancí SAT problému společne s vlastní implementací SAT solveru pracujíci s výstupem evolučně navrženého programu. Na závěr jsou shrnuty dosažené výsledky The goal of this Master's Thesis is finding a SAT solving heuristic by the application of an evolutionary algorithm. This thesis surveys various approaches used in SAT solving and some variants of evolutionary algorithms that are relevant to this topic. Afterwards the implementation of a linear genetic programming system that searches for a suitable heuristic for SAT problem instances is described, together with the implementation of a custom SAT solver which expoloits the output of the genetic program. Finally, the achieved results are summarized.
Keywords: complexity; evolutionary algorithms; Genetic programming; NP-complete problem; SAT problem; SAT solver.; evolučné algoritmy; Genetické programovanie; NP-úplný problém; SAT problém; SAT solver.; zložitosť

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/53467

Permalink: http://www.nusl.cz/ntk/nusl-236224


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses