suche Algorithmus, um Inzucht zu vermeiden
-
Ich bastele gerade an nem genetischen Algorithmus. Ohne, daß ich es wollte,
(vorher plante) haben soch bereits die Begriffe Art, Rasse und Individuum
getrennt. Und jetzt hab ich noch ne Idee. Ich will zur Erhaltung der Vielfalt
im Gen-Pool ab jetzt Inzucht vermeiden.
Vielleicht so, daß Viecher, die in der Liste der Vorfahren (einschließlich sich
selber) bis zu den Grosseltern nen gemeinsamen Vertreter haben, nicht heiraten
dürfen (oder wollen).
Bisher steht ungefähr sowas:class Animal1:public Animal{ private: int* table; Animal1(const Animal1&);//forbidden Animal1& operator=(const Animal1&);//forbidden public: int score;//for foreign use only public: Animal1(); ~Animal1(); int live(World* w);//do "good" actions in world and world will increase my score void mergein(Warrior1 const& a,Warrior1 const& b);//replace me by new created child of a and b void exportScript();//write body of live() with hardcoded table };Es ist natürlich ein leichtes, auch noch
Animal* parent1; Animal* parent2;einzubauen.
Mein naiver Ansatz wäre dannvoid sammleVorfahren(Animal* a,tiefe t,vector<Animal*>& vorfahren){ vorfahren.push_back(a); if(t>0){ sammleVorfaren(a->parent1,t-1,vorfahren); sammleVorfaren(a->parent2,t-1,vorfahren); } } bool verwandt(Anlimal* a,Animal* b){ vector<Animal*> vorfahren; sammleVorfahren(a,2,vorfaren); sammleVorfahren(b,2,vorfaren); vector.sort(); return vector.hatGleicheAufeinanderfolgendeElemente(); }Aber das sieht ja furchtbar schlimm aus! Nee, sowas code ich nicht gerne.
Daher frage ich, ob Euch was einfällt.
Ihr seid vollig frei in der Wahl der Waffen. Hauptsache, es wird nachher schnell.
Inbesondere müssen es nicht Zeiger auf Vorfahren sein, sondern denkbar sind auch
ints oder strings, die bei verwandtschaft sich nr in soundsovielen Bitstellen
unerscheiden oder sowas. Und das Verfahren darf sogar manchmal nen Fehler machen,
wenn es dafür sauschnell wird. Unter 1% wäre aber schon fein.
-
Wie lange leben deine Tiere eigentlich?
Ich meine damit:
Können sich Tiere der n-ten Generation eventuell mit Tieren
der (n+x)-ten Generation paaren?Jockel
-
is das nich egal? ich habe bis jetzt genetische Algorithmen eher als Optimierungsverfahren betrachtet, dh. bessere min max suche in irgendeinem Funktionsgebirge vor allem wenn zb. die Gradienten unbekannt sind, ich glaube bei genetischen algorithmen oder besser "Evolutionsstrategien" sollte man sich nich zu sehr auf das natürliche Vorbild versteifen, da ein rekombinier-, mutierbarer Bitvektor nun mal kein wirkliches Lebewesen ist und wenn du deinen "Genpool" vergrößern willst starte einfach mit ner größeren Population oder nimm entsprechend Lange "Eingeschaftsvektoren", wird sich sowieso alles regulieren und mal ganz davon abgesehen wer sagt denn das "Inzucht" bei diesen Algorithmen nicht zu was besserem führt, wie schon gesagt man sollte es nicht so ganz streng betrachten
bye
tt
-
Handelt es sich hierbei denn um einen "normalen" genetischen Algorithmus?
Wohl eher nicht, denn dann ist es doch uninteressant, ob
Individuen die gleichen Vorfahren haben.Jockel
-
was ist denn für dich ein "normaler genetischer Algorithmus"?
bye
tt
-
-
Warte mal nicht das ich dich jetzt falsch verstehe, auf was war dein Post vorher bezogen?
Handelt es sich hierbei denn um einen "normalen" genetischen Algorithmus?
[...]Wenn das auf meins bezogen war dann sind wir ja einer Meinung was ein "normaler genetischer Algorithmus" macht.
Andersherum müsste das aber heissen das Volkards algo dann kein "normaler genetischer Algorithmus ist"...Ich bin grad etwas verwirrt über deine Antwort.
bye
tt
-
So hab ich unser Gespräch interpretiert:
Ich: Kinder aus unterschiedlichen Generationen (an volkard)?
(Ich gehe davon aus, dass kein normaler Algo. genutzt wird).Du: Das ist egal (weil du meinst, das es sich doch um normalen Algo. handelt).
Ich: Glaube ist kein normaler Algo. gemeint, daher das Interesse für die Eltern.
Danch: Klärung, was normaler Algo. ist.
So hab ich's verstanden.
Letztlich kann uns nur Volkard sagen, was sein Algorithmus eigentlich ist.
Jockel
-
ok, dann hab ich dich doch nich falsch verstanden
Letztlich kann uns nur Volkard sagen, was sein Algorithmus eigentlich ist.
jupp
bye
tt
-
Jockelx schrieb:
Wie lange leben deine Tiere eigentlich?
Ich meine damit:
Können sich Tiere der n-ten Generation eventuell mit Tieren
der (n+x)-ten Generation paaren?ja. es paaren sich zur zeit die aus dem ersten drittel mit denen aus dem zweiten drittel und die kinder ersetzen das dritte drittel in der nach fitness sortierten liste.
-
Jockelx schrieb:
Handelt es sich hierbei denn um einen "normalen" genetischen Algorithmus?
ja. beim kinderkriegen crossover und mutation. die auswahl mit den dritteln ist nicht ganz normal, aber bisher ganz erfolgreich.
void Warrior1::mergein(Warrior1 const& a,Warrior1 const& b){ int f=rand()%1; for(int i=0;i<SIZE;++i){ if(rand()%16==0) f^=1; if(rand()%64==0) table[i]=rand()%8; else if(f) table[i]=a.table[i]; else table[i]=b.table[i]; } }Wohl eher nicht, denn dann ist es doch uninteressant, ob
Individuen die gleichen Vorfahren haben.die inzucht macht den gen-pool zu einseitig. der zufällig mal enstandene top-warrior kreuzt sich mit allen anderen wiederholt bevor andere gen-linien kommen konnten.
-
Wahrscheinlich zu stumpf, aber wenigstens schon mal ne Idee:
Jedem Animal ne zufällige oder eindeutige ID, 4 Vorfahren-ID's
und beim Paaren diese halt vergleichen.Ich weiss, ist etwas armselig, aber ich überleg noch ein
bisschen.Jockel
-
Hallo Volkard, ist ja witzig, ich beschäftige mich auch gerade mit GA
Was du vor hast ("Inzucht verhindern") macht man manchmal über die Hamming Distanz der beiden Strings. Allerdings finde ich dieses Verhindern der INzucht gar nciht mal so toll, weil dadurch die Konvergenz der Population kaputt gemacht wird.
-
btw, ich suche noch ein schönes Optimierungsproblem um meine GA und EA zu testen, hat jemand was nettes ?
-
Einhorn schrieb:
btw, ich suche noch ein schönes Optimierungsproblem um meine GA und EA zu testen, hat jemand was nettes ?
[url="http://www.gridwars.com/"]GridWars[/url]
bei mir war erst das probem da, dann erst GA.
-
Allerdings finde ich dieses Verhindern der INzucht gar nciht mal so toll,
weil dadurch die Konvergenz der Population kaputt gemacht wird.jo, schon richtig. aber meine früheren versuche mit nem 4-gewinnt-spiel sind
immer kläglich daran gescheitert, daß ein einigermaßen guter bot sein erbgut
ruck zuck über alle individuen verteilt hatte. alle saßen auf dem selben lokalen
gipfel und waren scheiße und alle waren gleich. bis auf die mutierten, die waren
alle schlechter. das inzucht-verhindern würde zwar nicht verhindern, daß die
bots alle auf einen loalen gipfel stürmen, aber wenigstens vstark verzögern,
daß der starke bot sein erbgut so massiv verstreut, daß ar kein anderes mehr existiert.
und so schlimm stört es die konvergenz wohl auch nicht, immerhin heiratet er ja nur
solche bots nicht, die ihm eh schon recht ähnlich sind.
deswegen habe ich diesmal arten. bots verschiedener arten können nicht heiraten.
so will ich dafür sorgen, daß ne art, die nen lokalen gipfel erreicht hat und
stagniert, wenigstens ner anderen art als guter trainingspartner bereitsteht.
und das kreuzen und mutieren ist artspezifisch, da kann ich gleich gegeneinander
testen, was besser ist.
was mir zur zeit am meisten sorgen macht, ist die selektion.
-
mal eine Frage, ist es nicht Sinn der Sache das der "starke" Bot sein Erbgut massiv verstreut? Und woher nimmst du die Gewissheit das die alle in einem lokalem Maximum stecken?
Und was ist dein Selektionskriterium "nur" die Fitness?bye
tt
-
TheTester schrieb:
mal eine Frage, ist es nicht Sinn der Sache das der "starke" Bot sein Erbgut massiv verstreut?
ja. aber nicht zu stark. ich hab zur zeit ne population von 24 bots.
TheTester schrieb:
Und woher nimmst du die Gewissheit das die alle in einem lokalem Maximum stecken?
das verrät mir die stagnation.
Und was ist dein Selektionskriterium "nur" die Fitness?
ja. immer. "fitness" ist aber recht frei definierbar.
-
das verrät mir die stagnation.
nich das ich das falsch verstehe aber stagniert das nich auch alles in einem globalen Max?
Und wenn es wirklich ein lokales ist, probier doch noch eine konventionelle Optimierungsmethode hinterher zu schalten, hill climbing oder so. Insofern du überhaupt ein globales Max. finden möchtest."fitness" ist aber recht frei definierbar.
das stimmt, da ich GAs eigentlich bis jetzt nur zur Funktionsoptimierung betrachtet habe, habe ich als Kriterium die Funktion selbst verwendet, bzw. den Funktionwert. Aber ich glaube das ist bei dem worauf du hinarbeitest (gridwars) nicht wirklich passend
Wie stehts mit der Einführung einer "Mutationsrate" oder sowas in der Art? Damit könnte man doch die Mutationsgeschwindigkeit beeinflussen oder?
EDIT: ich glaub ne Mutationsrate hast du schon....
EDIT2: Noch eine kleine Frage, wie speicherst du die Einheiten ab? In einer Liste? Da könnte man zb. direkt eine Auswahlwahrscheinlichkeit drauf implementieren, zb. die sie schon oft gepaart haben, die kommen ans Ende wo die geringste Wahrscheinlichkeit der Auswahl für eine folgende Paarung. Wobei ich glaube das ist das was du mit der Auswahl von den letzten dritteln schon machst oder?
bye
tt
-
Wie wärs wenn du einen gencode einbaust, der sich dann jeweils
zur hälfte von der mutter und dem vater erbt.
Wenn 2 es dann treiben wollen, wird vorher dieser Code
verglichen, bei zu starker Änlichkeit, gehts halt net...Devil