Diskussion:No-free-Lunch-Theoreme

Erster Kommentar

Die Aussage der No-Free-Lunch-Theoreme ist, daß, wenn man die Menge aller mathematisch möglichen Probleme zugrundelegt, alle Suchalgorithmen im Durchschnitt gleich gut (oder gleich schlecht) sind.

Diese Theorie halte ich für sehr gewagt. Ich habe die Papiere nicht durchgearbeitet, aber ich kann mir nicht vorstellen, dass jemand das in dieser Allgemeinheit behauptet.

Beispiel: Ein Algorithmus zum Finden eines kürzesten Weg in einem Graphen wäre :

(1) Erzeuge alle Permutation über alle Knoten, berechne jeweils die Länge des Weges 
(2) Bestimme die Permutation mit dem minimalen Weg

und dieser Algorithmus soll im Durchschnitt genau so gut sein wie Dijkstra?

Obige Aussage ist schlampig formuliert, da in der Informatik "Suchalgorithmen" ein Fachwort darstellt. Gemeint ist wohl "Algorithmen, die die Problemlösung suchen".

Ein Algorithmus, der (unverändert!) für beliebige Problemstellungen jeweils eine (optimale) Lösung finden soll, also ganz ohne Anpassung auf bestimmte Problemklassen ~ dass der nicht sonderlich gut sein kann, halte ich für plausibel.

Oder anders ausgedrückt: Ein Algorithmus, der für bestimmte Problemklassen angepasst ist, um für diese schnell gute Lösungen zu finden, ist für andere Problemklassen dafür umso schlechter ~ there ain't no free lunch / man muss (woanders) dafür bezahlen.

--arilou (Diskussion) 14:52, 12. Nov. 2019 (CET)

Bitte kommentar über mir löschen

Lies dir mathematische Sätze doch erstmal anständig durch, bevor du irgendeinen Unsinn dazu postest:

Du legst nicht alle mathematisch möglichen Probleme zu Grunde.

Ausserdem, schreib nicht deine eigene Meinung in Kommentare, sondern Kritik am Artikel!

Gruß

Erstens heißt das nicht "kommentar über mir löschen" sondern "Kommentar über mich löschen" und zweitens musst du schon mitteilen, wer du bist, wenn man den Kommentar über dich löschen soll.

SCNR -- Mulno 20:39, 16. Jan 2006 (CET)

War zwar nicht von mir, aber "über mir" ist natürlich richtig.--128.101.154.21 18:09, 2. Mär 2006 (CET)

Über mich ist natürlich richtig, denn einen Kommentar mach man nicht über jemandem, sonder über jemanden. AKKUSATIV!

Es geht doch um den Kommentar, der über _ihm_ (sprich: seinem Beitrag) steht. Und das ist immer noch Dativ.--128.101.154.21 23:22, 2. Mär 2006 (CET) Ergänzung: Und inhaltlich hat er natürlich auch recht; überhaupt sollte man sich nur dann über Mathematik auslassen, wenn man sie versteht.--128.101.154.21 23:24, 2. Mär 2006 (CET)

Dieser Einwand wird aber garantiert noch öfter kommen. Von daher ist es besser, wenn er mit Antwort da stehen bleibt - abgesehen davon, dass Diskussionbeiträge normalerweise nicht gelöscht, sondern höchstens archiviert werden, und auch das nur, wenn die Seite zu voll wird. Ein weiterer Punkt: wenn jemand eine Frage stellt, sollte man ihn nicht dafür prügeln. Es zeigt, dass er nachdenkt. Die Frage sachlich zu beantworten reicht aus. Siehe Wikipedia:Wikiquette. --Hob 09:53, 3. Mär 2006 (CET)

