~/A Genetic Algorithm in C++
Feb 8, 2022
Implementation of a Genetic Algorithm in C++
1
2
3
4
|
// solutions to retain for the generation
const int SAMPLE_SIZE = 1000;
// solutions per generation
const int NUM = 60000;
|
Solution and Fitness function
Each solution in the population is made up of this basic structure which includes the fitness function.
1
2
3
4
5
6
7
|
struct Solution {
double rank, x, y, z;
void fitness() {
double ans = (6*x-y+std::pow(z, 200))-25;
rank = (ans == 0) ? 9999 : std::abs(1/ans);
}
};
|
Fancy C++11 Distributions
1
2
3
4
5
6
7
8
|
std::random_device device;
std::uniform_real_distribution<double>unif(
-100000,
100000);
std::uniform_int_distribution<int>cross(
0,
SAMPLE_SIZE-1);
std::uniform_real_distribution<double> m(0.99,1.01);
|
Helper data structures
1
2
|
std::vector<Solution> solutions;
std::vector<Solution> sample;
|
The General Algorithm
In the simplest terms our algorithm is simply a loop
that tries to select the best solution by randomly generating solutions.
flowchart LR
A[Start] --> B[Generate Solutions]
B --> F{Found best solution?}
F --Yes-->E[End]
F --No -->B
The Algorithm In (slightly more) Detail
- rank solutions
- selects the top solutions
- mutate solutions
- generate new solutions from old solutions
Step 0: Creating solutions
1
2
3
4
5
6
7
|
for(int i = 0; i < NUM; i++)
solutions.push_back(Solution{
0,
unif(device),
unif(device),
unif(device)
});
|
Step 1: Ranking
Top solutions are sorted in descending order based on rank.
1
2
3
4
5
6
7
|
std::sort(
std::execution::par,
solutions.begin(),
solutions.end(),
[](const auto& lhs, const auto& rhs) {
return lhs.rank > rhs.rank;
});
|
Step 2: Mutation
After selecting the top solutions, each x, y, and z parameter is slightly mutated using a small random multiplier.
1
2
3
4
5
6
7
|
std::for_each(
sample.begin(),
sample.end(), [&](auto& s) {
s.x *= m(device);
s.y *= m(device);
s.z *= m(device);
});
|
Step 3: Crossover
The mutated sample undergoes crossover, randomly selecting parameter values from the top solutions to generate a new population.
1
2
3
4
5
6
7
8
|
for (int i = 0; i < NUM; i++) {
solutions.push_back(Solution{
0,
sample[cross(device)].x,
sample[cross(device)].y,
sample[cross(device)].z,
});
}
|