+/GENN

genetically evolving neural networks

git clone https://git.julia.blue/+/GENN

Joseph RyanUpdate Readmea43321c

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