Kombinatorische Optimierung und Fitnesslandschaft-Untersuchungen

Auf lokaler Suche basierende Meta-Heuristiken wie Simulated Annealing, Tabu Search und Genetische Algorithmen lassen sich für viele kombinatorische Optimierungsprobleme erfolgreich einsetzen. Die Erfahrung zeigt jedoch, dass die Lösungsgüte der lokalen Suche von der Konfiguration des darunter liegenden Suchraums beeinflusst wird. Die Struktur der Fitnesslandschaft beleuchtet in anschaulicher Weise die Frage nach dem Schwierigkeitsgrad, mit dem ein lokales Suchverfahren konfrontiert wird. Im Allgemeinen erscheinen Landschaften mit vielen weit verstreuten lokalen Optima und geringer Fitness-Distanz-Korrelation als schwer zu lösende Probleme für eine lokales Suchverfahren. In der Literatur werden zwei Wege unterschieden, um kombinatorische Optimierungsprobleme mit komplexen Fitnesslandschaften zu lösen. Eine Möglichkeit besteht in der Entwicklung problemspezifischer Nachbarschaften, die den Lösungsraum aufgrund spezieller Moves gewissermaßen glätten und somit Barrieren zwischen lokalen Minima abbauen. Eine andere Möglichkeit ist es, Steuerungsparameter für die verwendete Meta-Heuristik zu definieren, wodurch temporäre Verschlechterungen bei der lokalen Suche zugelassen werden, um Barrieren zwischen den Optima überwinden zu können. Aufgrund des unzureichenden theoretischen Verständnisses werden vielfach statistische Kennzahlen für die Beschreibung einer Fitnesslandschaft herangezogen. Das Forschungsprojekt untersucht die problemspezifische Aussagekraft von Kennzahlen für Fitnesslandschaften am Beispiel von Schedulingproblemen.