Zufall ist sicher nicht, dass zur Zeit gerade in mehreren aktuellen Heften Artikel zur Bedeutung des Zufalls in der Informatik zu finden sind.
Dort finden wir einen Artikel mit dem Thema Zufall und zufallsgesteuerte Algorithmen von Juraj Hromkovic. Dort heißt es in der Einleitung:
Zufallssteuerung ist heutzutage ein fester Bestandteil von Informatiksystemen, und wir verdanken ihr einige der faszinierendsten mathematisch-naturwissenschaftlichen Entdeckungen in der Informatik. Das erste Ziel dieses Artikels ist es, den Lesern an einem einfachen Beispiel zu zeigen, dass zufallsgesteuerte Systeme und Programme eine Leistungsfähigkeit besitzen, die deterministische nie erreichen können. Das zweite Ziel ist es, anhand der "Methode der häufigen Zeugen" zum Verständnis der Berechnungsstärke zufallsgesteuerter Algorithmen beizutragen.
Weiter heißt es dort:
Die meisten Menschen haben zum Zufall eine negative emotionale Einstellung, weil sie Zufall mit Ungewissheit verbinden. Am liebsten hätten sie eine exakte Zukunftsvorhersage, um auf alle möglichen Alternativen vorbereitet zu sein; ersatzweise schließen sie viele Versicherungen ab, um gegen Eventualitäten gewappnet zu sein. Einige Menschen spielen aber auch gerne mit Zufall, insbesondere wenn die Vision eines Lotteriegewinns bevorsteht.
und weiter unten:
Die Physiker waren die Ersten, die auf die Idee kamen, durch zufallsgesteuerte Systeme Naturprozesse zu simulieren. Der große Nutzen von Zufallssteuerung fand aber erst in der Informatik durch den Entwurf von zufallsgesteuerten Algorithmen statt. Was sind aber zufallsgesteuerte Algorithmen? Die Programme (Algorithmen), die wir gewohnt sind, sind deterministisch. "Deterministisch" bedeutet, dass das Programm und die Problemeingabe die Arbeit des Programms vollständig bestimmen. In jedem Augenblick ist in Abhängigkeit von den aktuellen Daten eindeutig klar, was die nächste Aktion des Programms sein wird. Zufallsgesteuerte Programme können mehrere Möglichkeiten haben, ihre Arbeit fortzusetzen, und welcher der Möglichkeiten das Programm folgt, wird zufällig entschieden. Es sieht so aus, als ob ein zufallsgesteuertes Programm von Zeit zu Zeit eine Münze wirft, und abhängig davon, ob Kopf oder Zahl gefallen ist, wählt es die entsprechende Strategie auf seiner Suche nach dem richtigen Resultat. Auf diese Weise kann ein zufallsgesteuertes Programm mehrere unterschiedliche Berechnungen für ein und dieselbe Eingabe durchlaufen. Im Unterschied zu deterministischen Programmen, wo immer eine zuverlässige Berechnung des richtigen Resultates gefordert wird, dürfen einige Berechnungen des zufallsgesteuerten Programms auch falsche Resultate liefern. Das Ziel ist jedoch, die Wahrscheinlichkeit einer falschen Berechnung klein zu halten, was in gewissem Sinne bedeutet, den proportionalen Anteil der Berechnungen mit falschem Resultat zu reduzieren.
Bei den GA sind wir glücklicherweise noch in einer etwas besseren Lage: Wir brauchen geradezu zwischendurch "falsche" Zwischenergebnisse, um die genetische Vielfalt sicherzustellen. Durch den iterativen Charakter des Algorithmus werden auch zwischenzeitliche Verschlechterungen verkraftet. Danach sind weitere Verbesserungen immer noch möglich. Weiter aus dem Artikel:
Auf den ersten Blick sieht ein zufallsgesteuertes Programm unzuverlässig aus im Vergleich zu deterministischen Programmen, und man kann fragen, wozu es gut sein soll, gelegentlich falsche Resultate zu erhalten. Es existieren aber Aufgaben von enormer praktischer Bedeutung, bei denen der schnellste deterministische Algorithmus auf dem schnellsten Rechner mehr Zeit zur Berechnung braucht als die Zeit vom Urknall bis zum heutigen Tag, die Aufgabe also praktisch unlösbar ist.
Und da kommt ein "Wunder" - ein zufallsgesteuerter Algorithmus, der die Aufgabe in ein paar Minuten auf einem Standard-PC löst mit einer Fehlerwahrscheinlichkeit von l zu Tausend Milliarden. Warum kann man so ein Programm trotzdem als zuverlässig ansehen, obwohl es Fehler macht? Ganz einfach: Ein herkömmliches deterministisches Programm, das diese Aufgabe in einem Tag berechnet, ist viel unzuverlässiger als unser zufallsgesteuertes Programm, weil die Wahrscheinlichkeit des Auftretens eines Hardwarefehlers während des 24-stündigen Programmlaufs viel höher ist als die Wahrscheinlichkeit einer fehlerhaften Ausgabe des schnellen zufallsgesteuerten Algorithmus.
In dem angegebenen Artikel wird eine spezielle Anwendung auf ein kryptologisches Problem weiter untersucht. Am Schluss heisst es dann:
Die Methode der häufigen Zeugen ist ein leistungsfähiges Verfahren zum Entwurf von zufallsgesteuerten Algorithmen. Der effiziente zufallsgesteuerte Primzahltest basiert auf dieser Methode und gehört damit zu den wichtigsten Anwendungen von großer praktischer Bedeutung in der Kryptographie. Die besten bekannten deterministischen Algorithmen würden für den Primzahltest großer Zahlen mehr Zeit benötigen als die Lebensdauer des Universums. ...
Aber für die Praxis ist es im Augenblick auch nicht wichtig, ob schnelle deterministische Algorithmen für die Aufgaben existieren oder nicht. Das Einzige, was zählt, ist, dass die Lösungen von Problemen durch zufallsgesteuerte Algorithmen effizient und hinreichend zuverlässig sind. Den Unterschied zwischen der Effizienz der bestmöglichen deterministischen Algorithmen und der bestmöglichen zufallsgesteuerten Algorithmen zu bestimmen, bleibt eine der zentralen Forschungsaufgaben der theoretischen Informatik.
John R. Koza von der Universität Stanford führte vor kurzem ein Experiment durch, das dieser Not abhelfen könnte. Koza ist Pionier im genetischen Programmieren (Spektrum der Wissenschaft 9/1992, S. 44): Er weist den Computer an, zufällig Programme zu erzeugen und sie immer wieder geringfügig zu verändern. Unter den veränderten Programmen überleben diejenigen, welche von ihnen die vorgegebene Aufgabe am besten erfüllen; alle anderen werden gelöscht. Kozas Programm ist in einem doppelten Sinne genetisch: Es soll nach einem genetischen Algorithmus ein kleines, aber kompliziertes Teil des E-Cell-Modells von Grund auf neu erstellen; dieses wiederum soll das Verhalten von Genen beschreiben.
Eine der Aufgaben war, aus bekannten Enzymen eine chemische Maschine zusammenzustellen, die Fettsäuren und Glyzerin zu Diacylglyzerin umwandelt. Jede Variante der Programme, die für diese Aufgabe "gezüchtet" wurden, wurde der Einfachheit halber auf einen äquivalenten elektronischen Schaltkreis abgebildet und dessen Verhalten mit einem kommerziellen Schaltkreis-Simulator durchgerechnet.
Nach einem Tag spuckte Kozas Supercomputer Beowulf, eine Spezialanfertigung aus tausend Prozessoren, ein Programm aus, das dem echten Reaktions-Netz glich. Vier Enzyme, fünf Zwischenprodukte, sämtliche Rückkopplungsschleifen und sogar die Reaktionsgeschwindigkeiten jedes Enzyms warenkorrekt wiedergegeben. Es gab nur diese eine "richtige" Antwort; keine andere Anordnung funktionierte annähernd so gut.
Nach Kozas Überzeugung sind mit genetischem Programmieren auch größere Probleme zu bewältigen. Vielleicht können die evolvierenden Programme eines Tages die verschlungenen Pfade nachvollziehen, auf denen Zellen ihre Nahrung in Energie, Wachstum und Abfall verwandeln. Die Methode wird aber nur funktionieren, wenn Messwerte über den Stoffumsatz echter Zellen im Verlauf der Zeit vorliegen. Solche Daten sind immer noch rar.
Dort hat das Heft 3/01 das Schwerpunktthema "Unsicherheit und Vagheit". Hierbei geht es zwar überwiegend um Unsicherheit und Vagheit bei der Logik, reasoning and deceision und Fuzzy - Methoden usw, trotzdem sind Zufall und Wahrscheinlichkeiten hier genauso von zentraler Bedeutung.