Inhaltsverzeichnis

Abk  ürzungsverzeichnis  II

Variablenverzeichnis   III

Abbildungsverzeichnis   V

Tabellenverzeichnis   VI

1.  Einleitung  1

2.  Themenfelder und Grundlagen  2

2.1  Elektrochemische Bearbeitung: Prinzip und Modell  2

2.2  Die Partikelschwarmoptimierung  5

2.2.1  Geschichte und Funktionsweise  6

2.2.2  Ergebnisbeeinflussende Faktoren  10

2.2.3  Vereinfachungen und Abwandlungen  15

2.3  Betrachtung der PSO-Parameterwahl zur Lösung des EC-MProblems nach Rao et al.  17

2.4  Grundlagen der Empirischen Analyse  19

2.4.1  Überblick  19

2.4.2  Methoden  21

3.  Untersuchung zur optimierten Parameterwahl bei der Partikelschwarmoptimierung  28

3.1  Planung und Erhebung  28

3.2  Datenanalyse  30

3.2.1  Deskriptive Datenanalyse  30

3.2.2  Vergleich mit den Ergebnissen bei hoher Vektorbegrenzung  49

3.2.3  Analyse der Regionen guter Parameterqualität  51

3.2.4  Stellungnahme zur Parameterwahl von Rao et al. und der Lösung des ECM  54

3.3  Stichprobenbasierter Algorithmus zur automatischen Parameterwahl  58

3.3.1  Prinzip und Programmierung  58

3.3.2  Funktionalität und Laufzeit  60

4.  Fazit  62

Literaturverzeichnis   64

Anhang   66

I

Abkürzungsverzeichnis

DB ……………………………………..Datenbank

ECM …………………………………….Electrochemical Machining

PSO ……………………………..………Partikelschwarmoptimierung

RgP ………………………..…….…….Region guter Parameterqualität

StAbw ………………………………..…..Standardabweichung

ZF …………………………………….Zielfunktion

II

Variablenverzeichnis

a j ……………………………………Wert j aus der Erhebung

……………………………………Gewichtung des persönlich/ global besten Ergebnisses c p/g

d ……………………………………Dimension

f ……………………………………Dimension der Abtragmenge (ECM)

f* ……………………………………Beste Ausprägung der Dimension f

f(a j ) ……………………………………relative Häufigkeit von a j

gbest ……………………………………Index des Partikel mit dem global besten Ergebnis

gbestx/-y ……………………………………x-/-y-Koordinate des global besten Ergebnisses

g_increment ……………………………………Gewichtung des global besten Ergebnisses

h(a j ) ……………………………………Absolute Häufigkeit von a j

H(x) ……………………………………Kumulierte Häufigkeitsverteilung des Merkmal X

p id ……………………………………s. pbest; von Partikel i in Dimension d

pbest ……………………………………Wert des persönlich besten Ergebnisses

pbestx/-y ……………………………………x-/-y-Koordinate des persönlich besten Ergebnisses

p_increment ……………………………………Gewichtung des persönlich besten Ergebnisses

presentx/ -y ……………………………………Gegenwärtige x-/-y-Koordinate

M

……………………………………Gewichtung des persönlich/ global besten Ergebnisses

p g /

r ……………………………………Zufallsvariable

rand() ……………………………………Zufallsvariable

s s ……………………………………Standardabweichung

² s ² s ……………………………………Varianz

² s ……………………………………Varianz einer Stichprobe

III

t ……………………………………Zeitpunkt

U ……………………………………Dimension der Fließgeschwindigkeit des Elektrolyt (ECM)

U* ……………………………………Beste Ausprägung der Dimension U

V ……………………………………Dimension der angelegten Stromspannung (ECM)

V* ……………………………………Beste Ausprägung der Dimension V

V max ……………………………………Vektorbegrenzung

v id ……………………………………Vektor Partikel i in Dimension d

vx[][] ……………………………………Vektor

w ……………………………………Gewichtung des aktuellen Vektors

WPBS ……………………………………Gewichtung des persönlich besten Ergebnisses

WGBS ……………………………………Gewichtung des global besten Ergebnisses

x ……………………………………arithmetisches Mittel

x med ……………………………………Median

x mod ……………………………………Modus

x 1 ,…,x n ……………………………………Ausprägungen 1-n

Z 1 ……………………………………Zielfunktion zur Minimierung der Ungenauigkeit

