JGAP parallelisieren?

[Dark Halo]

Hallo,

ich hoffe, ich bin in diesem Forum richtig gelandet.

In einem Projekt würde ich gerne das Framework JGAP für evolutionäre Algorithmen benutzen. Da der Grundaufbau eines evolutionären Algorithmus nicht besonders kompliziert ist, lässt sich an vielen Stellen parallelisieren. Das Paradebeispiel ist die Berechnung der Fitness für ein Individuum, was innerhalb der Population für jedes Individuum unabhängig geschehen kann, d.h. die Aufrufe lassen sich hervorragend parallelisieren.

Da die Berechnungen bei dem Projekt doch recht intensiv sind, würde ich gerne die vorhandenen Ressourcen größtmöglich auslasten und die benötigte Zeit, so gut es geht, minimieren.

Ich habe allerdings kein Indiz dafür auffinden können, dass JGAP bereits von Haus aus parallelisiert, was auch nachvollziehbar ist; schließlich weiß das Framework ja nicht, ob nicht doch Abhängigkeiten irgendwo bestehen. Ebenfalls habe ich aber auch keine Gründe gefunden, die dafür sprechen, dass benutzerdefinierte Parallelisierung überhaupt möglich ist.

Aus diesem Grund suche ich nun hier Rat, in der Hoffnung, dass jemand vielleicht Bescheid weiß: Kann man JGAP benutzerdefiniert parallelisieren? Oder muss ich ggf. das Framework beiseite legen und mir selbst das Grundgerüst zusammenbasteln?

Um es nochmal klar zu stellen: Es geht mir nicht darum, die Fitnessfunktion oder genetische Operatoren zu parallelisieren, sondern die Aufrufe von jenen!
Es muss bspw. für 40 Individuen pro Generation jeweils einmal die Fitnessfunktion zur Berechnung des Fitnesswertes aufgerufen werden. Ich hätte also gerne, dass bei vier Threads statt 40 sequentiellen nur vier Mal 10 ( = 40 / 4) parallele Aufrufe benötigt werden.

Ich hoffe, dass jemand Rat weiß.

 

[Marco13]

Klingt interessant, aber auch vieeel zu spezifisch, als dass man damit rechnen könnte, dass da jemand eine Antwort einfach so aus dem Ärmel schüttelt. Nach einem 5-minütigen Blick über die Doku würde ich mal schauen, was die "Genotype#evolve"-Methode so macht...

 

[0x7F800000]

Ich würde einfach jedem processor ein Genotype zuweisen, sodass jeder Prozessor für sich alleine evolve() in einer schleife aufruft. Alle paar hunderttausend Zyklen hältst du die einzelnen Threads an, holst dir die Population's der Genotype, schmeißt die alle in ein Topf, dezimierst die mit der Fitness-Funktion auf irgendeinen Bruchteil, unterteilst die übriggebliebenen wieder in "Genotypes" (pro Thread eins), und lässt diese Gruppen für eine Weile weiter unabhängig voneinander evolvieren.... :bahnhof:

 

[Dark Halo]

Hallo,

ja, die Frage ist sehr spezifisch, das stimmt. Aber genau deswegen stelle ich sie auch hier: Ich konnte nämlich keine aussagekräftigen Informationen diesbezüglich ausfindig machen, und meine letzte Hoffnung lag eben darin, dass ja vielleicht doch irgendwer schon einmal in die Richtung was gemacht hat. Dass das nicht sehr wahrscheinlich ist, war mir auch klar. Aber Probieren geht über Studieren, eh?

Die Idee, verschiedene Genotypen von jeweils einem Thread simulieren zu lassen, war zunächst auch mein erster Gedanke. Das Problem dabei ist allerdings, dass die verschiedenen Genotypen im Schnitt gleich schnell gegen das (Sub)Optimum konvergieren. Ich gewinne also gar keine Geschwindigkeit. Es können natürlich Schwankungen auftreten, dass Genotyp 1 "besser" ist als Genotyp 2, aber nach dem Gesetz der großen Zahlen wird die Schwankung gegen 0 gehen. Ich habe nach k Iterationen also n verschiedene Genotypen, die sich im Grunde nicht viel nehmen. Im Gegenteil: Die einzelnen Genotypen konvergieren gegen eine lokale Lösung, die vielleicht gar nicht dem Optimum entspricht! Warum ist das so?

Verständlicherweise werde ich pro Thread nicht dieselbe Anzahl an Individuen in der Population verwenden, als wenn ich nur einen Thread verwenden würde. Ich würde bei n Threads eben nur pro Thread m / n viele Individuen betrachten, wenn es insgesamt in der Gesamtpopulation m Individuen gibt. Darunter leidet dann natürlich die Heterogenität innerhalb des Genotyps, denn es gibt weniger verschiedene Individuen. Nach einigen Iterationen herrscht nur noch Homogenität (idealerweise). Natürlich würde das Mischen der verschiedenen Genotypen vermutlich wieder zu hoher (erwünschter) Heterogenität führen, allerdings geschieht dies viel zu selten: Die meiste Zeit herrscht Homogenität unter den Individuen innerhalb des Genotyps. Das will man aber nicht, denn so gibt es keine Diversität unter den Individuen, sodass sich noch optimalere Lösungen bilden können.

Meine Idee ist es also nun, dass ich von der Klasse GABreeder ableite und dort die evolve()-Methode "mutiere" (wenn wir schon bei den Begriffen sind ). Denn diese Methode leistet letztlich den Hauptarbeit: Selektieren, Crossover, Mutieren etc. Alles Dinge, die sich wunderbar parallelisieren lassen. Den Grundteil kann ich unverändert übernehmen. Die Teile, die sich parallelisieren lassen, kann man allerdings anpassen. Der Konfiguration muss man dann natürlich noch mitteilen, welchen Brüter sie zu verwenden hat.

Ich hoffe mal, dass das meinen Wünschen entspricht. Und wer weiß: Vielleicht hat in Zukunft ja jemand anders ein ähnliches Problem und stößt dann auf diesen Thread.

Grüße
- Das alles umgebende Dunkle Halo.