No-free-Lunch-Theoreme
Die No-free-Lunch-Theoreme oder auch Nichts-ist-umsonst-Theoreme sind eine Reihe von Sätzen aus der Theorie der kombinatorischen Optimierung, die sich auf Suchverfahren und ihre universelle Anwendbarkeit beziehen. Die Bezeichnung stammt von der amerikanischen Redensart There ain’t no such thing as a free lunch, auf deutsch sinngemäß: „man bekommt nichts geschenkt“.
Aussage
Die Aussage der No-free-Lunch-Theoreme ist, dass, wenn man die Menge aller mathematisch möglichen Probleme zugrundelegt, alle Suchalgorithmen im Durchschnitt gleich gut (oder gleich schlecht) sind.
Ein Suchverfahren kann implizite Annahmen über die Art des zu lösenden Problems enthalten, und nur für die Klasse von Problemen, auf die diese Annahmen zutreffen, ist das Verfahren besser als andere.
Als Schlussfolgerung aus den No-free-Lunch-Theoremen wurde die Forderung abgeleitet, nicht einfach allgemeine Suchverfahren wie Evolutionäre Algorithmen und simulierte Abkühlung (simulated annealing) zu verwenden, sondern sie mit möglichst viel Wissen an die untersuchte Problemklasse anzupassen.
Die Theoreme wurden von David Wolpert und William G. Macready hergeleitet.
Versuchte Anwendung auf Evolutionprozesse
William A. Dembski hat die No-free-Lunch-Theoreme für seine umstrittenen Hypothesen der spezifizierten Komplexität angewandt, die seiner Meinung nach mathematische Schranken für Evolutionsprozesse formulieren.[1] Dembski verwendet diese Schranken als Argument gegen die Evolutionstheorie und für ein Intelligent Design.
Diese Argumentation wird jedoch allgemein als nicht wissenschaftlich seriös betrachtet.[2][3][4][5][6] Neben anderen Einwänden wird hauptsächlich angeführt, dass Evolutionsprozesse nicht als eine Suche nach einem bestimmten von vornherein vorgegebenen optimalen Element innerhalb einer Such-Menge betrachtet werden können, wie es die No-free-Lunch-Theoreme voraussetzen.[3][7] Die darwinsche Evolution ist im Allgemeinen eher als eine „Vermeidungsstrategie“ statt als „Suchstrategie“ zu betrachten, da hauptsächlich Überleben und Reproduktion zählen und nur solche Evolutionsschritte sicher ausgeschlossen sind, die zu Arten führt, welche dazu prinzipiell nicht in der Lage sind. Die No-free-Lunch-Theoreme sind also gar nicht anwendbar.
Ein weiterer Einwand besagt, dass die Theoreme eine Aussage über den Durchschnitt aller denkbaren Probleme machen. In der Evolutionstheorie bedeutet das: gemittelt über alle möglichen Fitnesslandschaften. Über die Effektivität des Prozesses aus Mutation und Selektion für die tatsächlich vorkommenden Fitnesslandschaften können die Theoreme nichts aussagen. Insbesondere sind die Mehrzahl aller theoretisch denkbaren Fitnesslandschaften völlig regellos, während bereits die Naturgesetze eine gewisse Struktur voraussetzen.[5]
Wolpert selbst verwirft Dembskis Ausführungen als unmathematisch (written in jello)[4] und fügt zudem an, dass die Fitnessfunktion evolutionärer Systeme weder als in der Zeit konstant noch als für alle Individuen identisch angesehen werden kann. Dies ist aber eine wichtige Voraussetzung für die No-free-Lunch-Theoreme und macht daher ebenfalls eine Anwendung auf evolutionäre Prozesse unmöglich.[4][5] Tatsächlich konnten Wolpert und Macready für eine bestimmte Klasse solcher ko-evolutionären Systeme die Existenz optimaler Algorithmen beweisen.[8]
Weblinks
- David H. Wolpert, William G. Macready, 31. Dezember 1996 (PDF-Datei; 343 kB)
- Artikel der 1995 International Conference on Genetic Algorithms (ICGA-95) in Pittsburgh
- Sammlung von Artikeln zum Thema No-free-Lunch
Einzelnachweise
- ↑ William A. Dembski, No Free Lunch: Why Specified Complexity Cannot Be Purchased without Intelligence. (Lanham, Md.: Rowman & Littlefield, 2002). ISBN 0-7425-1297-5.
- ↑ J. Rosenhouse (2002) Probability, Optimization Theory, and Evolution. Evolution, 56(8):1721–1722.
- ↑ 3,0 3,1 H. Allen Orr Book Review of No Free Lunch, Boston Review
- ↑ 4,0 4,1 4,2 David Wolpert (2003) William Dembski’s treatment of the No Free Lunch theorems is written in jello Mathematical Reviews.
- ↑ 5,0 5,1 5,2 Richard Wein (2002) Not a Free Lunch But a Box of Chocolates
- ↑ M. Perakh (2004) There is a free lunch after all: William Dembski’s wrong answers to irrelevant questions. In M. Young and T. Edis, editors, Why Intelligent Design Fails, chapter 11. Rutgers University Press.
- ↑ Richard Dawkins, The Blind Watchmaker (New York: W. W. Norton & Company, 1996), Seite 50.
- ↑ D.H. Wolpert, W.G. Macready: Coevolutionary free lunches. IEEE Transactions on Evolutionary Computation, 2005, 9(6): S. 721–735.