Benutzerspezifische Werkzeuge

Heuristik

Der Begriff wird eingeordnet und erläutert. Anschließend werden Erscheinungsformen und grundlegende Konzepte zur Entwicklung von Heuristiken vorgestellt.

Einordnung

Der Begriff Heuristik stammt vom griechischen „heuriskein“ (finden) und bedeutet sinngemäß  „Anleitung, um auf methodischem Wege zur Erkenntnis zu gelangen“. Innerhalb der Wirtschaftsinformatik wird er unterschiedlich verwendet. So bezeichnen Heuristiken in der Künstlichen Intelligenz zumeist „Daumenregeln“, die zur Reduzierung des mit einer Suchaufgabe verbundenen Aufwandes dienen [Kopfer 1989, S. 19]. Im Operations Research versteht man unter Heuristiken Verfahren zur Lösung komplexer Optimierungsprobleme. Hierbei wird die gegebene Problemstruktur in geeignet erscheinender Weise berücksichtigt, um entweder möglichst schnell zu einer akzeptablen Lösung oder in akzeptabler Zeit zu einer möglichst guten Lösung zu gelangen. Im Unterschied zu den auf mathematischer Optimierung beruhenden exakten Verfahren können Heuristiken die Optimalität einer Lösung nicht feststellen und somit auch nicht garantieren. Deshalb werden sie auch suboptimierende Verfahren genannt. Als Approximationsverfahren werden Heuristiken bezeichnet, für die eine Worst-Case-Schranke angegeben werden kann.

Formen von Heuristiken

Im Operations Research werden Heuristiken eingeteilt in [Domschke, Drexl 2007, S. 128]:

  1. Eröffnungsverfahren, die eine zulässige Lösung konstruieren,
  2. Verbesserungsverfahren, die eine Lösung durch lokale Suche iterativ verbessern,
  3. Unvollständige exakte Verfahren, die die beste gefundene Lösung eines vorzeitig abgebrochenen exakten Verfahrens liefern, und
  4. Verbundverfahren, die die genannten Ansätze miteinander kombinieren.

Des Weiteren werden problemspezifische und universelle Heuristiken unterschieden. Problemspezifische Heuristiken nutzen spezielle Eigenschaften der Problemstruktur und sind deshalb bei Änderungen der Problemstellung oft nicht mehr einsetzbar. Demgegenüber basieren universelle Heuristiken auf allgemeinen, d. h. auf unterschiedliche Problemstellungen übertragbaren, aber in der Regel weniger effizienten Suchstrategien. Zu diesen Verfahren, die auch als Metaheuristiken bezeichnet werden, gehören der Ameisenalgorithmus, unterschiedliche Formen von Evolutionären Algorithmen , Simulated Annealing, die Tabusuche und Variable Neighborhood Search [Reeves 1993].

Literatur

Domschke, Wolfgang; Drexl, Andreas: Einführung in Operations Research. Berlin : Springer-Verlag 2007

Kopfer, Herbert: Heuristische Suche in Operations Research und Künstlicher Intelligenz. Habilitationsschrift: Freie Universität Berlin 1989

Reeves, Colin (Hrsg.): Modern Heuristic Techniques for Combinatorial Problems. Oxford : Blackwell Scientific Publications 1993

 

Autor


 

Prof. Dr. Christian Bierwirth, Universität Halle, Institut für Betriebswirtschaftslehre, Lehrstuhl für Produktion und Logistik, Große Steinstraße 73, 06108 Halle (Saale)

Autoreninfo


Zuletzt bearbeitet: 26.09.2014 12:33
Letzter Abruf: 21.11.2017 16:22
Artikelaktionen