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]:
-
Eröffnungsverfahren, die eine zulässige Lösung konstruieren,
-
Verbesserungsverfahren, die eine Lösung durch lokale Suche iterativ verbessern,
-
Unvollständige exakte Verfahren, die die beste gefundene Lösung eines vorzeitig abgebrochenen exakten Verfahrens liefern, und
-
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ätr Berlin 1989
Reeves, Colin (Hrsg.): Modern Heuristic Techniques for Combinatorial Problems. Oxford : Blackwell Scientific Publications 1993
