Auf dem Gebiet der Optimierung gibt es sehr viele äußerst schwierige Aufgaben, für die eine mathematische Lösung auch ökonomisch wertvoll ist: die Organisation von Rundreisen kürzester Gesamtlänge, die Wahl günstigster Standorte, die Auslegung von Telephon-, Strom-, Wasserleitungs- oder Fernheizungsnetzen, die Anordnung elektronischer Schaltkreise auf einem integrierten Computer-Chip (das sogenannte Chip-Placement) oder das Erstellen von Stunden-, Bahn-, Bus- und Flugplänen. Auslastungen von Fuhr- und Maschinenparks (Bild 1) sind ebenso wichtig für Unternehmen wie minimaler Verschnitt bei Holz oder Blech. Hersteller von Tabak, Säften und ähnlichen Produkten stehen häufig vor der Aufgabe, aus einem Vorrat verschiedener Sorten die kostengünstigste Mischung zusammenzustellen, die alle Geschmackskriterien und Beschränkungen für den Schadstoffgehalt erfüllt.

Geldanleger möchten für ihr Kapital eine maximale Rendite bei möglichst geringem Risiko erzielen. Bei dieser Aufgabe mögen nicht nur die mathematischen Probleme schwierig sein; weil es darauf ankommt, geschickter zu agieren als die übrigen Marktteilnehmer, darf der Anlageberater die mathematische Aufgabe, geschweige denn die Lösung, eigentlich gar nicht kommunizieren: Idee und geldwerter Vorteil wären gleich dahin.

Da stehen nun auf der Anwenderseite die Planer vor teuersten Investitionen, die sie so gewinnbringend wie möglich einsetzen möchten, auf der anderen Seite die Wissenschaftler, die bei den meisten solcher Aufgaben achselzuckend bemerken: „Diese Problematik ist NP-vollständig“, was ungefähr soviel bedeutet wie „hoffnungslos schwierig“. Betriebe versuchen dennoch weiterzukommen, indem sie nicht direkt nach der allerbesten Möglichkeit suchen, sondern das Verbesserungspotential wenigstens annähernd ausschöpfen.

Leider ist traditionell das Verhältnis der Mathematiker zu den Praktikern nicht das beste. Praktiker versuchen, ihre Engpässe bei der Planung aufgrund von Erfahrung und Intuition und durch Ändern hinderlicher technischer Umstände zu beseitigen. Mathematiker sind oft geneigt, überhaupt nur über glatt und ästhetisch formulierte Modelle nachzudenken; sie winden sich bei häßlichen Praxisfällen und enttäuschen Anwender, die Hilfe erwarten. Mathematiker verstehen zu wenig, daß sie selbst für Konzepte, Daten und Präzisierungen zuständig sind, die eine komplizierte Situation erst mathematisch handhabbar machen – wer soll es denn sonst tun? Praktiker haben deshalb von ihnen eine Meinung, die sie meist nicht einmal auf den Gedanken kommen läßt, bei ihnen Rat zu suchen.

Im Wissenschaftlichen Zentrum der IBM in Heidelberg versuchen wir, eine Brücke zu schlagen. Wir haben uns vorgenommen, Aufgaben wie die skizzierten nicht theoretisch zu studieren, zu analysieren und zu klassifizieren, sondern sie so zu lösen, wie sie sind. Das hört sich blauäugig und draufgängerisch an, läuft aber schlicht auf viel Arbeit im Detail, lange Diskussionen und quälend mühseliges Bestimmen der Rahmendaten hinaus. Wenn der Rechner erst einmal Daten und Problem eingelesen hat, ist schon sehr viel getan. Das eigentliche Anwenden mathematischer Technologie, der Algorithmenentwurf, die Implementation und schließlich die Lösung – das dauert gar nicht so lange.

Wir berichten von dieser Arbeit und dabei von ganz elementaren und dennoch erstaunlich leistungsfähigen und vielseitigen Optimierungsverfahren. Zunächst aber wollen wir etliche Arten von Problemen etwas detaillierter vorstellen.

Das Problem des Handlungsreisenden

