# Design problem in C++

I am trying to engineer a library for the Genetic Algorithm optimization method.

The main class for the GA is quite general. Here is what I have for it

`````` struct GAOptions{
size_t max_ga_steps;
double weight;// -1 gives the maximum while +1 gives the minimum
double cxpb;
double mutpb;
};
template<class INDIVIDUAL>
INDIVIDUAL GeneticAlgorithm(
const GAOptions opt)
{
using Population = std::vector<INDIVIDUAL>;
Population population = INDIVIDUAL::generatePopulation();
int population_size = population.size();

for(auto &ind: population){
ind.updateFitness();
}

std::sort(begin(population), end(population),
[&opt](auto &a, auto& b){ return opt.weight*a.getFitness() < opt.weight*b.getFitness(); });

double prev{std::numeric_limits<double>::infinity()};
INDIVIDUAL prev;
INDIVIDUAL current = population[0];

int ga_steps{};
while(!INDIVIDUAL::fittestFound(current, prev) &&
ga_steps < opt.max_ga_steps){
ga_steps++;

// Perform elitism. Take xx% of the best
Population offspring;
int s = (5*population.size())/100;
offspring.insert(begin(offspring), begin(population), begin(population) + s);

// Inject new blood, xx% new population
s = (10*population.size())/100;
for(int i = 0; i < s; i++) {
offspring.push_back(
INDIVIDUAL::create()
);
}

// Mate the top 50% of the population
for(auto i = offspring.size(); i < population.size(); i++){
int m = rand()%(population.size()/2);
int f = rand()%(population.size()/2);
INDIVIDUAL child = population[m].mate(population[f], cxpb);
offspring.push_back(child);
}

for(auto& child: offspring){
if(static_cast<double>(rand())/RAND_MAX < mutpb){
child.mutate(0.1);
}
}

for(auto &ind:offspring){
ind.updateFitness();
}

population = offspring;
prev = current;

std::sort(begin(population), end(population),
[&weight](auto &a, auto& b){ return weight*a.getFitness() < weight*b.getFitness(); });
current = population[0];
}

INDIVIDUAL best = population[0];

return best;
}
``````

As you can see there are a few requirements on the INDIVIDUAL template parameter. Aside from the member functions there are three static functions that need to be implemented.

The problem I am having is that static functions are not as flexible as I want them to be. For instance if the INDIVIDUAL class needs to know some info regarding how to create itself, that can not be passed to static method and since it is a static method it can not be part of the object.

Lets say I have an Individual class where the constructor needs three values in order to be able to create an object. The static create method is not going to be able to handle this.

How do I get around this issue? One thought from me is to use `std::function` for the three static methods as part of `GAOptions` and remove the static functions from the INDIVIDUAL. This way I can use lambda expression to sort of bundle the info I need.

Any thoughts are appreciated. Please let me know if I should clear up something.

• You could turn `GAOptions` into something like `std::char_traits`, and have it templated over `INDIVIDUAL` and `GA_TRAITS` Jun 22, 2021 at 10:50
• Thanks @Caleth. Could you give an example? Jun 22, 2021 at 11:24

In C++20, I'd write this as `concept`s, prior to that it'd be equivalent documentation.

"A type is an `individual` if it has a default constructor, copy constructor & assignment, and given ..., the expressions `individual.mate(partner)`, `individual.mutate(mutator)`, `individual.updateFitness()` and `individual.getFitness()` exist, and have the semantics ..."

``````template <typename T>
concept individual = std::semiregular<T> && requires (T individual, const T & partner, double mutator)
{
{individual.mate(partner)} -> std::convertible_to<T>;
{individual.mutate(mutator)};
{individual.updateFitness()};
{individual.getFitness()} -> std::totally_ordered;
};
``````

"A type is a `ga_traits` if it has member type aliases `individual_type` and `population_type`, and given ..., the expressions `traits.create()`, `traits.generatePopulation()` and `traits.fittestFound(x, y)` exist, and have the semantics ..."

