Inhalt

4. Evolutionäres Computing

Evolutionäres Computing ist ein weitgefaßter Begriff für ein breites Feld von Programmiertechniken. Es umfaßt genetische Algorithmen, komplexe adaptive Systeme, evolutionäre Programmierung usw. Der Hauptgedanke all dieser Techniken ist die Idee der Evolution, die Idee, daß ein Programm sich zu einem bestimmten Ziel hinentwickelt. Dieses Ziel kann alles mögliche sein, vom Lösen ingenieurtechnischer Probleme bis hin zum Sieg in einem Spiel.

4.1 EC Klassen- und Codebibliotheken

Das sind Klassen- oder Codebibliotheken, die in Programmen im Umfeld des Evolutionären Computing verwendet werden können. Sie können nicht als lauffähige Anwendung betrieben werden, sondern sind als Werkzeuge zur Entwicklung eigener Programme gedacht.

daga

daga ist eine experimentielle Version eines zweistufigen genetischen Algorithmus', der kompatibel zu GALOPPS GA Software ist. Es ist ein Meta-GA, das eine Population von GAs dynamisch entwickelt, um ein Problem zu lösen, das den darunterliegenden GA-Schichten übergeben wird. Werden mehrere GAs (mit verschiedenen Operatoren, Parametereinstellungen usw.) gleichzeitig mit der Lösung desselben Problems beauftragt, haben diejenigen eine höhere Überlebenswahrscheinlichkeit, die eine bessere Performance zeigen. Diese GAs werden dann mit der »Aufzucht« der nächsten Makro-Generation beauftragt, d. h., sie erzeugen neue »Tochter-«GAs mit den vererbten Charakteristika der Eltern-GA oder GAs. Auf diese Weise versuchen wir, gute Problemlösungs-Strategien über die ganze Breite der GA-Population zu fördern.

Ease

Ease - Evolutionary Algorithms Scripting Evironment - ist eine Erweiterung zur Sprache Tcl, die Befehle zum Erzeugen, Ändern und Überprüfen von Individual- Populationen bereitstellt. Diese Populationen werden durch Realzahl-Vektoren und/oder Bitfolgen dargestellt.

EO

EO ist eine schablonenbasierte, ANSI-C++ konforme Bibliothek für Evolutionary Computation. Sie enthält Klassen für alle denkbaren Arten der Evolutionary Computation (besonders genetische Algorithmen). Da sie komponentenbasiert ist, ist es sehr einfach, bestehende abstrakte oder konkrete Klassen abzuleiten, falls man eine benötigte nicht findet.

FORTRAN GA

Dies ist die FORTRAN-Version des Treibers für einen genetischen Algorithmus. Der Code initialisiert eine zufällige Probe aus Individuen mit unterschiedlichen Parametern, die unter Verwendung des genetischen Algorithmus' optimiert werden soll. Dies geschieht beispielsweise mittels der Auslese. Das verwendete Auswahlschema ist die konkurrierende Auslese mit einer Mischtechnik zur Auswahl zufälliger Paare zur Weiterverwendung. Die Routine enthält binäre Codierungen für die Individuen, Sprungmutation, Langzeitmutation und die Option zur Einzel- oder Einheitskreuzung. Niching (Streuung) und eine Auswahlmöglichkeit für die Anzahl der Kindprogramme pro Paar wurden hinzugefügt. Kürzlich wurde die Bibliothek noch um die Möglichkeit der Verwendung von Mikro-GAs erweitert.

GAlib: Matthew's Genetic Algorithms Library

GALib beinhaltet eine Menge von Objekten mit genetischen Algorithmen in C++. Die Bibliothek stellt Werkzeuge zur Verwendung genetischer Algorithmen zur Verfügung, um Optimierungen in C++-Programmen unter Benutzung von Repräsentations- und genetischen Operatoren vorzunehmen. Die Dokumentation beinhaltet einen umfassenden Überblick über die Implementierung genetischer Algorithmen sowie Beispiele zur Anpassung der GALib-Klassen.

GALOPPS

GALOPPS ist ein flexibler, allgemeiner GA in C. Er wurde auf der Grundlage der Architektur des Goldberg Simple Genetic Algorithm (SGA) entwickelt, um ihn für die Benutzer einfacher erlernbar und erweiterbar zu machen. GALOPPS erweitert die Möglichkeiten von SGA in mehrfacher Hinsicht:

GAS

