Bedeutung von (meta) heuristischen Methoden

10

  1. Zur Optimierung aus Wikipedia :

    In der Informatik bezeichnet Metaheuristik eine Berechnungsmethode, die ein Problem optimiert , indem iterativ versucht wird, eine Kandidatenlösung in Bezug auf ein bestimmtes Qualitätsmaß zu verbessern. Metaheuristiken machen nur wenige oder keine Annahmen über das zu optimierende Problem und können sehr große Räume von Kandidatenlösungen durchsuchen. Metaheuristiken garantieren jedoch nicht, dass jemals eine optimale Lösung gefunden wird. Viele Metaheuristiken implementieren irgendeine Form der stochastischen Optimierung.

    Andere Begriffe, die eine ähnliche Bedeutung wie metaheuristisch haben, sind: derivatfreie, direkte Suche, Black-Box oder einfach nur heuristischer Optimierer. Zu diesem Thema wurden mehrere Bücher und Umfragepapiere veröffentlicht.

    • Ich frage mich, wie ich feststellen kann, ob eine Optimierungsmethode metaheuristisch ist oder nicht. Zum Beispiel,

      (1) Ist die Simplex-Methode zur linearen Programmierung metaheuristisch?

      (2) Sind die meisten nichtlinearen Programmiermethoden wie Gradientenabstieg, Lagrange-Multiplikatormethode, Strafmethoden, Innenpunktmethoden (Barrieremethoden) metaheuristisch?

      (3) Sind alle gradientenfreien Methoden wie die Nelder-Mead-Methode oder die Downhill-Simplex-Methode metaheuristisch?

    • Welche Optimierungsmethoden sind nicht metaheuristisch?

  2. Allgemeiner (über die Optimierung hinaus) für Problemlösungstechniken aus Wikipedia :

    Heuristik bezieht sich auf erfahrungsbasierte Techniken zum Lösen, Lernen und Entdecken von Problemen . Wenn eine umfassende Suche nicht praktikabel ist, werden heuristische Methoden verwendet, um den Prozess der Suche nach einer zufriedenstellenden Lösung zu beschleunigen. Beispiele für diese Methode sind die Verwendung einer Faustregel, einer fundierten Vermutung, eines intuitiven Urteils oder des gesunden Menschenverstandes.

    Genauer gesagt sind Heuristiken Strategien, die leicht zugängliche, wenn auch lose anwendbare Informationen verwenden, um die Problemlösung bei Menschen und Maschinen zu steuern.

    Ich frage mich, wie ich die Bedeutung von "Heuristik" verstehen soll.

    • Wie kann ich feststellen, ob eine Technik zum Lösen, Lernen und Entdecken von Problemen heuristisch ist oder nicht?

    • Was sind einige "Problemlösungs-, Lern- und Entdeckungstechniken", die nicht heuristisch sind?

Danke und Grüße!

optimization heuristics Tim
quelle

Antworten:

7

Heuristik funktioniert in der Praxis in vielen Fällen, obwohl es kein detailliertes Argument dafür gibt, warum sie gut funktionieren sollte.

Die Metaheuristik ist kein Algorithmus, sondern ein allgemeines heuristisches Schema oder eine Idee, die in bestimmten Algorithmen verwendet werden kann.

Zum Beispiel ist der Simplex-Algorithmus für die lineare Programmierung weder Heuristik noch Metaheuristik, da er eine gut etablierte Konvergenztheorie hat. Das Quadrat gilt für sequentielle quadtatische Programmierung oder innere Punktmethoden. (Innenpunktmethoden sind ein allgemeines Schema, aber keine Heuristik und daher keine Metaheuristik, da damit eine ziemlich starke Theorie verbunden ist.)