Die kombinatorische Optimierung beschäftigt sich mit der typischen Frage: Welche aus einer Menge von (sehr vielen) Kombinationen ist die beste, kürzeste, billigste, kleinste oder effizienteste? Die bekannteste dieser Aufgaben ist das Problem des Handlungsreisenden (TSP nach englisch Traveling Salesman Problem): Ein Vertreter soll eine Reihe von Kunden nacheinander in beliebiger Reihenfolge aufsuchen, wobei er daran interessiert ist, die kürzestmögliche Strecke abzufahren. Wie viele Möglichkeiten hat der Vertreter, seine n Kunden nacheinander aufzusuchen? Für die Wahl des ersten hat er n Möglichkeiten. Seinen zweiten Kunden kann er unter den n–1 verbleibenden Kandidaten auswählen. Schließlich hat er nur noch den letzten aufzusuchen (eine Möglichkeit), und danach kehrt er nach Hause zurück. Die Anzahl der möglichen Reihenfolgen ist demnach nX(n–1)X(n–2)X...x3X2X1. Die Mathematiker schreiben dafür n!, gesprochen „n-Fakultät“ (Fakultät heißt auch Möglichkeit). Es ist 1!=1, 2!=2, 5!=120, 10!=3628800. Mit wachsendem n steigt n! extrem schnell an. Auch bessere Taschenrechner weigern sich bereits, 70! auszurechnen, da sie Zahlen über nicht mehr anzeigen können. Ein in der Fachwelt bekanntes Rundreiseproblem hat der Augsburger Mathematiker Martin Grötschel – inzwischen Vize-Präsident des Konrad-Zuse-Zentrums für Informationstechnologie in Berlin – 1984 publiziert: Ein Automat soll an 442 Stellen Löcher in eine Lei-terplatte bohren, und zwar so, daß der Gesamtweg des Bohrkopfs von Loch zu Loch möglichst kurz ist. Nun hat die Zahl 442! über 1000 Dezimalstellen. Es ist darum völlig aussichtslos, sämtliche oder auch nur sehr viele Rundtouren einfach auszuprobieren. Jedoch fand Olaf Holland 1987 in seiner Dissertation an der Universität Bonn durch eine Kombination analytischer und numerischer Methoden das globale Optimum, also die exakt kürzeste Rundtour (Bild 2). Im gleichen Jahre gelang es Manfred Padberg vom Courant-Institut der Universität New York und Giovanni Rinaldi vom Institut für Systemanalysen in Rom, ein weiteres berühmtes TSP zu lösen: eine Rundreise durch die 532 größten Städte der USA. TSPs gehören ebenso wie die im folgenden geschilderten Aufgaben zur Klasse der NP-vollständigen Probleme. Innerhalb der größeren Klasse NP (non-deterministic polynomial), die ungefähr aus unseren Alltagsproblemen besteht, bezeichnet man als NP-vollständig eine Unterklasse besonders schwierig zu lösender Probleme. Wenn man aber ein effizientes Programm für eines von ihnen gefunden hat, kann man daraus ein ebenso gutes Programm für jedes andere Problem in NP ableiten. Man könnte damit also eine große Menge von Problemen auf einen Schlag lösen. Nur sind die meisten Informatiker nach vielen Jahren Arbeit überzeugt davon, daß es ein solches Programm, genauer: ein Programm, welches globale Optima für NP-vollständige Probleme in angemessener Zeit liefert, nicht geben kann. Sie fürchten vielmehr, daß der Aufwand zum Finden des globalen Optimums bestenfalls durch einen Ausdruck zu beschreiben ist, bei dem die Anzahl der Städte im Exponenten steht, also etwa für das 442-Stationen-Problem. Das wäre eine astronomisch lange Zeit. So kommt man zu der eingangs erwähnten Gleichsetzung von „NP-vollständig“ mit „hoffnungslos schwierig“. Im konkreten Einzelfall jedoch hat ein TSP oft eine bestimmte Struktur. Leiterplatten etwa tragen deutliche Linienmuster in der Waagerechten oder der Senkrechten. Wenn man das in irgendeiner Weise in das Programm einfließen läßt, kann man im Einzelfall doch zum Ziel kommen. Die besten heutigen Methoden lösen einzelne TSPs mit ungefähr 3000 Stationen, wenn das Muster halbwegs gut strukturiert ist. Wie also hilft sich der Praktiker, der – wie etwa im IBM-Werk Sindelfingen – Platten für Computerbauteile mit 10000 Löchern zu bohren hat? Er sucht eben nicht nach der exakten Lösung, also der allerkürzesten Verbindung, sondern gibt sich mit einer fast optimalen zufrieden. (Ein Praktiker nennt alles eine „Lösung“, was die Nebenbedingungen einhält und praktikabel ist. Beim TSP ist für ihn, da es keine Nebenbedingungen gibt, jede Rundtour eine Lösung, und er spricht je nach Tourlänge von guten oder schlechten Lösungen. Mit exakter Lösung meinen wir hier die des mathematischen Problems TSP: eine Rundtour kürzestmöglicher Länge.)

Rucksackprobleme

Bei den in der Praxis häufigen Rucksackproblemen (knapsack problems) gilt es, möglichst viele Gegenstände aus einer gegebenen Menge in einen Rucksack, eine Kiste oder auch den Laderaum eines Lastwagens zu packen. (Das füllbare Volumen kann auch die verfügbare Finanzmasse eines Geldanlegers sein; die Gegenstände wären dann verschiedene Wertpapiere, deren Gesamtpreis die Finanzkraft des Anlegers nicht übersteigen darf.) Außer der Volumenbeschränkung ist möglicherweise auch noch eine Höchstgewichtsschranke zu beachten. Diese Aufgabe ist oft mit einem TSP vermischt: Es sollen auf jeden Lastwagen Kisten geladen werden, deren Ablieferungspunkte nahe zusammenliegen, so daß es durch diese Punkte eine kurze TSP-Tour gibt. Sind noch Bedingungen für die maximale Fahrzeit und Ablieferungstermine einzuhalten (ein Kunde ist bis 10.00 Uhr mit Ware zu beliefern, die man erst um 8.15 aus dem Lager holen kann), so haben wir eine massive mathematische Problematik vor uns.

Ähnliche Aufgaben stellen sich bei der Verschnittoptimierung, die vom weihnachtlichen Plätzchenbacken geläufig ist: Mond-, Stern- und Tannenbaumplätzchen sind so auszustechen, daß der ausgerollte Teig möglichst gut ausgenutzt wird. Wer diese Probleme für einfach hält, braucht nur ein wenig Tangram zu spielen: Dabei sind einige Dreiecke, Vierecke und andere Figuren zu einer vorgeschriebenen großen Figur, etwa einem Quadrat, zusammenzulegen. Das ist schon bei 10 Teilen alles andere als leicht. Beim Plätzchenbacken kann man das Problem durch Neuausrollen des Verschnitteiges entschärfen. Beim Aussägen von Spanplattenteilen, Stanzen von Blechen, Zuschneiden von Leder oder Textilien aber ist der Abfall nicht zu retten. Verbesserte mathematische Lösungen schlagen hier unmittelbar als Materialeinsparungen zu Buche.

Stundenpläne

