vorige nächste

Vorbedingungen


Wir wollen dabei die Grundlage nicht vergessen. An erster Stelle sollte bei der Betrachtung von Algorithmen die Frage stehen:

Warum überhaupt ...?

Wie wir inzwischen herausgefunden haben, ist der wesentliche Grund, dass es Probleme gibt, die auf anderem Wege nicht oder nicht effektiv genug gelöst werden können. Wie kann das sein, wo doch die Leistung von Computern in den letzten Jahren so immens zugenommen hat?
Die Antwort ist sehr einfach: Es sind Probleme, die so groß sind, dass selbst mit den schnellsten denkbaren Computern eine Lösung innerhalb der Lebensdauer des Weltalls nicht möglich ist. Insbesondere die [np-vollständigen Probleme haben (bisher?) einer vollständigen Lösung standhaft getrotzt. Viele von ihnen haben neben dieser vertrackten Eigenschaft aber gleichzeitig die Möglichkeit, prinzipiell mögliche Zustände des Systems nicht nur anzugeben, sondern sie auch schnell zu bewerten.

Welche Bedingungen müssen für einen Ansatz mit Evolutionären Algorithmen vorgegeben sein?

  1. Das Problem ist ein Suchproblem, da es kein direktes Lösungsverfahren gibt.
  2. Der Suchraum ist so groß, dass eine vollständige Suche versagen muss.
  3. Es gibt aber eine relativ schnelle Bewertungsfunktion für Zustände im Lösungsraum.
  4. Keines der optimierten Suchverfahren liefert eine Lösung.

 


Anmerkung 1:

[np-vollständige Probleme sind Probleme, bei denen zwar die Größe des Lösungsraumes exponentiell von der Zahl der Knoten abhängt, bei denen aber andererseits eine Bewertung mit polynomialem Aufwand zu bestimmen ist.]

Anmerkung 2:

Die Informatiker sind immer vorsichtig. Solange nicht nachgewiesen wurde, dass es tatsächlich nicht geht, nimmt man zwar an, dass es nicht geht und stellt sich darauf ein, nimmt aber auch an, dass es dennoch gehen könnte.