GAS bedeutet "Genetic Algorithms Stuff". GAS ist Freeware. Der Zweck dieser Bibliothek ist es, künstliche Evolutionen zu erforschen und auszuwerten. Die vorrangige Implementierungssprache von GAS ist Python. Das GAS Softwarepaket ist als Python-Rahmen gedacht, um eigene Anwendungen zu entwickeln. Es enthält eine Beispielanwendung, wo versucht wird, Python-Programmzeilen zu erzeugen. Dieses spezielle Problem fällt unter die Kategorie der Genetischen Programmierung (GP) und/oder Automatischen Programmierung. Selbstverständlich versucht GAS auch, für andere Anwendungen der Genetischen Algorithmen nützlich zu sein.

GAUL

Die Genetische Algorithmen-Bibliothek (Genetic Algorithm Utility Library - GAUL) ist eine flexible Programmbibliothek, die entworfen wurde, um die Entwicklung von Anwendungen zu unterstützen, die genetische Algorithmen benutzen müssen. Folgende Funktionen werden abgebildet:

GECO

GECO (Genetic Evolution through Combination of Objects) ist eine erweiterbare objektorientierte Werkzeugsammlung zur Konstruktion genetischer Algorithmen (in Lisp). Es stellt eine Menge von allgemeinen erweiterbaren Klassen und Methoden zur Verfügung. Einige einfache Beispiele zeigen die Verwendung dieser Bibliothek.

Genetic

Dies ist ein Paket für genetische Algorithmen und KI in Python. Genetic kann typischerweise jedes Problem lösen, das in der Minimierung einer Funktion besteht. Es beinhaltet auch einige Demos und Beispiele, wie das TSP (Rundreiseproblem).

GPdata

GPdata-3.0.tar.gz (C++) enthält eine Version von Andy Singleton's GP- Quick Version 2.1, das stark erweitert wurde, um folgende Merkmale zu unterstützen:

Die FTP-Seite enthält auch ein kleines C++-Programm (ntrees.cc), mit dem man die Anzahl der Unterschiede berechnen kann, die auf eine gegebenen Länge, einer gegebenen Funktion und einem Terminal bestehen.

gpjpp Genetic Programming in Java

gpjpp ist ein Java-Package, das ich geschrieben habe, um Forschungen zur genetischen Programmierung anzustellen. Es ist ein Teil des gpc++ Kernels, der von Adam Fraser und Thomas Weinbrenner geschrieben wurde. Das Package enthält vier von Koza's Standardbeispielen: die künstliche Ameise, den »hopping lawnmower«, symbolische Regression und den booleschen Multiplexer. Nachfolgend eine unvollständige Auflistung der Merkmale:

jaga

Ein einfaches in Java geschriebenes Package zur Programmierung genetischer Algorithmen.

lil-gp

patched lil-gp *

lil-gp ist ein allgemeines C-Werkzeug für die genetische Programmierung. Es wurde mit einer ganzen Reihe von Zielen vor Augen programmiert: Geschwindigkeit, einfache Handhabbarkeit und eine Reihe von weiteren Forderungen, z.B.

* Am gepatchten lil-gp-Kernel wird gerade gearbeitet, mit Änderungen im bezug auf Multithreading, Koevolution und anderen Optimierungen und Leistungsmerkmalen.

Lithos

Lithos ist ein stapelbasiertes Evolutionssystem (ES). Im Gegensatz zu den meisten ES ist seine Repräsentationssprache komplett computerbezogen, wodurch es schneller und kompakter als die S-Ausdrücke ist, die ansonsten in der genetischen Programmierung genutzt werden. Die hier vorgestellte Version bezieht sich auf das Go-Spiel, kann aber durch den Einsatz einer anderen Evaluierungsfunktion an andere Probleme angepaßt werden. Das Programm wird mit dem ANSI C-Quellcode ausgeliefert.

PGAPack

Parallel Genetic Algorithm Library

PGAPack ist eine vielseitig einsetzbare, datenstrukturneutrale Bibliothek für genetische Algorithmen. Sie wurde entwickelt, um die am häufigsten gewünschten Möglichkeiten einer Bibliothek für genetische Algorithmen in einer integrierten, nahtlos einzupassenden und portablen Art und Weise zusammenzufassen. Hauptmerkmale von PGAPack V1.0 sind:

PIPE

Das Programm PIPE (Probabilistic Incremental Program Evolution) ist eine neuartige Technik zur automatischen Programmsynthese. Die Software wurde in C geschrieben. Es

Sugal

