+/GENN
genetically evolving neural networks
git clone https://git.julia.blue/+/GENN
a43321c
imdone-todo-updates
1#include "../include/NEAT.h" 2 3#define WEIGHTMUTATE 0 4#define PERTURBMUTATE 1 5#define ENABLEMUTATE 2 6#define STEPSIZE 3 7#define LINKMUTATE 4 8#define NODEMUTATE 5 9#define CROSSOVER 6 10 11NEAT ::NEAT (int inputs ,int outputs ) { 12 std::srand (time (NULL )); 13population = 250 ; 14f .open ("log.txt" ); 15m [WEIGHTMUTATE ]= .8 ; 16m [PERTURBMUTATE ]= .9 ; 17m [ENABLEMUTATE ]= .02 ; 18m [STEPSIZE ]= .4 ; 19m [LINKMUTATE ]= .05 ; 20m [NODEMUTATE ]= .03 ; 21m [CROSSOVER ]= .75 ; 22c1 = 1 ; 23c2 = 1 ; 24c3 = .4 ; 25staleThreshold = 15 ; 26distanceThreshold = 3 ; 27//maxSpecies = 20; 28maxFitness = 0 ; 29generation = 0 ; 30for (int i = 0 ;i < population ;++ i ) { 31pool .push_back (Genome (inputs ,outputs ,m )); 32labelInnovations (pool .back ()); 33 } 34for (int i = 0 ;i < inputs ;++ i ) { 35for (int j = 0 ;j < outputs ;++ j ) { 36newInnovation (i ,inputs + j ); 37 } 38 } 39classify (); 40} 41 42//doesn't check if combination exists, must check innovationExists() before 43int NEAT ::newInnovation (int a ,int b ) { 44 std::array < int ,2 > temp = {a ,b }; 45innovation .push_back (temp ); 46return innovation .size ()- 1 ; 47} 48 49int NEAT ::findInnovation (int a ,int b ) { 50for (int i = 0 ;i < innovation .size ();++ i ) { 51if (innovation [i ][0 ]== a && innovation [i ][1 ]== b ) { 52return i ; 53 } 54 } 55return newInnovation (a ,b ); 56} 57 58 59void NEAT ::labelInnovations (Genome & g ) { 60for (int i = 0 ;i < g .structure .size ();++ i ) { 61g .structure [i ].id = findInnovation (g .structure [i ].input ,g .structure [i ].output ); 62 } 63} 64 65 66Genome NEAT ::mate (Genome * a ,Genome * b ) { 67if (b -> fitness > a -> fitness ) { 68Genome * temp = a ; 69a = b ; 70b = temp ; 71 } 72Genome child = Genome (* a ); 73if (double (rand ()) /RAND_MAX < child .mutationRates [CROSSOVER ]) { 74for (int i = 0 ;i < child .structure .size ();++ i ) { 75for (int j = 0 ;j < b -> structure .size ();++ j ) { 76if (b -> structure [j ].id == child .structure [i ].id ) { 77child .structure [i ].weight = (child .structure [i ].weight + b -> structure [j ].weight ) /2 ; 78if (child .structure [i ].enabled != b -> structure [i ].enabled ) { 79child .structure [i ].enabled = rand () /RAND_MAX < .25 ; 80 } 81break ; 82 } 83 } 84 } 85 } 86mutate (child ); 87return child ; 88} 89 90void NEAT ::mutate (Genome & g ) { 91//ENABLE 92if (double (rand ()) /RAND_MAX < g .mutationRates [ENABLEMUTATE ]) { 93int temp = rand () %g .structure .size (); 94g .structure [temp ].enabled = !g .structure [temp ].enabled ; 95 } 96//WEIGHTS 97if (double (rand ()) /RAND_MAX < g .mutationRates [WEIGHTMUTATE ]) { 98for (int i = 0 ;i < g .structure .size ();++ i ) { 99if (double (rand ()) /RAND_MAX < g .mutationRates [PERTURBMUTATE ]) { 100g .structure [i ].weight += ((rand () %2 )* 2 - 1 )* (rand () /RAND_MAX )* g .mutationRates [STEPSIZE ]; 101 }else { 102g .structure [i ].weight = double (rand ())* 4. /RAND_MAX - 2 ; 103 } 104 } 105 } 106//ADD CONNECTION 107if (double (rand ()) /RAND_MAX < g .mutationRates [LINKMUTATE ]) { 108int a = rand () %g .nodes ; 109int b = rand () % (g .nodes - g .inputs )+ g .inputs ; 110bool temp = true; 111for (int i = 0 ;i < g .structure .size ();++ i ) { 112if (g .structure [i ].input == a && g .structure [i ].output == b ) { 113temp = false; 114 } 115 } 116if (temp ) { 117g .structure .push_back (Link (a ,b ,double (rand ())* 4. /RAND_MAX - 2 )); 118g .structure .back ().id = findInnovation (a ,b ); 119 } 120 } 121//ADD NODE 122if (double (rand ()) /RAND_MAX < g .mutationRates [NODEMUTATE ]) { 123int temp = rand () %g .structure .size (); 124if (g .structure [temp ].enabled ) { 125g .structure [temp ].enabled = false; 126g .structure .push_back (Link (g .structure [temp ].input ,g .nodes ,1 )); 127g .structure .back ().id = findInnovation (g .structure [temp ].input ,g .nodes ); 128g .structure .push_back (Link (g .nodes ,g .structure [temp ].output ,g .structure [temp ].weight )); 129g .structure .back ().id = findInnovation (g .nodes ,g .structure [temp ].output ); 130g .nodes ++ ; 131 } 132 } 133//slightly alter all mutation rates (.05 is the volatility) 134for (int i = 0 ;i < 7 ;++ i ) { 135g .mutationRates [i ]+= ((rand () %2 )* 2 - 1 )* .05 * g .mutationRates [i ]; 136 } 137} 138 139double NEAT ::distance (Genome a ,Genome b ) { 140int aMaxID = 0 ; 141for (int i = 0 ;i < a .structure .size ();++ i ) { 142aMaxID = std::max (aMaxID ,a .structure [i ].id ); 143 } 144int bMaxID = 0 ; 145for (int i = 0 ;i < b .structure .size ();++ i ) { 146bMaxID = std::max (bMaxID ,b .structure [i ].id ); 147 } 148int disjoint = 0 ; 149double weights = 0 ; 150int similarConnections = 0 ; 151int ai = 0 ,bi = 0 ; 152for (int i = 0 ;i < innovation .size ();++ i ) { 153int tempa = -1 ; 154int tempb = -1 ; 155while (ai < a .structure .size ()&& a .structure [ai ].id < i ){ 156ai ++ ; 157 } 158if (a .structure [ai ].id == i );{ 159tempa = ai ; 160 } 161while (bi < b .structure .size ()&& b .structure [bi ].id < i ){ 162bi ++ ; 163 } 164if (b .structure [bi ].id == i );{ 165tempb = bi ; 166 } 167if (tempa != -1 && tempb != -1 ) { 168similarConnections ++ ; 169weights += std::abs (a .structure [tempa ].weight - b .structure [tempb ].weight ); 170 }else if (tempa != -1 || tempb != -1 ) { 171disjoint ++ ; 172 } 173 } 174int n = std::max (a .structure .size (),b .structure .size ()); 175return std::abs (c1 * std::abs (a .structure .size ()- b .structure .size ()) /n + c2 * disjoint /n + c3 * weights /similarConnections ); 176} 177 178void NEAT ::adjustFitness () { 179for (int i = 0 ;i < species .size ();++ i ) { 180 std::sort (std::begin (species [i ].genomes ), std::end (species [i ].genomes ),Genome ::compare ); 181for (int j = 0 ;j < species [i ].genomes .size ();++ j ) { 182species [i ].genomes [j ]-> adjustedFitness = species [i ].genomes [j ]-> fitness ; 183species [i ].genomes [j ]-> adjustedFitness /=species [i ].genomes .size (); 184 } 185if (species [i ].genomes [0 ]-> fitness > species [i ].maxFitness ) { 186species [i ].maxFitness = species [i ].genomes [0 ]-> fitness ; 187species [i ].staleness = 0 ; 188maxFitness = std::max (maxFitness ,species [i ].maxFitness ); 189 }else { 190species [i ].staleness ++ ; 191 } 192 } 193 std::sort (std::begin (species ), std::end (species ),Species ::compare ); 194} 195 196void NEAT ::cull () { 197for (int i = 0 ;i < species .size ();++ i ) { 198if (species [i ].staleness >=staleThreshold && species [i ].maxFitness < maxFitness ) { 199species .erase (species .begin ()+ i ); 200i -- ; 201 } 202 } 203} 204 205//only adds champion if species has 5+ genomes 206void NEAT ::repopulate () { 207 std::vector < Genome > newPool ; 208newPool .reserve (population ); 209 std::vector < int > parents ; 210for (int i = 0 ;i < species .size ();++ i ) { 211newPool .push_back (Genome (* species [i ].genomes [0 ])); 212//only top 20 percent of species is allowed to reproduce unless it is smaller than 6 genomes 213if (species [i ].genomes .size () >=5 ) { 214species [i ].genomes .resize (species [i ].genomes .size () /5 ); 215 } 216for (int j = 0 ;j < species [i ].genomes .size ();++ j ) { 217parents .push_back (i ); 218 } 219 } 220while (newPool .size ()< population ) { 221/* Only needed if stuff is breaking 222if (parents.size() == 0) { 223newPool.push_back(Genome(pool[0].inputs, pool[0].outputs, m));; 224continue; 225} 226*/ 227int temp = parents [rand () %parents .size ()]; 228// 1 in 1000 chance of interspecies mating 229if (rand () %1000 == 1 ) { 230int temp2 = parents [rand () %parents .size ()]; 231newPool .push_back (mate (species [temp ].genomes [rand () %species [temp ].genomes .size ()], 232species [temp2 ].genomes [rand () %species [temp2 ].genomes .size ()])); 233 }else { 234newPool .push_back (mate (species [temp ].genomes [rand () %species [temp ].genomes .size ()], 235species [temp ].genomes [rand () %species [temp ].genomes .size ()])); 236 } 237 } 238//~Vector Magic~ prob not necessary but it will serve as a reminder of the monolithic memory leak I had earlier 239 std::vector < Genome > ().swap (pool ); 240pool = newPool ; 241for (int i = 0 ;i < species .size ();++ i ) { 242species [i ].genomes .clear (); 243//I actually have no clue how vector memory allocation works... this is prob irrelevant 244species [i ].genomes .shrink_to_fit (); 245species [i ].genomes .push_back (& pool [i ]); 246 } 247for (int i = 0 ;i < pool .size ();++ i ){ 248 std::sort (std::begin (pool [i ].structure ),std::end (pool [i ].structure ),Link ::compare ); 249 } 250} 251 252 253void NEAT ::classify () { 254for (int i = species .size ();i < population ;++ i ) { 255bool newSpecies = true; 256for (int j = 0 ;j < species .size ();++ j ) { 257if (distance (pool [i ],* species [j ].genomes [0 ])< distanceThreshold ) { 258newSpecies = false; 259species [j ].genomes .push_back (& pool [i ]); 260break ; 261 } 262 } 263if (newSpecies ) { 264species .push_back (Species ()); 265species .back ().genomes .push_back (& pool [i ]); 266 } 267 } 268/* Experimental feature: reactive threshold to stabilize species numbers 269if(species.size()>maxSpecies){ 270distanceThreshold+=.1; 271} 272*/ 273} 274 275void NEAT ::nextGen () { 276adjustFitness (); 277log (); 278status (); 279cull (); 280repopulate (); 281classify (); 282generation ++ ; 283} 284 285 286void NEAT ::log () { 287f <<"Gen: " <<generation << std::endl ; 288f <<"Max Fitness: " <<species [0 ].genomes [0 ]-> fitness << std::endl ; 289f <<"Champion: " <<pool [0 ].encode ().c_str () << std::endl ; 290 291} 292 293void NEAT ::status () { 294double averageSize = 0 ; 295double averageFitness = 0 ; 296double minSize = 999 ,maxSize = 0 ; 297for (int i = 0 ;i < population ;++ i ) { 298averageSize += pool [i ].structure .size (); 299averageFitness += pool [i ].fitness ; 300minSize = std::min (minSize , (double )pool [i ].structure .size ()); 301maxSize = std::max (maxSize , (double )pool [i ].structure .size ()); 302 } 303averageSize /=population ; 304averageFitness /=population ; 305 std::cout <<"Gen: " <<generation <<" Fitness: " <<species [0 ].genomes [0 ]-> fitness <<" " <<averageFitness 306 <<" Species: " <<species .size () <<" Size: " <<minSize <<" " <<averageSize <<" " <<maxSize 307 << std::endl ; 308} 309