Eine weitere große Klasse von Optimierungsaufgaben behandelt Pläne für Zeitabläufe. Am bekanntesten ist das Erstellen eines Stundenplans für die Schule. Es ist schon sehr schwer, überhaupt eine Lösung zu finden, die zulässig ist. Lehrdeputate, Oberstufenkursblöcke und Fachräume müssen beachtet werden. Wenn der Planer lange gearbeitet hat und fast fertig ist, entdeckt er typischerweise, daß Klasse 6b eine Stunde zu wenig Sport hat. Zu den noch verfügbaren Zeiten ist jedoch die Turnhalle belegt. Läßt sich nach einigem Hin und Her doch ein Termin finden, gibt der Sportlehrer in dieser Stunde gerade Englisch in der 11a. Dieses Problem ist so schwierig, daß in aller Regel der zum Unterrichtsbeginn erreichte Stand der Überlegungen wohl oder übel als Stundenplan für ein ganzes Halbjahr herhalten muß.

Ein Plan, so man ihn denn hat, ist gemeinhin sehr sensibel gegen Änderungen. Fällt zum Beispiel eine Lehrerin wegen Mutterschaftsurlaubs aus, muß meist ein großer Teil des Plans umgestoßen werden.

In der industriellen Praxis kommen solche Fragen sehr oft vor. Produktionsabläufe, Fließbandfertigungen, Walzstraßenauslastungen und Prozeßsteuerungen wollen optimiert sein (vergleiche dazu den Beitrag von Hans-Peter Lipp auf Seite 101). Hier hat der Mathematiker ein Betätigungsfeld, auf dem eine reiche Ernte in Form von Einsparungen eingebracht werden kann.

Die Suche nach guten Lösungen: Heuristiken

Wir haben klarzumachen versucht, warum Optimierungsprobleme der Praxis der Suche nach einer exakten Lösung widerstehen. Anwender können aber nicht so lange warten, bis die mathematische Forschung eines Tages doch exakte Lösungen findet. (Bis dahin gibt es ohnehin neue, größere Probleme, die den Theoretiker abermals überfordern.) In der Zwischenzeit behelfen sie sich mit Heuristiken: Daumenregeln, die wenigstens grob in die Nähe der optimalen Lösungsqualität führen sollen.

Viele Anwenderprogramme für Personal Computer lösen heute ihre TSPs mit der Regel des nächsten Nachbarn: „Fahre stets zu der nächstgelegenen Stadt, die du noch nicht besucht hast.“ Dieses Rezept sieht vernünftig aus und ist auch gar nicht schlecht; es erbringt erfahrungsgemäß Touren, die 5 bis 10 Prozent länger als die optimalen sind. Bei den meisten anderen Problemen ist es allerdings viel mühsamer, annehmbare Lösungen zu erzielen.

Wie können bessere Heuristiken aussehen? Martin Grötschel gab bei der Publikation des 442-Stationen-Problems eine Lösung an, die nur um 1,5 Prozent schlechter ist als die Optimallösung, die Olaf Holland später gefunden hat. Noch näher an das Optimum zu gelangen ist schon sehr schwer. Die Methode des simulated annealing („simuliertes Ausglühen“), die bei ihrer Einführung durch Scott Kirkpatrick, C. D. Gelatt und M. P. Vecchi vom IBM-Forschungszentrum in Yorktown Heights (US-Bundesstaat New York) 1983 einen entscheidenden Durchbruch darstellte, erzielt gerade Ergebnisse, die bis auf 1,25 Prozent an das Optimum heranreichen. Wir haben hingegen ganz einfache heuristische Regeln entdeckt, die in kurzer Zeit Lösungen liefern, die lediglich 0,3 bis 0,4 Prozent vom Optimum entfernt sind. Diese Regeln, den Sintflut-Algorithmus und die Methode des Threshold Accepting (TA), stellen wir hier vor.

Wanderungen im Lösungsraum

Mathematische Optimierungsprobleme werden so formuliert: Gegeben ist eine Menge X von Zuständen („Lösungen“ im Praktikerjargon; ein Zustand kann also eine Tour oder ein Stundenplan sein). Da die Zustände untereinander eine Art geometrische Beziehung haben – man kann zwei sehr ähnliche als eng benachbart, zwei sehr unterschiedliche als weit entfernt auffassen –, nennt man X auch einen Raum von Zuständen. Auf diesem Raum ist eine reellwertige Zielfunktion f definiert. Das heißt: Für jeden Zustand x aus dem Raum X kann man eine reelle Zahl f(x) berechnen, die ein Maß für die Qualität von x darstellen soll; zum Beispiel kann f(x) die Länge der Tour x sein oder die Anzahl der Teile im Rucksack bei der Packung x. Optimieren bedeutet: Suche einen Zustand x im Raum X, für den f(x) minimal (etwa beim TSP) oder maximal wird (beim Rucksackproblem). Da das Minimieren von f dasselbe bedeutet wie das Maximieren von –f, ist nur eine Theorie für die Maximierung erforderlich (vergleiche „Optimieren mit Evolutionsstrategien“ von Paul Ablay, Spektrum der Wissenschaft, Juli 1987, Seite 104).

In der Schule haben wir ein Rezept für die Maximierung von Funktionen gelernt: Bilde die Ableitung f' der Funktion f und suche die Nullstellen von f'. Nur dort können Maxima sein. Leider funktioniert das Verfahren beim TSP oder bei Stundenplänen nicht. Der Raum der Rundtouren beim TSP enthält zwar sehr viele, aber doch nur endlich viele Elemente; deswegen kann man von Stetigkeit, Grenzwerten und insbesondere Ableitungen gar nicht reden. Es bleibt nur ein schwacher Abglanz von Stetigkeit: Nimmt man an der Lösung eine sehr kleine Änderung vor, wird sich die Zielfunktion auch nur wenig ändern. (Wenn noch nicht einmal das gälte, wäre blindes Durchprobieren so gut wie jedes andere Verfahren.)