Z 2 ……………………………………Zielfunktion zur Minimierung des Funkenfluges

……………………………………Maximierung der Abtragrate Z 3

Z ……………………………………Multikriterielle Zielfunktion

IV

Abbildungsverzeichnis   

Abbildung  1: Prinzip und Aufbau des ECM  

Abbildung  2: Partikelbewegungen in einer Dimension nach Position im Zeitablauf bei C 0,01  

Abbildung  3: Partikelbewegungen in einer Dimension nach Position im Zeitablauf bei C 0,1  

Abbildung  4: Partikelbewegungen bei d 1, C 1,0 und r Є 0 1 nach Position im Zeitablauf.  

Abbildung  5: Bewegung eines einzelnen Partikels bei d 1, ohne V max  

Abbildung  6: Bewegung eines einzelnen Partikels bei d 1, mit V max  

Abbildung  7: Varianten der Verteilung. Von links nach rechts: Linkssteil, symmetrisch, rechtssteil.  

Abbildung  8: Kontingenztabelle absoluter Häufigkeiten.  

Abbildung  9: Kontingenztabelle relativer Häufigkeiten.  

Abbildung  10: bester Zielfunktionswert (y-Achse) jeder Iterationen (x-Achse) pro Wiederholung (1-  

10)  für Z 1 , Z 2 , Z 3 und Z.  

Abbildung  11: Absolute Häufigkeiten der Mittelwerte in den angelegten Intervallen  

Abbildung  12: Matrix für w 0,5 bei Z 1 , gelb 20, 17,4285 dunkelgrün 20, hellgrün 17,4285  

Abbildung  13: Häufigkeitsverteilung der 100 besten Kombinationen in Bezug auf w bei Z 1  

Abbildung  14: Häufigkeitsverteilung der besten Kombinationen in Bezug auf w.  

Abbildung  15: Häufigkeiten der Mittelwerte in den angegebenen Intervallen.  

Abbildung  16: Häufigkeiten der Mittelwerte in den angegebenen kleineren Intervallen.  

Abbildung  17: Häufigkeitsverteilung der besten Kombinationen in Bezug auf w bei Z 2  

Abbildung  188: Matrix für w 0,4 bei Z 2 1,2 gelb 1,3, 1,055 dunkelgrün 1,1, hellgrün 1,055  

Abbildung  19: Graphische Darstellung der berechneten Mittelwerte als Kombination der c-Werte für  

w  0,4  

Abbildung  20: : Matrix für w 0,5 bei Z2. 1,2 gelb 1,3, 1,055 dunkelgrün 1,1, hellgrün 1,055  

Abbildung  21: Häufigkeitsverteilung der 100 besten Kombinationen in Bezug auf w bei Z 2  

Abbildung  22: Absolute Häufigkeiten der Mittelwerte in den angegebenen Intervallen.  

Abbildung  23: Absolute Häufigkeiten der Mittelwerte in den angegebenen Intervallen.  

Abbildung  24: Häufigkeitsverteilung der 100 besten Kombinationen in Bezug auf w bei Z 3  

Abbildung  25: Matrix für w 0,4 bei Z 3 25 gelb 26,5, 26,5 dunkelgrün 26,6, hellgrün 26,6  

Abbildung  26: Matrix für w 0,5bei Z 3 25 gelb 26,5, 26,5 dunkelgrün 26,6, hellgrün 26,6  

Abbildung  27: Häufigkeitsverteilung der besten Kombinationen in Bezug auf w bei Z 3  

Abbildung  28: Häufigkeiten der Gewichtung w in den besten 50 Kombinationen.  

Abbildung  29: Standardabweichungen der Parameterkombinationen bei n 100. Sortierung  

  (qualitativ) aufsteigend nach Mittelwerten. Oben links: Z 1 , Unten links: Z 2 , Oben recht: Z 3 , Unten  

rechts  : Z. Werte der y-Achse in  

Abbildung  30: Standardabweichung der RgP des 75 -Quantils von Z 1 Werte der y-Achse in  

V

Abbildung  31: Treppenfunktion der Aufsteigend sortierten Standardabweichungen von RgP von Z  3

Werte  der y-Achse in  54

Abbildung  32: Stichprobenverteilung in einer beispielhaften c p -c g -Matrix.  59

Tabellenverzeichnis   

Tabelle 1:  Ergebnisse der EC-MOptimierung nach Rao et al.  18

