entsprechende Codierung Particle Swarm Optimization

Question

Das Problem

Ich habe auf Particle Swarm Optimization ein wenig Forschung zu tun, so dass ich sagte, ich es auf die Probe gestellt würde.

Das Problem, das ich zu lösen versuche, ist das Balanced Partition Problem - oder reduziert einfach auf das Subset Sum Problem (wo die Summe die Hälfte aller Zahlen ist).

Es scheint die allgemeine Formel für Geschwindigkeiten für Partikel Aktualisierung ist

aber ich werde nicht für diese Frage zu sehr ins Detail gehen.

Da es keinen PSO-Versuch online für das Subset-Sum-Problem gibt, schaute ich stattdessen auf das Problem des reisenden Verkäufers.

Sie sind Ansatz für die Aktualisierung der Geschwindigkeiten beteiligten Gruppen von besuchten Städten, Subtrahieren voneinander und einige Manipulation daran.

Ich sah keine Beziehung zwischen diesem und der obigen Formel.

Mein Ansatz

So verschrottet ich die Formel und versuchte, meine eigene Herangehensweise an das Subset-Sum Problem.

Ich verwendete im Wesentlichen gbest und pbest, um die Wahrscheinlichkeit des Entfernens oder Hinzufügen eines bestimmten Elements zu der Teilmenge zu bestimmen.

also - wenn mein Problemraum ist [1,2,3,4,5] (Ziel ist 7 oder 8) und meine aktuellen Teilchen (Subset) hat [1,None,3,None,None] und die gbest ist [None,2,3,None,None] dann gibt es eine höhere Wahrscheinlichkeit des Haltens 3 ist, Hinzufügen 2 und 1 Entfernen , basierend auf

Ich kann Code aber nicht denken, dass es notwendig ist, erhalten Sie die Idee (ich benutze Python BTW - daher None).

Also im Grunde funktionierte das bis zu einem gewissen Grad, ich bekam anständige Lösungen, aber es war sehr langsam bei größeren Datensätzen und Werten.

Meine Frage

Bin ich das Problem kodieren, und die Teilchen „Geschwindigkeiten“ auf intelligente Weise zu aktualisieren?

Gibt es eine Möglichkeit festzustellen, ob dies korrekt konvergiert?

Gibt es eine Ressource, die ich verwenden kann, um zu lernen, wie konvergente "update" -Formeln für bestimmte Problembereiche erstellt werden?

Vielen Dank im Voraus!

Answer 1

Encoding

Ja, Sie codieren, dies richtig: jede Ihrer Bit-Karten (das ist effektiv, was Ihre 5-Elemente-Listen sind) ist ein Teilchen.

Konzept

Ihr konzeptionelles Problem mit der Gleichung ist, weil Ihr Problem Raum ein diskretes Gitter Graph ist, der sich nicht sofort Schritt zum Update verleihen. Zum Beispiel, wenn Sie eine feinere Granularität erhalten möchten, indem Sie Ihre Lernrate anpassen, reduzieren Sie diese im Allgemeinen um einen kleinen Faktor (zB 3). Was bedeutet es in diesem Raum, Schritte nur 1/3 so groß zu machen? Deshalb hast du Probleme.

Die Hauptmöglichkeit, die ich sehe, ist, 3x so viele Partikel zu erzeugen, aber dann die Übergangswahrscheinlichkeiten alle durch 3 zu teilen. Dies genügt immer noch nicht sehr gut, aber es simuliert den Prozess etwas anständig.

Discrete Steps

Wenn Sie einen sehr großen Graphen haben, wo eine hohe Geschwindigkeit Sie Dutzende von Übergängen in einem Schritt geben könnte, können Sie eine glattere Abstand (Verlust oder Fehler) nutzen Funktion Ihr Modell führen . Mit etwas so Kleinem, wo man nicht mehr als 5 Schritte zwischen zwei Positionen hat, ist es schwer mit einem solchen Konzept zu arbeiten.

Stattdessen verwenden Sie eine Fehlerfunktion basierend auf der geschätzten Entfernung zur Lösung. Der einfachste ist es, die Gesamtmenge des Partikels von der Näherung von 7 oder 8 zu subtrahieren. Eine größere Schwierigkeit besteht darin, basierend auf dieser Differenz und den Partikelelementen "im Spiel" die Entfernung zu schätzen.

Nachweis der Konvergenz

Ja, es gibt einen Weg, es zu tun, aber es erfordert eine gewisse funktionelle Analyse. Im Allgemeinen möchten Sie demonstrieren, dass die Fehlerfunktion über den Partikelraum konvex ist. Mit anderen Worten, Sie müssten beweisen, dass Ihre Fehlerfunktion eine zuverlässige Entfernungsmetrik ist, zumindest was die relative Platzierung betrifft (beweisen Sie, dass ein niedrigerer Fehler bedeutet, dass Sie näher an einer Lösung sind).

Update Erstellen von Formeln

Nein, das ein heuristisches Feld ist anhand der Form des Problemraumes, wie durch die Partikelkoordinaten definiert, die Fehlerfunktion und die Bewegungseigenschaften.

Extra-Empfehlung

Ihre aktuellen zulässigen Übergänge "add" und "Löschen" Element. Fügen Sie "swap elements" hinzu: Tauschen Sie ein anwesendes Mitglied gegen ein abwesendes Mitglied aus. Dies ermöglicht der trivialen Fehlerfunktion, einen konvexen Raum für Sie zu definieren, und Sie werden in sehr kurzer Zeit zusammenlaufen.