OO-Entwurf von Evolutionären Algorithmen Stefan Walter Seminar – Projektgruppe 431...

OO-Entwurf vonEvolutionären Algorithmen

Stefan Walter

Seminar – Projektgruppe 431„Metaheuristiken“

Lehrstuhl XI 10.04.2003

Autor: Stefan Walter 2/34

OO-Entwurf von Evolutionären Algorithmen

12. April 2003

Gliederung

Systematische Herangehensweise Grundprinzipien und Beispiele

TEA DREAM JEO – Java Evolving Objects Entwurf eines EA mit Mitteln der OOP

12. April 2003

Gliederung

12. April 2003

Systematische Herangehensweise

Allgemeiner OO – Entwurf Anwendungsfälle („use cases“) beschreiben Strukturierung des Problems Isolieren der Elemente, die als Klassen in Frage kommen Beschreibung der Kommunikation der Klassen Beschreibung der Hierarchien (Vererbung, Aggregation)

12. April 2003

Systematische Herangehensweise

Mögliche Strukturierung von EA „passiv“

• Population• Chromosomen

• Insel• Umgebungen (environments)

„aktiv“• Initiatoren• Brüter (breeders)• Selektoren (selectors)• Bewerter (assessors)• Übersiedler (migrators)• Abbrecher (terminators)

12. April 2003

Inselmodell

Zur parallelen Ausführung des gleichen Algorithmus auf mehreren Maschinen

Austausch von Informationen durch Migration Individuen werden zwischen den Inseln ausgetauscht Auswahl durch spezielle Operatoren („migrators“)

Beeinflussung durch Parameter Häufigkeit der Migration Anzahl der Ausgetauschten Individuen Auswahl der Inseln mit denen kommuniziert wird

(Nachbarschaft) Häufiger Austausch vieler Individuen -> panmikitsche

Population

12. April 2003

Das Panmikitische Modell

Quasi eine große Population Parallelisierung von Mutation und

Funktionsauswertung, da beschränkt auf Individuen Individuen werden auf verschiedene Prozessoren

verteilt Crossover und Selektion wird komplizierter

12. April 2003

Gliederung

12. April 2003

TEA – Toolbox for Evolutionary Algorithms

Ergebnis einer früheren PG am Lehrstuhl XI Ziel: Ermöglichung einer „natürlichen“ Repräsentation

des Problems ohne Festlegung auf Standardrepräsen-tationen: Binäre Kodierung (Genetische Algorithmen, GA) Reele Vektoren (Evolutionsstrategien, ES) Bäume (Genetische Programmierung, GP)

12. April 2003

Struktur (aktiver Teil) teaPopulation (Population) teaIndividual (Individuum)

• teaIIntVector• teaIMultiChromo• teaISimple

Chromosome• teaCPermutation

12. April 2003

Struktur (aktiver Teil) teaMutate (Mutationen)

• Jeweils Unterklassen für die entsprechende Datentypen teaRecombine

• Ebenfalls Unterklassen für die entsprechende Datentypen teaReplace (Ersetzungen)

12. April 2003

Gliederung

12. April 2003

„Distributed Resource Evolutionary Algorithm Machine“ Basis für verteilte evolutionäre Algorithmen Kommunkation über das Internet „CPU sharing“ für komplexe Algorithmen

Skalierbare Auslegung Verschiedene Einstiegspunkte für Benutzer

12. April 2003

Struktur der Benutzung:

12. April 2003

Benutzer A möchte Rechenzeit zur Verfügung

stellen Experimente anderer

überwachen Benutzer A benutzt die

grafische Konsole

12. April 2003

Benutzer B möchte Algorithmen entwerfen Nicht auf Textbasis

programmieren Benutzer B interagiert mit

GUIDE Schicht Beeinflussung der

evolution engine durch Parameter

Dadurch beliebige EA möglich

Problemspezifische Einstellungen mit Java-ähnlicher Hochsprache

12. April 2003

Benutzer C möchte Das System durch EASEA

programmieren Hochsprachliche EA

Entwicklungsumgebung Produziert Java code,

benutzt die JEO Bibliothek Dateien können direkt

vom Java compiler bearbeitet werden

12. April 2003

Benutzer D Programmiert direkt in

