vorige nächste

Genetische Algorithmen: Ein anderer Ansatz


Ein ganz anderer Ansatz zur Lösung als der A*-Algorithmus verfolgt mit den Evolutionären Algorithmen eine grundsätzlich andere Suchstrategie. Es ist eine Strategie, die wir am Anfang unseres Kurses nur ganz nebenbei erwähnt haben, eigentlich nur der Vollständigkeit halber, und dann gleich wieder verworfen haben. Es ist der Ansatz von zufälliger Suche!

Wir waren uns schon am Anfang klar geworden, dass wir bei diesem Ansatz damit rechnen müssen, gar nicht zur Lösung zu kommen, angewandt auf das tsp heißt das, nicht zu einem Weg minimaler Länge zu kommen.

Ein solches Verfahren liefert uns in der Regel also nicht "die" optimale Lösung, sondern nur eine suboptimale. Das ist aber auch schon viel, wenn man denn keine andere Methode hat, deren Lösungen die Qualität der so erreichten haben.

tsp Bild

 


Anmerkung 1: Evolutionäre Algorithmen

Evolutionäre Algorithmen sind begrifflich etwas weiter gefasst als der Begriff der Genetischen Algorithmen, deren Anwendung im entsprechenden Abschnitt beschrieben wird.

Anmerkung 2: suboptimale

Beachten Sie, dass die wirklich optimale Lösung zu finden, in vielen Anwendungen eine im strengen Sinne "akademische" Frage ist, die den Anwender herzlich wenig interessiert. Der will nur möglichst wenig Kosten haben, das soll aber jetzt erreicht werden und nicht in ferner Zukunft!