Tabelle 2:  EC-MParameterwahl nach Rao et al. (2008)  18

Tabelle 3:  Die 15 besten Parameterkombinationen zur Ermittlung der minimalen Ungenauigkeit.  34

Tabelle 4:  Die besten 20 Parameterkombinationen zur Berechnung der maximalen Abtragrate  43

Tabelle 5:  Ausschnitt aus der Datenerhebung zu Z.  45

Tabelle 6:  Werte der Funktion Z im Vergleich mit den besten monokriteriellen Werten.  46

Tabelle 7:  Die 10 besten Mittelwerte der multikriteriellen Optimierung  48

Tabelle 8:  Die 10 besten Mittelwerte der EC-MZielfunktionen für V max 50 bzw. 10  50

Tabelle 9:  5-Punkte-Zusammenfassung für die Verteilung der arithmetischen Mittel über alle n  100

Wiederholungen  für die Regionen guter Parameterqualität  52

Tabelle 10:  Prozentuale Abweichung der einzelnen Größen vom Minimalwert.  52

Tabelle 11:  Vergleich der besten ermittelten Ergebnisse.  56

Tabelle 12:  Ermittelte EC-MDimensionswerte für die verschiedenen Funktionen.  56

Tabelle 13:  Monokriterielle Ergebnisse bei der besten multikriteriellen Lösung.  57

Tabelle 14:  Parameterkombinationen mit den besten ermittelten Zielfunktionswerten.  57

Tabelle 15:  5-Punkte-Zusammenfassung der 100 PSO-Durchläufe mit vorgelagerte Parameterwahl  

durch  den Merels-Algorithmus.  60

Tabelle 16:  Arithmetische Mittel und Standardabweichungen bei vorgelagertem Merels Algorithmus  

in  100 PSO-Durchläufen.  61

VI

1. Einleitung

Mehrdimensionale Problemstellungen finden sich in allen wissenschaftlichen Bereichen, in denen Ziele und Entscheidungen das Ergebnis mehrerer Entscheidungsvariablen (als Ausprägungen der Dimensionen) sind. Hängt eine Entscheidung von mehreren, oft konfliktionären, Zielen ab, so wird sie als multikriteriell bezeichnet. ¹ Begründet sein kann diese Eigenschaft, wie später noch zu sehen sein wird, durch gleichzeitig verwendete Entscheidungsvariablen mit unterschiedlichen Einflüssen innerhalb der Zielfunktionen. ² Komplexität und Anwendbarkeit haben nicht zuletzt durch den Einsatz der Informationstechnologie stark zugenommen und an Bedeutung für die Wissenschaft gewonnen. Vor allem das Abbilden realer Situationen, wie sie zum Beispiel in den Ingenieursbereichen vorkommen, ist oft nur mit komplexen Funktionen möglich, welche nur unter enormem Zeitaufwand oder starker Approximation lösbar sind. Die zeiteffiziente Lösung solcher Probleme ist somit ein wissenschaftliches Anliegen und führt zu immer neuen Optimierungsverfahren. Gegenstand dieser Ausarbeitung soll das von Kennedy und Eberhart Mitte der 1990er-Jahre publizierte Verfahren der Partikelschwarmoptimierung (PSO) sein. Dieser evolutionäre Algorithmus, dessen Ergebnisse stark von externen Parametern abhängen, soll hier an einer beispielhaften Problemstellung auf die Möglichkeit der optimalen Parameterwahl hin empirisch untersucht werden. Diese Ausarbeitung wird beweisen, dass für das betrachtete Problem nach Rao et. al. (2008) sogenannte Regionen guter Parameterqualitäten (RgP) existieren, in denen jene Parameter der Partikelschwarmoptimierung liegen, welche zu optimalen Ergebnissen führen. Basierend auf dieser Beobachtung wird gezeigt werden, dass die Kenntnis von der Position einer solchen Region genügt, um eine gezielte Stichprobe im entsprechenden Parameterbereich zu nehmen, um zu annähernd global optimalen Ergebnissen zu gelangen. Auf diese Weise wird es ebenfalls möglich sein, die von Rao et al. vorgenommene Parameterwahl auf ihre Qualität hin zu beurteilen. Abschließend wird ein vom Autor entwickelter Algorithmus vorgestellt, welcher beide Eigenschaften umsetzt und so die Laufzeit der Partikelschwarmoptimierung bei gleichbleibend guten Ergebnissen auf bis zu 0,5% der zuvor durchgeführten Erhebung reduziert.