Aber selbst wenn man Ableitungen bilden könnte: Beim TSP gibt es unseren Erfahrungen zufolge Millionen, ja Milliarden von lokalen Maxima und Minima. Nur solche findet man mit dem Schulrezept. Welches aber von Milliarden lokaler Minima repräsentiert die kürzeste Tour? Wieder stehen wir so vor einer großen Menge von Lösungen und können beliebig lange suchen.

Sinnvoller – und allgemein üblich – ist es, ein iteratives Verfahren mit lokaler Veränderungssuche zu verwenden. Wir beschreiben hier zunächst einen ganz einfachen Vertreter dieser Klasse. Die Suche nach einer guten Lösung startet mit irgendeiner, zum Beispiel einer spontan hingezeichneten Rundtour. Der Optimierer verändert diese an einer Stelle ein wenig (Bild 3) und schaut nach, ob die neuerstellte Lösung besser (kürzer) ist. Wenn ja, ersetzt der Optimierer die alte Tour durch die neue und prüft wiederum: Kann er daran herumändern, so daß eine noch bessere Lösung entsteht? Wenn ihm das gelingt, arbeitet er mit dieser Lösung weiter. Und so geht es immer fort, bis dem Optimierer nichts mehr einfällt. Die gefundene Lösung ist dann nicht mehr dadurch verbesserbar, daß sie lokal verändert wird. Der Mathematiker spricht von einem lokalen Optimum (beim TSP von einem lokalen Minimum).

Es ist nicht jedermanns Sache, sich im abstrakten Raum der Touren zurechtzufinden. Leichter ist der Weg eines Bergsteigers zu beschreiben. Stellen Sie sich also vor, Sie stünden irgendwo auf der Erde und suchten nach dem höchsten Gipfel. Ihr Standort x ist ein Zustand, die Menge X der Zustände ist die Menge der Punkte auf der Erde, und f(x) ist die Höhe von x über dem Meeresspiegel. (Wenn, wie beim TSP, das Minimum von f gesucht ist, muß man –f statt f mit der Höhe identifizieren.) Allerdings sind Sie blind: Sie können die Landschaft um sich herum nicht überschauen, sondern nur Ihre nächste Umgebung abtasten. Eine lokale Veränderung Ihres Standortes vollziehen Sie durch einen Schritt in irgendeine Richtung. Die mathematische Anweisung: „Verändern Sie lokal die Lösung zu einer immer besseren Lösung!“ heißt in diesem Kontext: „Wandern Sie auf der Erde herum, aber immer nur bergauf!“

Wir wollen diesen Algorithmus HINAUF nennen. Es ist freilich ein gieriger und daher letzten Endes schlechter Algorithmus. Wer nach dieser Vorgabe handelt, ist nicht bereit, einmal Erreichtes wieder preiszugeben, auch wenn er in ferner Zukunft einen viel größeren Gewinn ernten könnte. Wenn wir – um im Bild zu bleiben – mit diesem Algorithmus in Heidelberg am Neckarufer beginnen würden, kämen wir vielleicht bis auf den Gipfel des Königstuhls – aber der Mount Everest wäre noch weit.

Obgleich sofort klar wird, daß HINAUF schlecht ist, benutzen wir alle diesen Algorithmus immer wieder. Bei den Plätzchen aus dem Kuchenteig probieren wir nacheinander für jedes einzelne, wie die Form den verbleibenden Teig am besten ausnutzt, und stechen dann unwiderruflich aus. Auch wenn wir später eine bessere Gesamtkonzeption für die Anordnung der Plätzchen entdecken – die Entscheidung ist nicht mehr zu revidieren.

Mathematisch bedeutet dies, daß wir in jedem Moment nur Verbesserungen suchen und nicht mehr bergab zurückgehen, um schließlich eine richtig gute Lösung zu erhalten. Wer heute in der betrieblichen Praxis solche Regeln benutzt, hat mit einiger Sicherheit ein erhebliches Einsparpotential.

Threshold Accepting

Modifizieren wir die Gipfelstürmerei ein wenig. Wir wählen eine nichtnegative Zahl T, genannt Toleranzschwelle (threshold), und stellen die neue Bergsteigerregel auf: „Wandere ziellos auf der Erde herum; es sind nur solche Schritte verboten, die um mehr als T Zentimeter nach unten führen.“

Ist T groß, so darf der Alpinist nahezu unbehindert von dieser Regel wandern. Wir wählen den Wert von T am Anfang sogar mit Bedacht so groß, daß er sich fast nicht bemerkbar macht. Im Laufe des Verfahrens aber senken wir T langsam auf null ab. Der Gipfelstürmer verfängt sich bei großem T im Himalaja und begibt sich dann durch Verkleinerung von T immer zügiger auf den Pfad nach ganz oben (siehe Kasten auf dieser Seite). Im Hochgebirge, bei kleinen T-Werten, greift die Regel öfter; dort ist oft ein Schritt verboten. Das Einhalten des Steilheitsverbotes zwingt den Bergsteiger langsam in immer höhere Regionen (Bild 5). Wird schließlich T=0, ist der Algorithmus identisch mit HINAUF. Das ist die Grundidee des Threshold-Accepting-Algorithmus (TA).

Sehen wir uns einen Berg an, auf dessen Gipfel man nur über Steilhänge gelangt, etwa den Zuckerhut von Rio de Janeiro. Ist der TA-Alpinist dort hinaufgeraten, kommt er wegen des Steilheitsverbots nie wieder herunter. Die Suche steckt fest.