Java Benutzt die JEO Bibliothek

• Objekte müssen entsprechende Interfaces aus JEO implementieren

12. April 2003

Benutzer E Ist Experte und

programmiert direkt mit Hilfe DRM API

Benutzt den Kern des Systems, die DRM (Distributed Resource Machine)

12. April 2003

Gliederung

12. April 2003

JEO – Java Evolving Objects

Ist eine Java Bibliothek für die Durchführung evolutionärer Experimente

Flexibel für fast jedes Experiment geeignet Basiert auf dem Inselmodell ermöglicht verteilte

Ausführung

12. April 2003

Struktur: Folgt den Richtlinien der Objektorientierten

Programmierung• Objekt der gleichen Klasse können ausgetauscht werden

verändert nur die Spezifikation des Experiments• JEO ist benutzbar wie ein LEGO-Kasten• Erweiterbarkeit durch Implementierung von Interfaces• Mobil und portabel Implementierung von java.io.Serializable

12. April 2003

InfoHabitants Individuen in DREAM Besteht aus Genom (Problemlösung) und Fitness Braucht Resourcen, um auf einer Insel zu überleben

12. April 2003

Genome Evolvierbarer Teil des Individuums Set aus Genen = Problemlösung Operationen

• Initialisierung (durch Inter Objekt)• Modifikation (durch Operator Objekt)

Es stehen viele verschiedene Genome zur Verfügung

12. April 2003

Fitness Deutet auf Güte der Lösung hin Einzige Bedingung an die Fitness: Vergleichbarkeit

• Erreicht durch erben von Interface java.lang.Comparable• Jedes Objekt das von o.g. Interface erbt, kann Fitness sein

12. April 2003

Breeders Wendet Variationsoperatoren an Population an Erzeugt Nachkommengeneration Benutzt eine Vielzahl von Variationsoperatoren Kontrolliert die Anwendung der Variationsoperatoren, bis

Population spezifizierte Größe erreicht hat

12. April 2003

Selectors Auswahl eines InfoHabitants aus der Population Für verschiedene Operationen benutzt

• Zeugung: Selektion von Eltern für Produktion von Nachkommen

• Migration: Emigrator sucht InfoHabitant zum Auswandern, ImMigrator sucht lokalen InfoHabitant, der durch Einwanderer ersetzt wird

• Reward: Rewarder suchen InfoHabitants, die belohnt werden sollen

Verschieden Versionen für verschiedene Strategien

12. April 2003

Assessors (Bewerter, Schätzer) Evaluierung und Ersetzung

• Sollte immer zusammen (nacheinander) ausgeführt werden• Zusammengefasst in Assessor

Ausführung nach Veränderungen

12. April 2003

Migrators Dienen dem Austausch von Lösungen zwischen den

Inseln Erhöhen die Diversizität der Inselbevölkerung Kontrolle über Häufigkeit und Umfang des Austausches

12. April 2003

Terminators Überprüfen Abbruchbedingungen und beenden evntl. die

Evolution Abbruchbedingungen können einfach (Zähler) oder

komplex sein (Qualität der Lösung) Außerdem statistische Funktionen

12. April 2003

Gliederung

12. April 2003

Entwurf von EA mittels OOP (Fazit)

Umsetzung der Rollen eines EA fast zwingend Übersetzung in entsprechende Klassen

Beachtung objektorientierter Prinzipien wie bei anderen Programmentwürfen Design der Schnittstellen Kapselung Vollständigkeit Geheimhaltung Etc.

12. April 2003

Entwurf von EA mittels OOP (Fazit)

Vorteile durch OO-Ansatz Austauschbarkeit von Objekten

• Funktionale Elemente von verschiedenen EA Delegation

• Änderung des Algorithmus zur Laufzeit Vererbung

• Spezialisierungen auf Basis einer allgemeinen Klasse

Ziel: Kleinsten gemeinsamen Nenner finden für ein flexibles

Klassenmodell Darauf aufbauend spezielle Ansätze

12. April 2003

OO-Entwurf von Evolutionären Algorithmen Stefan Walter Seminar – Projektgruppe 431...

Documents

Integriertes Lean Management und BIM Gestützte Ausbau ... · Zusammenfassung III Dem eher rein evolutionären Schritt vom Zeichenbrett zur 2D-CAD-Zeichnung folgt nun der vielmehr