¹ „konfliktionär“ i.S.v. „nicht gleichzeitig erreichbar“

² vgl. Formel (2.1) - (2.3)

1

2. Themenfelder und Grundlagen

Der Titel dieser Arbeit lässt bereits drei Bereiche erkennen die sich in dieser Arbeit wiederfinden werden: Die empirische Analyse, die Partikelschwarmoptimierung und das Problemfeld der optimalen Parameterwahl. Letzteres soll in Kapitel 3 anhand einer Problemstellung aus dem Ingenieurbereich geschehen, welche im nächsten Unterpunkt zunächst einführend dargestellt wird. Im Anschluss wird ein Überblick über die Partikelschwarmoptimierung selbst gegeben, so dass danach die Zusammenführung durch Rao et al. kurz widergegeben werden kann. Ein Einblick in das Themenfeld der empirischen Analyse wird die notwendigen Grundlagen für eine eigene entsprechende Untersuchung in Kapitel 3 legen und das Kapitel abschließen.

2.1 Elektrochemische Bearbeitung: Prinzip und Modell

In Fällen, in denen die mechanische Bearbeitung von metallenen Oberflächen nicht möglich (zu hart, zu flexibel, zu empfindlich) oder nicht ökonomisch ist, werden seit den 1940er Jahren unkonventionelle Methoden eingesetzt. Rao et al. (2008) nennen hier beispielhaft die chemische, elektrochemische, thermale, und die elektrothermale Bearbeitung. ³ Bei dem hier betrachteten ECM wird, auf Grundlage des Phänomens der Elektrolyse nach Faraday von 1833, die Oberfläche eines Objektes nur durch eine chemische Reaktion und ohne physikalischen Kontakt bearbeitet. Das Werkstück fungiert hierbei, wie in Abbildung 1 zu sehen, als Anode, das bearbeitende Werkzeug als Kathode der elektrolytischen Zelle. Die beim Anlegen von elektrischer Spannung entstehende Potentialdifferenz (2-30V) zwischen beiden Elektroden erzeugt eine Wanderung der negativ geladenen Elektronen von der Anode (Werkstück) hin zur positiven Kathode, dem Werkzeug.

Dadurch wird über die chemische Reaktion die Oberfläche des Werkstückes ohne physikalische Berührung abgetragen. In dem Wasser, welches beide Elektroden als Elektrolyt umgibt, bildet sich

³ Rao et al. (2008), S. 949 ⁴ Rao et al. (2008), S. 950

2

Wasserstoff, welcher später im Modell noch relevant sein wird. ⁵ Rao et al. (2008) sehen die größten Vorteile des Verfahrens vor allem in der großen Bandbreite an bearbeitbaren Materialien, welche nur durch deren chemische Eigenschaften und nicht durch Härte oder andere physikalische Eigenschaften limitiert wird. Wilson (1982) ergänzt diesen Punkt um den der hohen Qualität und der vergleichsweise niedrigen Kosten. ⁶ Genau hier sehen erstere jedoch einen großen Nachteil: Während Wilson sich auf die Anschaffungskosten konzentriert und lediglich längere Anlernzeiten für Mitarbeiter und noch nicht ausgereifte Verfahren zur Werkzeugproduktion anführt (Anm. d. Verf.: Dieser Nachteil war in der ersten Fassung fast 40 Jahre vor Rao et al.), sehen Rao et al. den Hauptnachteil in den variablen Kosten, speziell dem hohen Energieverbrauch. ⁷ Wilson bestätigt den hohen Verbrauch bei seiner Berechnung der operativen Kosten und gibt für den Betrieb eine 12V-Anlage mit einer Stromstärke von 10.000 Ampere an. ⁸ Genau hierin sehen die Autoren ihren Artikel begründet: Durch die hohen Kosten die das Verfahren verursacht (Anfangsinvestitionen mindestens auf dem Niveau regulärer Maschinen, Stromverbrauch höher) trägt ein optimierter Einsatz durch die daraus resultierenden geringeren variablen Kosten stark zur ökonomischen Umsetzbarkeit des Verfahrens bei. Sie führen dazu drei Zielfunktionen an, welche sie der Arbeit von Acharya et al. (1986) entnommen haben: Die Abtragrate, die dimensionale Genauigkeit und die Werkzeugstandzeit.

1. Genauigkeit