Die Methode des Simulated Annealing umgeht diese Problematik durch eine elegante Akzeptanzregel: Ist die potentielle neue Lösung schlechter als die alte, entscheidet man durch ein Zufallsexperiment, ob man sie trotzdem akzeptiert oder nicht. Die Wahrscheinlichkeit, zu akzeptieren, läßt man stark vom Verschlechterungsgrad abhängen. Geringe Verschlechterungen werden einigermaßen oft akzeptiert, starke sehr selten. Mit Simulated Annealing findet man von Zuckerhüten im Prinzip wieder herunter. Irgendwann akzeptiert der Algorithmus auch einmal drastische Verschlechterungen (nach langer Zeit eventuell, aber immerhin). Simulated Annealing fängt sich allerdings leichter in lokalen Optima als TA und braucht lange für das Herauskommen.

Der Name des Verfahrens stammt aus der Metallurgie. Beim sogenannten Ausglühen wird das Material lange erhitzt und dann langsam abgekühlt. Mit zunehmender Abkühlung sinkt die Bewegungsfreiheit der Atome im Kristallgitter; das ist analog der allmählich abnehmenden Freiheit des gedachten Bergsteigers, Verschlechterungsschritte zu machen (vergleiche „Optimieren durch simuliertes Ausglühen“ von Wolfgang Kinzel, Spektrum der Wissenschaft, April 1988, Seite 19).

Bei der Konstruktion solcher Verfahren haben die Forscher stets besonders darauf geachtet, daß die Algorithmen sich immer wieder von Zuckerhüten wegbewegen können. Das kann TA nun gerade nicht. Endet man damit jedesmal auf einem Zuckerhut, vielleicht sogar auf einem ganz kleinen, aber steilen Maulwurfshügel im Flachland?

Wir haben TA an Problemen verschiedenster Art und Größe getestet. Bei kleinen kommen Zuckerhut-Phänomene durchaus vor. Die Überraschung aber war: Bei größeren Problemen wie etwa dem 442-Stationen-TSP treten sie so gut wie niemals auf. Für dessen Lösung braucht TA nur eine Sekunde Rechenzeit auf einer Workstation.

Wir haben große Serien laufen lassen mit vielen tausend Versuchen und immer neuen Startpunkten. Es stellte sich heraus, daß TA in mehr als der Hälfte aller Durchläufe ein besseres Ergebnis erzielte als die beste bekannte Lösung mit Simulated Annealing. Y. Rossier, M. Troyon und Th. M. Liebling von der Ecole Polytechnique Fédérale in Lausanne erzielten 1986 mit Simulated Annealing einen Wert von 51,42 inch für das 442-Stationen-Problem. Diese Lösung war Weltrekord bis zur Berechnung der exakten Lösung durch Olaf Holland mit einem Wert von 50,69. Aber TA unterbietet die Lösung Rossiers und seiner Kollegen bereits im Durchschnitt. Die beste unter 100 TA-Lösungen liegt im allgemeinen in der Qualität nur noch 3 bis 4 Promille vom Hollandschen Optimum entfernt, die schlechteste von vielen tausend verfehlt es nur um 5 Prozent. (In der Praxis braucht man also nur einige wenige Versuche mit TA zu machen und die beste der berechneten Lösungen zu nehmen.)

Gibt es demnach in großen Lösungsräumen vielleicht gar keine Zuckerhüte? Doch. Wenn man von Hand ein TSP optimiert, das heißt eine Lösung konstruiert, die für den unbefangenen Betrachter optimal aussieht, dann ist das häufig ein Zuckerhut: Jede kleine Veränderung ist eine erhebliche Verschlechterung, aber der höchste Gipfel liegt woanders. Gibt man dem TA-Algorithmus eine solche Lösung als Ausgangspunkt, kann er daran nichts mehr verbessern. Aber von alleine, mit irgendwelchen Anfangsdaten, findet er so etwas so gut wie nie.

Man kann mit TA und anderen Algorithmen zu noch besseren Lösungen gelangen, indem man einfach ein reichhaltigeres Sortiment an Veränderungsschritten einführt, um von Lösung zu Lösung zu springen. Wir haben tatsächlich eine komplexe Version von TA, die beim 442-Stationen-Problem eben zwei Sekunden statt einer läuft, fast immer den Wert 51,20 unterbietet und manchmal sogar die Hollandsche Optimallösung findet, wenn wir 30 Minuten Rechenzeit zulassen. Alle solche Hybrid-Algorithmen sind aber eher Kraftmeierei als eine praktische Hilfe bei industriellen Anwendungen: Man braucht viel Arbeits- und Testzeit beim Entwurf, und der Zusatznutzen ist gering. Wenn wir 30 Minuten Rechenzeit zur Verfügung haben, können wir ebensogut die triviale Form von TA, deren Fortran-Text auf eine DIN-A4-Seite paßt, 1800mal laufen lassen; das beste der dabei erzielten Ergebnisse ist schwer zu schlagen, denn es liegt nur etwa 1 bis 2 Promille vom Optimum entfernt.

Der Sintflut-Algorithmus

Es gibt noch ein sehr einfaches, überraschend erfolgreiches Optimierungsprinzip. Denken wir uns wieder einen Bergsteiger, der einen möglichst hohen Gipfel auf der Erde sucht. Diesmal lassen wir ihn allein auf der Erde zurück und erzeugen eine Sintflut. Der wasserscheue Alpinist wandert ziellos im Regen auf der Erde umher; nur darf er mangels Arche nicht ins Wasser. Er bleibt stehen, wenn er allseits von den Fluten eingeschlossen ist. Steht er in diesem letzten Augenblick auf einem unbedeutenden Nebenmaximum (sagen wir: dem Ararat) oder auf dem Mount Everest?

Auf unsere Optimierungsprobleme übersetzt: Wie oben programmieren wir Übergangsschritte von Lösung zu Lösung. Nur die Akzeptanzregel ändern wir gegenüber dem Threshold Accepting.

