[boost] [GSOC] Thoughts about a metaheuristic library

Subject: [boost] [GSOC] Thoughts about a metaheuristic library
From: Murilo Adriano Vasconcelos (muriloufg_at_[hidden])
Date: 2011-03-27 13:38:26

Hi,

I'm thinking about proposing a library of genetic algorithms for this GSOC
and wondered what the community thinks about it.
The main idea is to provide a in extensible set of classes that a user can
easily implement a GA without difficulty.

/* Individual with double as fitness fuction type
 * An individual is a possible solution for the problem
 * In this case, bit_individual can be a class with boost::array<bool>
 * and some more information like the fitness function type
 * and an interface for basic things like sorting the population
 */
typedef bit_individual<double> individual_d;

// Fitness function: evaluates a solution
double fitness_func(const individual_d& ind)
{
double value = 0.0;
 // calc the fitness of ind
 return value;
}

// Fitness evaluator
fitness_function fitness(fitness_func);

// A population is a set of solutions
population<individual_d> pop;

// We can for example initialize the poulation with
// some size passing a random number generator (rng)
initialize_random_population(pop, SIZE, rng);

// The tournament selector: chooses T_SIZE elements from population
// and selects the one with greater fitness
tournament_selector<individual_d> selector(T_SIZE);
// roullete_selector<individual_d> ...

// This specifies the mutation rate of each bit of each individual
bit_mutation<individual_d> mutator(RATE);

// Crossover in
bit_crossover<individual_d> cross; // 1-point crossover
// bit_crossover<individual_d> cross(n) : n-point crossover

// When the algorithm will stop: in this case, number of generations
generation_continuator<individual_d> continuator(MAX_GEN);
// can be fitness_continuator<individual_d> cont(val) : continues until the
best fitness is less than val

// Genetic Algorithm functor
ga<individual_d> algo(selector, cross, CROSS_RATE, mutator, fitness,
continuator);

// Run the GA taking pop as initial population
algo(pop);

// Gets the best element from the population
individual_d best_element = pop.best_element();

// Prints the fitness of the best element
std::cout << best_element.fitness() << std::endl;

For this basic example, the user only have to choose the parameters (like
selector, crossover, continuator, ...) and provide a fitness function with
the problem specific rating for an individual.

This library can be extended to cover more metaheuristics and be
parallelized with Boost.MPI.

Ideas about the design and other thinks are also welcome.

Regards,
-- 
Murilo Adriano Vasconcelos
http://murilo.wordpress.com