A feasibility-preserving local search operator for constrained discrete 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: 2008
Tagungsband: Proceedings of the 2008 IEEE Congress on Evolutionary Computation (CEC 2008)
Seitenbereich: 1968-1975
ISBN: 9781424418237


Abstract


Meta-heuristic optimization approaches are commonly applied to many discrete optimization problems. Many of these optimization approaches are based on a local search operator like, e.g., the mutate or neighbor operator that are used in Evolution Strategies or Simulated Annealing, respectively. However, the straightforward implementations of these operators tend to deliver infeasible solutions in constrained optimization problems leading to a poor convergence. In this paper, a novel scheme for a local search operator for discrete constrained optimization problems is presented. By using a sophisticated methodology incorporating a backtracking-based ILP solver, the local search operator preserves the feasibility also on hard constrained problems. In detail, an implementation of the local serach operator as a feasibility-preserving mutate and neighbor operator is presented. To validate the usability of this approach, scalable discrete constrained testcases are introduced that allow to calculate the expected number of feasible solutions. Thus, the hardness of the testcases can be quantified. Hence, a sound comparison of different optimization methodologies is presented. © 2008 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. (2008). A feasibility-preserving local search operator for constrained discrete optimization problems. In Proceedings of the 2008 IEEE Congress on Evolutionary Computation (CEC 2008) (pp. 1968-1975). Hong Kong, HK.

MLA:
Lukasiewycz, Martin, et al. "A feasibility-preserving local search operator for constrained discrete optimization problems." Proceedings of the 2008 IEEE Congress on Evolutionary Computation, CEC 2008, Hong Kong 2008. 1968-1975.

BibTeX: 

Zuletzt aktualisiert 2018-27-10 um 21:50