Soweit ich weiß, probieren genetische Algorithmen mehrere Variationen aus und bewerten die Fitness jeder Variation. Dann wählen sie die besten Variationen aus, ändern sie ein wenig und setzen den Prozess mit der nächsten Generation fort.
Aber was ist, wenn wir unbegrenzte Rechenressourcen haben? Können wir dann einfach alle möglichen Variationen ausprobieren und ihre Fitness bewerten, ohne auf den komplexen Prozess der Zucht neuer Generationen zurückgreifen zu müssen? Mit anderen Worten, werden genetische Algorithmen nur benötigt, wenn die Berechnung teuer ist und eine Brute-Force-Methode unmöglich ist? Oder fügen sie noch weitere Vorteile hinzu?
genetic-algorithms
Eugene
quelle
quelle
Antworten:
Genetische Algorithmen sind im Grunde eine geführte Trial-and-Error-Methode. Der einzige Vorteil, den ich mir für eine GA gegenüber einer umfassenden Suche vorstellen kann, besteht darin, dass Sie, da GA eine Fitnessfunktion schrittweise optimiert, möglicherweise schneller zu einer optimalen Lösung gelangen, da die GA Lösungen bevorzugt, die schrittweise besser sind. Eine umfassende Suche, die garantiert eine Lösung findet, kann viel bewirken.
Wenn "Rechenressourcen" CPU, aber keinen Speicher bedeutet, hat der GA-Genpool möglicherweise einen geringeren Speicherbedarf und benötigt weniger Speicher.
Auf der anderen Seite kann ein GA aufgrund des Bergsteigens an einem lokalen Maximum hängen bleiben und Mutationen können möglicherweise nicht ausreichen, um ihn loszuwerden.
Außerdem nimmt die Suchzeit für GA exponentiell mit der Größe der Eingabe zu, sodass eine umfassende Suche möglicherweise immer schneller wird, abhängig von der Größe des gesuchten Bereichs und davon, ob Sie die Größe des Bereichs einschränken können durch Ausschluss von Möglichkeiten.
...
In letzter Zeit habe ich über GAs in Bezug auf "Entropie pro Sekunde" nachgedacht und den Fortschritt meiner GA als Maß dafür gemessen, wie viele verschiedene Möglichkeiten sie pro Sekunde durchläuft. Dann kann ich das mit der Gesamtentropie des Problemraums vergleichen. Wenn eine Brute-Force-Suche diese Entropie pro Sekunde mit Parallelisierung oder schnellen Prozessoren übertreffen kann, ist die "beste Punktzahl" eines GA nicht besser als eine entdeckte "beste Punktzahl".
Aber ich habe das gerade übernudelt; Ich habe einen GA noch nicht so instrumentiert.
(Entropie ist
ln(N)für N mögliche Zustände oderln(N) - sum(n * ln(n) for all n) / Nwonsind die möglichen Wege, um ein Ergebnis aus N möglichen Ergebnissen zu erzielen.)Interessante Frage :)
quelle
Ja, wenn die Berechnung kostenlos wäre, würden Sie überhaupt keine genetischen Algorithmen benötigen. Aber denken Sie daran, dass dies ein riesiges "Wenn" ist, das keiner von uns jemals erleben wird!
Da Sie jedoch fragen, ob die Berechnung unendlich schnell wäre, gäbe es keinen Grund, den einfachsten kombinatorischen Brute-Force-Vorschlaghammer zum Generieren und Testen eines Problems nicht anzuwenden. Jede Frage, die mit einem endlichen Satz von Informationen beantwortet werden kann (dh ein Problem der Einschränkungszufriedenheit im weitesten Sinne dieses Begriffs, das in der Tat ziemlich locker ist), wäre sofort lösbar. Bergsteigen, Heuristik und all die cleveren Vereinfachungen, mit denen wir jetzt beispielsweise eine erstklassige Schachmaschine bauen, wären einfach nicht notwendig.
Anders ausgedrückt: Wenn sich die Berechnung einer unendlichen Geschwindigkeit nähert, hängt die Entscheidung, welcher Ansatz verwendet werden soll, davon ab, wie schwierig es ist , das auszuführende Computerprogramm zu schreiben , und nicht davon, wie lange es dauert, bis es tatsächlich ausgeführt wird. und das bedeutet, dass es sich einfach nicht lohnt, einen komplizierteren Algorithmus zu erfinden, wenn der einfachste möglich gleichzeitig funktioniert und ausgeführt wird.
Die Berechnung hat sich in der Tat in diese Richtung bewegt, aber denken Sie auch hier daran, dass wir noch nicht ganz da sind und es wahrscheinlich nie sein werden. (Es sei denn, der Quantencomputer ist natürlich perfektioniert.)
quelle
Das Problem bei unendlich schnellen Berechnungen ist, dass sie unendlich schnell einen Zustandsraum abdecken, der größer ist als die Informationsgrenze unseres bekannten Universums. Sie haben "Brute Force" erwähnt, denken Sie jedoch daran, dass Brute Forcing Chess beispielsweise eine Ausgabe erzeugen kann, deren Größe die Anzahl der Atome im Universum überschreitet.
Wenn Sie das Beispiel Schach weiter verfolgen, müssen Sie beim Brute-Force-Schach die Anzahl der von Ihnen in Betracht gezogenen Schachbrettkombinationen verringern und eine Entscheidung treffen, welche Zustände beibehalten und welche Zustände verworfen werden sollen - also in der Tat selektive Algorithmen. wie genetische Algorithmen, wird für immer notwendig sein.
quelle
Wenn mit "unbegrenzten Rechenressourcen" gemeint ist, dass Ihr Algorithmus 0 Mal benötigt und der Speicher unbegrenzt ist und Elektrizität keine Rolle spielt, würde ich sagen, dass der einzige Algorithmus, der verwendet wird, ein Brute-Force-Algorithmus ist, der jede mögliche Eingabe versucht und garantiert ist um das Beste zu finden. Wenn Sie sich auf unbegrenzten Speicher beziehen, aber einen möglichen Zeitunterschied benötigen, ist ein genetischer Algorithmus möglicherweise vorzuziehen, da er möglicherweise schneller zu einer Lösung führt als ein Brute-Force-Algorithmus. Die Lösung des genetischen Algorithmus ist jedoch möglicherweise nicht optimal. Je nach Kontext und Ihren Anforderungen bevorzugen Sie möglicherweise immer noch die Brute-Force-Methode.
Da unbegrenzte Rechenressourcen nicht möglich sind, schien die Frage zunächst wie eine müßige Spekulation. Mit zunehmender Rechenleistung wird die Frage jedoch immer relevanter, da wir in Zeiten enormer Supercomputer möglicherweise keine genetischen Algorithmen benötigen. Ich habe jedoch festgestellt, dass Computer, selbst wenn sie leistungsfähiger werden, immer wieder aufgefordert werden, immer härtere Berechnungen mit immer mehr Daten durchzuführen. Letztendlich denke ich, dass genetische Algorithmen auf absehbare Zeit bei uns sein werden und auch dann verwendet werden, wenn viel Rechenleistung verfügbar ist.
Wenn jedoch jemals wirklich unbegrenzte Rechenressourcen verfügbar würden, würde sich viel mehr ändern, als ob genetische Algorithmen verwendet werden sollen oder nicht.
quelle