Rolf Wanka Alexander Raß Erlangen, 30. April 2015 ¨ Ubungen zur Vorlesung Organic Computing SS 2015 Blatt 3 ¨ ¨ Diese Ubungen finden am 5./6. Mai und am 12./13. Mai als praktische Ubung in CIP-Pools statt: Der Dienstag-Termin in Raum 0.157-115, CIP Pool EEI (E-Technik-Geb¨aude), der Mittwoch-Termin in Raum 01.155-113, CIP-Pool Informatik (blaues Hochhaus). Ggf. auf Emails von Alexander Raß achten. ¨ In dieser Ubung soll ein Partikelschwarmoptimierer programmiert und an einigen Beispielfunktionen getestet werden. W¨ahlen Sie selbst eine Programmiersprache aus (Empfehlung: Java, C++ oder MATLAB). AUFGABE 9: a) Programmieren Sie zun¨achst einen einfachen PSO, der nur die folgenden Komponenten enth¨alt. Dabei sind a, bloc und bglob keine Vektoren, sondern lediglich Zahlen: – Standard-Bewegungsgleichungen: (k+1) = a ·~vi + bloc ·~rloc (~pi −~xi ) + bglob ·~rglob (~pglob −~xi ) (k+1) = ~xi +~vi ~vi ~xi (k) (k) (k) (k) (k) (k) (k+1) (k) – ~pglob ist die beste bis zur k-ten Iteration gefundene L¨osung, ~rloc und ~rglob sind Zufallsvektoren, deren Komponenten jeweils uniform im Intervall [0, 1] verteilt sind. – Partikel-Initialisierung: zuf¨allig mit uniformer Verteilung im Suchraum. (0) – Geschwindigkeits-Initialisierung: ~vi = ~0 – Minimiert werden soll die S PHERE-Funktion f : [−100 . . . 100]n → R mit (~x = (x1 , . . . , xn )) n f (~x) = ∑ xi2 i=1 S PHERE ist eine sehr einfache Funktion mit nur einem lokalen Optimum, das auch das globale Optimum ist: f (0, . . . , 0) = 0. – Verwenden Sie die sog. Infinity-Strategie, um mit obigen Suchraumgrenzen umzugehen: Alle Funktionswerte außerhalb des Suchraums sind unendlich. b) Testen Sie f¨ur verschiedene Dimensionalit¨aten (z.B. n = 2, n = 30, n = 100), ob Ihr Schwarm das globale Optimum findet. Testen Sie verschiedene Einstellungen f¨ur die Parameter (Standard-Parameter sind z.B.: a = 0.72984, bloc = bglob = 1.496172). Welchen Einfluss haben Dimensionalit¨at und die Wahl der Parameter? AUFGABE 10: Implementieren Sie weitere Minimierungsprobleme: • Rosenbrock: f : [−30 . . . 30]n → R f (~x) = n−1 ∑ 100 · xi+1 − xi2 2 + (1 − xi )2 i=1 Rosenbrock besitzt nur ein lokales Optimum, f (1, . . . , 1) = 0, welches sich innerhalb eines langen, schmalen Tals befindet. • Rastrigin: f : [−5.12 . . . 5.12]n → R n f (~x) = 10 · n + ∑ xi2 − 10 · cos (2 · π · xi ) i=1 Im Gegensatz dazu hat Rastrigin sehr viele lokale Optima, die regelm¨aßig im Suchraum verteilt sind. Das globale Minimum ist f (0, . . . , 0) = 0. • Schwefel: f : [−500 . . . 500]n → R p n |xi | f (~x) = ∑ −xi · sin i=1 Das globale Optimum, f (420.9687, . . . , 420.9687) = −n · 418.9829, befindet sich nahe der Suchraumecke und ist weit vom zweitbesten Optimum entfernt. Wie erfolgreich ist Ihr PSO auf den verschiedenen Problemen? AUFGABE 11: (optional) Integrieren Sie weitere Methoden, mit quaderf¨ormigen Suchraumbeschr¨ankungen umzugehen (vgl. Blatt 2, Aufgabe 5). Welche sind besonders erfolgreich auf den gegebenen Funktionen? AUFGABE 12: (optional) a) Erweitern Sie Ihren PSO um die drei in Aufgabe 7 (Blatt 2) abgebildeten Kommunikationsstrukturen: vollst¨andiger Graph (gbest), Ring, Gitter. b) Vergleichen Sie die Nachbarschaftsstrukturen gbest und Gitter. Welche Strategie scheint f¨ur die 30dimensionale Rosenbrock, und welche f¨ur die 30-dimensionale Rastrigin-Funktion besser geeignet zu sein? F¨uhren Sie dazu je 1000 L¨aufe pro Strategie und Funktion aus, und vergleichen Sie die Mittelwerte (und Standardabweichungen) der besten gefundenen L¨osungen. K¨onnen Sie Ihr Ergebnis erkl¨aren?