Ausgewählte Grundlagen der Optimierungjawi0001/EA-Vorlesung/PDF/K1_Opt-Grundlagen... · Planung und Optimierung mit evolutionären Verfahren K1: Ausgewählte Grundlagen der Optimierung

Metaheuristiken fur¨ die mehrkriterielle Optimierung ...ls11- · Metaheuristiken fur¨ die mehrkriterielle Optimierung Endbericht der Projektgruppe 447 Universitat Dortmund¨ 27

Folie 1/ Grundriss der evolutionären Psychiatrie (Kn/ib) Grundriss der evolutionären Psychiatrie von Dr. med. Thomas Knecht

Stromerregte Hysteresebremsen Current Controlled … · · 2017-05-164 B GmbH · Bunsenstraße 1 · 24145 Kiel · Germany · Phone +49 (0)431-65 02 77 · Fax +49 (0)431-65 05 11

Offenlegung gemäß Artikel 431 – 455 Verordnung (EU) Nr ......Offenlegung 2015 der Raiffeisenbank Wels Seite 2 Offenlegung gemäß Artikel 431 - 455 Verordnung (EU) Nr. 575/2013

Ein spannender Tag Elektrizitätslehre in der Grundschule · Informationen zum Projekt: Dr. Margot Janzen Renate Weschenfelder Telefon: +431-880-1261 / 1248 / 3168 Telefax: +431-880-5468

Das Janusgesicht der Religion. Zur Evolution von Religionen und den evolutionären Chancen eines aufgeklärten Humanismus Gerhard Schurz (Universität Düsseldorf)

Jahresinhaltsverzeichnis Ernährung im Fokus 2011 · Schnelles Abnehmen mit fettreicher Diät September 431 Fördern Antioxidanzien die Krebsentstehung? September 431 Neue Strategien

Die deutsche Kompositionsfreudigkeit Übersicht und Einführungneon.niederlandistik.fu-berlin.de/static/bs/Schlücker (2012)_Deutsche... · evolutionären „Protosprache“, die

Planung und Optimierung mit evolutionären Verfahrenjawi0001/EA-Vorlesung/PDF/K0_EA-Einf… · Studiengänge Informatik und Wirtschaftsinformatik K0_EA-Einfuehrung.pptx 3 Einführung

OO-Entwurf von Evolutionären Algorithmen

Verlauf der Linie 431 · Verlauf der Linie 431 Rathaus Hauptstraße Katholische Kirche Aldinger Straße Hegnach Neckarrems Rems K l e ine Gartenstra ß e Hart w e i n b e r g str

#1 2012€¦ · J.P. Sauer & Sohn Maschinenbau GmbH Postfach 9213 D-24157 Kiel Tel. +49 (0) 431/3940-0 Fax +49 (0) 431/3940-24 e-mail: info@sauersohn.de Internet: ... intake or as

Dr. Leonhard Stiegler Automation - DHBW Stuttgartsrupp/IBS/03_Feldbusse.pdf · Ethernet hat eine beispiellose Erfolgsgeschichte, nicht zuletzt wegen seines evolutionären Ansatzes

Metaheuristiken zur Lösung von Standardproblemen des ... · Metaheuristiken zur Lösung von Standardproblemen des Cutting and Packing Inauguraldissertation zur Erlangung des Grades

Bianca 431 - BoatNet Bianca 4… · Bianca- Segelyachten sind für Ihre sehr gute Bauqualität und herausragenden Segeleigenschaften bekannt. Die Bianca 431 hat 5 Kabinen, wo von

So˝ne, Stra˝d & ibahn · MECKLENBURGISCHE BÄDERBAHN1 MECKLENBURGISCHE BÄDERBAHN MOLLI GMBH Reservierung, Preise, Informationen: Telefon 038293 431 331 · Telefax 038293 431 372

Modul 431: Aufträge im IT-Umfeld selbständig durchführen

Wärmeversorgung Neuwerk-West / Eiderkaserne · 4 IPP ESN Power Engineering GmbH Rendsburger Landstraße 196 -198 D 24113 Kiel Tel. +49 431 64959 80 Fax +49 431 64959 898 info@ipp