Wie in Abbildung 1 zu sehen besteht eine Differenz in den Distanzen zwischen den beiden Elektroden im Bereich des Zuflusses (Y 0 ) und des Abflusses (Y 1 ). Diese Differenz bestimmt die Genauigkeit des Verfahrens. Erreicht wird die Maximierung der Genauigkeit über die Minimierung der Ungenauigkeit, definiert durch (Y 0 - Y 1 ). 2. Abtragrate

Als Produkt der bearbeiteten Fläche und der Abtragmenge des Werkzeuges (im engl.: tool feed rate = f) wird die Abtragrate (im engl.: material removal rate = MRR) bei der konstanten bearbeitbaren Fläche vor allem durch die Abtragmenge des Werkzeugs bestimmt, so dass für die Maximierung MRR max =f max gilt. 3. Werkzeugstandzeit

Vor allem beeinflusst durch die Menge der Funken pro cm, wird die Haltbarkeit des verwendeten Werkzeugs über die Minimierung des Funkenfluges maximiert.

⁵ Wilson (1982), S.12f.

⁶ Rao et al. (2008), S. 950. Wilson (1982), S. 4f.

⁷ Rao et al. (2008), S. 290. Wilson (1982), S. 7.

⁸ Wilson (1982), S. 43f.

3

Alle drei Zielfunktionen können mit den Dimensionen Abtragmenge (f), Fließgeschwindigkeit des Elektrolyt (U) und Angelegte elektrische Spannung (V) beschrieben werden. Mit Bezug auf Acharya et al. (1986) führen Rao et al. (2008) die folgenden, einzeln optimierbaren Zielfunktionen an:

x Minimierung der dimensionalen Ungenauigkeit

^{0,381067 0,372623 3,155414 3,128926} f U V e Z (3.1)

1

x Minimierung des Funkenfluges

^{3,528342 0,000742 2,52255 0,391436} f U V e Z (3.2)

2

x Maximierung der Abtragrate

f Z (3.3)

3

An den Funktionen ist bereits ersichtlich, dass die Ziele konfliktionär sind. Sowohl Z 1 als auch Z ² stehen in positiver Abhängigkeit zu f, was aufgrund des Minimierungsziels bedeutet, dass f möglichst klein gewählt werden muss. Diese Eigenschaft ist konträr zu dem Maximierungsziel in (2.3) und kommt in der gemeinsamen Betrachtung aller Ziele in der multikriteriellen Zielfunktion Z mit

zum Tragen. Z 1min , Z 2min und Z 3max sind die zuvor bereits in der monokriteriellen Optimierung ermittelten Werte, welche hier als fixe Divisoren fungieren. ⁹ Z 1 -Z 3 werden durch das Optimierungsverfahren ermittelt und bewertet. Ziel ist es, jene Ausprägungen für Z 1 - Z 3 zu finden, welche zu einem minimalen Z führen. Jene Kombination an Ausprägungen in den Dimensionen f, U und V, die zu diesem minimalen Wert führt, stellt die optimale Einstellung der ECM-Parameter dar. Die Variablen w 1 -w 3 geben die Möglichkeit einer Gewichtung einzelner Elemente, die Autoren lassen die Elemente jedoch gleichgewichtet, so dass

w w w 1 (3.5)

1 2 3

gilt. In der Realität unterliegt die Bearbeitung verschiedenen Nebenbedingungen (NB), die in das Modell übernommen werden müssen.

x Temperatur-NB:

⁹ Fix bedeutet in diesem Zusammenhang, dass sie in jeder Wiederholung monokriteriell neu berechnet werden, während der multikriteriellen Optimierung in der aktuellen Wiederholung jedoch konstant sind.

4

Die entstehende Temperatur muss unter der Siedetemperatur des Elektrolyts bleiben. Nach Umformungen gelangten die Autoren für den vorliegenden Fall zu der Funktion

1

x Passivitäts-NB:

Zur Vermeidung von Passivität (passive Elemente gehen nicht in Lösung) muss die Schicht aus gasförmigem Sauerstoff dicker sein als die sich im Laufe des Verfahrens bildende passive Schicht. Dafür gilt

t ^{0,844369 2,526076 1,546257 12,57697} f U V e 1 0 (3.7)

x „Choking“-NB:

