Was sind die relevanten Unterschiede - Leistung und Anwendungsfälle - zwischen simuliertem Annealing mit Bean-Suche und genetischem Algorithmus ?
>Ich weiß, dass SA als GA gedacht werden kann, wo die Populationsgröße nur eins ist, aber ich kenne den Hauptunterschied zwischen den beiden nicht.
Ich versuche auch, an eine Situation zu denken, in der SA GA übertrifft oder GA SA übertrifft, nur ein einfaches Beispiel, das mir helfen wird zu verstehen, wird ausreichen.
Genau genommen sind diese beiden Dinge - Simulated Annealing (SA) und genetische Algorithmen weder Algorithmen noch deren Zweck Data Mining.
Beide sind Meta-Heuristiken - ein paar Ebenen über dem "Algorithmus" auf der Abstraktionsskala. Mit anderen Worten, beide Begriffe beziehen sich auf Metaphern auf hoher Ebene - eine aus der Metallurgie und die andere aus der Evolutionsbiologie. In der meta-heuristischen Taxonomie ist SA eine single-state Methode und GA ist eine Populationsmethode (in einer Unterklasse zusammen mit PSO, ACO, etc.) bezeichnet als biologisch inspirierte Meta-Heuristiken ).
Diese beiden Meta-Heuristiken werden zur Lösung von Optimierungsproblemen verwendet, insbesondere (wenn auch nicht ausschließlich) in der kombinatorischen Optimierung (auch als Constraint-Satisfaction-Programming bezeichnet). Kombinatorische Optimierung bezieht sich auf die Optimierung, indem aus einer Menge von diskreten Elementen ausgewählt wird - mit anderen Worten, es gibt keine kontinuierliche Funktion zum Minimieren. Das Rucksackproblem, das Problem des reisenden Verkäufers, das Problem des Schneidens von Lagerbeständen - sind alles kombinatorische Optimierungsprobleme.
Die Verbindung zum Data Mining ist, dass der Kern vieler (meist?) betreuten Machine Learning (ML) -Algorithmen die Lösung eines Optimierungsproblems ist (zB Multi-Layer Perceptron und Support Vector Machines).
>Jede Lösungstechnik zur Lösung von Kappenproblemen, unabhängig vom Algorithmus, besteht im wesentlichen aus diesen Schritten (die typischerweise als ein einzelner Block innerhalb einer rekursiven Schleife codiert sind):
kodieren Sie die domänenspezifischen Details in einer Kostenfunktion (es ist die schrittweise Minimierung des Wertes kam von dieser Funktion zurück stellt eine "Lösung" für die c / o Problem);
wertet die Übergabe der Kostenfunktion aus in einer anfänglichen 'rate' (um zu beginnen Iteration);
basierend auf dem von der zurückgegebenen Wert Kostenfunktion, erzeuge eine nachfolgende Kandidatenlösung (oder mehr als einer, abhängig von der Meta-Heuristik) zu den Kosten Funktion;
wertet jede Kandidatenlösung nach es in einem Argument übergeben, um die Kostenfunktion;
Wiederholen Sie die Schritte (iii) und (iv) bis entweder ein Konvergenzkriterium ist zufrieden oder eine maximale Anzahl von Iterationen sind erreicht.
Meta-Heuristiken sind auf den obigen Schritt (iii) gerichtet; Daher unterscheiden sich SA und GA darin, wie sie Kandidatenlösungen für die Bewertung durch die Kostenfunktion generieren. Mit anderen Worten, das ist der richtige Ort, um zu verstehen, wie sich diese beiden Meta-Heuristiken unterscheiden.
Informell besteht die Essenz eines Algorithmus, der auf die Lösung der kombinatorischen Optimierung gerichtet ist, in der Behandlung einer Kandidatenlösung, deren von der Kostenfunktion zurückgegebener Wert schlechter als der aktuelle Wert ist Kandidatenlösung (diejenige, die den niedrigsten Wert aus der Kostenfunktion zurückgibt). Der einfachste Weg für einen Optimierungsalgorithmus, solch eine Kandidatenlösung zu handhaben, ist es, sie direkt abzulehnen - das ist es, was der Hill-Climbing-Algorithmus tut. Aber dadurch wird einfaches Bergsteigen immer eine bessere Lösung verpassen, die von der gegenwärtigen Lösung durch einen Hügel getrennt ist. Anders ausgedrückt muss ein ausgeklügelter Optimierungsalgorithmus eine Technik enthalten, um eine Kandidatenlösung (vorübergehend) besser als die aktuelle beste Lösung zu akzeptieren (dh bergauf), weil eine noch bessere Lösung als die aktuelle Lösung auf einem schlechteren Weg liegen könnte Lösung.
Wie also generieren SA und GA Kandidatenlösungen?
Die Essenz von SA wird normalerweise ausgedrückt als die Wahrscheinlichkeit, dass eine kostenintensivere Kandidatenlösung akzeptiert wird (der gesamte Ausdruck in der doppelten Klammer ist ein Exponent:
) %Vor%Oder in Python:
%Vor%Der Begriff "Temperatur" ist eine Variable, deren Wert während des Optimierungsvorgangs abklingt - und daher sinkt die Wahrscheinlichkeit, dass SA eine schlechtere Lösung akzeptiert, wenn die Iterationszahl zunimmt.
Anders ausgedrückt, wenn der Algorithmus beginnt, zu iterieren, ist T sehr groß, was, wie Sie sehen, den Algorithmus veranlasst, zu jeder neu erstellten Kandidatenlösung zu gehen, ob besser oder schlechter als die aktuelle beste Lösung - dh sie macht einen random walk im Lösungsraum. Wenn die Iterationszahl ansteigt (dh wenn sich die Temperatur abkühlt), wird die Suche des Lösungsraums durch den Algorithmus weniger permissiv, bis das Verhalten bei T = 0 identisch mit einem einfachen Hill-Climbing-Algorithmus ist (dh nur Lösungen, die besser sind als die aktuellen besten Lösung werden akzeptiert).
Genetische Algorithmen sind sehr unterschiedlich. Zum einen - und das ist eine große Sache - erzeugt es keine einzige Kandidatenlösung, sondern eine ganze "Population" von ihnen. Es funktioniert folgendermaßen: GA ruft die Kostenfunktion für jedes Mitglied (Kandidatenlösung) der Bevölkerung auf. Dann ordnet er sie, vom besten zum schlechtesten, geordnet nach dem Wert, der von der Kostenfunktion zurückgegeben wird ("beste" hat den niedrigsten Wert).Aus diesen Rangwerten (und den entsprechenden Kandidatenlösungen) wird die nächste Population erstellt. Neue Mitglieder der Bevölkerung werden im Wesentlichen auf drei Arten geschaffen. Das erste wird gewöhnlich als "Elitismus" bezeichnet und bezieht sich in der Praxis normalerweise darauf, nur die am höchsten bewerteten Kandidatenlösungen zu nehmen und sie unverändert - unverändert - an die nächste Generation weiterzugeben. Die anderen beiden Arten, auf die neue Mitglieder der Bevölkerung gewöhnlich als "Mutation" und "Crossover" bezeichnet werden. Mutation beinhaltet üblicherweise eine Änderung eines Elements in einem Kandidatenlösungsvektor von der aktuellen Population, um einen Lösungsvektor in der neuen Population zu erzeugen, z. B. [4, 5, 1, 0, 2] = & gt; [4, 5, 2, 0, 2]. Das Ergebnis der Überkreuzungsoperation ist wie das, was passieren würde, wenn Vektoren Sex haben könnten - d. H. Einen neuen Kindvektor, dessen Elemente aus jeweils zwei Elternteilen bestehen.
Das sind also die algorithmischen Unterschiede zwischen GA und SA. Was ist mit den Unterschieden in der Leistung?
In der Praxis: (Meine Beobachtungen beschränken sich auf kombinatorische Optimierungsprobleme) GA übertrifft fast immer SA (gibt einen niedrigeren "besten" Rückgabewert aus der Kostenfunktion zurück, dh einen Wert nahe dem globalen Minimum des Lösungsraums), aber bei höheren Rechenkosten. Soweit mir bekannt ist, wird in den Lehrbüchern und technischen Publikationen die gleiche Schlussfolgerung bezüglich der Auflösung angeführt.
Aber hier ist die Sache: GA ist inhärent parallelisierbar; Darüber hinaus ist es trivial, weil die einzelnen "Suchagenten", die jede Population umfassen, keine Nachrichten austauschen müssen - dh sie arbeiten unabhängig voneinander. Offensichtlich bedeutet das, dass GA-Berechnungen verteilt werden können , was bedeutet, dass in der Praxis viel bessere Ergebnisse (näher am globalen Minimum) und bessere Leistung (Ausführungsgeschwindigkeit) erzielt werden können.
Unter welchen Umständen könnte SA GA übertreffen? Das allgemeine Szenario, das ich denke, wären solche Optimierungsprobleme mit einem kleinen Lösungsraum, so dass das Ergebnis von SA und GA praktisch gleich ist, aber der Ausführungskontext (z. B. Hunderte von ähnlichen Problemen im Batch-Modus) bevorzugt den schnelleren Algorithmus (welcher sollte immer SA sein).
Es ist wirklich schwierig, die beiden zu vergleichen, da sie von verschiedenen Bereichen inspiriert wurden.
Ein genetischer Algorithmus hält eine Population von möglichen Lösungen aufrecht und wählt bei jedem Schritt Paare möglicher Lösungen aus, kombiniert sie (crossover) und wendet einige zufällige Änderungen (Mutationen) an. Der Algorithmus basiert auf der Idee des "Überlebens des Stärkeren", wobei der Auswahlprozess nach einem Fitnesskriterium durchgeführt wird (normalerweise ist er bei Optimierungsproblemen einfach der Wert der Zielfunktion, die mit der aktuellen Lösung bewertet wird). Der Übergang wird in der Hoffnung gemacht, dass zwei gute Lösungen, wenn sie kombiniert werden, eine noch bessere Lösung ergeben könnten.
Auf der anderen Seite verfolgt Simulated Annealing nur eine Lösung im Raum möglicher Lösungen und berücksichtigt bei jeder Iteration, ob zu einer benachbarten Lösung übergegangen werden soll oder in der aktuellen bleiben soll, abhängig von einigen Wahrscheinlichkeiten (die mit der Zeit abfallen). Dies unterscheidet sich von einer heuristischen Suche (sagen wir gierige Suche) darin, dass es nicht unter den Problemen des lokalen Optimums leidet, da es sich von Fällen lösen kann, in denen alle benachbarten Lösungen die schlechtesten sind.
Ich bin weit entfernt von einem Experten für diese Algorithmen, aber ich werde versuchen und helfen.
Ich denke, der größte Unterschied zwischen den beiden ist die Idee des Crossover in GA und jedes Beispiel einer Lernaufgabe, die besser für GA als für SA geeignet ist, hängt davon ab, was Crossover in dieser Situation bedeutet und wie es implementiert wird .
Die Idee des Crossover ist, dass Sie zwei Lösungen sinnvoll kombinieren können, um eine bessere zu erreichen. Ich denke, das macht nur Sinn, wenn die Lösungen für ein Problem in irgendeiner Weise strukturiert sind. Ich könnte mir zum Beispiel eine Mehrklassen-Klassifizierung vorstellen, die zwei (oder viele) Klassifikatoren verwendet, die gut darin sind, eine bestimmte Klasse zu klassifizieren und sie durch Abstimmung zu kombinieren, um einen viel besseren Klassifikator zu bilden. Ein anderes Beispiel könnte Genetic Programming sein, wo die Lösung als Baum ausgedrückt werden kann, aber ich finde es schwierig, darauf zu kommen Ein gutes Beispiel, bei dem Sie zwei Programme kombinieren können, um ein besseres zu erstellen.
Ich denke, es ist schwierig, einen zwingenden Fall für den anderen vorzubringen, weil sie wirklich sehr ähnliche Algorithmen sind, die vielleicht aus sehr unterschiedlichen Ausgangspunkten entwickelt wurden.