suche Algorithmus, um Inzucht zu vermeiden

volkard

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 ?

volkard

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.

volkard

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.

TheTester

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

volkard

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.

TheTester

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

phlox81

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

devil81 schrieb:

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

Genau darum gehts ja schon
Es gibt allerdings diverse Crossover und Selektionsvarianten...

Prof84

volkard schrieb:

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.

Also basierend von einen reinen GA Ansatz (den ich nie favorisiere) fallen mir folgende Verbesserungsvorschläge ein:
- frühzeitige Konvergenz verhindern, d.h eine andere Initialisierung fahren
z.B. n beste einer zufälligen Menge, heuristische Bereichsregel etc.
- dein restricted mating (Insest) führt zu früh zu einen lokalen Maximum und Du versuchst es mit "artfremden" Einfluss zu brechen.
Wie wäre es mit einer Aufteilung des Fitnesswerts auf einer Gruppe von Bots?! So verhindest Du auch dass der pareto optimale Bot sich "Agent Smith"-mässig vermehrt. Weiterhin wählst Du nur den Baldwin Effekt für die Selektion. Innerhalb der Gruppe nimmst Du eine Tranction Selection Komponente für die Selektion - d.h. n Bots in der lokalen Maximum Gruppe haben gleiche Reproduktionschancen.
- ein Hybridisierungsansatz nach Lamarck bei genetische Operatoren mit einen heuristischen Crossover. Nach der Selektion Spleisen - d.h. Kürzen oder Spalten der Gene - in Erwägung ziehen.
- temporäre Abhängigkeit der Mutationsrate, Cross-Over und Reproduktionrate

volkard schrieb:

was mir zur zeit am meisten sorgen macht, ist die selektion.

Also ich würde eine Mischung aus der Konvergenzmessung und der relativen Fitness zu n Bots für m Bots die Reproduktionswahrscheinlichkeit festlegen.
Und für den Rest "Sozialhilfe " Tranction Selection festlegen. - In der KI ist der Zauberstab immer eine würzige Mischung ...

Hallo Volkard,

bei "nur" 24 bots könnte man die Inzucht über einen Bitschlüssel verhindern.
Jeder Bot bekommt ein bit im 32bit Integer und einen Vorfahrspeicher, in dem alle bits der Eltern drinstehen.
Wenn dann bei einer und Verknüpfung zwischen zwei bots noch bits dastehen haben sie gemeinsame vorfahren...
Um die Generationstiefe zu begrenzen müsste man dann am besten noch einen vektor oder eine queue hernehmen, in die werden dann immer die bits eingetragen und wenn der vektor/queue eine bestimmte länge erreicht hat, wird der älteste eintrag gelesen und das entsprechende bit im Vorfahrspeicher gelöscht.

Hoffe das war verständlich.
Das ist bestimmt ziemlich schnell und ließe sich auch auf mehr bots ausweiten nur bei zu vielen ist natürlich doof.

k.

Prof84

Habe gerade als Nebenprodukt noch ein bisschen Stoff gefunden ...
http://www.informatik.oelinger.de/data/datafiles_datafile_1045559964.pdf
http://www.informatik.oelinger.de/data/datafiles_datafile_1045560046.pdf

@volkard:
Gib mal laut über Deine "Fitnesswerte" ... persönlich noch ohne Konvergenz im lokalen Maximum gefangen?!

volkard

Prof84 schrieb:

@volkard:
Gib mal laut über Deine "Fitnesswerte" ... persönlich noch ohne Konvergenz im lokalen Maximum gefangen?!

projekt liegt erstmal auf eis.
muss vorher alle tollen features der gcc ausprobieren.