``````template <typename T>
concept ga_traits = requires (T traits)
{
typename T::individual_type;
typename T::population_type;
{traits.create()} -> individual && std::same_as<typename T::individual_type>;
{traits.generatePopulation()} -> std::same_as<T::population_type>;
{traits.fittestFound(std::declval<typename T::individual_type>(), std::declval<typename T::individual_type>()) -> std::convertible_to<bool>;
};
``````
• Basically what you have written here is that you don't have anything static. Instead all the statics are given as normal members to trait. I am not able to use c++ 20 so not having the concept will just give me some more compiler errors for the user to understand Jun 22, 2021 at 19:04
• Before C++20 a concept is documentation, not code, e.g. the table for CharTraits Jun 22, 2021 at 20:05

The way I solved this problem is template template parameters. Basically your INDIVIDUAL class is itself a template that you can specialize based on the type it's instantiated with. I used it to do things like have my INDIVIDUAL (which in my code I called "Chromosome") be able to represent different encodings like binary, real-valued, permutations, etc. Each of those was represented by an instance of a set of types I called "Encoding". So instead of

``````template <class T>
class population { ... }
``````

you get something like

``````template <template <typename> class Chromosome, typename Encoding>
class population { ... }
``````

where Chromosome itself is a template like

``````template <typename Encoding>
class chromosome { ... }
``````

Now if I have two different instantiations of Chromosome, say for `int` and `double` that have different requirements, I just write them as partial specializations of the `chromosome` class. In my case, my encoding types were classes themselves rather than primitives like `int` or `double`, but the same principle applies.

The plus side is that this is extremely flexible, and flexible in a way that enables really great runtime performance. The downside is that it's really cumbersome to work with. The template parameters are contagious, and the result is that almost every class depends on the same set of template parameters, and everything becomes one giant compilation unit. Compile times are brutal, error messages are useless, and there's a fair amount of boilerplate that effectively exists just to provide a poor man's idea of dynamic polymorphism sitting on top of this mass of static polymorphism so that you can use the same compiled executable to handle different types of encodings and functionality based off a configuration file.

The most common alternative I think would have been to have some form of `Object` as your lowest level type represented inside that vector that makes up an INDIVIDUAL and then rely on runtime polymorphism to vary the behavior across instantiated types. That introduces a couple of problems. One is what you're running into here where it really demands a set of common interfaces to those objects. You could try to abstract out things like object creation into some sort of factory objects to get around some of this, but that's kind of gross too. Second, a GA is effectively a pretty tight loop that runs tens of millions of iterations, and it's nice if the innermost loop there is closer to the metal. My solution solves that problem, but at a really steep usability price that I'm not altogether happy with.

My code is here (https://github.com/deong/sls). The specific files related to what you're talking about here would be chromosome.{h,cpp} and encoding.{h,cpp}. Most of this is 10-15 year-old code, and there are some idioms that aren't great (lots of `using namespace std;` which I don't feel great about today, and that sort of thing), and obviously no modern niceties like `auto`. But you're welcome to mine it for ideas if you want.

• Thanks for the answer. I don't understand why I should have INDIVIDUAL as template since I really don't care what and how anything is represented there. It has several methods that would give me the metrics and functionality that I want without knowing what is inside. Am I missing something here? That said I will look through your code for sure. Jun 22, 2021 at 19:00
• The main reason is to be very flexible with respect to the underlying types. My GA package supports binary coded GAs, where the INDIVIDUAL basically contains a `vector<int>` as well as real-valued encodings where the same class contains a `vector<double>` instead, permutation encodings, constrained encodings, etc. Each has specialized genetic operations (xover, mutation) that all work on the same Chromosome type, just with template specializations for the different underlying cases. If you're only going to be supporting simple GAs with binary chromosomes, it's overkill. Jun 22, 2021 at 19:16