Der Nelder-Mead = Downhill-Simplex-Algorithmus zur Minimierung einer Funktion ist eine Heuristik (er kann bei ganz einfachen Problemen in höheren Dimensionen tatsächlich fehlschlagen), und die Tabu-Suche ist eine Metaheuristik (da jedoch ziemlich viele verschiedene Algorithmen geschrieben werden können, die eine Tabu-Suche verwenden, aber sind sonst von ganz anderer Qualität.

Arnold Neumaier
quelle
Vielen Dank! (1) Um zu sagen, ob eine Methode metaheuristisch ist, muss man dann prüfen, ob sie eine Theorie darüber hat, wann sie zum wahren Optimierer konvergiert? Wenn eine Methode noch keine solche Theorie hat, ist sie dann fleischheuristisch? Wenn es eines Tages eine Theorie dafür gibt, wird sie dann von metaheuristisch zu nicht-metaheuristisch? (2) "Andere Begriffe, die eine ähnliche Bedeutung wie metaheuristisch haben, sind: derivatfreie, direkte Suche, Black-Box oder einfach nur heuristischer Optimierer." Ich frage mich, ob Metaheuristik nur Funktionswerte verwendet und ableitungsfrei ist. Ist es eine Suchmethode in Ihrer Antwort auf meine andere Frage?
Tim
@Tim: metaheuristisch bedeutet: (i) keine Konvergenztheorie und (ii) kein bestimmtes Verfahrensrezept, sondern allgemeine Prinzipien. - Derivatfrei (= direkte Suche = Black Box; unterschiedliche Namen für dasselbe aus unterschiedlichen historischen Wurzeln) kann heuristisch sein oder nicht; Es wird nur über die Eingabe informiert, die der Benutzer bereitstellen muss.
Arnold Neumaier
Vielen Dank! Ich frage mich, ob Metaheuristik nur Funktionswerte verwendet und ableitungsfrei ist.
Tim
@ Tim: Wahrscheinlich ja; Ich kenne nichts, was eigentlich Metaheuristik genannt wird und Gradienten verwendet.
Arnold Neumaier
7

Ich werde nicht über Simplex und Nelder-Mead iterieren, da @ArnoldNeumaier bereits eine sehr gute Erklärung gegeben hat, aber meine 2 Cent hinzufügen wollte.

Eines der besten Zitate, das ich vor einiger Zeit gehört habe, um den Unterschied zwischen Heuristik und Metaheuristik zu beschreiben: Eine Heuristik ist eine ziemlich gute Regel. Eine Metaheuristik ist eine ziemlich gute Regel, um ziemlich gute Regeln zu finden.

Sie sollten es nur als einen Weg sehen, gute Heuristiken für bestimmte Probleme zu finden. Wenn Sie sich eine der folgenden Fragen stellen, sprechen Sie im Grunde genommen von einer Metaheuristik:

  • Wie sollte ich die Parameter dieser Heuristik anpassen, um die Leistung bei diesem Problem zu verbessern?
  • Ist diese Heuristik besser als diese Heuristik?

Es gibt eine Reihe von Metaheuristiken, die Sie zum Lösen, Lernen und Entdecken von Problemen verwenden können , nämlich:

Ich finde, dass die meisten Metaheuristiken etwas von natürlichen Phänomenen inspiriert sind, die schwer genau zu erklären sind, aber gute Konvergenzeigenschaften haben.

Hier ist ein guter Link, wenn Sie mehr über andere metaheuristische Techniken erfahren möchten

Charles Menguy
quelle
Vielen Dank! Ich bin mir nicht sicher, ob ich verstehe: "Eine Heuristik ist eine ziemlich gute Regel. Eine Metaheuristik ist eine ziemlich gute Regel, um ziemlich gute Regeln zu finden." Sind beispielsweise simuliertes Tempern, Partikelschwarm, Ameisenkolonie und Tabu-Suche heuristisch oder metaheuristisch? Wenn sie einer der beiden sind, was sind ihre Gegenstücke für den anderen?
Tim
Was Sie aus diesem Zitat verstehen sollten, ist, dass sowohl Heuristiken als auch Metaheuristiken weder exakt noch bewiesen sind, also "ziemlich gute Regel". Eine Metaheuristik befindet sich auf einer höheren Ebene als eine Heuristik. Durch mehrere aufeinanderfolgende Iterationen können Sie eine Reihe von Parametern finden, mit denen ein Problem korrekt gelöst werden kann. Wenn Sie von Anfang an wüssten, was dieser Parametersatz ist, müssten Sie nur eine Heuristik schreiben, um das Problem zu lösen. Da Sie es jedoch nicht wissen, müssen Sie einen Algorithmus verwenden, um diese Parameter für Ihre Heuristik zu finden: eine Metaheuristik. Hoffe das klärt sich.
Charles Menguy
Und die Algorithmen, die ich hier gegeben habe, sind alle Metaheuristiken, und Sie können weitere Details auf dem Link finden, den ich gegeben habe. Ich bin mir nicht sicher, was Sie genau für Kollegen meinen.
Charles Menguy
Mit Gegenstücken meine ich zum Beispiel, wenn die Algorithmen alle Metaheuristiken sind, müssen die Heuristiken, mit denen sie arbeiten, selbst plus spezifische Werte für ihre einstellbaren Parameter sein?
Tim
Nehmen Sie zum Beispiel simuliertes Glühen. Was es am Ende tut, ist eine Suche in einer Markov-Kette. Die "Regel" der Heuristik wäre anzunehmen, dass ein Zustand in der Markov-Kette die Lösung ist. Die Metaheuristik sucht nach Konvergenz in der Markov-Kette, um den optimalen Zustand zu finden, der die Lösung beschreibt. Im Allgemeinen sollten Sie sich nicht zu sehr bemühen, die Unterscheidung zu treffen: Verwenden Sie Heuristiken, wenn es eine "relativ" einfache Lösung gibt, die leicht berechnet werden kann, und Metaheuristiken, wenn der Lösungsraum zu groß ist und Sie klüger sein müssen Lösung des Problems.
Charles Menguy