Zu Beginn wird eine Zielfunktionsschranke WASSERSTAND definiert. Der Sintflut-Algorithmus akzeptiert jede (beliebig schlechte) Lösung x, wenn ihr Zielfunktionswert f(x) nur höher liegt als die Zahl WASSERSTAND. Es regnet ohne Unterlaß: Jedesmal, wenn der Sintflut-Algorithmus eine neue Lösung akzeptiert hat, wird im Programm die Zahl WASSERSTAND ein wenig erhöht. Das Programm endet, wenn es keine Veränderung mehr findet, die es beim aktuellen Wert von WASSERSTAND akzeptieren könnte.

Wir haben, offen gestanden, nicht ernsthaft geglaubt, daß dieser Algorithmus funktionieren würde. Was passiert, wenn wir in England starten oder auf Helgoland? Wenn die Sintflut steigt, zerfallen auch die Kontinente zu Inseln. Von wasserumschlossenem Land kann der Sintflut-Algorithmus nie mehr herunter, ist also womöglich von jeder guten Lösung abgeschnitten.

Doch seltsam: Wir haben den Sintflut-Algorithmus für die Produktionsoptimierung, für große Chip-Placements, für schwierigste industrielle Mischungsprobleme eingesetzt; wir haben damit auch Tausende von TSPs durchgerechnet. Wieder war nur ein winziges Programm erforderlich. Das Ergebnis war jedesmal exzellent: Der Sintflut-Algorithmus ist fast genauso gut wie TA, nicht ganz so stabil in der Qualität der Lösungen, dafür jedoch etwas schneller.

Ein Versuch, den Erfolg zu verstehen

Warum liefern so einfache Regeln so gute Ergebnisse, wenn diese Algorithmen die Gefahr, in lokalen Optima gefangen zu werden, schlichtweg ignorieren? Da haben wir Vermutungen.

Sehen wir uns das Problem des Handlungsreisenden an. Gesucht sind kurze Touren. Eine elementare Veränderung, ein sogenannter LIN-2-OPT-Schritt, entsteht durch Herausnehmen zweier Strecken aus der Tour und Einfügen zweier neuer. Für die Wahl der ersten herauszunehmenden Strecke haben wir im 442-Stationen-Problem 442 Möglichkeiten, für die zweite noch 441. Da es nicht darauf ankommt, welche der beiden Strecken wir zuerst herausnehmen, gibt es 442¥441/2=97461 Möglichkeiten, aus einer Rundtour durch einen LIN-2-OPT-Schritt eine andere zu generieren. Eine Rundtour ist ein lokales Minimum, wenn keine dieser 97461 Änderungen eine kürzere Rundtour liefert.

Daran sehen wir, daß bei größeren TSPs ein lokales Minimum etwas ziemlich Seltenes sein muß. Der Gipfelsucher rennt bei ansteigender Sintflut gleichsam in Panik hin und her im Lösungsraum und beachtet nur den WASSERSTAND. Kann er dabei so viel Pech haben, eine so seltene Konfiguration zu erreichen? Gegen Ende, wenn das Wasser hoch steht, wird er sicherlich mehr und mehr in solche Lösungen gezwungen – aber eben erst ganz am Ende.

Die Inselbildung im Lösungsraum scheint nach unseren experimentellen Erfahrungen erst dann einzusetzen, wenn der Algorithmus schon im Bereich sehr guter Lösungen ist. Außerdem haben wir beobachtet, daß es in allen von uns programmierten Problemstellungen sehr viele sehr gute Lösungen gibt, die sehr unterschiedlich aussehen. Es ist – ganz gegen die erste Intuition – nicht so, daß bessere und bessere Lösungen der exakt besten Lösung langsam immer ähnlicher würden.

Vielleicht haben die großen Probleme auch Lösungslandschaften, die wie die Wellenoberfläche eines Ozeans aussehen, wenn der schlagartig einfrieren würde. Die Aufgabe hieße dann: Suche den höchsten Wellenkamm.

Diese Aufgabe exakt zu lösen sieht sehr schwer aus bei so vielen Wellen. Aber wenn wir nur eine Welle finden wollen, die fast so hoch ist wie die höchste: Das mag viel einfacher sein. Und das leistet bereits ein Verfahren wie der Sintflut-Algorithmus.

Wir haben den Eindruck, daß die Optimierungsprobleme der Praxis typischerweise zu so regelmäßigen Strukturen tendieren. Sie sind – so unsere These – gutartig genug, daß wir sie mit TA oder dem Sintflut-Algorithmus behandeln können. In der Regel sind sie ja historisch enstanden. Die Geographie der Städte eines Landes und die Verteilung von Löchern in Leiterplatten sind nicht als bösartige Prüfexempel für Algorithmen konzipiert, und Fließbänder werden von Fachleuten gebaut, die schon eine sehr gute Vorstellung von der Arbeitsweise und vom Materialfluß haben. In den zugehörigen Lösungsräumen sollte es mithin nicht allzu wild hergehen.

Würfeln ist nicht immer optimal

Das gute Abschneiden des TA- und des Sintflut-Algorithmus gegenüber Simulated Annealing wirft eine grundsätzliche Frage auf. Simulated Annealing verwendet an entscheidender Stelle den Zufall, nämlich bei der Entscheidung, ob ein Verschlechterungsschritt akzeptiert werden soll. Es ist – auch in anderen Algorithmen – üblich, die Veränderungsschritte selbst ebenfalls nach dem Zufall auszuwählen, weil man befürchtet, daß bei systematischem Durchprobieren aller Möglichkeiten ein repräsentatives Sortiment erst sehr langsam zustande kommen könnte.

Unsere Ergebnisse widersprechen dem. In die Entscheidungsregeln von TA- und Sintflut-Algorithmus geht nirgendwo der Zufall ein. Wenn wir die Veränderungsschritte systematisch statt zufällig auswählen lassen, werden diese Algorithmen sogar eher besser statt schlechter. Vielleicht hat man in der Vergangenheit im wesentlichen schlechte deterministische mit guten stochastischen Algorithmen verglichen und so ein schiefes Bild gewonnen.