Sugal [soo-gall] bezeichnet das »SUnderland Genetic ALgorithm«-System. Das Ziel von Sugal ist es, Forschung und Implementation genetischer Algorithmen auf einer gemeinsamen Softwareplattform zu betreiben. Als solches unterstützt Sugal eine große Anzahl von Varianten genetischer Algorithmen und hat vielfältige Möglichkeiten der nutzerdefinerten Anpassung und Erweiterung.

4.2 EC Software Kits/Applicationen

Das sind verschiedene Anwendungen, Softwaresammlungen usw. zur Forschung auf dem Gebiet des EC. Die Benutzung ist unterschiedlich schwierig, da diese Software hauptsächlich für bestimmte Forschungsinteressen konzipiert wurde statt als einfach zu bedienendes kommerzielles Softwarepaket.

ADATE

ADATE (Automatic Design of Algorithms Through Evolution) ist ein System zur automatischen Programmierung, d.h. für induktives Schließen von Algorithmen, was wohl die geeignetste Art der Entwicklung künstlicher und allgemeiner Intelligenz ist. Das ADATE-System kann automatisch nicht-triviale und neuartige Algorithmen generieren. Algorithmen werden durch eine breite kombinatorische Suche generiert, die durch komplizierte Programmtransformationen und Heuristiken angestoßen werden. Das ADATE-System ist besonders geeignet zur Synthese symbolischer, funktionaler Programme und hat diverse einzigartige Fähigkeiten.

esep & xesep

Dies ist ein neuer Zeitplaner, genannt Evolution Scheduler, der auf genetischen Algorithmen und Evolutionärer Programmierung basiert. Er läuft mit dem originalen Linux Prioritätenscheduler. Das bedeutet, daß man die Scheduling- Strategie ohne einen Systemneustart ändern kann. Man kann einfach das Manager- Programm esep verwenden, um jederzeit zwischen beiden umzuschalten. esep ist an sich ein Programm zum Scheduling von Status, Kommandos und Administration. Wir wollten nicht den ursprünglichen Prioritätenscheduler entfernen. Stattdessen verfügen Sie mit esep über eine weitere Alternative für einen intelligenten Scheduler, der den natürlichen Konkurrenzkampf auf einfache und effektive Weise darstellt.

Xesep ist eine graphische Benutzeroberfläche für esep (Evolution Scheduling and Evolving Processes). Sie wurde wurde entworfen, um dem Nutzer den Start und die Arbeitsweise zu zeigen und ihm ein Gefühl für Evolution Scheduling und Evolving Processes zu geben, einschließlich der Unterprogramme zur Anzeige des System-, Entwicklungsprozeß-, Warteschlangen- und Evolution Scheduling-Status, und zwar periodisch in solch einer kleinen Zeit wie eine kleine Sekunde.

Corewars

Corewars ist ein Spiel, das eine virtuelle Maschine mit einer Anzahl von Programmen simuliert. Jedes Programm versucht, das andere zum Abstürzen zu bringen. Das Programm, das am längsten läuft, gewinnt. Eine Anzahl von Beispielprogrammen wird mitgeliefert, und neue Programme können vom Spieler geschrieben werden. Screenshots sind auf der Homepage von Corewars zu sehen.

Corewar VM

Dies ist eine virtuelle Maschine, die in Java geschrieben wurde (also eine virtuelle Maschine für eine andere virtuelle Maschine!) für ein Corewar-Spiel.

Grany-3

Grany-3 ist ein vollständig ausgestatteter Simulator für einen zellularen Automaten. Er wurde in C++ implementiert unter Verwendung von Gtk--, flex++/bison++, doxygen und gettext und ist nützlich für Festkörperphysiker.

JCASim

JCASim ist ein Allzwecksystem für die Simualtion zellularer Automaten in Java. Es beinhaltet eine allein lauffähige Anwendung und ein Applet für Web-Präsentationen. Die zellularen Automaten können in Java, CDL oder unter Verwendung eines interaktiven Dialogs spezifiziert werden. Das System unterstützt viele unterschiedliche Gittergeometrien (1D, 2D Quadrat, Sechsecke, Dreiecke, 3D), Nachbarschaften, Grenzbedingungen und kann die Zellen unter Verwendung von Farben, Text, oder Icons darstellen.

JGProg

JGProg (Genetic Programming) ist eine in Java implementierte experimentielle Plattform für Genetische Programmierung. JGProg ist Open-Source. Es werden zwei »Beispielwelten« mit zur Verfügung gestellt, in denen sich eine Population entwickelt und das Problem löst.

Inhalt