Der optimale Bestand in einem Warenlager, die ideale Form einer Turbinenschaufel oder auch die effizienteste Verlegung dicht gepackter Leiterbahnen in einem Chip - all dies sind Beispiele für Aufgabenstellungen, die mit kniffligen Optimierungsproblemen zu tun haben. Um diese soll es im folgenden Beitrag gehen.
Für Optimierungsprobleme ist vor allem eines kennzeichnend: Man kennt keine einfachen Formeln beziehungsweise keine Algorithmen, die rasch zum Ziele führen könnten. Man muß letztlich durch mehr oder weniger geduldiges Ausprobieren herausfinden, welche Lösung aus der Menge der überhaupt denkbaren die beste ist oder doch wenigstens die brauchbarste.
Ähnliche Optimierungsaufgaben hat auch die Natur schon seit jeder zu lösen gehabt. Denn sowie ein Lagerverwalter versuchen muß, exakt nur den kostengünstigsten Lagerbestand vorrätig zu halten, der gleichzeitig die rasche Belieferung der Kunden ermöglichen und dennoch eher knapp bemessen sein sollte, so hat die Evolution beispielsweise das optimale Jagdverhalten eines Luchses herausfinden müssen oder auch die optimale Form eines Schwalbenflügels. Weshalb eigentlich nicht weiter verwundern kann, daß Menschen jetzt mehr und mehr lernen, Optimierungsaufgaben ähnlich elegant zu lösen wie die Natur dies seit Millionen von Jahren vorführt - und zwar auf dem Wege von Versuch und Irrtum beziehungsweise von Mutation und Selektion.
Strukturen im Rechner simuliert
Menschen kommt bei dieser neuen und evolutionären Strategie des Optimierens zupaß, daß sie im Gegensatz zur gemächlich und blind wartenden Natur über schnelle Rechner zum Simulieren komplexen Systeme beziehungsweise Strukturen verfügen. Das befreit sie davon, Generationen beziehungsweise Millionen suboptimaler Kreaturen zugrunde gehen lassen zu müssen, damit am Ende die Besten das Lebensspiel um den Platz an der Sonne gewinnen können. Denn im Rechner kann man relativ einfach jene Strukturen simulieren, die mit Blick auf ihre Eignung für eine bestimmte Aufgabe miteinander verglichen werden müssen. Anschließend lassen sich schmerzlos jene von der weiteren "Fortpflanzung" ausschließen, die sich nicht bewährt haben. Obendrein kann man diese simulierte Evolution im Rechner auch noch viel schneller ablaufen lassen, als die "Natur" dies in der Realität fertigbringen könnte.
Viele Menschen können nur schwer verstehen, warum es bei Optimierungsaufgaben nicht ebenso elegante Lösungsvorschriften gibt wie beispielsweise, jene, die für ein Kapital von 346 786 Mark exakt voraussagt, wieviel es in 17 Jahren real wert sein wird, wenn der Zinssatz 7,23 Prozent und die Inflation 3,48 Prozent beträgt. Die Erklärung dafür ist im Grunde ganz einfach: Anders als bei derartigen Rechnungen mit ihren langfristig voraussehbaren Zinssätzen und Inflationsraten kann man bei Optimierungsaufgaben in der Regel immer nur ein kurzes Stück des weiteren Wegs überschauen.
Weshalb hier die Gefahr stets groß ist, daß man sich über kurz oder lang in eine falsche Richtung wendet. Wer heute eine Optimierungsaufgabe lösen muß, der findet sich in einer ähnlichen Lage wieder wie ein Schiffbrüchiger auf einer unbekannten Insel, der, nachts anlandend, noch vor Tagesanbruch versucht, den höchsten aller Gipfel zu erklimmen.
Er will nämlich so früh wie möglich ein rettendes Schiff ausmachen können. Doch da er im Dunklen nichts weiter sieht als stets nur die nächsten zwei Schritte, kann er nur solange in jeweils der momentan steilsten Richtung bergauf gehen, bis er irgendeinen lokalen Gipfel also ein "lokales Maximum beziehungsweise Optimum" - erklommen hat. Denn weder kann er sehen, daß der höchste Berg erst zwei Täler weiter aufragt, noch hat er Zeit genug für eine vollständige systematische Erforschung sämtlicher Punkte seines Eilands.
Für Optimierungsaufgaben aus dem richtigen Leben ist typisch, daß man sie sich als extrem großflächige Inseln mit vielen kleinen lokalen Gipfeln beziehungsweise lokalen Optima vorstellen kann. Typisch ist auch, daß man in der Praxis sehr bald an das - vorläufige - Ende der Suche kommt. Deshalb scheint es zumindest in der theoretischen Behandlung solcher Aufgaben sinnvoll, statt bloß eines einzigen schiffbrüchigen Wanderers gleich einige Dutzend oder gar Tausende in Marsch zu setzen - und sie somit von ganz unterschiedlichen Ausgangspunkten aus in die jeweils steilste Bergauf-Richtung suchen zu lassen. Solche Ansätze erfordern jedoch entsprechend höheren Rechenaufwand - und verbieten sich daher fast ebenso, wie die schon erwähnte, systematische und deshalb aufwendige Durchmusterung sämtlicher Punkte der Insel.
Der Weg zum nächsten Gipfel
Statt bei der Suche nach dem höchsten Gipfel vor jedem einzelnen Schritt immer erst neu die Richtung zu ändern und sich dabei stets erneut nach der örtlich maximalen Steigung zu richten, kann man auch leicht modifizierte Suchstrategien anwenden, die allerdings pro Einzelschritt manchmal fast keinen Höhengewinn mehr bringen. Denn es hat sich in der Praxis gezeigt, daß dadurch so manches lokale Optimum vermieden und ein höherer Berg erreicht werden kann. Überdies weiß man von der Natur, daß auch sie durch ähnliche Strategien vielfach vermeidet, in unerwünschten Optimierungs-Sackgassen zu enden.
So ist eine Insel mit beispielsweise 500 Gipfeln, die viele kleine, viele mittlere und viele hohe Berge umfaßt, ein besseres Beispiel für realitätsnahe Optimierungsprobleme als etwa eine Insel mit vielen kleinen und nur einem hohen Gipfel. Denn die erstere Konfiguration von Optima entspricht dem, was die Wirklichkeit uns vorlegt, besser als die zweite - und somit kann man an ihrem Beispiel auch gleich sehen: es ist oft gar nicht nötig, den einzigen - sagen wir - 900-Meter-Berg der Insel zu finden. Oft reicht es, wenn man nur irgendeinen der Gipfel über 880 Meter erklimmt: Die Aussicht auf rettende Karavellen ist dann schon gut genug.
Der Gedanke, sich auch mit dem Erreichen hinlänglich guter Optima zu begnügen, liegt einer Lösungsstrategie für Optimierungsaufgaben zugrunde, die sich gut am Beispiel eines Vertreters darstellen läßt, der von Stadt zu Stadt reisen muß und dabei einen möglichst kurzen Weg wählen möchte. Denn dieser Mann kann auf einer (Computer-) Karte alle zur Reise gehörenden Städte zunächst einfach durch eine beliebig gewählte Route verbinden und dann folgende Strategie wählen: Ich selektiere zufallsgesteuert zwei Verbindungen zwischen je zwei Städten, vertausche sie miteinander und prüfe dann, ob die resultierende Gesamtstrecke kürzer geworden ist. Wenn ja, wiederhole ich den Vorgang mit zwei anderen Verbindungen und wenn nein, mache ich das Vertauschen "vielleicht" rückgängig und wiederhole den Vorgang erst dann, und zwar wieder mit zwei anderen Verbindungen.
Weiteres Abkürzen nicht mehr rentabel
Das vage Wort "vielleicht" besagt, daß die Wahrscheinlichkeit, mit der diese Strategie manchmal auch ein an sich schädliches, routenverlängerndes Vertauschen akzeptiert, eine langsam sich ändernde Größe ist. Denn in den frühen Phasen des gesamten Prozesses ist diese Wahrscheinlichkeit eher groß, während sie mit wachsender Zahl von Interaktionen mehr und mehr abnimmt, so daß gegen Ende nur noch Änderungen akzeptiert werden, die mit Sicherheit eine kürzere Route zur Folge haben, während anfangs auch "ungünstige" Vertauschungen noch akzeptiert werden, denn in den frühen Phasen des Algorithmus dienen sie noch dem Vermeiden lokaler Optima.
Diese Strategie führt zu einer Route, die zwar einerseits fast nie den kürzesten aller denkbaren Wege darstellen wird, die aber andererseits durch keine kürzere mehr ersetzt werden kann. Und außerdem führt diese Strategie vor allem zu einer Route, die für die meisten praktischen Zwecke kurz genug ist, beziehungsweise, um präzise zu sein, so kurz, daß weiterer Aufwand zum Abkürzen der Strekke sich kaum mehr lohnen dürfte.
Die Natur geht trickreicher vor
Mit dem beschriebenen Verfahren, das Fachleuten als "Simulated annealing" bekannt ist, lösten Wissenschaftler wie etwa Scott Kirkpatrick in den USA eine Reihe schwieriger Probleme in Verbindung mit der Entwicklung komplexen Computer-Chips. Denn diese Technik führt immer dann zu hinreichend brauchbaren Optima, wenn es etwa um das zweckmäßigste Aufteilen einer gegebenen Schaltung auf verschiedene Einzel-Chips oder auch um das Plazieren der einzelnen Schaltelemente auf dem Chip sowie das Anordnen mehrerer Chips auf einer Platine geht. "Hinreichend brauchbar" besagt, daß die Lösungen mindestens so gut waren wie jene, die man mit herkömmlichen und umständlicheren Optimierungsstrategien finden kann.
Mögen die hier skizzierten Tricks und Strategien beim Lösen des Handlungsreisenden sowie des Chip-Aufteilungs-Problems auch ziemlich raffiniert anmuten, geht doch die belebte Natur noch viel trickreicher vor.
Geschöpfe der lebenden Natur passen sich optimal an die Gegebenheiten der Umwelt an. Sie stellen stets leicht abweichende Kopien ihrer jeweiligen Eltern dar - die fortlaufende Optimierung dieser Lebewesen im Laufe der Jahrtausende kommt dadurch zustande, daß die jeweils "besser angepaßten" einer Generation vergleichsweise mehr Nachkommen produzieren als die anderen.
Das biologisch-evolutionäre Konzept von Mutation und Selektion regte den bekannten Informatiker John Holland - er ist auch Konstrukteur eines bekannten zellulären Automaten - schon Mitte der 70er-Jahre an, einen ersten genetischen Algorithmus zu entwerfen, der adaptiv bestimmte Suchaufgaben lösen sollte; eine Technik, bei der Holland mit einer Art von binär codierter "Chromosomen-Erbmasse" arbeitete, deren weniger brauchbare Teile im Laufe der Zeit und mit der Abfolge der einzelnen Generationen aussterben sollten. Ähnliche Konzepte genetisch-algorithmischer Art lassen sich auch nutzen, will man statt Suchaufgaben knifflige Probleme der Optimierung in Angriff nehmen. Computer-Optimierungstechniken, die auf genetischen Mechanismen der skizzierten Arten aufbauen, können schon heute verblüffende Leistungen vollbringen. So suchte beispielsweise David Glower von der Universität Iowa nach einem Verfahren, mit dem man die rund 3000 bis 5000 Bildzeichen fernöstlicher Schriften mit Hilfe einer gewöhnlichen Rechner-Tastatur sollte schreiben können.
Ihm kam zu Hilfe, daß die einzelnen Bildsymbole etwa der Kanji-Schrift jeweils eine andere Kombination von annähernd 160 elementaren Grundelementen darstellen.
Glower stand also im Grunde vor der Aufgabe, diese 160 Elementarzeichen jetzt so den knapp 100 Standard-Computertasten zuzuordnen, daß die einzelnen Schriftzeichen sich fortan relativ leicht erzeugen lassen. Dies ist möglich, indem man die verschiedenen Umschalt-Tasten wie CTRL, ALT etc. einsetzt; Glover meinte jedoch, dies müsse sich eleganter lösen lassen.
Da man aus 160 x 160 Grundzeichen rund 26 000 Bildsymbole zusammensetzen kann, war Glover rasch klar, daß im Grunde nur etwa jedes fünfte bis achte der theoretisch erzeugbaren Bildsymbole gültig ist und daß man durch geschicktes Zuordnen der einzelnen Elementarzeichen ein System müßte schaffen können, bei dem jeweils ein einziges Paar von Tasten das gewünschte Symbol erzeugen könnte.
Mit 70 Tasten 4900 Schriftzeichen
Schaltet man eine Tastatur dann in den Fernost-Schriftzeichen-Modus um, so genügen fortan theoretisch 70 verschiedene Tasten, um - paarweise angeschlagen - 70 x 70, also 4900, verschiedene Schriftzeichen zu erzeugen. Und da eine Standardtastatur deutlich dies alles im Grunde durchaus machbar.
Das Problem dabei besteht darin, für die geforderte Doppel-Zuordnung von Tasten- und Schriftzeichen eine praktikable Lösung zu finden, und zwar eine, die folgendes sicherstellt: je zwei verschiedene Paare von Tastaturanschlägen erzeugen einerseits fast immer zwei verschiedene Zeichen, möglichst selten das gleiche, andererseits erfaßt das System dennoch wirklich lückenlos alle vorkommenden Kanji-Schriftsymbole.
Hier muß der Computer, so hat Glover sich ausgerechnet, mit annähernd (10 hoch 180) vorstellbaren Zuordnungen zurechtkommen und aus der großen Menge denkbarer Möglichkeiten auch noch eine selektieren, die die geforderten strengen Bedingungen erfüllt.
Glover setzte für seine Suche nach einer optimalen Lösung einen genetischen Algorithmus ein, der mit gewissen Modifikationen ein wenig jenem Arbeitsverfahren des Simulated annealing gleicht, das vorhin für die Lösung der Routen-Probleme des reisenden Vertreters beschrieben wurde. Dabei wählte er als Kriterium für die Qualität der jeweils gefundenen Zuordnung einfach die Zahl jener Kanji-Schriftzeichen, die mit jeweils nur einer einzigen Kombination von zwei Tasten erzeugt werden konnten, die also nicht unerwünschterweise auch über andere Kombinationen erzeugt werden können.
Der Forscher ließ seinen Computer arbeiten - und fand nach einigen zehntausend Läufen beziehungsweise Generationen, daß sein genetischer Algorithmus ihm Lösungen von ausgesprochen hoher Güte lieferte. Denn, das zeigten seine weiteren Berechnungen, die vom Rechner jeweils ausgeworfenen Lösungen für das beschriebene Zuordnungsproblem waren im Durchschnitt jeweils besser als rund (10 hoch 16) andere Zuordnungen.
Industrielle Arbeitsplanung
Ein weiteres Beispiel für den hohen praktischen Nutzen, den genetische Optimierungsverfahren schon heute bringen können, stammt aus dem Bereich der industriellen Arbeitsplanung.
In diesem Feld müssen Lösungen für die Aufgabe gefunden werden, einzelne Produkte, etwa Kurbelwellen und Zahnräder, möglichst kostengünstig herzustellen und die vorhandenen Drehbänke und Fräsautomaten, Sägen und Schleifmaschinen dabei nicht nur möglichst gut auszunutzen, sondern darüber hinaus noch weitere Randbedingungen zu erfüllen.
Drei Forscher der Universität Edinburgh stellten hier als Ausgangspopulation oder auch "Ur-Horde" zunächst eine Reihe unterschiedlicher, bewährter Arbeitspläne auf, die divergente Strategien verfolgen.
Während der eine Plan beispielsweise versucht, alle Arbeit mit nur einer universellen Werkzeugmaschine auszuführen, strebt der andere danach, für jeden einzelnen Teil-Arbeitsgang das jeweils billigste Werkzeug einzusetzen.
Das bedeutet, die verschiedenen Strategien der diversen Pläne widersprechen einander auf vielfältige Art und Weise, weshalb sie in der Praxis mithin zu Anweisungen führen, die niemals zugleich befolgt werden könnten.
Neue Technik macht sich bald bezahlt
Philip Husbands und seine Kollegen codierten die einzelnen Pläne anschließend in computerlesbare Form und unterzogen die entstandenen Programme nunmehr den beschriebenen Mechanismen genetischer Auslese auf Basis von Mutation und Kreuz-Rekombination mit anschließender Selektion der Angepaßtesten beziehungsweise Optimalen. Im Wettlauf der verschiedenen Folge-Generationen dieser Arbeitspläne wurden am Ende Varianten "herausgemendelt", die ein weit billigeres Produzieren erlauben sollen als jene Pläne, die man auf dem Wege der konventionellen Optimierung je habe entwickeln können.
Die neue Technik der genetischen Algorithmen macht sich also auch praktisch alsbald bezahlt.