[GSOC] Thoughts about a metaheuristic library

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

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.
I'm also curious to see what the community thinks about this. I know there have been a couple of similar C++ projects over the years (GALib, Evolving Objects), but I don't think that they have been terribly successful. On the other hand the field of metaheuristic search is pretty active (academically, anyways). This is definitely not a summer-long task, but I think could make a nice Boost Library, in the long run. Let's see what others say. Andrew

On 03/27/2011 03:57 PM, Andrew Sutton wrote:
Let's see what others say.
I think this is a good research area and is reasonable to explore as a GSOC topic. I'd be interested in what sort of concepts and API emerge for such a library. I'm not sure if the topic area is one that would ultimately be included in boost or not. Strong integration with boost.mpi, boost.thread/process would make a more compelling case, though I think the concepts and API are much more important to think about for now and shouldn't be constrained by existing boost technologies.

Thanks for the feedback Andrew and Brian. I'm also curious to see what the community thinks about this. I know
there have been a couple of similar C++ projects over the years (GALib, Evolving Objects), but I don't think that they have been terribly successful.
Sometime ago I needed to use Envolving Objects and I feel that is something discontinued (I had some compile errors, fixed and tried to report to someone and got no answers). On the other hand the field of metaheuristic search is pretty active
(academically, anyways).
You are right, this is part of the motivation for such a library :). And more, the use of metaheuristic in optimization field is also increasing. This is definitely not a summer-long task, but I think could make a nice
Boost Library, in the long run.
I think that GSoC project for starting this is a good idea because of time constraints to have something. And obviously the funds received by the student allows full time dedication. I think this is a good research area and is reasonable to explore as a
GSOC topic. I'd be interested in what sort of concepts and API emerge for such a library. I'm not sure if the topic area is one that would ultimately be included in boost or not. Strong integration with boost.mpi, boost.thread/process would make a more compelling case, though I think the concepts and API are much more important to think about for now and shouldn't be constrained by existing boost technologies.
I think that this library can have a very attractive design. I agree with you that is important to use as many Boost features as we can, but this can't be a constraint. The idea is to have a functional set of components and helper functions/templates at the end of the program for the Genetic Algorithm, built in a way to easy add/extend components for other metaheuristics. What do you think? If the community thinks that is a reasonable idea, I need a volunteer to be the mentor. Regards, -- Murilo Adriano Vasconcelos http://murilo.wordpress.com
participants (3)
-
Andrew Sutton
-
Brian Schrom
-
Murilo Adriano Vasconcelos