+/GENN

genetically evolving neural networks

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

Joseph RyanStill brokeneb6e103

v0.2
8.1 KiB260 linesraw
1#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    double m[7];
14    population = 150;
15    f.open("log.txt");
16    m[WEIGHTMUTATE] = .8;
17    m[PERTURBMUTATE] = .9;
18    m[ENABLEMUTATE] = .02;
19    m[STEPSIZE] = .4;
20    m[LINKMUTATE] = .05;
21    m[NODEMUTATE] = .03;
22    m[CROSSOVER] = .75;
23    c1 = 1;
24    c2 = 1;
25    c3 = .4;
26    staleThreshold = 15;
27    distanceThreshold = 3;
28    maxSpecies = 20;
29    generation = 0;
30    for (int i = 0; i < population; i++) {
31        pool.push_back(new Genome(inputs, outputs, m));
32    }
33    classify();
34}
35
36Genome *NEAT::mate(Genome *a, Genome *b) {
37    if (b->fitness > a->fitness) {
38        Genome *temp = a;
39        a = b;
40        b = temp;
41    }
42    Genome *child = new Genome(a->encode());
43    if (double(rand()) / RAND_MAX < child->mutationRates[CROSSOVER]) {
44        for (int i = 0; i < a->totalConnections; i++) {
45            double newWeight = a->structure[i]->weight;
46            for (int j = 0; j < b->totalConnections; j++) {
47                if (b->structure[j]->input->id == a->structure[i]->input->id &&
48                    b->structure[j]->output->id == a->structure[i]->output->id) {
49                    child->structure[i]->weight = (newWeight + b->structure[j]->weight) / 2;
50                }
51            }
52        }
53    }
54    mutate(*child);
55    return child;
56}
57
58//doesn't check if combination exists, must check innovationExists() before
59int NEAT::newInnovation(int a, int b) {
60    std::array<int, 2> temp = {a, b};
61    innovation.push_back(temp);
62    return innovation.size() - 1;
63}
64
65bool NEAT::innovationExists(int a, int b) {
66    for (int i = 0; i < innovation.size(); i++) {
67        if (innovation[i][0] == a && innovation[i][1] == b) {
68            return false;
69        }
70    }
71    return true;
72}
73
74void NEAT::mutate(Genome &g) {
75    //ENABLE
76    if (double(rand()) / RAND_MAX < g.mutationRates[ENABLEMUTATE]) {
77        int temp = rand() % g.totalConnections;
78        g.structure[temp]->enabled = !g.structure[temp]->enabled;
79    }
80    //WEIGHTS
81    for (int i = 0; i < g.totalConnections; i++) {
82        if (double(rand()) / RAND_MAX < g.mutationRates[WEIGHTMUTATE]) {
83            if (rand() / RAND_MAX < g.mutationRates[PERTURBMUTATE]) {
84                g.structure[i]->weight += ((rand() % 2) * 2 - 1) * (rand() / RAND_MAX) * g.mutationRates[STEPSIZE];
85            } else {
86                g.structure[i]->weight = double(rand()) * 4. / RAND_MAX - 2;
87            }
88        }
89    }
90    //ADD CONNECTION
91    if (double(rand()) / RAND_MAX < g.mutationRates[LINKMUTATE]) {
92        int a = rand() % g.totalNodes;
93        int b = rand() % (g.totalNodes - g.inputs);
94        if (!g.hasConnection(a, b)) {
95            Neuron *tempStart = NULL;
96            Neuron *tempEnd = NULL;
97            for (int i = 0; i < g.totalNodes; i++) {
98                if (a == g.nodes[i]->id) {
99                    tempStart = g.nodes[i];
100                }
101                if (b == g.nodes[i]->id) {
102                    tempEnd = g.nodes[i];
103                }
104            }
105            g.totalConnections++;
106            g.structure.push_back(new Connection(tempStart, tempEnd, double(rand()) * 4. / RAND_MAX - 2));
107        }
108    }
109    //ADD NODE
110    if (double(rand()) / RAND_MAX < g.mutationRates[NODEMUTATE]) {
111        Connection *temp = g.structure[rand() % g.totalConnections];
112        temp->enabled = false;
113        int newNodeID = 0;
114        for (int i = 0; i < g.totalNodes; i++) {
115            if (g.nodes[i]->id > newNodeID) {
116                newNodeID = g.nodes[i]->id;
117            }
118        }
119        Neuron *newNode = new Neuron(newNodeID + 1);
120        g.nodes.push_back(newNode);
121        g.structure.push_back(new Connection(temp->input, newNode, 1));
122        g.structure.push_back(new Connection(temp->input, newNode, temp->weight));
123        g.totalNodes++;
124        g.totalConnections += 2;
125    }
126    //slightly alter all mutation rates (.05 is the volatility)
127    for (int i = 0; i < 7; i++) {
128        g.mutationRates[i] += ((rand() % 2) * 2 - 1) * .05 * g.mutationRates[i];
129    }
130}
131
132double NEAT::distance(Genome *a, Genome *b) {
133    if (b->fitness > a->fitness) {
134        Genome *temp = a;
135        a = b;
136        b = temp;
137    }
138    int disjoint = b->totalConnections;
139    int n = a->totalConnections;
140    double sum = 0;
141    for (int i = 0; i < n; i++) {
142        for (int j = 0; j < b->totalConnections; j++) {
143            if (a->structure[i]->input->id == b->structure[j]->input->id &&
144                a->structure[i]->output->id == b->structure[j]->output->id) {
145                sum += fabs(a->structure[i]->weight - b->structure[j]->weight);
146                disjoint--;
147                break;
148            }
149        }
150    }
151    return std::abs(c1 * disjoint / n + c2 * (n - b->totalConnections) + c3 * sum / (b->totalConnections - disjoint));
152}
153
154void NEAT::adjustFitness() {
155    for (int i = 0; i < species.size(); i++) {
156        std::sort(species[i].genomes.begin(), species[i].genomes.end(), Genome::compare);
157        for (int j = 0; j < species[i].genomes.size(); j++) {
158            species[i].genomes[j]->adjustedFitness = species[i].genomes[j]->fitness;
159            //species[i].genomes[j]->adjustedFitness /= species[i].genomes.size();
160        }
161        if (species[i].genomes[0]->fitness > species[i].maxFitness) {
162            species[i].maxFitness = species[i].genomes[0]->adjustedFitness;
163            species[i].staleness = 0;
164        } else {
165            species[i].staleness++;
166        }
167    }
168    std::sort(species.begin(), species.end(), Species::compare);
169}
170
171void NEAT::cull() {
172    for (int i = 0; i < species.size(); i++) {
173        if (species[i].staleness >= staleThreshold) {
174            species.erase(species.begin() + i);
175            i--;
176        }
177    }
178}
179
180void NEAT::repopulate() {
181    std::vector<Genome *> newPool;
182    for (int i = 0; i < species.size(); i++) {
183        newPool.push_back(new Genome(species[i].genomes[0]->encode()));
184        for (int j = 0; j < species[i].genomes.size() - 1; j++) {
185            newPool.push_back(mate(species[i].genomes[rand() % std::max((int) species[i].genomes.size() / 5, 1)],
186                                   species[i].genomes[rand() % std::max((int) species[i].genomes.size() / 5, 1)]));
187        }
188    }
189    while (newPool.size() < population) {
190        newPool.push_back(mate(pool[rand() % population], pool[rand() % population]));
191    }
192    for (int i = 0; i < population; i++) {
193        delete pool[i];
194    }
195    pool = newPool;
196    for (int i = 0; i < species.size(); i++) {
197        species[i].genomes.clear();
198        species[i].genomes.push_back(pool[i]);
199    }
200}
201
202
203void NEAT::classify() {
204    for (int i = species.size(); i < population; i++) {
205        bool newSpecies = true;
206        for (int j = 0; j < species.size(); j++) {
207            if (distance(pool[i], species[j].genomes[0]) < distanceThreshold) {
208                newSpecies = false;
209                species[j].genomes.push_back(pool[i]);
210                break;
211            }
212        }
213        if (newSpecies) {
214            species.push_back(Species());
215            species.back().genomes.push_back(pool[i]);
216        }
217    }
218    if(species.size()>maxSpecies){
219        distanceThreshold+=.1;
220    }
221}
222
223void NEAT::nextGen() {
224    adjustFitness();
225    log();
226    status();
227    cull();
228    repopulate();
229    classify();
230    generation++;
231}
232
233NEAT::~NEAT() {
234    for (int i = 0; i < population; i++) {
235        delete pool[i];
236    }
237    f.close();
238}
239
240
241void NEAT::log() {
242    f << "Gen: " << generation << std::endl;
243    f << "Max Fitness: " << species[0].genomes[0]->fitness << std::endl;
244    f << "Champion: " << species[0].genomes[0]->encode() << std::endl;
245}
246
247void NEAT::status() {
248    double averageSize = 0;
249    double averageFitness = 0;
250    for (int i = 0; i < population; i++) {
251        averageSize += pool[i]->totalConnections;
252        averageFitness += pool[i]->fitness;
253    }
254    averageSize /= population;
255    averageFitness /= population;
256    std::cout << "Gen: " << generation << " Max Fitness: " << species[0].genomes[0]->fitness << " Species: "
257              << species.size() << " Average Size: " << averageSize << std::endl;
258}
259
260