Partikelschwarm-Optimierung

Dieser Forschungsschwerpunkt beschäftigt sich mit der Untersuchung der Metaheuristik der sog. Partikelschwärme. Dabei wird bei einem Optimierungsproblem der Raum der zulässigen Lösungen von einem sog. Schwarm von Individuen, die Einzellösungen darstellen, erkundet. Ein einzelnes Individuum bewegt sich dabei durch den Lösungsraum, indem es seine eigene bislang beste Lösung und die Lösungen anderer Individuen auswertet und kombiniert. Das Verfahren ist inspiriert vom Verhalten von Vögel- und Fischschwärmen.

Der allgemeine Partikelschwarm erkundet in der Regel einen in alle Richtungen unbeschränkten Lösungsraum. Jedoch ergibt sich regelmäßig aus den Anwendungen, dass die Lösungen nur aus einem eingeschränkten Bereich gewählt werden dürfen. D.h. wenn ein Individuum den Lösungsraum verlassen will, muss das Verfahren so angepasst werden, dass letztlich keine unzulässigen Lösungen ausgegeben werden dürfen. Wir untersuchen eine Reihe von solchen Bound-Handling-Methoden analytisch und experimentell und können einige »Daumenregeln« aufstellen, wie solche Methoden aussehen sollten. Insbesondere können wir zeigen, dass sich Partikel gerade am Anfang der Berechnung mit sehr hoher Wahrscheinlichkeit sehr nah an den Lösungsraumgrenzen befinden, was häufig dazu führt, dass sie sich gerade dort, weit weg von der optimalen Lösung, festsetzen.

Wir untersuchen auch, welche anderen Individuen ein Individuum konsultieren sollte, um seine neue Position zu bestimmen. Neben der Anfrage nach der bislang besten eigenen und der bislang besten globalen sind Netzwerkstrukturen zwischen den Individuen vorstellbar. Wir erforschen den Einfluss solcher Netzwerkstrukturen auf die Geschwindigkeit, mit der sich der Schwarm auf eine Lösung festlegt, die Qualität von Lösungen, den Zusammenhalt des Schwarms, und wir untersuchen, wie man diese Netzwerkstruktur ggf. während der Ausführung dynamisch ändern kann, um Verbesserungen im Schwarmverhalten hervorzurufen.

Publikationen


Beendete Abschlußarbeiten

  • Andreas Siegling.
    Entwurf, Implementierung und Analyse von Partikelschwarm-Algorithmen für das Sortierproblem.
    Universität Erlangen-Nürnberg, April 2015.
  • Alexander Raß.
    Explanation of Stagnation at Points that are not Local Optima in Particel Swarm Optimization by Potential Analysis.
    Universität Erlangen-Nürnberg, November 2014.
  • Lydia Schwab.
    Einsatz der Partikelschwarmoptimierung zur Bildregistrierung in der medizinischen Bildverarbeitung.
    Masterarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, Juli 2014.
  • Franz Köferl.
    Experimentelle Untersuchung des Einflusses von Bound-Handling-Strategien auf die Partikel-Verteilung bei der Partikelschwarmoptimierung.
    Bachelorarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, Mai 2014.
  • Bernd Bassimir.
    Experimentelle Untersuchung der Forced-Steps-Variante der Partikelschwarmoptimierung.
    Bachelor-Arbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, Mai 2014.
  • Vanessa Lange.
    Einfluss des lokalen Attraktors bei der Partikelschwarmoptimierung.
    Bachelor-Arbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, März 2014.
  • Daniel Zink.
    Partikelschwarmoptimierung für das Graphfärbungsproblem.
    Bachelor-Arbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, März 2012.
  • Andreas Fischer.
    Partikelschwarmoptimierung für das Set Cover Problem.
    Bachelor-Arbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, September 2011.
  • Matthias Hoffmann.
    Partikelschwarmoptimierung für das TSP.
    Studienarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, November 2010.
  • Valerian Brem.
    Analyse und Erweiterung eines selbstoptimierenden Partikelschwarms.
    Studienarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, Mai 2010.
  • Ludmilla Omeltschuk.
    Anwendung von Constraint-Handling-Methoden in der Partikelschwarmoptimierung.
    Studienarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, März 2010.
  • Thomas Ritscher.
    Konzeption eines selbstoptimierenden Partikelschwarms.
    Studienarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, April 2009.
  • Matthias Gleiß.
    Einsatz von Methoden der Partikelschwarmoptimierung zur Lösung des MaxSAT-Problems.
    Diplomarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, August 2007.
  • Johannes Jordan.
    Dynamische Nachbarschaftsgraphen in der Partikelschwarmoptimierung.
    Studienarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, Juli 2007.