Stimmt, mein Ton war total unangemessen, Entschuldigung. Und inhaltlich hab ich auch nix beigetragen. Zur Frage: Ich denke, dass die Formulierung "...alle Suchalgorithmen im Durchschnitt gleich gut (oder gleich schlecht) sind." aus dem Artikel nicht besonders glücklich ist. Alleine schon aus dem Grund, dass der Durchschnitt "über alles" sozusagen "konstant" ist, so wie z. B. im Durchschnitt ja auch alle Menschen gleich groß sind. Bei diesen Sätzen geht es wohl eher darum, dass es unmöglich ist, eine schwierige Aufgabe mit einem schnellen Algorithmus zu lösen. Und dass diese Tatsache sicher ist! Das alles (=mein Geschwafel) ist natürlich höchst unpräzise und drückt letztendlich selbst eine Tautologie aus :-) Das Problem bei mathematischen Sätzen ist immer: Man kann sie nur erklären, indem man sie konkret hinschreibt; und das macht auch nur Sinn, wenn der Leser wirklich alle darin vorkommenden Begriffe versteht, sprich ihre Definition kennt.--128.101.154.21 16:55, 3. Mär 2006 (CET)

Der Durchschnitt wird ja nicht über alle Algorithmen, sondern über alle Eingaben gebildet, und dann werden verschiedene Algorithmen verglichen und der Artikel behauptet, dass kein Unterschied zwischen den Algorithmen besteht. Das ist einfach Unsinn, wie ich mit dem Extrembeispiel erläutern wollte. Wenn dem so wäre, bräuchte man für einen Algorithmus gar keine mittlere Laufzeit anzugeben, denn die wäre ja immer gleich! -- Mulno 23:08, 3. Mär 2006 (CET)

Der zitierte Satz ist vielleicht etwas mißverständlich formuliert. Natürlich gibt es zu jedem Problem bessere und schlechtere Lösungsalgorithmen. Aber: Ein Algorithmus, der für eine bestimmte Art von Problemen optimal ist, kann für eine andere Art von Problemen fürchterlich schlecht sein. Die Kernaussage ist daher: Es gibt keinen Algorithmus, der für alle möglichen Probleme optimal ist. Andererseits kann ich mir gut vorstellen, dass manche Algorithmen immer suboptimal sind. --Franz Halač 16:07, 5. Mär 2006 (CET) (nachträglich signiert)

Naja, wenn kein Algorithmus für alle Probleme optimal ist, dann ist jeder Algorithmus immer suboptimal. Das ist trivial.--12.106.8.140 17:18, 5. Mär 2006 (CET) Ergänzung: Seh grad, dass ich falsch gelesen hab, ziehe meinen Kommentar zurück.--12.106.8.140 17:19, 5. Mär 2006 (CET)

Überarbeiten

Aus der QS-Diskussion:

So wie die Theoreme hier beschrieben sind, ist es Unsinn. Siehe z.B. englische Version. Auf jeden Fall muss beschrieben sein, auf welche Probleme sich die NFL-Theoreme beziehen und was die Einschränkungen sind. Alle Algorithmen können nicht gleich gut sein, man kann nämlich jeden Algorithmus beliebig schlecht machen. -- 84.57.153.181 20:19, 18. Jan. 2007 (CET)

In der Diskussion wird einiges durcheinander geworfen. Der Durchschnitt wird nicht über die Menge der möglichen Eingaben gebildet. Es steht im Artikel "...wenn man die Menge aller mathematisch möglichen Probleme zugrundelegt..". Der Durchschnitt der Güte des Algorithmus wird also über die Menge aller möglichen Probleme gebildet.

Zum Punkt der beliebig schlechten Algorithmen: Beliebig schlecht ist dieser nur für EIN bestimmtes Problem. Man kann für jeden Algorithmus aber immer auch ein Problem hernehmen, für das dieser beliebig gut ist. Denn die möglichen Probleme sind nicht begrenzt. Über alle Probleme ist nach dem Theorem dann jeder Algorithmus gleich gut. Der eine kann Problem A gut, und Problem B schlecht lösen, der andere genau umgekehrt, und das ändert damit nichts am Durchschnitt.

"No-free-Lunch"

Ist das üblich, englische Wendungen nach deutschen Regeln groß- bzw. kleinzuschreiben?

Als nächstes wird das noch nach "No-freees-Lunch-Theorem" verschoben, damit das Adjektiv die richtige deutsche Endung hat? --Hob 23:31, 28. Jan. 2009 (CET)

