Gentischer Optimierer

[Gabber19]

Hidiho,

Ich hab vor mir nen Genetischen Optimierer zu basteln.
Wieso das Ganze?
1.Weil wir inner Schule ein Problem lösen dürfen sollen müssen, das sich nicht analytisch lösen lässt. (man kann keine Formel nehmen und Rechnen).
2. Aus Spass an der Freude

Programmiersprache soll Java sein, weil ich da im Mom am weitesten bin, und auch genug Ansprechpartner dafür hab.

Jetzt die Frage, hat einer von euch schon mal so einen gemacht, oder damit hantiert?

Gruss
Gabber

PS: Wieso hat es hier kein Forum für "SelfMade" SW ?

 

[DeepInTrouble]

Blöde Frage, aber was is ein "Genetischer Optimierer"

MfG DepInTrouble

 

[Gabber19]

Blöde Frage, aber was is ein "Genetischer Optimierer"

MfG DepInTrouble

Bei dieser Optimierungsart, wird eine Art "Lösungspopulation" gezüchtet, und danach die Beste Lösung genommen.
Das ist auch die Grundlage für einen Biologischen "Rechner", obwohl das genau der falsche Name ist und man damit nichts machen kann, wozu die heutigen Rechner im Stande sind.
Dieser biologische "Rechner" ist genau da gut, wo der heutige Rechner versagt.

Ein beispielhaftes Problem ist das "travelling Salesman"Problem.
Nehmen wir an, wir haben 16 Destinationen, die wir der Reihe nach besuchen wollen.
Da wir aber aus Schottland kommen, wollen wir Sprit sparen und suchen uns den kürzesten Weg aus.
Das ist eine ziemlich eklige angelegenheit..
bei 2 Orten ist die Sache klar, eine Möglichkeit
bei 3 Orten .. 2 Möglichkeiten
bei 4 Orten .. 6 Möglichkeiten
bei 5 Orten .. 120 Möglichkeiten
([n-1]! für die MatheFreunde )
bei 16 Orten wären es 1'307'674'368'000
Schauen wir uns mal den Rechenaufwand dafür an :

Speicherplatz pro Möglichkeit :
Jede Möglichkeit hat einen Start und 15 Destinationen drin, das sind 4 Bit*16 (da es 16 Destinationen gibt, 2^4=16).
--> Also 256 Bit oder 32 Byte

Speicherplatz für alle Lösungen
(Anzahl Lösungen * Speicherplatz pro Lösung)
rund 38 TerraByte! (mit 1kB=1024Byte).

Mal abgesehen davon, dass man die Lösungen generieren muss, nur mal der Rechenaufwand für die Wege von allen Lösungen:

Rechenaufwand pro Lösung :
Es müssen 15 Teilstücke zusammengezählt werden. Wir haben hier Integer als Wege und darum brauchen wir 15 Instruktionen / Lösung.

Rechenaufwand Problem:
15 * (n-1)! = 294 TerraI
Ein 2.4GHz P4 schafft 6400 MIPS (SysoftSandra2003) und hätte 12h alleine um die Wege auszurechnen.

Also, dieser Weg wird uns die nächsten paar Jahre nicht schnell genug zu einer Lösung bringen oder ?

und hier kommt das genetische Optimieren daher, es generiert zufällig eine Population mit Lösungen, lässt schlechte sterben, erschafft neue aus älteren und lässt das mal ne Weile laufen, so bekommt man schnell "quasi"optimale Lösungen.

Wo die Mathematik versagt, kommt ihr die Biologie (Darwin) zu Hilfe.

Hoffe das dient als Anfang

 

[KurzGedacht]

 

[impac7]

Habe ich den Algo richtig verstanden?

Man berechnet die Länge eines zufalligen Weges und speicher Weg und dazugehörige Länge. Dann bestimmt man einen weiteren zufalligen Weg, berechnet die Länge und vergleicht den gespeicheerten Weg mit dem eben berechneten Wert. Der kürzere Weg wird wieder gespeichert der längere überschrieben, so dass immer nur ein Weg Speicherplatz belegt.

Etwa so?

 

[Gabber19]

Nein, das wäre auch eine Möglichkeit, allerdings haben PCs nur schlechte Zufallsgeneratoren.

Bei einem Genetischen Optimierer werden x Individuen zufällig gestartet, diese nach gewissen Kriterien wieder gekillt, mutiert, vermehrt.
so enstehen immer "fittere" Lösungen, wenn man das gut macht, bekommt man eine ganze Population verschiedener guter Lösungen,
macht man es nicht so geschickt, hat man danach einfach eine Population gleicher Lösungen.