Wird ein genetischer Algorithmus benötigt, wenn die Berechnung unendlich schnell ist?

8

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?

Eugene
quelle
1
Ich habe dies als zu Stackoverflow gehörend gekennzeichnet, aber meiner Meinung nach gehört es zur Website für Informatik (für die es im Kennzeichnungsassistenten keine Option gibt). (Aber ich habe immer noch gestimmt; interessante Frage!)
Patrick M
5
Wenn Sie über unendlichen Speicher und unendlich schnelle Berechnungen verfügen, können Sie einfach alle möglichen Zustände des Systems generieren, dann jeden Zustand auswerten und die idealen auswählen oder daraus schließen, dass keiner der möglichen Zustände zufriedenstellend ist. "Unendlich" macht die ganze Frage zu einer sinnlosen IMO. Nun, außer wenn der Problemraum auch unendlich ist, aber dann sind wir ziemlich weit entfernt von allem, was ein "Programmierer" tun könnte.
Hyde

Antworten:

14

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 oder ln(N) - sum(n * ln(n) for all n) / Nwo nsind die möglichen Wege, um ein Ergebnis aus N möglichen Ergebnissen zu erzielen.)

Interessante Frage :)

rauben
quelle
1
Läuft diese Entropiefrage nicht im Grunde genommen auf "GAs wiederholen oft Zustände und Brute Force tut dies niemals"? Die Art und Weise, wie ich darüber nachdenke, dass ein Suchalgorithmus eine Permutation über den Lösungsraum definiert und durch diese definiert wird. Kurz gesagt, ein Suchalgorithmus ist nichts anderes als die Reihenfolge, in der er die Punkte besucht (Modulo etwas Overhead aufgrund wiederholter Auswertungen). Die NFL-Theoreme sind dann vollkommen sinnvoll - ich kann immer ein Problem konstruieren, für das mein Algorithmus früher als Ihr Optimum ankommt und umgekehrt.
Deong
1
@deong In vielen Fällen können gelegentlich bessere Zustände oder sogar optimale Zustände abgelehnt werden (z. B. nicht deterministische Systeme), so dass es erforderlich sein kann, Fälle wiederholt zu suchen.
Resgh
1
Ich würde sagen, es steckt ein bisschen mehr dahinter als nur das; Erstens, während die Frage "unbegrenzte Rechenressourcen" voraussetzt, werden GAs normalerweise verwendet, wenn eine umfassende Suche völlig unmöglich ist (wir sprechen hier von "Warten auf das Ende des Universums", was hier nicht möglich ist, und Sie nähern sich schnell mit interessanten Problemen). Zweitens haben GAs zusätzlich zu einer einfachen alten Mutation einen Crossover-Operator. Für bestimmte Arten von Problemen (NFL-Holding) ist dies eine sehr gute Heuristik und weitaus besser als eine erschöpfende Suche. Dem Rest würde ich weitgehend zustimmen.
Daniel B
4
GAs werden im Allgemeinen nicht verwendet, um optimale Lösungen zu finden. Sie dienen dazu, vernünftige Lösungen für einen begrenzten Zeitraum zu finden.
Cruncher
1
Simuliertes Tempern ist eine Variation des genetischen Algorithmus, die das lokale Maxima / Minima-Problem sehr effektiv angeht.
recursion.ninja
6

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.)

Kilian Foth
quelle
3
Selbst wenn Quantencomputer perfektioniert sind, vermuten wir (wissen es aber noch nicht genau), dass NP-Complete keine Teilmenge von BQP ist. Wenn dies zutrifft, bedeutet dies, dass die Klasse von Problemen, die von einem Quantencomputer mit hoher Wahrscheinlichkeit in Polynomzeit gelöst werden kann, nicht die NP-harten Optimierungsprobleme enthält, für die man im Allgemeinen eine GA verwenden würde.
Deong
1
Es gibt viel größere Konsequenzen bei unendlicher Rechengeschwindigkeit ... Zum Beispiel werden jetzt alle erkennbaren Probleme entscheidbar. Yay für das Halteproblem!
Cruncher
3

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.

frage das Kollektiv
quelle
1
Nun, es sei denn, seltsame Physik wie geschlossene zeitliche Kurven (gegen Ende) funktionieren und können für allgemeine Berechnungen verwendet werden.
Eigentlich ist GA überhaupt nicht gut für Schach. Heuristischer Schnitt, ja
Konrad Morawski
Erinnert mich an diese Geschichte ... Als ich sie zum ersten Mal las, war ich verwirrt, warum das Schreiben einer Suchroutine lange dauerte - es dauerte eine Weile, bis mir klar wurde, dass sich der Aspekt "Suche" vom Aspekt "Simulation" unterschied .
Pandubear
2

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.

Paul J Abernathy
quelle
In Anlehnung an "keine besseren Algorithmen benötigen" oder was haben Sie in Zukunft, weil unsere Maschinen so leistungsfähig sind: Ich denke oft an winzige Optimierungen, die in frühen CPUs wie Pipelining vorgenommen wurden. Es erscheint uns heutzutage trivial, ein paar zusätzliche Taktzyklen zu gewinnen, aber diese Zyklen summieren sich. Ich denke, dass es entscheidend ist, diese kleinen Optimierungen vorzunehmen, um uns in Zukunft zu superschnellen Computern zu bewegen. Ohne sie hätten wir nur ein bisschen schnelle Computer.
DLeh