Implementation für große Praxisprobleme

Hier sind nun ganz einfache Algorithmen, die überraschend gute Ergebnisse für TSPs und für Rucksackprobleme liefern. Haben wir damit für alles zu Optimierende eine annehmbare Lösung gefunden? Leider nein. Die gutartigen Lösungsraumstrukturen ergeben sich in der Praxis zwar schon – aber nur dann, wenn man sie bei der Implementierung geschickt herausarbeitet. Wenn man – etwa bei Stundenplänen oder Chip-Placements – die möglichen Änderungsschritte ungeschickt auswählt, passiert etwas ganz Typisches: Es gibt einfach zu wenige zulässige Änderungschritte. Man versuche beispielsweise den Unterrichtsplan einer ganzen Schule zu verändern, indem man einfach zwei Lehrer vertauscht. Das ist nur möglich, wenn sie beide die Fächer, auf die sich der Austausch bezieht, unterrichten dürfen. Schulräume müssen zur Unterrichtsart passen: Im Physikraum kann kein Sport getrieben werden. Der Planer muß Blöcke für Leistungskurseinheiten beachten, die Lehrdeputate der einzelnen Lehrer einhalten und weiteres mehr.

Die Bedingungen, die eine Lösung erfüllen muß, sind im mathematischen Lösungsraum wie Sperrgebiete. Der Sintflut-Algorithmus wandert also nicht nur mit der Einschränkung durch den Wasserstand umher, sondern stößt überall an Mauern mit Aufklebern wie: Studienrätin K. darf nicht Sport unterrichten. Naive Implementationen ergeben so viele Mauern, daß der Sintflut-Algorithmus in Labyrinthe gerät. Dann ist es wenig hilfreich, daß auch noch überall das Wasser steigt.

Wir sind über solche Schwierigkeiten hinweggekommen, indem wir derartige Sperrgebiete nur indirekt wiedergegeben haben. Der Alpinist darf in unseren Programmen im Prinzip überall hin. Wenn er aber auf einem vom Problem her verbotenen Punkt x steht, bekommt er beim Zielfunktionswert f(x) einen Abzug nach der Maßgabe, wie stark verboten dieser Punkt x ist. Wiederum bildlich gesprochen heißt dies: Das verbotene Gelände wird künstlich abgesenkt und gerät daher im Verlauf der Sintflut auch eher unter Wasser. Wir tun so, als wäre ein Zustand, der gegen eine Vorschrift verstößt, nicht unmöglich, sondern nur teuer (man denke an Vertragsstrafen bei Terminüberziehungen). Das will geschickt programmiert sein: Es kommt darauf an, in welcher Reihenfolge und mit welcher Geschwindigkeit man einerseits das verbotene Gelände absenkt, andererseits den Wasserstand ansteigen läßt. Wenn das gelingt, läuft der Gipfelstürmer mit solchen Strafregeln munter durch alle verbotenen Zonen; bei ansteigender Wasserlinie wird er mit der Zeit aber in erlaubte Zonen gezwungen.

Einerseits ist der Sintflut-Algorithmus also sehr einfach zu implementieren, im Prinzip jedenfalls. Andererseits braucht es für komplexe Strukturen mit vielen Nebenbedingungen Kunstfertigkeit, Erfahrung und Übung, um weiterzukommen. Wir haben bei unseren komplexeren Projekten immer große Erfolge erzielt, aber erst nach viel Arbeit. Die Definitionen der Schritte von Lösung zu Lösung, eines recht glatten Lösungsraumes und der Strafen für den Aufenthalt in Verbotszonen sind kritische Punkte.

Probleme mit dem Problem

Selten bekommen wir von den Praktikern, deren Problem wir lösen sollen, eine Diskette mit allen Informationen und der fertig formulierten Aufgabe. In den meisten Fällen fehlen Daten.

Ein Beispiel: Wir sollten die Wege von Bohrautomaten optimieren. Das Programm dafür hatten wir ja, denn das 442-Stationen-TSP ist genau von dieser Art. Wir brauchten eben nur die Koordinaten der Löcher und eine Sekunde Rechenzeit. Die Koordinaten sind in einem Programm (NC-Programm für englisch numerical control, numerische Steuerung) codiert und dann noch durch Prüfziffern verschlüsselt. Keiner der Zuständigen kannte das Prüfzifferverfahren; keiner fühlte sich imstande, die Koordinaten ohne Wochen an Arbeit zu extrahieren. Die Bediener der Maschinen sind ja auch nie mit solchen Fragen konfrontiert.

Das ist der entscheidende Moment in der Beziehung des Praktikers mit dem Wissenschaftler. Hier sagt der Mathematiker meist: „Na, dann geht es leider nicht. Schade, mit den Koordinaten auf einer Diskette hätte ich’s gekonnt.“ Und der Mann im grauen Kittel findet seine Vorstellung von den weltfremden Forschern wieder einmal bestätigt.

Wir haben nicht gleich klein beigegeben und das NC-Programm erst einmal mitgenommen. Unser erfahrener Kollege Ulrich Schauer schrieb in drei Wochen zwei Programme. Eines extrahiert die Koordinaten, das andere fügt die neue Reihenfolge wieder in ein Maschinenprogramm ein und setzt die richtigen Prüfbits. Zwischendurch hat der Computer wirklich nur eine Sekunde gerechnet.

Es folgte noch eine Dienstreise, um festzustellen, wieviel Zeit die Maschine zum Abfahren verschieden langer Strecken braucht. In Wirklichkeit will man ja nicht den Weg minimieren, sondern die Bearbeitungszeit, und da der Bohrkopf auf dem Weg von Loch zu Loch beschleunigen und bremsen muß, ist das durchaus ein Unterschied.

