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.