SAT-decoding in evolutionary algorithms for discrete constrained optimization problems

Beitrag bei einer Tagung
(Konferenzbeitrag)


Details zur Publikation

Autorinnen und Autoren: Lukasiewycz M, Glaß M, Haubelt C, Teich J
Jahr der Veröffentlichung: 2007
Tagungsband: In Proceedings of the 2007 IEEE Congress on Evolutionary Computation (CEC 2007)
Seitenbereich: 935-942
ISBN: 9781424413409


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.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Glaß, Michael Prof. Dr.-Ing.
Juniorprofessur für Informatik
Haubelt, Christian Prof. Dr.-Ing.
Technische Fakultät
Teich, Jürgen Prof. Dr.-Ing.
Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)


Zitierweisen

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: 

Zuletzt aktualisiert 2018-29-10 um 20:50