Particle Swarms for Constrained Optimization

Partikelschwärme für Optimierungsprobleme mit Nebenbedingungen

Please always quote using this URN: urn:nbn:de:bvb:29-opus-19334
  • Particle swarm optimization (PSO) is an optimization approach from the field of artificial intelligence. A population of so-called particles moves through the parameter space defined by the optimization problem, searching for good solutions. Inspired by natural swarms, the movements of the swarm members depend on own experiences and on the experiences of adjacent particles. PSO algorithms are mainly used for continuous optimization problems, whose feasible space is often restricted by a set of constraints. A special case are box constraints, which define upper and lower bounds for the problem parameters. In the literature, there exist several so-called bound handling strategies to integrateParticle swarm optimization (PSO) is an optimization approach from the field of artificial intelligence. A population of so-called particles moves through the parameter space defined by the optimization problem, searching for good solutions. Inspired by natural swarms, the movements of the swarm members depend on own experiences and on the experiences of adjacent particles. PSO algorithms are mainly used for continuous optimization problems, whose feasible space is often restricted by a set of constraints. A special case are box constraints, which define upper and lower bounds for the problem parameters. In the literature, there exist several so-called bound handling strategies to integrate box constraints in PSO algorithms, such as setting infeasible particles to the nearest feasible position or reflecting them at the boundary. In this thesis, various aspects of box-constrained particle swarm optimization are examined. The core of this work is the theoretical analysis of the impact of box constraints for particle swarm optimization. It is shown mathematically that initial particle swarm performance strongly depends on the chosen bound handling strategy due to the fact that, with overwhelming probability, many particles leave the feasible space at the beginning of the optimization. Moreover, by using a simplified PSO model, is shown that this effect can be reduced if particle velocities are scaled with respect to the problem dimensionality. A thorough experimental evaluation shows that bound handling also significantly influences the final solution quality of a particle swarm optimizer, especially when applied to high-dimensional problems. Three way to cope with these results in practical PSO applications are presented: The careful selection of bound handling strategies, the use of self-adaptation, and the use of velocity adaptation. Finally, the investigated PSO algorithms are applied to an optimization problem from the field of mechanical engineering.show moreshow less
  • Partikelschwarmoptimierung (PSO) ist ein Optimierungsverfahren aus dem Bereich der Künstlichen Intelligenz. Eine Population sogenannter Partikel bewegt sich auf der Suche nach guten Lösungen durch den durch das Optimierungsproblem festgelegten Suchraum. Inspiriert von natürlichen Schwärmen, hängen die Bewegungen der Schwarmmitglieder sowohl von eigenen Erfahrungen als auch von den Erfahrungen benachbarter Partikel ab. PSO-Algorithmen werden vor allem für kontinuierliche Optimierungsprobleme eingesetzt, deren Gültigkeitsbereich oftmals durch eine Reihe von Nebenbedingungen beschränkt ist. Als Spezialfall hat der Gültigkeitsbereich die Form eines hochdimensionalen Quaders, d.h., für jedenPartikelschwarmoptimierung (PSO) ist ein Optimierungsverfahren aus dem Bereich der Künstlichen Intelligenz. Eine Population sogenannter Partikel bewegt sich auf der Suche nach guten Lösungen durch den durch das Optimierungsproblem festgelegten Suchraum. Inspiriert von natürlichen Schwärmen, hängen die Bewegungen der Schwarmmitglieder sowohl von eigenen Erfahrungen als auch von den Erfahrungen benachbarter Partikel ab. PSO-Algorithmen werden vor allem für kontinuierliche Optimierungsprobleme eingesetzt, deren Gültigkeitsbereich oftmals durch eine Reihe von Nebenbedingungen beschränkt ist. Als Spezialfall hat der Gültigkeitsbereich die Form eines hochdimensionalen Quaders, d.h., für jeden Parameter des Optimierungsproblems sind obere und untere Schranken festgelegt. In der Literatur existieren zahlreiche Möglichkeiten, quaderförmige Suchraumbeschränkungen in PSO-Algorithmen zu integrieren. So können ungültige Partikel beispielsweise auf die Suchraumgrenze gesetzt oder an dieser reflektiert werden. In dieser Arbeit wird das Verhalten von Partikelschwärmen in beschränkten Suchräumen untersucht. Kern der Arbeit ist die theoretische Analyse der Anwendung von PSO-Algorithmen auf Optimierungsprobleme mit quaderförmigen Suchraumbeschränkungen. Es wird bewiesen, dass viele Partikel den Gültigkeitsbereich zu Beginn der Optimierung mit überwältigender Wahrscheinlichkeit verlassen. Als Konsequenz ergibt sich, dass die Art und Weise, wie ungültige Partikel behandelt werden, großen Einfluss auf das anfängliche Schwarmverhalten hat. Unter Verwendung eines vereinfachten PSO-Modells wird weiterhin gezeigt, dass dieser Effekt reduziert werden kann, wenn die Partikelgeschwindigkeiten an die Suchraumdimensionalität angepasst werden. Ausführliche experimentelle Studien zeigen, dass, insbesondere bei Anwendung auf hochdimensionale Optimierungsprobleme, die Strategie der Behandlung ungültiger Partikel auch auf die finale Lösungsqualität signifikanten Einfluss hat. Es werden drei Möglichkeiten vorgestellt, mit diesen Resultaten in der Praxis umzugehen: Die sorgfältige Auswahl von Strategien zur Behandlung ungültiger Partikel, die Verwendung von Selbstadaption und der Einsatz von Geschwindigkeitsadaption. Abschließend werden die untersuchten PSO-Algorithmen auf ein Optimierungsproblem aus dem Bereich Maschinenbau angewendet.show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Sabine Helwig
URN:urn:nbn:de:bvb:29-opus-19334
Advisor:Rolf Wanka
Document Type:Doctoral Thesis
Language:English
Year of Completion:2010
Publishing Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Granting Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Technische Fakultät
Date of final exam:2010/07/19
Release Date:2010/07/29
Tag:Global optimization; Particle swarm optimization
SWD-Keyword:Partikel-Schwarm-Optimierung; Globale Optimierung
Institutes:Technische Fakultät / Technische Fakultät -ohne weitere Spezifikation-
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
open_access (DINI-Set):open_access