In der Produktionsoptimierung sind die Daten oft nur zu schätzen. Die Zielsetzungen sind nicht genau bekannt oder definiert. Will die Produktionsleitung eher die Lagerhaltung oder Lieferverzögerungen verringern, oder geht es ihr darum, kostenintensive Maschinenumrüstungen zu vermeiden? In welchem Verhältnis stehen solche Zielsetzungen zueinander?

Firmen errechnen beispielsweise, wieviel die Lagerung einer einzelnen Produkteinheit pro Tag kostet. Wenn wir nun den Lagerbestand durch Optimierung auf die Hälfte senken, erspart das aber nicht so viel wie gedacht, denn die zweite Lagerhalle, die wir überflüssig gemacht haben, steht noch immer da, nur eben ungenutzt. Wir haben den Bestand halbiert, nicht die Kosten.

Wenn wir fragen, wie lange ein Maschinenumbau dauert, gibt es Dialoge wie diesen:

„Das ist verschieden. Manche Leute sind sehr fix.“

„Wieviel Zeit ungefähr?“

„Kann man nicht sagen, so eine halbe Stunde.“

„Ist das sicher?“

„Nun ja, manchmal tricksen wir: Bei etwas Glück macht die Maschine da gerade diese kleinen Teile, da kann man den Hebel da schnell umlegen, sehen Sie, dann braucht man gar nicht abzuschalten.“

„Geht der Trick immer?“

„Nein. Kann auch nicht jeder hier. Ist doch egal.“

Vielleicht vermittelt das ein Gefühl dafür, wie schwierig es ist, aus einem Problem ein mathematisches Modell zu machen. Wir müssen immer daran denken, daß wir die Menschen am Arbeitsplatz, die uns bei der Formulierung helfen sollen und können, von der Arbeit abhalten. Wir kritisieren durch unser bloßes Dasein im Betrieb die Abläufe, wie sie sind. Wir sind denen verdächtig, die sich oft mit gutem Grund für Experten halten. Ein normaler Mensch erwartet nichts von der Mathematik.

Und es geht doch besser

Den Produktionsplan eines Chemieunternehmens oder die Walzstraße eines Stahlwerks zu optimieren erfordert viel Arbeit, die bezahlt werden will. Diese Kosten amortisieren sich nur, wenn die Optimierung entsprechende Verbesserungen einbringt. Es stellt sich also am Anfang die Frage: Lohnt das Optimieren überhaupt? Wieviel besser ist der Computer gegenüber einem menschlichen Disponenten?

Nach unseren Erfahrungen ist ein Mensch schon bei einem TSP mit 50 Städten um 10 Prozent schlechter als das Programm. Bei extrem komplizierten Problemen wie Produktionsplänen gelingt es dem Rechner schon einmal, Lager- oder Verspätungskosten um 30, ja 50 Prozent zu senken. Bei einer Mischungsoptimierung erzielten wir 8 Prozent Materialkostenersparnis.

Oft sind Probleme gar nicht als Optimierungsprobleme erkannt. Ein Farbplotter zur Bildausgabe ist schon werksseitig darauf eingestellt, die Farbpunkte in einer bestimmten Reihenfolge auf das Papier zu setzen. Kann man seine Arbeit durch Optimierung vielleicht erheblich beschleunigen? Bohrautomaten sind zunächst darauf programmiert, ihre Löcher im wesentlichen von links nach rechts zu bohren, und brauchen dafür häufig doppelt so lange wie bei einem optimalen Verfahren.

Wenn wir aber verstehen wollen, warum Rechnerlösungen häufig so überraschend gut sind, empfiehlt es sich, unser eigenes Verhalten zu beobachten. Beim Kofferpacken legen wir zuerst die großen Teile hinein. Bei der Stundenplanerstellung beginnt der Planer typischerweise mit Fachräumen und Oberstufenkursblöcken. Bei der Maschinenbelegung verplant der Disponent zuerst die wichtigen, großen Aufgaben.

Auf den Punkt gebracht: Der Mensch fängt stets mit der Hauptsache an, fährt mit den mittelwichtigen Dingen fort und steht schließlich vor unlösbaren Problemen bei Kleinigkeiten. Mathematisch gesprochen: Er benutzt den Algorithmus HINAUF; er versucht, in jedem Schritt möglichst weit voranzukommen.

Und das ist vielleicht eine Antwort: Die menschliche Intuition paßt schlecht zu Optimierungsproblemen. Die Verbesserung, die Computer erzielen können, entsprechen häufig dem Unterschied zwischen HINAUF und TA. Und der kann sehr groß sein.

Manchmal gibt es freilich auch einen Optimierungserfolg, der völlig ohne mathematische Methoden erzielt wird und bei uns entsprechend gemischte Gefühle hervorruft. Der Mathematiker Bernhard Korte, der an der Universität Bonn Optimierungsprobleme bearbeitet, berichtet von einem Fall wie diesem: Die Bohrer nutzen sich an Leiterplatten sehr rasch ab. Wird ein Bohrer stumpf, erhitzt er sich stark und bricht schließlich; daraufhin bleibt die Maschine automatisch stehen und zeigt durch ein rotes Licht an, daß ein Wechsel erforderlich ist. Eine Firma sparte erhebliche Kosten ein, indem sie die Leuchtanzeige durch eine Klingel ersetzte. Dadurch sank nämlich die Zeit, bis der in andere Tätigkeiten vertiefte Bediener den Maschinenausfall zur Kenntnis nahm und einen neuen Bohrer einsetzte, und die Produktion erhöhte sich beträchtlich.


Aus: Spektrum der Wissenschaft 3 / 1993, Seite 42
© Spektrum der Wissenschaft Verlagsgesellschaft mbH