Nach englischen Regeln müsste alles kleingeschrieben werden (also auch lunch), siehe zum Beispiel die englischen Wikipedia-Artikel en:No free lunch in search and optimization und en:No free lunch theorem. (Das No ist hier nur großgeschrieben, da es am Anfang der Artikelüberschrift steht – im Fließtext wird es kleingeschrieben.)

Die (deutschen) Regeln zur Groß- und Kleinschreibung von Fremdwörtern findet man beispielsweise bei canoo.net dargestellt. -- Sprachpfleger 01:19, 29. Jan. 2009 (CET)

Ah, danke. --Hob 07:20, 29. Jan. 2009 (CET)

There ain't no such thing as a free lunch?

Müsste es nicht "There's no such thing as a free lunch" heissen? (nicht signierter Beitrag von 84.253.33.98 (Diskussion | Beiträge) 15:12, 12. Aug. 2009 (CEST))

Milton Friedman hat die beanstandete Formulierung genauso veröffentlicht. Diese wurde allerdings als Begründung der freien Marktwirtschaft verwendet. Das ist meiner Meinung nach zwar falsch (unsere Wikipedia ist ja ein gutes Gegenbeispiel: Hier wird gute Arbeit zum Wohle vieler geleistet, ohne dass eine Gegenleistung erwartet oder erbracht wird. Wikipedia ist mehr wert als die Kosten zum Betreiben der Server!), aber das steht hier nicht zur Diskussion. Die Formulierung ist korrekt!--FerdiBf (Diskussion) 20:15, 12. Aug. 2013 (CEST)

Satz (Mathematik)

Dieser Artikel ist der Kategorie "Satz (Mathematik)" zu unrecht zugeordnet, denn es handelt sich nicht um einen mathematischen Satz, ein solcher könnte nicht umstritten sein. Es handelt sich vielmehr um eine Hypothese oder besser noch um ein Paradigma. Ich werde diese Kategorie daher entfernen. Die Formulierungen "alle Suchalgorithmen" und "besser/schlechter" sollten dringend präzisiert werden. Handelt sich möglicher Weise um eine Art Binsenweisheit, dass problemspezifische Lösungsansätze schneller zum Ziel führen können? --FerdiBf 18:46, 27. Dez. 2011 (CET)

Arbitragefreiheit

In der Ökonomie interpretiert man die Arbitragefreiheit (oder einen Grad von Arbitragefreiheit) als there is no such thing as a free lunch. Gibt es da eine Verbindung?--FerdiBf 18:58, 27. Dez. 2011 (CET)

Überarbeitung

Ich habe den Artikel überarbeitet und eine Herleitung und die genaue Originalformulierung des ersten Theorems hinzugefügt. Der Artikel sollte nun in einem grundsätzlich akzeptablen Zustand sein, allerdings muss noch viel getan werden. Würde jemand die Diskussion hier etwas aufräumen? Ich kenne mich dar nicht so genau aus, aber sicher könnte man den ersten Post irgendwie harmonischer einsortieren. -Schwatzwutz !?! 12:22, 9. Aug. 2013 (CEST)

Hallo Schwatzwutz. Vielen Dank für die dringend notwendige Überarbeitung. Die zum Teil unsachliche Diskussion, die sicher auch den schlechten, früheren Artikelversionen vor deiner Überarbeitung geschuldet ist, habe ich strukturiert, mittelfristig sollte die allerdings archiviert werden. Ich bin mit Dir der Meinung, dass noch einiges zu tun bleibt. Ich habe folgende Verständnisprobleme, an denen der Artikel vielleicht wachsen kann (oben hatte ich bereits zwei Diskussionsbeiträge verfasst):

1. Es ist von zwei Sätzen die Rede. In der "Originalformulierung" finde ich aber nur ein Theorem 1. Was ist die zweite Aussage?

2. Es geht hier wohl um Algorithmen oder Strategien, die auf alle Probleme anwendbar sein sollen. Ein Algorithmus (Turing-Maschine) ist für die meisten Probleminstanzen (Eingangsdaten) aber gar nicht sinnvoll sondern bricht im Idealfall einfach ab. Hier fehlen offenbar ein paar erhellende Erläuterungen. Mir fehlt hier die Quintessenz.

