Parker Banks / mbeddedNets

Generates neural net instances through genetic algorithm for use in task learning by m3pi. Reward determined by detection of black areas on arena floor, or by amount of area explored in limited time. Due to memory size, limited # of nets.

Dependencies:   Ping m3pimaze mbed

Code/CGenAlg.cpp@0:ac93d9db8dbd, 2015-04-23 (annotated)

Committer:
parkbanks
Date:
Thu Apr 23 20:16:51 2015 +0000
Revision:
0:ac93d9db8dbd
Initial commit, bot fully working.

Who changed what in which revision?

UserRevisionLine numberNew contents of line
parkbanks 0:ac93d9db8dbd 1 #include "CGenAlg.h"
parkbanks 0:ac93d9db8dbd 2
parkbanks 0:ac93d9db8dbd 3 //const unsigned int numElite = 1;
parkbanks 0:ac93d9db8dbd 4 //const unsigned int numCopies = 2;
parkbanks 0:ac93d9db8dbd 5
parkbanks 0:ac93d9db8dbd 6 // constructor
parkbanks 0:ac93d9db8dbd 7 // set up population with random floats
parkbanks 0:ac93d9db8dbd 8 CGenAlg::CGenAlg(int popsize, float MutRat, float CrossRat, int numweights) : m_iPopSize(popsize),
parkbanks 0:ac93d9db8dbd 9 m_dMutationRate(MutRat),
parkbanks 0:ac93d9db8dbd 10 m_dCrossoverRate(CrossRat),
parkbanks 0:ac93d9db8dbd 11 m_iChromoLength(numweights),
parkbanks 0:ac93d9db8dbd 12 m_dTotalFitness(0),
parkbanks 0:ac93d9db8dbd 13 m_cGeneration(0),
parkbanks 0:ac93d9db8dbd 14 m_iFittestGenome(0),
parkbanks 0:ac93d9db8dbd 15 m_dBestFitness(0),
parkbanks 0:ac93d9db8dbd 16 m_dWorstFitness(99999)
parkbanks 0:ac93d9db8dbd 17 {
parkbanks 0:ac93d9db8dbd 18 //initialise population with randomly weighted chromosomes, set fitness to 0
parkbanks 0:ac93d9db8dbd 19 for (int i=0; i<m_iPopSize; ++i)
parkbanks 0:ac93d9db8dbd 20 {
parkbanks 0:ac93d9db8dbd 21 m_vecPop.push_back(SGenome());
parkbanks 0:ac93d9db8dbd 22
parkbanks 0:ac93d9db8dbd 23 for (int j=0; j<m_iChromoLength; ++j)
parkbanks 0:ac93d9db8dbd 24 {
parkbanks 0:ac93d9db8dbd 25 m_vecPop[i].vecWeights.push_back(RandomClamped());
parkbanks 0:ac93d9db8dbd 26 }
parkbanks 0:ac93d9db8dbd 27 }
parkbanks 0:ac93d9db8dbd 28 }
parkbanks 0:ac93d9db8dbd 29
parkbanks 0:ac93d9db8dbd 30 // Mutates a chromosome by perturbing its weights, m_dMutationRate given in main
parkbanks 0:ac93d9db8dbd 31 void CGenAlg::Mutate(vector<float> &chromo)
parkbanks 0:ac93d9db8dbd 32 {
parkbanks 0:ac93d9db8dbd 33 //traverse the chromosome and mutate each weight dependent
parkbanks 0:ac93d9db8dbd 34 //on the mutation rate
parkbanks 0:ac93d9db8dbd 35 for (int i=0; i<chromo.size(); ++i)
parkbanks 0:ac93d9db8dbd 36 {
parkbanks 0:ac93d9db8dbd 37 //do we perturb this weight?
parkbanks 0:ac93d9db8dbd 38 if (RandFloat() < m_dMutationRate)
parkbanks 0:ac93d9db8dbd 39 {
parkbanks 0:ac93d9db8dbd 40 //add or subtract a small value to the weight
parkbanks 0:ac93d9db8dbd 41 chromo[i] += (RandomClamped() * 0.3);
parkbanks 0:ac93d9db8dbd 42 }
parkbanks 0:ac93d9db8dbd 43 }
parkbanks 0:ac93d9db8dbd 44 }
parkbanks 0:ac93d9db8dbd 45
parkbanks 0:ac93d9db8dbd 46 // returns a chromo based on roulette wheel sampling
parkbanks 0:ac93d9db8dbd 47 SGenome CGenAlg::GetChromoRoulette()
parkbanks 0:ac93d9db8dbd 48 {
parkbanks 0:ac93d9db8dbd 49 //generate a random number between 0 & total fitness count
parkbanks 0:ac93d9db8dbd 50 float Slice = (float)(RandFloat() * m_dTotalFitness);
parkbanks 0:ac93d9db8dbd 51
parkbanks 0:ac93d9db8dbd 52 //this will be set to the chosen chromosome
parkbanks 0:ac93d9db8dbd 53 SGenome TheChosenOne;
parkbanks 0:ac93d9db8dbd 54
parkbanks 0:ac93d9db8dbd 55 //go through the chromosones adding up the fitness so far
parkbanks 0:ac93d9db8dbd 56 float FitnessSoFar = 0;
parkbanks 0:ac93d9db8dbd 57
parkbanks 0:ac93d9db8dbd 58 for (int i=0; i<m_iPopSize; ++i)
parkbanks 0:ac93d9db8dbd 59 {
parkbanks 0:ac93d9db8dbd 60 FitnessSoFar += m_vecPop[i].dFitness;
parkbanks 0:ac93d9db8dbd 61
parkbanks 0:ac93d9db8dbd 62 //if the fitness so far > random number return the chromo at
parkbanks 0:ac93d9db8dbd 63 //this point
parkbanks 0:ac93d9db8dbd 64 if (FitnessSoFar >= Slice)
parkbanks 0:ac93d9db8dbd 65 {
parkbanks 0:ac93d9db8dbd 66 TheChosenOne = m_vecPop[i];
parkbanks 0:ac93d9db8dbd 67
parkbanks 0:ac93d9db8dbd 68 break;
parkbanks 0:ac93d9db8dbd 69 }
parkbanks 0:ac93d9db8dbd 70
parkbanks 0:ac93d9db8dbd 71 }
parkbanks 0:ac93d9db8dbd 72
parkbanks 0:ac93d9db8dbd 73 return TheChosenOne;
parkbanks 0:ac93d9db8dbd 74 }
parkbanks 0:ac93d9db8dbd 75
parkbanks 0:ac93d9db8dbd 76 // given parents and storage for the offspring this method performs
parkbanks 0:ac93d9db8dbd 77 // crossover according to the GAs crossover rate
parkbanks 0:ac93d9db8dbd 78 void CGenAlg::Crossover(const vector<float> &mum,
parkbanks 0:ac93d9db8dbd 79 const vector<float> &dad,
parkbanks 0:ac93d9db8dbd 80 vector<float> &baby1,
parkbanks 0:ac93d9db8dbd 81 vector<float> &baby2)
parkbanks 0:ac93d9db8dbd 82 {
parkbanks 0:ac93d9db8dbd 83 //just return parents as offspring dependent on the rate
parkbanks 0:ac93d9db8dbd 84 //or if parents are the same
parkbanks 0:ac93d9db8dbd 85 if ( (RandFloat() > m_dCrossoverRate) || (mum == dad))
parkbanks 0:ac93d9db8dbd 86 {
parkbanks 0:ac93d9db8dbd 87 baby1 = mum;
parkbanks 0:ac93d9db8dbd 88 baby2 = dad;
parkbanks 0:ac93d9db8dbd 89
parkbanks 0:ac93d9db8dbd 90 return;
parkbanks 0:ac93d9db8dbd 91 }
parkbanks 0:ac93d9db8dbd 92
parkbanks 0:ac93d9db8dbd 93 //determine a crossover point
parkbanks 0:ac93d9db8dbd 94 int cp = RandInt(0, m_iChromoLength - 1);
parkbanks 0:ac93d9db8dbd 95
parkbanks 0:ac93d9db8dbd 96 //create the offspring
parkbanks 0:ac93d9db8dbd 97 for (int i=0; i<cp; ++i)
parkbanks 0:ac93d9db8dbd 98 {
parkbanks 0:ac93d9db8dbd 99 baby1.push_back(mum[i]);
parkbanks 0:ac93d9db8dbd 100 baby2.push_back(dad[i]);
parkbanks 0:ac93d9db8dbd 101 }
parkbanks 0:ac93d9db8dbd 102
parkbanks 0:ac93d9db8dbd 103 int i;
parkbanks 0:ac93d9db8dbd 104 for (i=cp; i<mum.size(); ++i)
parkbanks 0:ac93d9db8dbd 105 {
parkbanks 0:ac93d9db8dbd 106 baby1.push_back(dad[i]);
parkbanks 0:ac93d9db8dbd 107 baby2.push_back(mum[i]);
parkbanks 0:ac93d9db8dbd 108 }
parkbanks 0:ac93d9db8dbd 109
parkbanks 0:ac93d9db8dbd 110
parkbanks 0:ac93d9db8dbd 111 return;
parkbanks 0:ac93d9db8dbd 112 }
parkbanks 0:ac93d9db8dbd 113
parkbanks 0:ac93d9db8dbd 114
parkbanks 0:ac93d9db8dbd 115 // takes a population of chromosones and runs the algorithm through one cycle.
parkbanks 0:ac93d9db8dbd 116 // Returns a new population of chromosones.
parkbanks 0:ac93d9db8dbd 117 vector<SGenome> CGenAlg::Epoch(vector<SGenome> &old_pop)
parkbanks 0:ac93d9db8dbd 118 {
parkbanks 0:ac93d9db8dbd 119 //assign the given population to the classes population
parkbanks 0:ac93d9db8dbd 120 m_vecPop = old_pop;
parkbanks 0:ac93d9db8dbd 121
parkbanks 0:ac93d9db8dbd 122 //reset the appropriate variables
parkbanks 0:ac93d9db8dbd 123 Reset();
parkbanks 0:ac93d9db8dbd 124
parkbanks 0:ac93d9db8dbd 125 //sort the population (for scaling and elitism)
parkbanks 0:ac93d9db8dbd 126 sort(m_vecPop.begin(), m_vecPop.end());
parkbanks 0:ac93d9db8dbd 127
parkbanks 0:ac93d9db8dbd 128 //calculate best, worst, average and total fitness
parkbanks 0:ac93d9db8dbd 129 CalculateBestWorstAvTot();
parkbanks 0:ac93d9db8dbd 130
parkbanks 0:ac93d9db8dbd 131 //create a temporary vector to store new chromosones
parkbanks 0:ac93d9db8dbd 132 vector <SGenome> vecNewPop;
parkbanks 0:ac93d9db8dbd 133
parkbanks 0:ac93d9db8dbd 134 //Now to add a little elitism we shall add in some copies of the
parkbanks 0:ac93d9db8dbd 135 //fittest genomes. Make sure we add an EVEN number or the roulette
parkbanks 0:ac93d9db8dbd 136 //wheel sampling will crash
parkbanks 0:ac93d9db8dbd 137
parkbanks 0:ac93d9db8dbd 138 if (m_vecPop[1].dFitness > 130 && m_vecPop[2].dFitness > 130)//2 copies of 1 elite
parkbanks 0:ac93d9db8dbd 139 {
parkbanks 0:ac93d9db8dbd 140 GrabNBest(2, 2, vecNewPop);
parkbanks 0:ac93d9db8dbd 141 }
parkbanks 0:ac93d9db8dbd 142 else if (m_vecPop[1].dFitness > 130)//2 copies of 1 elite
parkbanks 0:ac93d9db8dbd 143 {
parkbanks 0:ac93d9db8dbd 144 GrabNBest(1, 4, vecNewPop);
parkbanks 0:ac93d9db8dbd 145 }
parkbanks 0:ac93d9db8dbd 146
parkbanks 0:ac93d9db8dbd 147
parkbanks 0:ac93d9db8dbd 148 //now we enter the GA loop
parkbanks 0:ac93d9db8dbd 149
parkbanks 0:ac93d9db8dbd 150 //repeat until a new population is generated
parkbanks 0:ac93d9db8dbd 151 while (vecNewPop.size() < m_iPopSize)
parkbanks 0:ac93d9db8dbd 152 {
parkbanks 0:ac93d9db8dbd 153 //grab two chromosones
parkbanks 0:ac93d9db8dbd 154 SGenome mum = GetChromoRoulette();
parkbanks 0:ac93d9db8dbd 155 SGenome dad = GetChromoRoulette();
parkbanks 0:ac93d9db8dbd 156
parkbanks 0:ac93d9db8dbd 157 //create some offspring via crossover
parkbanks 0:ac93d9db8dbd 158 vector<float> baby1, baby2;
parkbanks 0:ac93d9db8dbd 159
parkbanks 0:ac93d9db8dbd 160 Crossover(mum.vecWeights, dad.vecWeights, baby1, baby2);
parkbanks 0:ac93d9db8dbd 161
parkbanks 0:ac93d9db8dbd 162 //now we mutate
parkbanks 0:ac93d9db8dbd 163 Mutate(baby1);
parkbanks 0:ac93d9db8dbd 164 Mutate(baby2);
parkbanks 0:ac93d9db8dbd 165
parkbanks 0:ac93d9db8dbd 166 //now copy into vecNewPop population
parkbanks 0:ac93d9db8dbd 167 vecNewPop.push_back(SGenome(baby1, 0));
parkbanks 0:ac93d9db8dbd 168 vecNewPop.push_back(SGenome(baby2, 0));
parkbanks 0:ac93d9db8dbd 169 }
parkbanks 0:ac93d9db8dbd 170
parkbanks 0:ac93d9db8dbd 171 //finished so assign new pop back into m_vecPop
parkbanks 0:ac93d9db8dbd 172 m_vecPop = vecNewPop;
parkbanks 0:ac93d9db8dbd 173
parkbanks 0:ac93d9db8dbd 174 return m_vecPop;
parkbanks 0:ac93d9db8dbd 175 }
parkbanks 0:ac93d9db8dbd 176
parkbanks 0:ac93d9db8dbd 177 // Elitism, inserts NumCopies of NBest fittest genomes into a pop vector
parkbanks 0:ac93d9db8dbd 178 void CGenAlg::GrabNBest(int NBest,
parkbanks 0:ac93d9db8dbd 179 const int NumCopies,
parkbanks 0:ac93d9db8dbd 180 vector<SGenome> &Pop)
parkbanks 0:ac93d9db8dbd 181 {
parkbanks 0:ac93d9db8dbd 182 //add the required amount of copies of the n most fittest
parkbanks 0:ac93d9db8dbd 183 //to the supplied vector
parkbanks 0:ac93d9db8dbd 184 while(NBest--)
parkbanks 0:ac93d9db8dbd 185 {
parkbanks 0:ac93d9db8dbd 186 for (int i=0; i<NumCopies; ++i)
parkbanks 0:ac93d9db8dbd 187 {
parkbanks 0:ac93d9db8dbd 188 Pop.push_back(m_vecPop[(m_iPopSize - 1) - NBest]);
parkbanks 0:ac93d9db8dbd 189 }
parkbanks 0:ac93d9db8dbd 190 }
parkbanks 0:ac93d9db8dbd 191 }
parkbanks 0:ac93d9db8dbd 192
parkbanks 0:ac93d9db8dbd 193 // calculates fittest and weakest genomes
parkbanks 0:ac93d9db8dbd 194 void CGenAlg::CalculateBestWorstAvTot()
parkbanks 0:ac93d9db8dbd 195 {
parkbanks 0:ac93d9db8dbd 196 m_dTotalFitness = 0;
parkbanks 0:ac93d9db8dbd 197
parkbanks 0:ac93d9db8dbd 198 float HighestSoFar = 0;
parkbanks 0:ac93d9db8dbd 199 float LowestSoFar = 99999;
parkbanks 0:ac93d9db8dbd 200
parkbanks 0:ac93d9db8dbd 201 for (int i=0; i<m_iPopSize; ++i)
parkbanks 0:ac93d9db8dbd 202 {
parkbanks 0:ac93d9db8dbd 203 //update fittest if necessary
parkbanks 0:ac93d9db8dbd 204 if (m_vecPop[i].dFitness > HighestSoFar)
parkbanks 0:ac93d9db8dbd 205 {
parkbanks 0:ac93d9db8dbd 206 HighestSoFar = m_vecPop[i].dFitness;
parkbanks 0:ac93d9db8dbd 207
parkbanks 0:ac93d9db8dbd 208 m_iFittestGenome = i;
parkbanks 0:ac93d9db8dbd 209
parkbanks 0:ac93d9db8dbd 210 m_dBestFitness = HighestSoFar;
parkbanks 0:ac93d9db8dbd 211 }
parkbanks 0:ac93d9db8dbd 212
parkbanks 0:ac93d9db8dbd 213 //update worst if necessary
parkbanks 0:ac93d9db8dbd 214 if (m_vecPop[i].dFitness < LowestSoFar)
parkbanks 0:ac93d9db8dbd 215 {
parkbanks 0:ac93d9db8dbd 216 LowestSoFar = m_vecPop[i].dFitness;
parkbanks 0:ac93d9db8dbd 217
parkbanks 0:ac93d9db8dbd 218 m_dWorstFitness = LowestSoFar;
parkbanks 0:ac93d9db8dbd 219 }
parkbanks 0:ac93d9db8dbd 220
parkbanks 0:ac93d9db8dbd 221 m_dTotalFitness += m_vecPop[i].dFitness;
parkbanks 0:ac93d9db8dbd 222
parkbanks 0:ac93d9db8dbd 223
parkbanks 0:ac93d9db8dbd 224 }//next chromosome
parkbanks 0:ac93d9db8dbd 225 }
parkbanks 0:ac93d9db8dbd 226
parkbanks 0:ac93d9db8dbd 227 void CGenAlg::Reset()
parkbanks 0:ac93d9db8dbd 228 {
parkbanks 0:ac93d9db8dbd 229 m_dTotalFitness = 0;
parkbanks 0:ac93d9db8dbd 230 m_dBestFitness = 0;
parkbanks 0:ac93d9db8dbd 231 m_dWorstFitness = 99999;
parkbanks 0:ac93d9db8dbd 232 }