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
- Schmitt M., Wanka R., Schwab L.:
Multimodal Medical Image Registration Using Particle Swarm Optimization with Influence of the Data's Initial Orientation
12th IEEE Conf. on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB) (Niagara Falls)
In: Proc. 12th IEEE Conf. on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB) 2015
DOI: 10.1109/CIBCB.2015.7300314
BibTeX: Download - Raß A., Schmitt M., Wanka R.:
Explanation of Stagnation at Points that are not Local Optima in Particle Swarm Optimization by Potential Analysis
17th Genetic and Evolutionary Computation Conference (GECCO) (Madrid, Spain, 11. July 2015 - 15. July 2015)
In: ACM New York, NY, USA (ed.): Companion of Proc. 17th Genetic and Evolutionary Computation Conference (GECCO) 2015
DOI: 10.1145/2739482.2764654
BibTeX: Download - Schmitt M., Wanka R.:
Particle Swarm Optimization Almost Surely Finds Local Optima
Genetic and Evolutionary Computation Conference (GECCO) (Amsterdam)
In: Proc. 15th Genetic and Evolutionary Computation Conference 2013
DOI: 10.1145/2463372.2463563
BibTeX: Download - Schmitt M., Wanka R.:
Particle Swarm Optimization Almost Surely Finds Local Optima
In: Theoretical Computer Science 561A (2015), p. 57-72
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2014.05.017
BibTeX: Download - Lange V., Schmitt M., Wanka R.:
Towards a Better Understanding of the Local Attractor in Particle Swarm Optimization: Speed and Solution Quality
International Conference on Adaptive and Intelligent Systems (ICAIS) (Bournemouth, UK, 8. September 2014 - 10. September 2014)
In: Proc. International Conference on Adaptive and Intelligent Systems (ICAIS) 2014
DOI: 10.1007/978-3-319-11298-5_10
URL: https://www12.informatik.uni-erlangen.de/people/rwanka/publications/LSW14.php
BibTeX: Download - Bassimir B., Schmitt M., Wanka R.:
How Much Forcing is Necessary to Let the Results of Particle Swarms Converge?
International Conference on Swarm Intelligence Based Optimization (ICSIBO)
In: Proc. Int. Conf. on Swarm Intelligence Based Optimization (ICSIBO) 2014
DOI: 10.1007/978-3-319-12970-9_11
URL: http://www12.cs.fau.de/people/rwanka/publications/BSW14.php
BibTeX: Download - Schmitt M., Wanka R.:
Particles Prefer Walking Along the Axes: Experimental Insights into the Behavior of a Particle Swarm
Genetic and Evolutionary Computation Conference (GECCO) (Amsterdam, 6. July 2013 - 10. July 2013)
In: Companion of Proc. 15th Genetic and Evolutionary Computation Conference 2013
DOI: 10.1145/2464576.2464583
BibTeX: Download - Hoffmann M., Mühlenthaler M., Helwig S., Wanka R.:
Discrete Particle Swarm Optimization for TSP: Theoretical Results and Experimental Evaluations
International Conference on Adaptive and Intelligent Systems (ICAIS) (Klagenfurt)
In: Bouchachia A. (ed.): Proc. International Conference on Adaptive and Intelligent Systems (ICAIS), Berlin, Heidelberg: 2011
DOI: 10.1007/978-3-642-23857-4_40
BibTeX: Download - Omeltschuk L., Helwig S., Mühlenthaler M., Wanka R.:
Heterogeneous Constraint Handling for Particle Swarm Optimization
IEEE Swarm Intelligence Symposium (SIS) (Paris, 11. April 2011 - 15. April 2011)
In: Proc. IEEE Swarm Intelligence Symposium (SIS), New York, NY, USA: 2011
DOI: 10.1109/SIS.2011.5952578
BibTeX: Download - Helwig S., Neumann F., Wanka R.:
Particle Swarm Optimization with Velocity Adaptation
International Conference on Adaptive and Intelligent Systems (ICAIS'09) (Klagenfurt, Austria, 24. September 2009 - 26. September 2009)
In: Proc. 2009 International Conference on Adaptive and Intelligent Systems 2009
DOI: 10.1109/ICAIS.2009.32
URL: http://www12.informatik.uni-erlangen.de/people/helwig/publications/HNW09.php
BibTeX: Download - Helwig S., Neumann F., Wanka R.:
Velocity Adaptation in Particle Swarm Optimization
In: Handbook of Swarm Intelligence, Heidelberg: Springer, 2011, p. 155-173 (Adaptation, Learning, and Optimization (ALO), Vol.8)
DOI: 10.1007/978-3-642-17390-5_7
URL: https://www12.cs.fau.de/people/rwanka/publications/HNW11.php
BibTeX: Download - Ritscher T., Helwig S., Wanka R.:
Design and Experimental Evaluation of Multiple Adaptation Layers in Self-optimizing Particle Swarm Optimization
IEEE Congress on Evolutionary Computation (Barcelona, 18. July 2010 - 23. July 2010)
In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2010) 2010
DOI: 10.1109/CEC.2010.5586255
URL: http://www12.informatik.uni-erlangen.de/people/rwanka/publications/RHW10.php
BibTeX: Download - Gnezdilov A., Wittmann S., Helwig S., Kókai G.:
Acceleration of a Relative Positioning Framework
In: International Journal of Computational Intelligence Research 5 (2009), p. 130-140
ISSN: 0973-1873
DOI: 10.5019/j.ijcir.2009.176
BibTeX: Download - Helwig S., Wanka R.:
Theoretical Analysis of Initial Particle Swarm Behavior
10th International Conference on Parallel Problem Solving from Nature (PPSN08) (Dortmund, 13. September 2008 - 17. September 2008)
In: Proceedings of the 10th International Conference on Parallel Problem Solving from Nature, Berlin, Heidelberg: 2008
DOI: 10.1007/978-3-540-87700-4_88
URL: http://www12.informatik.uni-erlangen.de/people/helwig/publications/HW08.php
BibTeX: Download - Jordan JM., Helwig S., Wanka R.:
Social Interaction in Particle Swarm Optimization, the Ranked FIPS, and Adaptive Multi-Swarms
Genetic and Evolutionary Computation Conference (GECCO08) (Atlanta, Georgia, 12. July 2008 - 16. July 2008)
In: ACM Press (ed.): Proceedings of the Genetic and Evolutionary Computation Conference 2008
DOI: 10.1145/1389095.1389103
URL: http://www12.informatik.uni-erlangen.de/people/helwig/publications/JHW08.php
BibTeX: Download - Paetzold K., Wittmann S., Stoll T., Helwig S.:
Registration of measured and simulated non-ideal geometry using optimization methods.
10th CIRP International Seminar on Computet Aided Tolerancing (Erlangen)
In: International Seminar on Computet Aided Tolerancing 2007
BibTeX: Download - Helwig S., Wanka R.:
Particle Swarm Optimization in High-Dimensional Bounded Search Spaces
IEEE Swarm Intelligence Symposium 2007 (Honolulu, Hawaii, 1. April 2007 - 5. April 2007)
In: Proceedings of the 2007 IEEE Swarm Intelligence Symposium 2007
DOI: 10.1109/SIS.2007.368046
URL: http://www12.informatik.uni-erlangen.de/people/helwig/publications/HW07.php
BibTeX: Download - Mühlenthaler M., Raß A., Schmitt M., Siegling A., Wanka R.:
Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax
Conference on Foundations of Genetic Algorithms (FOGA) (Copenhagen, Denmark, 12. January 2017 - 15. January 2017)
In: ACM New York, NY, USA (ed.): Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms 2017
DOI: 10.1145/3040718.3040721
BibTeX: Download - Raß A., Schmitt M., Wanka R.:
Explanation of Stagnation at Points that are not Local Optima in Particle Swarm Optimization by Potential Analysis [Extended Version]
(2015)
URL: https://arxiv.org/abs/1504.08241
BibTeX: Download - Raß A., Schreiner J., Wanka R.:
Runtime Analysis of Discrete Particle Swarm Optimization Applied to Shortest Paths Computation
19th European Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCOP) (Leipzig, 24. April 2019 - 26. April 2019)
In: Springer International Publishing (ed.): Evolutionary Computation in Combinatorial Optimization, Cham: 2019
DOI: 10.1007/978-3-030-16711-0_8
BibTeX: Download - Bassimir B., Raß A., Schmitt M.:
Theory of particle swarm optimization: A survey of the power of the swarm’s potential
In: it - Information Technology 61 (2019), p. 169–176
ISSN: 1611-2776
DOI: 10.1515/itit-2019-0004
BibTeX: Download - Mühlenthaler M., Raß A.:
Runtime analysis of discrete particle swarm optimization algorithms: A survey
In: it - Information Technology 61 (2019), p. 177–185
ISSN: 1611-2776
DOI: 10.1515/itit-2019-0009
BibTeX: Download - Wanka R.:
Swarm Intelligence
In: it - Information Technology 61 (2019), p. 157-158
ISSN: 1611-2776
DOI: 10.1515/itit-2019-0034
BibTeX: Download - Raß A.:
High Precision Particle Swarm Optimization Algorithm (HiPPSO)
In: Journal of Open Research Software 8 (2020), p. 4
ISSN: 2049-9647
DOI: 10.5334/jors.282
URL: https://openresearchsoftware.metajnl.com/articles/10.5334/jors.282/
BibTeX: Download - Bassimir B., Schmitt M., Wanka R.:
Self-adaptive potential-based stopping criteria for Particle Swarm Optimization with forced moves
In: Swarm Intelligence (2020)
ISSN: 1935-3812
DOI: 10.1007/s11721-020-00185-z
BibTeX: Download - Schmitt M.:
Convergence Analysis for Particle Swarm Optimization (Dissertation, 2015)
URL: https://nbn-resolving.org/urn:nbn:de:bvb:29-opus4-61621
BibTeX: Download - Helwig S.:
Particle Swarms for Constrained Optimization (Dissertation, 2010)
URL: https://nbn-resolving.org/urn:nbn:de:bvb:29-opus-19334
BibTeX: Download - Mühlenthaler M., Raß A., Schmitt M., Wanka R.:
Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax
In: Natural Computing (2021)
ISSN: 1567-7818
DOI: 10.1007/s11047-021-09856-0
BibTeX: Download
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.