Design problem in C++

Question

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.

Answer 1

In C++20, I'd write this as concepts, 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>;
};

Answer 2

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.