Ab einer gewissen Suchraumgröße sind Planungs- und
Optimierungsproblems nicht mehr durch vollständige Verfahren zu
lösen. Ein Genetischer Algorithmus (GA) ist ein
zufallsbasiertes, iteratives Suchverfahren. Es löst komplexe
Optimierungsprobleme nicht auf herkömmlichem, algorithmischem
Weg, sondern auf der Basis eines stark vereinfachten Modells
biologischer Evolution.
Die Grundidee eines GA ist ein kollektiver Lernprozeß innerhalb
einer Population vieler Individuen (Chromosomen). Jedes dieser
Individuen entspricht einem bestimmten Punkt innerhalb des
Suchraumes aller in Frage kommenden Lösungen eines gegebenen
Optimierungsproblems. Durch die Verwendung der Operationen
Selektion, Mutation und Rekombination (Crossover)
entwickelt sich eine Population in Richtung besserer Regionen
des Suchraumes -- aufgrund der unterschiedlichen
Einzelindividuen parallel aus jeweils verschiedenen
Richtungen. Dabei bevorzugt die Selektionstechnik bei der
Entstehung einer Nachfolgegeneration durch Reproduktion bessere
Individuen der aktuellen Generation ("survival of the
fittest"). Rekombination (Crossover) ermöglicht die
Vermischung von 'Erbmaterial', und das Prinzip der
Mutation spiegelt eine Art Inovationspotential der Population
wider.
Für die Bearbeitung der Aufgaben dieses Blattes stellen wir
Ihnen eine C-Bibliothek zum Thema GA zur Verfügung
(LibGA, s.u.). Es steht Ihnen natürlich auch frei, sich eine
andere der vielen frei verfügbaren
Genetic-Algorithm-Libraries zu besorgen oder ganz auf den
Einsatz fremder Bibliotheken zu verzichten.
LibGA: A
User-friendly C Workbench for Order-based Genetic Algorithms
ist eine einfache aber dennoch leistungsfähige C Bibliothek für
GA-Anwendungen. Sie wurde speziell für die Bearbeitung von
ordnungsbasierten, kombinatorischen Optimierungsproblemen
entwickelt, kann aber auch für andersgeartete Fragestellungen
genutzt werden. LibGA bietet verschiedene Ansätze
(generational/steady-state), diverse Möglichkeiten für
Selektions- (uniform-random, roulette, rank-biased),
Replacement- (append, by-rank, first-weaker, weakest),
Mutations- (simple-invert, simple-random, swap) sowie
Crossover-Operatoren (simple, uniform, oder1/2, position, cycle,
PMX, asexual). Die Dokumentation führt in den Gebrauch der
Bibliothek und deren prinzipielle Eigenschaften ein.
- Dokumentation (postscript):
~awbs/Daten/Genetic/libga101/doc/libGA-{1|2}.ps.gz
- Library:
~awbs/Daten/Genetic/libga101/${ARCHITECTURE}/libGA.a
- Headerfile: ~awbs/Daten/Genetic/libga101/src/ga.h
- Falls nötig, kann das src-Verzeichnis kopiert und dann
mit make eine neue Library erzeugt werden.