I've built a genetic algorithm, but I feel like something is wrong in the selection/mutation part of my code. This is the part of the code I'm talking about:
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <random>
#include <string>
#include <iomanip>
#include <math.h>
// The random number generator I am using.
std::random_device rd;
std::mt19937 rng(rd());
for (int k = 1; k < population_size; k++) // Loop until new population is filled up. K = 1 because first individual has the best genes from last generation.
{
// Calculate total fitness.
double totalfitness = 0;
for (int i = 0; i < population_size; i++)
{
totalfitness += individuals[i].fitness;
}
// Calculate relative fitness.
for (int i = 0; i < population_size; i++)
{
individuals[i].probability = individuals[i].fitness / totalfitness;
}
std::uniform_real_distribution<double> dist2(0.0, 1.0); // Initiate random number generator to generate a double between 0 and 1.
double rndNumber = dist2(rng); // Generate first double
double rndNumber2 = dist2(rng); // Generate second double
double offset = 0.0; // Set offset (starting point from which it'll add up probabilities) at 0.
int father = 0; // father is the individual that is picked, initialize at 0.
int mother = 0;
// Pick first parent. Once picked, set the fitness for that individual at 0 so that it can not be picked again.
for (int i = 0; i < population_size; i++)
{
offset += individuals[i].probability;
if (rndNumber < offset)
{
father = i;
individuals[i].fitness = 0.0;
break;
}
}
offset = 0.0; // Reset offset to zero because we'll start again for the second parent.
totalfitness = 0; // Recalculate total fitness using only the remaining individuals and reset total fitness to 0
// Here we recalculate total fitness using only the fitness of the individuals remaining.
for (int i = 0; i < population_size; i++)
{
totalfitness += individuals[i].fitness;
}
// Then we recalculate probability for the individuals based on the new totalfitness.
for (int i = 0; i < population_size; i++)
{
individuals[i].probability = individuals[i].fitness / totalfitness;
}
// Then we give back the old fitness to the father/mother
individuals[father].fitness = 1 / (individuals[father].evaluation*individuals[father].evaluation);
// Then pick parent 2.
for (int i = 0; i < population_size; i++)
{
offset += individuals[i].probability;
if (rndNumber2 < offset)
{
mother = i;
break;
}
}
// Having picked father and mother, now the idea is to run a random number generator between 0 and 1 for each gene.
// So if: father {5, 8, 9, 3}
// mother {1, 5, 2, 6)
// rndnum {0, 0, 1, 1}
// then child {5, 8, 2, 6}
std::uniform_int_distribution<int> gene_selection(0, 1); // Initiate random number generator to generate an integer between 0 and 1.
for (int i = 0; i < number_of_variables; i++)
{
int gene1 = gene_selection(rng);
if (gene1 == 0)
{
new_individuals[k].chromosomes[0].push_back(individuals[father].chromosomes[0].at(i));
}
else if (gene1 == 1)
{
new_individuals[k].chromosomes[0].push_back(individuals[mother].chromosomes[0].at(i));
}
}
for (int j = 0; j < number_of_variables; j++)
{
for (int l = 0; l < 32; l++)
{
std::uniform_int_distribution<int> mutation(0, 50);
int mutation_outcome = mutation(rng);
if (mutation_outcome == 1)
{
new_individuals[k].chromosomes[0].at(j) ^= (1 << l);
if (new_individuals[k].chromosomes[0].at(j) == 0)
{
int new_var = uni(rng);
new_individuals[k].chromosomes[0].at(j) = new_var;
}
}
}
}
}
// When all new individuals have values, give individuals values of new_individuals and start next round of evaluation.
for (int i = 0; i < population_size; i++)
{
individuals[i] = new_individuals[i];
}
My code mostly seems to be working okay. What I can't seem to figure out is why it performs progressively worse. The first few generations it seems to find new, better solutions quite often. After a few generations it stops finding new best solutions.
This could of course be because there is no better solution, but I'm also doing the calculations in excel at the same time and an individual can often get better fitness just by increasing one of its "chromosomes" by 1, which would usually be a 1 bit change and since I usually run this code with 10000 individuals you'd say the program is bound to create an individual with this mutation.
I've stepped through my code a lot of times with the debugger now, displaying values at every step of the way etc, but I can't seem to find out where it's going wrong so I thought I'd post my code here and see if anyone could spot where I'm messing up.
Just for the record, the algorithm is simply a formula solver. So I can for example input a = 1, b = 6, target = 50, a*gene1 + b *gene2 and it'd (theoretically) assign a higher fitness the closer an individual would be to getting this outcome.
Also, if I had to make a guess where I've messed up, I'd say it's in the mutation part of the code:
for (int j = 0; j < number_of_variables; j++)
{
for (int l = 0; l < 32; l++)
{
std::uniform_int_distribution<int> mutation(0, 50);
int mutation_outcome = mutation(rng);
if (mutation_outcome == 1)
{
new_individuals[k].chromosomes[0].at(j) ^= (1 << l);
if (new_individuals[k].chromosomes[0].at(j) == 0)
{
int new_var = uni(rng);
new_individuals[k].chromosomes[0].at(j) = new_var;
}
}
}
}
I say this simply because this is the part I understand least myself and I could very much imagine I'd made an "invisible" error there.
Anyway, any help would be much appreciated.
