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)
ISBN: 9781424413409
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.
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