SAT-decoding in evolutionary algorithms for discrete constrained optimization problems

Lukasiewycz M, Glaß M, Haubelt C, Teich J (2007)


Publication Status: Published

Publication Type: Conference contribution, Conference Contribution

Publication year: 2007

Pages Range: 935-942

Article Number: 4424570

Conference Proceedings Title: In Proceedings of the 2007 IEEE Congress on Evolutionary Computation (CEC 2007)

Event location: Singapore SG

ISBN: 9781424413409

DOI: 10.1109/CEC.2007.4424570

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 And 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 Propositional 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. © 2007 IEEE.

Authors with CRIS profile

How to cite

APA:

Lukasiewycz, M., Glaß, M., Haubelt, C., & Teich, J. (2007). SAT-decoding in evolutionary algorithms for discrete constrained optimization problems. In In Proceedings of the 2007 IEEE Congress on Evolutionary Computation (CEC 2007) (pp. 935-942). Singapore, SG.

MLA:

Lukasiewycz, Martin, et al. "SAT-decoding in evolutionary algorithms for discrete constrained optimization problems." Proceedings of the 2007 IEEE Congress on Evolutionary Computation, CEC 2007, Singapore 2007. 935-942.

BibTeX: Download