1996 | ReviewPaper | Buchkapitel
Climbing up NP-hard hills
verfasst von : D. Duvivier, Ph. Preux, E. -G. Talbi
Erschienen in: Parallel Problem Solving from Nature — PPSN IV
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Evolutionary algorithms are sophisticated hill-climbers. In this paper, we discuss the ability of this class of local search algorithms to provide useful and efficient heuristics to solve NP-hard problems. Our discussion is illustrated on experiments aiming at solving the job-shop-scheduling problem. We focus on the components of the EA, pointing out the importance of the objective function as well as the manner the operators are applied. Experiments clearly show the efficiency of local search methods in this context, the trade-off between “pure” and hybrid algorithms, as well as the very good performance obtained by simple hill-climbing algorithms. This work has to be regarded as a step towards a better understanding of the way search algorithms wander in a fitness landscape.