This is a genetic algorithm I made. Currently, it seems to be flexible enough for my purposes. Since I am quite new to c++, I'd like to know what you think.
I am uncertain about several things and looking for advice!
Probably there are unnecessarily copying of whole Candidates. Where do they actually happen? How to avoid them? Should I use smart_ptrs?
Am I using static template function correctly, with the crossover method?
Is it Ok, to have whole template classes in a header file?
At the bottom, there is a simple usage that finds out a simple text.
GA.hpp
namespace GA{
// Candidate
template<class T, size_t SIZE>
class Candidate{
public:
std::array<T, SIZE> genes{};
float cost {std::numeric_limits<float>::infinity()};
void mutate(float mutation_rate){
/*!
this is called to mutate a candidate
*/
return tweak_mutate(mutation_rate);
}
template<class TT>
static std::array<TT, 2> crossover(TT const & mother, TT const & father, float crossover_rate){
/*!
this is called to create children form parents
*/
return uniform_crossover(mother, father, crossover_rate);
}
// Mutation Techniques
void tweak_mutate(float mutation_rate){
for (auto cell_idx=0; cell_idx < genes.size(); cell_idx++) {
if (RANDOM_NUM < mutation_rate) {
genes[cell_idx] += RANDOM_NUM<0.5 ? -1 : +1;
}
}
}
// Crossover Techniques
template<class TT>
static std::array<TT, 2> uniform_crossover(TT const & mother, TT const & father, float crossover_rate){
auto child1 = mother;
auto child2 = father;
if (RANDOM_NUM < crossover_rate)
for(auto cell=0; cell < mother.genes.size(); cell++){
if(RANDOM_NUM < 0.5)
std::swap(child1.genes[cell], child2.genes[cell]);
}
return std::array<TT, 2>({child1, child2});
}
};
// Population
template<class T>
class Population{
public:
std::vector<T> candidates;
unsigned int generation{0};
void init(size_t size){
candidates.clear();
generation = 0;
for(auto i=0; i<size; i++){
T candidate;
candidates.push_back(candidate);
}
}
std::array<T, 2> tournament_selection(){
size_t tournament_size = 2;
std::array<T, 2> parents; //select two parents;
for(auto i=0; i<parents.size(); i++){
T leader = candidates[rand()%candidates.size()];
for(auto j=0; j<tournament_size; j++){
T opponent = candidates[rand()%candidates.size()];
if(opponent.cost < leader.cost)
leader = opponent;
}
parents[i] = leader;
}
return parents;
}
void breed(){
std::vector<T> offsprings;
while(offsprings.size() < candidates.size()){
std::array<T, 2> parents = tournament_selection();
std::array<T, 2> children = T::crossover(parents[0], parents[1], 0.3);
for(auto & child : children)
child.mutate(0.003);
for(auto const & child : children)
offsprings.push_back(child);
}
std::swap(candidates, offsprings);
generation++;
}
};
};
main.cpp
example usage to find out a simple text
#include <iostream>
#include <stdio.h>
#include "TemplateGA.hpp"
struct MyCandidate : public GA::Candidate<unsigned char, 28>{
std::string phenotype;
};
std::string decode(MyCandidate const & candidate){
std::string text = "";
for(auto cell : candidate.genes)
text += (char)cell;
return text;
}
float distance(std::string const & a, std::string const & b){
float d{0};
size_t length = std::min(a.size(), b.size());
for(auto i=0; i<length;i++){
d += abs((int)a[i] - (int)b[i]);
}
return 1.0 * d/length;
}
int main(int argc, const char * argv[]) {
// insert code here...
// initalize
GA::Population<MyCandidate> pop;
pop.init(9);
while(true) {
// evaluate
for(auto & candidate : pop.candidates){
candidate.phenotype = decode(candidate);
candidate.cost = distance(candidate.phenotype, "Whats up, Genetic Algorhytm!");
}
// show population
std::cout << pop.generation << std::endl;
for(auto & candidate : pop.candidates){
std::cout << candidate.phenotype << " | " << candidate.cost << std::endl;
}
// breed population
pop.breed();
};
return 0;
}