Inhaltsübersicht I. Einleitung II. Beispiel: Investitionsprogrammplanung III. Anwendungsbereiche IV. Klassifikation heuristischer Verfahren V. Heuristische Grundprinzipien VI. Abbruch und Evaluation von Heuristiken I. Einleitung Rationales Entscheiden umfasst das Lösen von Entscheidungsproblemen. Ein Entscheidungsproblem besteht nun darin, eine Alternative aus einer Menge von Alternativen auszuwählen. Da die Anzahl der möglichen Alternativen groß sein kann, geht man häufig dazu über, die möglichen Alternativen nicht explizit zu betrachten, sondern die Eigenschaften einer möglichen Alternative durch eine Menge von Bedingungen, die eine mögliche Alternative auszeichnen, zu beschreiben. Jede Alternative, die alle diese Bedingungen erfüllt, wird als zulässige Alternative bzw. als zulässige Lösung des Entscheidungsproblems bezeichnet. Die formale und zumeist abstrakte Darstellung eines derartigen Entscheidungsproblems bezeichnet man als Entscheidungsmodell (vgl. z.B. Kapitel 1 in Gal, T./Gehring, H.  1981). In einem Entscheidungsmodell werden Alternativen durch Entscheidungsvariable operationalisiert, und eine Belegung der Entscheidungsvariablen mit Werten repräsentiert eine Lösung des Entscheidungsproblems. Das Lösen eines Entscheidungsproblems reduziert sich also im Wesentlichen auf das Bestimmen von Werten für die Entscheidungsvariablen eines Entscheidungsmodells. Können die Alternativen eines Entscheidungsproblems bewertet werden, dann sucht man unter den zulässigen Alternativen typischerweise eine „ beste “ Lösung, und die Funktion, die dabei den Wert einer Alternative bestimmt, nennt man Zielfunktion. Wir wollen uns hier auf die Betrachtung von Zielfunktionen beschränken, die jeder Lösung genau einen Wert zuordnen, d.h., wir beschränken uns auf Entscheidungsprobleme, bei denen Alternativen anhand eines einzigen Kriteriums miteinander verglichen werden. Ohne Beschränkung der Allgemeinheit kann dann angenommen werden, dass eine Lösung mit maximalem Zielfunktionswert gesucht ist. Das Entscheidungsproblem stellt sich daher als Optimierungsproblem, genauer gesagt als Maximierungsproblem dar. Man mache sich klar, dass z.B. Satisfizierungsprobleme eine scheinbar andere Zielsetzung verfolgen, tatsächlich jedoch Spezialfälle eines Optimierungsproblems sind (vgl. z.B. Dinkelbach, W.  1978). In diesem Kontext definiert sich ein heuristisches Verfahren bzw. eine Heuristik für ein Entscheidungsproblem als ein Rechenverfahren, das versucht, - eine zulässige Lösung mit - bestmöglichem Zielfunktionswert zu ermitteln. Die Betonung liegt hier auf „ versucht “ , denn zum einen kann bereits das Bestimmen irgendeiner zulässigen Lösung ein schwieriges Problem sein, sodass es oftmals keine Garantie dafür gibt, dass die Heuristik überhaupt eine zulässige Lösung findet. Zum anderen gibt es, selbst wenn eine zulässige Lösung gefunden werden kann, bei Heuristiken keine Gewähr dafür, dass eine zulässige Lösung mit maximalem Zielfunktionswert ermittelt wird (anderenfalls wäre es ein exaktes Verfahren bzw. ein optimales Verfahren); in aller Regel sind die berechneten Lösungen suboptimal. Man beachte, dass Suboptimalität nicht bedeutet, dass für ausgewählte Beispiele nicht auch optimale Lösungen bestimmt werden könnten. Vielmehr ist es so, dass es keine Garantie im Sinne eines mathematischen Beweises dafür gibt, dass eine optimale Lösung gefunden wird. Es sei angemerkt, dass die obige Definition eines heuristischen Verfahrens sehr weit interpretiert werden kann und sollte. So wollen wir selbst das simple zufällige Auswählen irgendeiner Alternative (das entspricht dem Belegen der Entscheidungsvariablen mit Zufallswerten) bewusst als Versuch gelten lassen, die Merkmale einer Heuristik zu erfüllen. Mit diesem Hinweis wird klar, dass der Ehrgeiz eines Entwicklers von Heuristiken darin bestehen sollte, „ gute “ Heuristiken zu erdenken. Typische Kriterien, deren Erfüllung eine „ gute “ Heuristik ausmacht, werden am Ende des Beitrages diskutiert. II. Beispiel: Investitionsprogrammplanung Zunächst wollen wir ein Beispiel betrachten, das als roter Faden die nachfolgenden Ausführungen begleitet, indem verschiedene Grundideen heuristischer Verfahren an dem Beispiel illustriert werden. Gegeben sei ein einfaches Investitionsprogrammplanungsproblem bei Sicherheit, das darin besteht, aus einer Menge von fünf Investitionsprojekten eine Teilmenge durchzuführender Projekte auszuwählen. Die Projekte sind nicht teilbar, d.h. ein Projekt wird entweder ganz oder gar nicht durchgeführt. Ziel ist es, die Summe der Endwerte der akzeptierten Projekte zu maximieren. Ein limitiertes Budget von 15 Geldeinheiten wirkt restriktiv auf die Auswahl von Investitionsprojekten. Die projektspezifischen Daten seien in Tab. 1 gegeben. Tab. 1: Daten des Beispiels zur Investitionsprogrammplanung Für dieses Entscheidungsproblem gibt es 32 Alternativen (32 Portfolios), von denen 23 zulässig sind. Definiert man nun eine Entscheidungsvariable xj, die den Wert eins annimmt, wenn Projekt j durchgeführt werden soll, und null, falls nicht, dann lässt sich das Entscheidungsproblem folgendermaßen modellieren: Max 5x1 + 2x2 + 7x3 + 4x4 + 9x5 unter den Nebenbedingungen 4x1 + 3x2 + 6x3 + 4x4 + 7x5 ≤ 15 x1, x2, x3, x4, x5 ∊ {0,1} III. Anwendungsbereiche Zwei Aspekte seien hier erwähnt, um zu begründen, weshalb es von Vorteil sein kann, heuristische Verfahren anstelle von optimalen Verfahren einzusetzen. Zum einen stellt sich das praktische Lösen eines Entscheidungsproblems oftmals als unerwartet schwierig heraus in dem Sinne, dass ein angewendetes Rechenverfahren zu hohe Rechenzeit beansprucht. So scheint das Investitionsprogrammplanungsbeispiel ein einfaches Entscheidungsproblem zu sein, denn durch schlichtes Aufzählen aller Möglichkeiten sollte ein endwertmaximales Portfolio leicht bestimmbar sein. Das mag für ein Beispiel mit fünf Projekten gelten, für größere Beispiele jedoch benötigen Computer schnell viele Stunden oder Tage. Selbst raffiniertere Verfahren zur Bestimmung einer optimalen Lösung haben das Problem, dass die Rechenzeit mit der Größe des Entscheidungsproblems inakzeptabel wächst. In solchen Situationen greift man typischerweise auf Heuristiken zurück, die selbst für sehr große Probleme eine (vergleichsweise) kurze Rechenzeit benötigen (sollten). Nun liegt die Frage nahe, ob ein Problem nur deshalb sehr langsam gelöst werden kann, weil dem Verfahrensentwickler keine effizientere Methode eingefallen ist, oder ob das Problem inhärent schwierig zu lösen ist. Die Beantwortung dieser Frage ist Gegenstand der Komplexitätstheorie. Für Entscheidungsprobleme vom Typ „ Investitionsprogrammplanung “ konnte übrigens gezeigt werden, dass sie schwierig im Sinne der Komplexitätstheorie sind (vgl. Martello, S./Toth, P.  1990). Aber auch dann, wenn optimale Lösungen berechenbar sind, kann es in Situationen rollierender Planung vorteilhaft sein, heuristische Verfahren zur Lösung der Teilprobleme einzusetzen. Das zugrunde liegende Phänomen ist, dass Heuristiken bei Planrevisionen eine geringere Nervosität des Planes aufweisen können und dass, ex post betrachtet, Heuristiken für das Gesamtproblem einen besseren Zielfunktionswert ergeben können als optimale Verfahren (vgl. Kimms, A.  1998). IV. Klassifikation heuristischer Verfahren Es werden in der Literatur verschiedene Kriterien herangezogen, um Heuristiken zu klassifizieren. Drei Aspekte sollen hier genannt werden. - Heuristiken für einen bestimmten Problemtyp (z.B. für Probleme vom Typ „ Investitionsprogrammplanung “ ) versuchen, für Beispiele dieses Typs zulässige Lösungen zu finden. Der Zielfunktionswert einer zulässigen Lösung definiert dann (bei einem Maximierungsproblem) eine untere Schranke für den optimalen Zielfunktionswert eines Beispiels. Grundsätzlich können an eine Heuristik zwei Fragen gestellt werden: (1) Liefert die Heuristik für jedes beliebige Beispiel eine zulässige Lösung? (2) Wie weit liegt die ermittelte untere Schranke LB im schlechtesten Fall von dem optimalen Zielfunktionswert OPT ≥ LB entfernt? Kann Frage 1 bejaht werden und gelingt es als Antwort auf Frage 2 eine Zahl α zu finden, sodass bewiesen werden kann, dass OPT ≤ α · LB für jedes beliebige Beispiel gilt, dann spricht man von einer Heuristik mit Gütegarantie bzw. von einem Approximationsverfahren. - Man unterscheidet Heuristiken auch danach, ob sie als Eingabe lediglich das betrachtete Beispiel benötigen und dann versuchen, eine zulässige Lösung zu konstruieren, oder ob sie zusätzlich eine bereits bekannte zulässige Lösung als Eingabe benötigen, um dann zu versuchen, diese Lösung zu verbessern. Im ersten Fall spricht man von (heuristischen) Konstruktionsverfahren, während man im zweiten Fall von (heuristischen) Verbesserungsverfahren spricht. - Wird ein Entscheidungsproblem durch ein formales Entscheidungsmodell abgebildet, dann stellt sich die Frage, ob das formale Modell lediglich ein Denkmodell darstellt, welches das zu lösende Problem präzise und unmissverständlich abbildet, oder ob das formale Modell selbst wesentlicher Bestandteil des Lösungsverfahrens (z.B. einer Methode der mathematischen Programmierung) ist. Geht das formale Modell nicht in das Verfahren ein, dann spricht man von „ common sense “ -Heuristiken, also von heuristischen Verfahren, die durch bloßes Verständnis, aber nicht notwendigerweise durch formale Beschreibung des Problems entwickelt wurden. Im anderen Fall spricht man von modellgestützten Heuristiken. V. Heuristische Grundprinzipien 1. Prioritätsregel-basierte Verfahren Unter Prioritätsregel-basierten Verfahren versteht man Konstruktionsverfahren, die, bei eventuellen Wahlfreiheiten während der Konstruktion einer Lösung, Prioritätsregeln anwenden, um die Wahlfreiheiten auf eine einzige Alternative einzuschränken. Am Beispiel „ Investitionsprogrammplanung “ sei dies illustriert. Ein einfaches Konstruktionsverfahren zur Bestimmung einer zulässigen Lösung könnte, beginnend mit einem leeren Portfolio, solange Projekte in das Portfolio aufnehmen, bis das Kapitalbudget keine weiteren Projekte zulässt oder alle Projekte im Portfolio sind. Dieses einfache „ common sense “ -Konstruktionsprinzip ist allerdings nicht eindeutig und lässt Wahlfreiheiten. Daher könnte man für jedes Projekt einen Prioritätswert definieren, um dann dasjenige Projekt mit dem höchsten Prioritätswert als nächstes auszuwählen. Plausibel ist hier beispielsweise der Quotient aus Endwert und Kapitalbedarf eines Projekts. Mit dieser Regel würde die folgende Lösung erzeugt werden: Zunächst wird Projekt 5 gewählt (Prioritätswert 9/7), dann Projekt 1 (Prioritätswert 5/4). Projekt 3 (Prioritätswert 7/6) kann wegen des zu hohen Kapitalbedarfs nicht aufgenommen werden. Also wird Projekt 4 (Prioritätswert 4/4) ausgewählt. Weitere Projekte können dem Portfolio nicht hinzugefügt werden. Bislang sind wir davon ausgegangen, dass Auswahlentscheidungen auf Basis von Prioritätswerten deterministisch getroffen werden. Als Konsequenz daraus ergibt sich, dass für ein gegebenes Beispiel das betrachtete Prioritätsregel-basierte Verfahren ein eindeutiges, vorherbestimmtes Ergebnis liefert. Die Zielfunktionswerte der erhaltenen Lösungen können regelmäßig dadurch verbessert werden, dass man zu randomisierten Verfahren übergeht. Der Unterschied zu dem bisher Betrachteten liegt darin, dass nicht mehr die Alternative mit dem höchsten Prioritätswert ausgewählt wird, sondern eine Zufallsentscheidung unter den in Frage kommenden Alternativen getroffen wird. Die Wahrscheinlichkeit für die Auswahl einer Alternative bestimmt sich dann durch eine monotone Funktion in Abhängigkeit des Prioritätswertes so, dass sich die Summe aller Auswahlwahrscheinlichkeiten zu eins addiert. In dieser Variante der Prioritätsregel-basierten Verfahren liefern dann mehrere Durchläufe des Konstruktionsverfahrens (wahrscheinlich) unterschiedliche Lösungen. In diesem Kontext spricht man daher auch von „ multi-pass “ -Verfahren anstelle von „ single pass “ -Verfahren. 2. Naturanaloge Verfahren Einige der modernen heuristischen Grundprinzipien lehnen sich an Naturbeobachtungen an und versuchen, gewisse Effekte bzw. Verhaltensmuster nachzuahmen. Genetische Algorithmen (vgl. Goldberg, D.  1989) imitieren die Evolution von Lebewesen. Lösungen entsprechen Individuen und werden durch „ Gene “ repräsentiert. Im Beispiel „ Investitionsprogrammplanung “ könnte eine Lösung beispielsweise durch ein binäres 5-Tupel dargestellt werden. Der Vektor (1,1,0,0,1) steht dann für ein Portfolio, bestehend aus den Projekten 1, 2 und 5. Aus einer gegebenen Menge von Lösungen werden dann Paare von „ Eltern “ ausgewählt. Betrachten wir für unser Beispiel das Elternpaar (1,1,0,0,1) und (1,0,1,1,0). Dieses Paar erzeugt dann zwei Nachkommen durch ein so genanntes „ Crossover “ , einer Operation, die Teile der Gene des einen Elternteils mit Teilen der Gene des anderen Elternteils kombiniert. Ein so genannter „ 1-Punkt-Crossover “ könnte beispielsweise so definiert sein, dass beide Elternlösungen an gleicher Stelle „ zerschnitten “ und dann über Kreuz wieder zusammengefügt werden. Wählt man beispielsweise einen Schnitt zwischen dritter und vierter Stelle der Lösungsvektoren, dann ergeben sich in dem Beispiel die beiden „ Kinder “ (1,1,0,1,0) und (1,0,1,0,1). Man beachte, dass die betrachteten Lösungen nicht notwendigerweise zulässig sein müssen (z.B. (1,0,1,0,1)). Zusätzlich wird häufig eine Operation eingeführt, die die Kinder zufällig „ leicht “ mutiert, sodass anstelle von (1,0,1,0,1) beispielsweise (1,0,1,1,1) entstehen könnte. Diese Mutation soll für Diversifikation sorgen. Allgemein wird aus einer Menge von 2n Lösungen durch Crossover und Mutation eine Menge von 4n Lösungen erzeugt. Aus dieser Menge werden dann 2n Lösungen selektiert, die die nächste zu betrachtende Population bilden. Die Selektion erfolgt auf Basis von Prioritätswerten, so genannten Fitness-Werten für einzelne Lösungen. Häufig benutzt man den Zielfunktionswert einer Lösung als Fitness-Wert, wobei eventuelle Unzulässigkeiten durch Strafwerte in den Fitness-Wert so eingerechnet werden, dass unzulässige Lösungen tendenziell nicht für den Bestand in einer neuen Population selektiert werden. Simulated Annealing (vgl. Aarts, E./Korst, J.  1989) simuliert das exponentielle Abkühlverhalten erhitzter Materialien. Grundprinzip eines solchen Verfahrens ist, ausgehend von einer gegebenen (zulässigen) Lösung eine neue (zulässige) Lösung zu erzeugen. Dazu definiert man sich eine so genannte Nachbarschaft einer Lösung. Zur Investitionsprogrammplanung könnten Lösungen beispielsweise (wie schon bei den genetischen Algorithmen gezeigt) durch einen binären Vektor kodiert werden. Benachbarte Lösungen eines Vektors könnten dann dadurch definiert sein, dass sie sich an nur einer einzigen Stelle vom betrachteten Vektor unterscheiden. Für die Lösung (1,1,0,0,1) gäbe es dann die fünf Nachbarn (0,1,0,0,1), (1,0,0,0,1), (1,1,1,0,1), (1,1,0,1,1) und (1,1,0,0,0). Aus der Menge von Nachbarlösungen wählt man dann eine Lösung mithilfe einer Prioritätsregel aus, um dann den Vorgang, ausgehend von der neuen Lösung, zu wiederholen. Sollte in einem Durchlauf eine Lösung ausgewählt werden, die einen schlechteren Zielfunktionswert als die vorher betrachtete Lösung aufweist, dann wird diese mit einer gewissen Wahrscheinlichkeit akzeptiert, ansonsten wird der neue Durchlauf mit der vorherigen Lösung gestartet. Diese Akzeptanzwahrscheinlichkeit sinkt im Laufe des Verfahrens exponentiell mit der Anzahl der Durchläufe. Eine Variante, die schlechtere Lösungen nur dann akzeptiert, wenn die Verschlechterung einen im Laufe des Verfahrens absinkenden Schwellwert nicht überschreitet, bezeichnet man als Treshhold Accepting. Ein weiterer populärer Typ von Verfahren, der hier aus Platzgründen nicht erläutert werden kann, wird als Ameisen-System (vgl. Dorigo, M./Maniezzo, V./Colorni, A.  1996) bezeichnet und basiert auf Analogien zur Nahrungssuche von Ameisen. 3. Lokale Suchverfahren Verfahren, die versuchen, eine gegebene Lösung zu verbessern, indem die zu definierende Nachbarschaft einer Lösung nach besseren Lösungen abgesucht wird, bezeichnet man als lokale Suchverfahren. Simulated Annealing and Treshhold Accepting gehören zu dieser Klasse von Heuristiken. Tabu Search (vgl. Glover, F./Laguna, M.  1997) gehört ebenfalls in diese Klasse. Benachbarte Lösungen werden hierbei vollständig untersucht, und diejenige benachbarte zulässige Lösung mit dem besten Zielfunktionswert wird ausgewählt und zwar auch dann, wenn sich der Zielfunktionswert im Vergleich zur vorherigen Lösung verschlechtert. Einem Kreisen um ein lokales Optimum soll dadurch entgegengewirkt werden, dass bestimmte Nachbarn einer Lösung für eine gewisse Anzahl von Durchläufen nicht zugelassen werden. Betrachtet man für das Investitionsprogrammplanungsbeispiel die bereits eingeführte Repräsentation einer Lösung als Binärvektor und definiert eine Nachbarschaft wie bei der Illustration von Simulated Annealing, dann könnte eine so genannte Tabuliste folgendermaßen definiert sein: Ein Vektor kann an einer Position nur dann verändert werden, wenn er in den letzten zwei Iterationen nicht verändert wurde. Das Protokoll in Tab. 2 skizziert den Ablauf eines solchen Verfahrens, wenn man mit der Lösung (1,1,0,0,1) startet. Tab. 2: Protokoll des Tabu Search-Verfahrens a) Abbruch und Evaluation von Heuristiken Fast alle der vorgestellten heuristischen Grundprinzipien sind iterative Verfahren (Ausnahme: „ single pass “ -Konstruktionsverfahren). Im Gegensatz zu optimalen Verfahren besitzen diese Heuristiken kein Abbruchkriterium der Art, dass eine bestimmte Bedingung signalisiert, dass weitere Durchläufe des Verfahrens keine besseren Lösungen erzielen können. Es stellt sich daher das Problem, ein geeignetes Abbruchkriterium zu definieren. Häufig finden folgende Kriterien Verwendung: - Abbruch nach einer vorgegebenen Rechenzeit. - Abbruch nach einer vorgegebenen Anzahl von Durchläufen. - Abbruch, sofern sich die beste bekannte Lösung innerhalb einer vorgegebenen Anzahl von Iterationen nicht mehr verbessert hat. Nach Beendigung des Verfahrens definiert die im Laufe der Berechnung beste gefundene Lösung das Ergebnis der Berechnung. Zur Evaluation einer Heuristik (auch im Vergleich mit anderen Heuristiken) muss eine Rechenstudie durchgeführt werden, die z.B. folgende Aspekte untersucht: - Benötige Rechenzeit bis zum Abbruch des Verfahrens (auf einem bestimmten Computer). - Benötigter Speicherplatzbedarf zur Durchführung der Berechnung auf einem Computer. - Güte der berechneten Lösung, gemessen als Abweichung von einer bekannten zulässigen Lösung, die z.B. mit einer anderen Heuristik bestimmt wurde, oder als Abweichung von einer oberen Schranke für den maximalen Zielfunktionswert. - Anzahl der Beispiele in eine Testumgebung, für die eine zulässige Lösung gefunden werden konnte. Literatur: Aarts, Emile/Korst, Jan : Simulated Annealing and Boltzman Machines, Chichester et al. 1989 Dinkelbach, Werner : Ziele, Zielvariablen und Zielfunktionen, in: DBW, Jg. 38, 1978, S. 51 – 58 Dorigo, Marco/Maniezzo, Vittorio/Colorni, Alberto : The Ant System: Optimization by a Colony of Cooperating Agents, in: IEEE Transactions on Systems, Man, and Cybernetics – Part B, 1996, Bd. 26, S. 1 – 13 Gal, Thomas/Gehring, Hermann : Betriebswirtschaftliche Planungs- und Entscheidungstechniken, Berlin et al. 1981 Glover, Fred/Laguna, Manuel : Tabu Search, Boston et al. 1997 Goldberg, David : Genetic Algorithms in Search, Optimization, and Machine Learning, Reading et al. 1989 Kimms, Alf : Stability Measures for Rolling Schedules with Applications to Capacity Expansion Planning, Master Production Scheduling, and Lot Sizing, in: Omega – The International Journal of Management Science, 1998, Bd. 26, S. 355 – 366 Martello, Silvano/Toth, Paolo : Knapsack Problems: Algorithms and Computer Implementations, Chichester et al. 1990