Started December 2016 · Open source; early project
I had worked on the vehicle routing problem: finding good routes for a fleet of vehicles. That work gave me a reason to build a reusable genetic algorithm library in C. I wrote libevol so I could use the same core with different ways of representing and evaluating a solution.
I used a short- and long-term memory mechanism: a current population and a limited record of earlier solutions. The algorithm scores solutions for both fitness and diversity. The library also includes the data structures I needed to build it.
The library
- Register functions for fitness, feasibility, distance, crossover, mutation and local improvement, so the algorithm can work with different problems.
- Manage a population of candidate solutions, select parents, produce children and keep a limited memory of earlier individuals.
- Use supporting C containers and utilities, including lists, hash tables, arrays, matrices, a queue and random number generation.
I organized the code using CLASS, a C coding style developed by Pieter Hintjens, with a clear API for each type. I kept using that approach in later C projects and adapted it for embedded systems, where memory often has to be allocated statically.
libevol is an early library, and its README only covers part of the design. I may build more projects on it in the future.