Eine sich bildende Wasserstoffschicht (aus dem oben angesprochenen, sich bei der chem. Reaktion bildenden Wasserstoff) an der Kathode kann den Elektrolytfluss behindern (daher „choking“= engl.: Drosseln, Verstopfen). Zur Vermeidung eines Verstopfens sollte die Schicht dünner sein als die Elektrodenlücke, weshalb

t ^{0,075213 2,488362 0,240542 11,75651} f U V e 1 0 (3.8)

gilt.

Zusätzlich gelten für die Parameter des ECM, also die Dimensionen des Modells, folgende quantitativen Grenzen:

Die von Rao et al. mit der Partikelschwarmoptimierung ermittelten Ergebnisse sollen im Unterpunkt 2.3 nach einer Einführung in das Verfahren in 2.2 dargestellt werden.

2.2 Die Partikelschwarmoptimierung

Das Kernelement dieser Arbeit ist das Verfahren der Partikelschwarmoptimierung und der Nachweis der Ergebnisbeeinflussung durch extern vorgegebene Parameter, so dass deduktiv aus den Erkenntnissen auf eine globale Möglichkeit der Parameterwahl geschlossen werden kann. Zur umfassenden Darstellung dieses Kernelements soll in diesem Unterpunkt zunächst auf die Geschichte und die Funktionsweise des Verfahrens eingegangen werden, zwei Bereiche die, wie im Folgenden zu sehen sein wird, am besten simultan erläutert werden. Im Anschluss wird auf Varianten und

5

Probleme eingegangen werden, bevor die ergebnisbeeinflussenden Faktoren herausgearbeitet werden.

2.2.1 Geschichte und Funktionsweise

Die Partikelschwarmoptimierung ist ein Verfahren zur Optimierung stetiger Funktionen, das Mitte der 1990er Jahre von Kennedy und Eberhart publiziert wurde. ¹⁰ Es basiert auf der künstlichen Imitierung von tierischem Schwarmverhalten und ist eher zufällig bei Arbeiten in eben letzterem Themenbereich entstanden. Um die Funktionsweise zu erläutern, soll der Entstehungsprozess des Verfahrens wiedergegeben werden. ¹¹ Ziel des von Heppner und Grenader (1990) ursprünglich geschriebenen Programmes war das Simulieren der synchronen Bewegungen eines Schwarms ohne das Vorgeben der individuellen Bewegungen. ¹² Dabei sollte gezeigt werden, aufgrund welcher Parameter sich die Angehörigen des Schwarms einheitlich verhalten ohne dabei zu kollidieren. Sie wurden dazu durch zufällig initialisierte Punkte in einem zweidimensionalen Koordinatensystem repräsentiert (im Folgenden bereits Partikel genannt), von denen jeder einen eigenen (zufälligen) Vektor, als Repräsentant von Bewegungsrichtung und -geschwindigkeit, zugewiesen bekam. ¹³ In jedem Durchlauf (=Iteration) bestimmt das Programm für jedem Partikel einen Nachbarn, dessen Vektor von dem fokussierten Partikel übernommen wird. Durch diese einfache Zuweisung wurde, eine einheitliche Bewegung erreicht. Um das schnelle Einschlagen einer gemeinsamen und von da an konstanten Richtung zu vermeiden, wurden zufällig ausgewählte Vektoren willkürlich verändert (laut Heppner und Grenader (1990) auch, um Einflüsse wie Wind oder andere Störfaktoren zu simulieren), wodurch ein „lebensechtes“ Schwarmverhalten simuliert werden konnte. 14

Laut Heppner und Grenander zeigten die Partikel, welche sie in Anlehnung an die beabsichtigte Ähnlichkeit auch „Vögel“ nannten, ein bestimmtes, von den Parametern abhängiges Verhalten, wie zum Beispiel das Fliegen im Kreis um eine bestimmte Stelle herum und ein anschließendes Bewegen durch den Raum, wobei Partikel, welche sich nicht in der Menge befanden, „eingesammelt“ und in den Schwarm aufgenommen wurden. 15

¹⁰ Kennedy, Eberhart (1995); Für die Definition von „stetig“ vgl. S. 21

¹¹ Dieses Vorgehen ist dem Paper von Kennedy und Eberhart (1995) entnommen.

¹² Heppner, Grenender (1990), S. 233, Ausschluss der externen Einflüsse auf S. 234, Modelleigenschaft (viii).

