Title :
SAT-decoding in evolutionary algorithms for discrete constrained optimization problems
Author :
Lukasiewycz, Martin ; Glaß, Michael ; Haubelt, Christian ; Teich, Jürgen
Author_Institution :
Univ. of Erlangen-Nuremberg, Nuremberg
Abstract :
For complex optimization problems, several population-based heuristics like Multi-Objective Evolutionary Algorithms have been developed. These algorithms are aiming to deliver sufficiently good solutions in an acceptable time. However, for discrete problems that are restricted by several constraints it is mostly a hard problem to even find a single feasible solution. In these cases, the optimization heuristics typically perform poorly as they mainly focus on searching feasible solutions rather than optimizing the objectives. In this paper, we propose a novel methodology to obtain feasible solutions from constrained discrete problems in population- based optimization heuristics. At this juncture, the constraints have to be converted into the Prepositional Satisfiability Problem (SAT). Obtaining a feasible solution is done by the DPLL algorithm which is the core of most modern SAT solvers. It is shown in detail how this methodology is implemented in Multi-objective Evolutionary Algorithms. The SAT solver is used to obtain feasible solutions from the genetic encoded information on arbitrarily hard solvable problems where common methods like penalty functions or repair strategies are failing. Handmade test cases are used to compare various configurations of the SAT solver. On an industrial example, the proposed methodology is compared to common strategies which are used to obtain feasible solutions.
Keywords :
evolutionary computation; genetic algorithms; SAT-decoding; constrained discrete problems; discrete constrained optimization problems; evolutionary algorithms; genetic encoded information; multiobjective evolutionary algorithms; penalty functions; population- based optimization heuristics; prepositional satisfiability problem; repair strategies; Biological information theory; Computer science; Constraint optimization; Evolution (biology); Evolutionary computation; Genetics; Glass; Iterative algorithms; NP-complete problem; Testing;
Conference_Titel :
Evolutionary Computation, 2007. CEC 2007. IEEE Congress on
Conference_Location :
Singapore
Print_ISBN :
978-1-4244-1339-3
Electronic_ISBN :
978-1-4244-1340-9
DOI :
10.1109/CEC.2007.4424570