3. Wahrscheinlich sind aber gar nicht alle Algorithmen (Turing-Maschinen) gemeint. Der Algorithmus, der auf allen Probleminstanzen endlos läuft, ist sicher schlechter als der Algorithmus, der die Probleminstanz ignoriert und 42 ausgibt. Ist das so?

4. Wahrscheinlich müssen die hier zu betrachtenden Probleminstanzen noch präzisiert werden. Auch die Formel in der "Originalformulierung" müsste weiter erläutert werden. Was bedeutet das Antreffen von Werten während der Optimierung?

Fragen über Fragen. Ich hoffe Dich motivieren zu können, hier Licht ins Dunkel zu tragen. Jedenfalls freue ich mich, dass sich jemand dieses Artikels angenommen hat.--FerdiBf (Diskussion) 20:02, 12. Aug. 2013 (CEST)

Abschnitt "Erklärung" zweifelhaft

Die Erklärung im gleichnamigen Abschnitt setzt stillschweigend die Annahme voraus, dass sich zu jeder Kombination aus Strategie und Qualitätswert ein passendes Optimierungsproblem findet, d.h. dass zu jedem Paar (x,y) ein f mit f(x) = y existiert. Es ist nicht offensichtlich, warum das so sein sollte. 137.248.121.100 17:06, 3. Sep. 2013 (CEST)

Erkärung nicht zweifelhaft mMn, denn jede solche Abbildung ist ein mögliches Optimierungsproblem. (nicht signierter Beitrag von 137.226.45.35 (Diskussion) 17:38, 23. Sep. 2013‎)

Hier (und im Artikel) gehen leider zwei Dinge durcheinander: (1) Es wird eine Menge von Abbildungen definiert, (2) Es wird etwas über die Bedeutung dieser Menge behauptet, ohne, dass diese Behauptung näher begründet wird. Zu (1): Die Definition besagt, dass F die Menge aller Abbildungen ist, die jeder Strategie einen Qualitätswert zuordnen. Ein solches F kann man definieren, von mir aus spricht nichts dagegen. Zu (2): Die Behauptung lautet, dass zu jeder Abbildung f ein Optimierungsproblem korrespondiert (laut Artikel so etwas wie: Gewinnmaximierung, Wegminimierung). Das ist eine starke Aussage und ich wüsste nicht, ob und warum sie stimmen soll.

Mein offensichtlicher Einwand wäre: Vielleicht gibt es ja eine Strategie s, mit der man für jedes gegebene Optimierungsproblem einen guten Qualitätswert erzielt. Dann wäre die Formalisierung falsch, weil sie Abbildungen kennt, zu denen kein entsprechendes Optimierungsproblem existiert. Um die Formalisierung zu retten, müsste man behaupten, dass es keine solche Strategie s gibt. Um diese Behauptung zu begründen, müsste man wahrscheinlich das No-free-Lunch-Theorem anwenden - dann hätte man es jedoch nicht erklärt, sondern bloß angewandt. Das eigentliche Erklärungsbedürftige - warum es keine solche Strategie s gibt - würde nicht erklärt werden. Elektrolurch Kontakt 15:28, 16. Okt. 2013 (CEST)

"Unter Permutation abgeschlossen"?

Ich kann mir leider nicht erklären, was das bedeuten soll. "Unter $Funktion abgeschlossen" bedeutet üblicher Weise, dass die Menge unter $Funktion auf sich selbst abgebildet wird. Permutationen sind aber per definitionem die Bijektionen in sich selbst. Das würde also für beliebige Mengen gelten. Es müsste also eine Obermenge sein, die aber nicht angegeben ist. Wenn aber dies gilt, wird jene Abgeschlossenheit nur von den trivialen Teilmengen erfüllt. Das ergibt auch wenig Sinn. Also nehme ich mal an, dass Permutation hier etwas anderes bedeutet, als der verlinkte Artikel impliziert.

Und der Link unter "abgeschlossen" verweist auf topologische Abgeschlossenheit, was vermutlich auch nicht gemeint ist. --1of3 (Diskussion) 17:14, 8. Aug. 2014 (CEST)

Formel - h und y werden nicht erklärt

Für die Formel werden h und y nicht erklärt. --Zulu55 (Diskussion) _Unwissen 09:45, 8. Mär. 2016 (CET)