- NFL-Theorem
-
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“.
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 Genetische 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 Macready hergeleitet.
Anwendung
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.
Diese Argumentation wird jedoch allgemein als nicht wissenschaftlich seriös betrachtet, neben anderen Einwänden hauptsächlich deswegen, weil 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. 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, ist die darwinsche Evolution im Allgemeinen eher als eine „Vermeidungsstrategie“ statt als „Suchstrategie“ zu betrachten. 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.
Weblinks
Wikimedia Foundation.