¹³ Der Name „Partikel“ wird erst am Ende des Papers von den Autoren eingeführt und gründet auf der Idee, dass Begriffe wie „Geschwindigkeit“ und „Beschleunigung“ eher zu Partikeln passen als zu Punkten, auch wenn hierzu akzeptiert werden muss, dass der, in der Vorstellung, mit Masse und Größe belegte Begriff „Partikel“ nicht perfekt zu den masse- und größelosen Teilnehmern des virtuellen Schwarms passt. Die Namensgebung wird von den Autoren selbst als „Kompromiss“ bezeichnet. Vgl. Kennedy, Eberhart (1995), S. 1947.

¹⁴ Frei Übersetzt nach der Formulierung von Kennedy, Eberhart (1995), S. 1944; Heppner, Grenander (1990), S. 234.

¹⁵ Heppner, Grenander (1990), S. 235.

6

Aus dieser Beobachtung resultierte die erste Abwandlung der Ursprungsimulation: Ein Punkt, repräsentiert durch seine X- und Y-Koordinate, sollte als simulierte Futterstelle von den Partikeln gemeinsam gefunden werden. Dazu glich jeder von ihnen seine gegenwertige Position mit der Funktion

Eval

ab, bei welcher geringere Werte als besser bewertet werden. ¹⁶ Es ist leicht zu erkennen, dass in dieser ersten, noch ohne Nebenbedingungen zu minimierenden Zielfunktion die Position (100; 100) angestrebt werden soll. Die Suche nach Vektoren, die letztendlich in der gesuchten Position enden sollen, lässt sich für jede Iteration in zwei Bereiche unterteilen. Zum einen speichert jeder Partikel für sich im Verlauf der Iterationen seine persönlich beste Position, also jene, deren X- und Y-Werte eingesetzt in die Funktion (x=presentx, y=presenty) den geringsten Funktionswert ergeben hat. Sie erhielt den Namen pbest mit den Koordinaten pbestx[] und pbesty[]. Durch das Einsetzen des Partikelindex in die Klammer wird der entsprechende Wert ausgegeben. Zum anderen ist allen Partikeln jene Position bekannt, die von allen bisher gefundenen Positionen aller Teilnehmer des Schwarms das global beste Ergebnis hervorgebracht hat. Bekannt bedeutet in diesem Kontext, dass dadurch, dass der Index des Partikels mit dem temporär global-minimalen pbest-Wert der Variable gbest zugewiesen wird, die global beste Position jederzeit über pbest[gbest] für alle abrufbar ist. Gleiches gilt für deren Koordinaten mit pbestx[gbest] und pbesty[gbest]. Beide Positionen beeinflussen den zukünftigen Vektor auf die gleiche Weise: Liegt die gegenwärtige Position (i.S.v. Ausprägung der Koordinate) über der bekannten besseren, so wird der entsprechende Vektorwert um eine gewichtete Zufallszahl reduziert. Liegt sie darunter, wird der Wert addiert. ¹⁷ Für die Simulation ergeben sich also in jeder Iteration die folgenden Anpassungen für den Vektor v in den Dimensionen X (=vx) und Y (=vy):

¹⁶ Kennedy, Eberhart (1995), S. 1944.

¹⁷ Bei der X-Koordinate sprechen Kennedy und Eberhart (1995) anschaulicher von rechts und links, bzw. bei der Y-Koordinate bei darüber und darunter.

7

Das Ergebnis war nach Kennedy und Eberhart (1995), dass der Schwarm bei hohen Werten für p_increment und g_increment auf den entsprechenden Punkt „stürzen“, während sie bei niedrigen Werten in synchronen Kleingruppen um den Punkt kreisen und letztendlich „auf im landen“. ¹⁹ Durch diese Erweiterung wurde nicht nur die Weitergabe von Wissen simuliert, sondern auch eine erste Zielfunktion gelöst, auch wenn in diesem Fall das Optimum im Vorfeld bekannt war.

