17

I am looking for a genetic algorithm library in C++ which can run in parallel, ideally scaling to a few hundred cores. As I understand it GAs are almost embarrassingly parallel, so I'm a little surprised that I'm having trouble finding a widely used parallel library.

The standard for GAs in C++ seems to be galib. It is quite nice but was made ~20 years ago and recommends parallelizing using PVM, which is not an option on my clusters.

So far I have found GAlib-mpi, which looks to have been made by a fellow graduate student who added some MPI code to galib. I am trying that out now.

I am wondering:

  1. Is there some other standard library that I am missing out on?
  2. If not, has anyone had a good experience with GAlib-mpi?

EDIT:

I ended up getting GAlib-mpi to work, but for future searchers I'll mention another option I found but did not try, pgapack.

Note for people considering Open Beagle: The documentation is fairly incomplete (about half the pages just have 'TODO' on them, and I couldn't find a real example using the HPC module), but there is a good amount of information available through the Google Group and Yahoo Group.

  • C++ for the GA engine or the library interface? – Franck Dernoncourt Mar 17 '14 at 19:15
  • Mostly the interface, since I will be programming in C++. – andyras Mar 17 '14 at 19:35
  • The most documented EC framework I'm aware of is ECJ but it is Java (maybe C++ interface exists somewhere?). – Franck Dernoncourt Mar 30 '14 at 17:03
  • Open Source? Free? What budget? – Nicolas Raoul Apr 16 '14 at 5:57
  • Ideally free/open source for my purposes. – andyras Apr 16 '14 at 12:28
5

You can use Open BEAGLE, it's one of the most widely used Evolutionary Computation (EC) framework, and does provide a master-slave model for parallel fitness evaluation.

Gagné, Christian, and Marc Parizeau. "Open BEAGLE: A New Versatile C++ Framework for Evolutionary Computation." GECCO Late Breaking Papers. 2002.

Genericity: With Open BEAGLE, the user can execute any kind of EC, as far as it fulfills some minimum requirements. The necessary condition is to have a population of individuals to which a sequence of evolving operations is iteratively applied. So far, two specialized frameworks were implemented using Open BEAGLE: Genetic Algorithms (GA) and Genetic Programming (GP). An Evolutionary Strategies (ES) framework is also planned for a future release. The user can take any of these specialized frameworks and modify them further to create his own specialized flavor of evolutionary algorithms.

User Friendliness: Open BEAGLE provides several mechanisms that offer a user friendly programming interface. For example, memory management of dynamically allocated objects is greatly simplified by the use of reference counting and automatic garbage collection.

Portability: The Open BEAGLE code is compliant with the C++ ANSI/ISO 3 standard. It requires the Standard Template Library (STL) (Musser and Saini, 1996). No specific calls are made to the operating system nor to the hardware.

Efficiency: To insure efficient execution, particular attention was given to optimization of critical code sections. Detailed execution profiles of these sections were done. Also, the fact that Open BEAGLE is written in C++ contributes to its overall good performance.

Robustness: Many validation statements are embedded into the code to ensure correct operation and to inform the user when there is a problem. Robust mechanisms for periodically saving the current evolution state have also been implemented in order to enable automatic restart of interrupted evolutions.

Elegance: The interface of Open BEAGLE was developed with care. Great efforts were invested in designing a coherent software package that follows good OO and generic programming principles. Moreover, strict programming rules were enforced to make the C++ code easy to read, understand, and modify.

Free Sourceness The source code of Open BEAGLE is free, available under the GNU Lesser General Public License (LGPL) (Free Software Foundation Inc., 2000). It can thus be distributed and modified without any fee. Open BEAGLE is available on the Web at http://www.gel.ulaval.ca/~beagle.

Software architecture diagram

1

When I was working on my Master thesis in France, I used Sferes2, which also relies on MPI for fitness evaluation parallelization. It has fewer features and less mature/documented than Open BEAGLE by far, but the code is much shorter (SLOC: 5K vs 40K for Open BEAGLE (1)) and very well-organized.

(1) Mouret, J-B., and Stéphane Doncieux. "Sferes v2: Evolvin'in the multi-core world." Evolutionary Computation (CEC), 2010 IEEE Congress on. IEEE, 2010:

This line of thought leads us to the following main objectives for Sferesv2:

  • Be multi-core from the ground-up: include multi-core optimizations from the start of the design process
  • Be up-to-date and multiobjective: provide a few but well selected implementations of "modern” EAs, and especially multiobjective EAs (MOEA)
  • Be based on modern C++ techniques to be both abstract and efficient.

Additionally, we set the following goals, which can be summarized by “the framework should be a good and simple piece of software”:

  • Be extensible: adding new algorithms should be straightforward.
  • Be simple: simple experiments (e.g. optimizing real parameters) should be simple to set-up and require the minimum amount of code.
  • Put the emphasize on efficient implementations rather than on covering the largest number of algorithms.
  • Be small: the source code should be a short as possible to allow new users to quickly master the library and to make maintenance easier.
  • Be tested: each important feature should be accompanied by a unit test.
  • Be portable to all current Unix flavors (especially GNU/Linux and MacOSX);
  • Be open source (GPL-compatible).
  • Be easy to interface with current existing code (especially for fitness functions).

UML class diagram of the main classes of Sferesv:

UML class diagram of the main classes of Sferesv

0

I have done a few bits and pieces with genetic algorithms (both single and multi-objective) on my website, for applications including routing optimization, function optimization, sorting networks etc.

All these applications were written in C++, either as straightforward console applications or as single window / dialog applications. It's not a framework, but the implementations start to take on a similarity after a while eg classes/methods for crossover, mutation, selection, fitness evaluations, constraint handling, maintaining populations etc.

Might be worth playing around with these if you are just seeking to get a feel for evolutionary computing and various genetic operators can be coded. Feel free to download these and see what you think. Comments and feedback always welcome!

http://www.technical-recipes.com/category/genetic-algorithms/

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.