Viele praktische Probleme sind „schwierig“ in dem Sinne, dass sie zu komplex sind, um in nützlicher Zeit gelöst zu werden. Zu dieser Problemklasse gehören viele Optimierungsaufgaben. Für praktische Anwendungen ist es oft genügend, die tatsächliche Lösung hinreichend gut anzunähern. Dafür bieten sich verschiedene Optimierungsmethoden an, wie z.B. genetische Algorithmen (GA).

Genetischen Algorithmen sind stochastische Suchverfahren, die Optimierungsstrategien von der Natur „abschauen“, abstrahieren und auf das zu lösende Problem anpassen. GA funktionieren nach den Prinzipien der biologischen Evolution (Darwinismus): Eine Menge von Lösungskandidaten wird als Ausgangspopulation erzeugt und anschliessend einer simulierten Evolution unterzogen. Die Lösungskandidaten „pflanzen sich fort“ und unterliegen einem Selektionsdruck, der dafür sorgt, dass die Qualität des geeignetsten Individuums von Generation zu Generation zunimmt oder zumindest nicht abnimmt. Schlechte Lösungen sterben aus, die Besten überleben. Lösungen werden zufällig gekreuzt (rekombiniert) und vereinzelt mutiert.

Im Forschungsbereich Optimierungsmethoden wird die GA Technologie auf verschiedene Problemstellungen angewendet, wie z.B. Routenplanung für Inspektionsfahrten, Optimierung von Projektplänen, Optimierung von Fussgängerströmen oder Optimierung von Stanzwerkzeugen. Weitere Anwendungen sind ein Generator von graphischen Logos oder das Matching von CVs mit Stellenbeschreibungen.

Herausforderungen

• Finden einer geeigneten Datenstruktur für die Repräsentation der Lösungskandidaten.
• Finden von effizienten, problemspezifischen Operatoren (Rekombinatoren, Mutatoren und Selektoren) welche die genotypischen Lösungen einer künstlichen Evolution unterwerfen.

Thema

• Genetische Algorithmen