Im Anschluss wurden inzwischen überflüssige Variablen identifiziert und entfernt, wie zum Beispiel die zufällige Veränderung von gefundenen Vektoren. Im Originaltext war bis zu diesem Zeitpunkt von flock die Rede, also ein Schwarm in Bezug auf Vögel, resultierend aus dem ursprünglichen Ziel des Programmes. Durch die Abschaffung der craziness genannten zufälligen Veränderung des Vektors wurde der (Anm. des Verf.: im deutschen einfach nur) Schwarm durch sein optisches Verhalten zu einem swarm, also eine Form des Schwarms, dem etwas mehr der ausschwärmende und sich verteilende Charakter anhaftet als dem vorher verwendeten Begriff. Mit Bezug auf die fünf Kriterien der swarm intelligence von Millonas (1994) begründen die Autoren den Begriff swarm als passenden Ausdruck für die Menge der initialisierten Partikel, so dass sich, zusammen mit der zuvor erläuterten Begründung für den Namen „particle“, für das Verfahren der Name particle swarm optimization, im Deutschen Partikelschwarmoptimierung, ergibt. ²⁰ Die Variablen pbest und gbest blieben als essentielle Bestandteile bestehen und werden bis heute in der Literatur verwendet, oft auch bezeichnet als kognitive- (also wahrnehmungs-) bzw. soziale Variable. ²¹ Nach dieser Verschlankung und dem vorher erbrachten Beweis für die Funktionalität bei zweidimensionalen Problemen wurde

¹⁸ Frei nach Kennedy, Eberhart (1995), S. 1944. Die Darstellungsform orientiert sich an gängigen Programmiersprachen und wird hier als bekannt vorausgesetzt. Literaturbeispiel zum Nachlesen: Eller (2010), S. 151ff. g_increment = Gewichtung des global besten Ergebnisses; p_increment = Gewichtung des persönlich besten Ergebnisses.

¹⁹ Vgl. Kennedy, Eberhart (1995), S. 1944.

²⁰ Kriterien der swarm intelligence nachzulesen in Millonas (1994), S2f. Frei interpretiert begründen die Autoren mit diesem Vergleich eine Ähnlichkeit zwischen ihrer künstlichen Intelligenz und dem Schwarm, welche mit der Ähnlichkeit von tatsächlich bionischen Lösungen und ihren biologischen Vorbildern vergleichbar ist.

²¹ Vgl. z.B. Rao et al. (2008), S. 953. Bergh, Engelbrecht (2005), S.939

8

das Verfahren von Kennedy und Eberhart für mehrdimensionale Problemstellungen durch das Erweitern der eindimensionalen Arrays zu D×N-Matrizen verallgemeinert und an gängigen Problemstellungen erfolgreich getestet. ²² In einem letzten Schritt erfolgte, zur besseren Nachvollziehbarkeit der Partikelbewegungen und zur Performancesteigerung, eine Anpassung der Einflussnahme des persönlich besten und des global besten Ergebnisses auf den individuellen Vektor. Im Gegensatz zum oben beschriebenen Verfahren sollte nun nicht nur die Ungleichheit der dimensionalen Ausprägungen ausschlaggebend sein, sondern es sollte auch die Distanz in die Berechnung eingehen. Der Vektor für t+1 wird damit für alle Dimensionen durch die Funktion

vx vx rand p increment pbestx presentx (3.12) [][] [][] ()* _ *( [][] [][])

berechnet, wobei x allgemein für die Dimension steht. ²³ Es ist zu sehen, dass die gewichtete Zufallszahl, welche in der Vorgängerversion den Vektor abändern sollte, nun die Distanz gewichtet bzw. abändert, so dass das Produkt in den Vektor einfließt. Durch die Möglichkeit von positiven oder negativen Distanzen (im Koordinatensystem) genügt diese eine Funktion für alle Positionen und reduziert somit die Anpassung aus (2.11) von vier auf eine Zeile pro Dimension. Die in diesem Paper nicht explizit erwähnte aber später als die Grundformel der Partikelschwarm-Vektorsuche akzeptierte Version bringt den Einfluss des global besten Wert mit ein:

Im Werk von Kennedy und Eberhart (2001) wird die Funktion

M M v t t p x t p x t ( ) v ( 1) ( ( 1)) ( ( 1)) (3.14)

i id p id id g gd id

als Ausgangsfunktion verwendet, in der folgende Variablenzuordnung gilt:

v bzw. v id vx[][] =

i pbestx[][] = p

id p gbestx[][] =

gd presentx[][] = x

id

für i = Index des Partikels = i[1;I] und d = Index der Dimension = d[1;D]. 25

²² D steht hier für die Dimensionen und N für die Anzahl an Partikeln. Für die Problemstellungen vgl. Kennedy, Eberhart (1995), S. 1945.

²³ Kennedy, Eberhart (1995), S. 1945.

²⁴ Vgl. z.B Bergh, Engelbrecht (2005), S. 939. Shi, Eberhart (1998), S. 69.

9