Friedrich-Alexander-Universität DruckenUnivisEnglish FAU-Logo
Techn. Fakultät Willkommen am Department Informatik FAU-Logo
Codesign
Lehrstuhl für Informatik 12
PSO
Home
Lehre/Teaching
Aufgaben/Administration
Publications
 

Department Informatik  >  Informatik 12  >  Personal  >  Rolf Wanka  >  Forschung

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.

Dissertationen

  • Manuel Schmitt.
    Convergence Analysis for Particle Swarm Optimization.
    Doktorarbeit, Universität Erlangen-Nürnberg,
    FAU University Press, 2015.
    (Zum Volltext)

  • Sabine Helwig.
    Particle Swarms for Constrained Optimization.
    Doktorarbeit, Universität Erlangen-Nürnberg, 2010.
    (Zum Volltext)

Publikationen

  • Raß, A.; Schreiner, J.; Wanka, R.:
    Runtime Analysis of Discrete Particle Swarm Optimization Applied to Shortest Paths Computation;
    in: Proc. 19th European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCOP), pp. 115-130, 2019.
    [doi:10.1007/978-3-030-16711-0_8]

  • Mühlenthaler, M.; Raß, A.; Schmitt, M.; Siegling, A.; Wanka, R.:
    Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax;;
    in: Proc. 14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA), pp. 13-24, 2017.
    [doi:10.1145/3040718.3040721]

  • Schwab, L.; Schmitt, M.; Wanka, R.:
    Multimodal Medical Image Registration Using Particle Swarm Optimization with Influence of the Data's Initial Orientation;
    in: Proc. 12th IEEE Conf. on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB), pp. 403-410, 2015. (More Information)
    [doi:10.1109/CIBCB.2015.7300314]

  • Raß, A.; Schmitt, M.; Wanka, R.:
    Explanation of Stagnation at Points that are not Local Optima in Particle Swarm Optimization by Potential Analysis;
    in: Companion of Proc. 17th Genetic and Evolutionary Computation Conference (GECCO); 2015, pp. 1463-1464, 2015. (More Information)
    [doi:10.1145/2739482.2764654]

  • Schmitt, M. ; Wanka, R.:
    Particle Swarm Optimization Almost Surely Finds Local Optima;
    Theoretical Computer Science, 561A (2015) 57-72. (Extended version of the GECCO 2013 paper, see below) (More Information)
    [doi:10.1016/j.tcs.2014.05.017]

  • Lange, V. ; Schmitt, M. ; Wanka, R.:
    Towards a Better Understanding of the Local Attractor in Particle Swarm Optimization: Speed and Solution Quality;
    in: Proc. International Conference on Adaptive and Intelligent Systems (ICAIS); 2014, to appear. (More Information)
    [doi:10.1007/978-3-319-11298-5_10]

  • Bassimir, B.; Schmitt, M.; Wanka, R.:
    How Much Forcing is Necessary to Let the Results of Particle Swarms Converge?
    in: Proc. Int. Conf. on Swarm Intelligence Based Optimization (ICSIBO), 2014, to appear. (More Information)

  • Schmitt, M.; Wanka, R.:
    Particle Swarm Optimization Almost Surely Finds Local Optima;
    in: Proc. 15th Genetic and Evolutionary Computation Conference (GECCO); pp. 1629-1636, 2013 [Best Paper Award]. (More Information)
    [doi:10.1145/2463372.2463563]

  • Schmitt, M.; Wanka, R.:
    Particles Prefer Walking Along the Axes: Experimental Insights into the Behavior of a Particle Swarm;
    in: Companion of Proc. 15th Genetic and Evolutionary Computation Conference (GECCO); pp. 17-18, 2013. (More Information)
    [doi:10.1145/2464576.2464583]

  • Helwig, S.; Branke, J.; Mostaghim, S.:
    Experimental Analysis of Bound Handling Techniques in Particle Swarm Optimization;
    IEEE Transactions on Evolutionary Computation, 17 (2013) 259-271.
    [doi:10.1109/TEVC.2012.2189404]

  • Hoffmann, M.; Mühlenthaler, M.; Helwig, S.; Wanka, R.:
    Discrete Particle Swarm Optimization for TSP: Theoretical Results and Experimental Evaluations;
    in: Proc. International Conference on Adaptive and Intelligent Systems (ICAIS); pp. 416-427, 2011. (More Information)
    [doi:10.1007/978-3-642-23857-4_40]

  • Omeltschuk, L.; Helwig, S.; Mühlenthaler, M.; Wanka, R.:
    Heterogeneous Constraint Handling for Particle Swarm Optimization;
    Proc. IEEE Swarm Intelligence Symposium (SIS), pp. 37-43, 2011. (More Information)
    [doi:10.1109/SIS.2011.5952578]

  • Helwig, S.; Neumann, F.; Wanka, R.:
    Velocity Adaptation in Particle Swarm Optimization;
    in: Handbook of Swarm Intelligence - Concepts, Principles and Applications, Springer, pp. 155-173, 2011. (More Information)
    [doi:10.1007/978-3-642-17390-5_7]

  • Ritscher, Th.; Helwig S.; Wanka, R.:
    Design and Experimental Evaluation of Multiple Adaptation Layers in Self-optimizing Particle Swarm Optimization;
    in: Proc. IEEE Congress on Evolutionary Computation (CEC) 2010. (More Information)
    [doi:10.1109/CEC.2010.5586255]

  • Helwig, S.; Neumann, F.; Wanka, R.:
    Particle Swarm Optimization with Velocity Adaptation;
    in: Proc. International Conference on Adaptive and Intelligent Systems (ICAIS); pp. 146-151, 2009. [Best Paper Award] (More Information)
    [doi:10.1109/ICAIS.2009.32]

  • Gnezdilov A.; Wittmann, S.; Helwig, S.; Kókai, G.:
    Acceleration of a Relative Positioning Framework
    International Journal of Computational Intelligence Research (IJCIR) 5(2) (2009) 130-140.
    [doi:10.5019/j.ijcir.2009.176]

  • Helwig, S.; Wanka, R.:
    Theoretical Analysis of Initial Particle Swarm Behavior;
    in: Proc. 10th International Conference on Parallel Problem Solving from Nature (PPSN); pp. 889-898, 2008. (More Information)
    [doi:10.1007/978-3-540-87700-4_88]

  • Jordan, J.; Helwig, S.; Wanka, R.:
    Social Interaction in Particle Swarm Optimization, the Ranked FIPS, and Adaptive Multi-Swarms;
    in: Proc. Genetic and Evolutionary Computation Conference (GECCO); pp. 49-56, 2008. (More Information)
    [doi:10.1145/1389095.1389103]

  • Stoll, T.; Wittmann, S.; Helwig S.; Paetzold, K.:
    Registration of measured and simulated non-ideal geometry using optimization methods;
    in: Proc. 10th CIRP International Seminar on Computer Aided Tolerancing; 10 pages, CD-ROM Proceedings, 2007. (More Information)

  • Helwig, S.; Wanka, R.:
    Particle Swarm Optimization in High-Dimensional Bounded Search Spaces;
    Proc. IEEE Swarm Intelligence Symposium (SIS), pp. 198-205, 2007. (More Information)
    [doi:10.1109/SIS.2007.368046]

Beendete Abschlußarbeiten

  • Florian Rühland.
    Untersuchung neuer Aktualisierungsmethoden bei der Partikelschwarmoptimierung mit abstoßenden Punkten.
    Masterarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, Januar 2019.

  • Jonas Schreiner.
    Laufzeitanalyse einer Variante der Partikelschwarmoptimierung angewandt auf das Kürzeste-Wege-Problem..
    Bachelorarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, Oktober 2018.

  • Alexander Hoen.
    Partikelschwarmoptimierung und das Rundreiseproblem.
    Masterarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg,Mai 2018.

  • Bernd Bassimir.
    Einbeziehung von Abstoßungsverhalten bei der Partikelschwarmoptimierung.
    Bachelorarbeit, Lehrstuhl für Informatik 12, Universität Erlangen-Nürnberg, Juli 2016.

  • Andreas Siegling.
    Entwurf, Implementierung und Analyse von Partikelschwarm-Algorithmen für das Sortierproblem.
    Bachelorarbeit, Lehrstuhl für Informatik 12, 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.
    Masterarbeit, Lehrstuhl für Informatik 12, 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.
  Impressum Stand: 25 July 2019.   R.W.