Skip to content

lukix/genemo

Repository files navigation

GeneMO - Genetic Algorithm Library

Build Status Coverage Status npm version MIT Licence

Simple to use genetic algorithm library. It enables fast prototyping by providing a number of universal genetic operators (for selection, crossover, mutation, etc.) and easy customization. Supports both NodeJS and web browsers.

Table of Contents

Installation
Example Usage
Getting Started
API Reference
How To Contribute

Installation

npm i genemo

Example Usage

Full examples with comments can be found in the ./examples directory. Here is a shorter version:

const Genemo = require('genemo');

Genemo.run({
  generateInitialPopulation: Genemo.generateInitialPopulation({
    generateIndividual, // Here, provide a function which generates an individual
    size: 200,
  }),
  selection: Genemo.selection.roulette({ minimizeFitness: false }),
  reproduce: Genemo.reproduce({
    crossover: Genemo.crossover.singlePoint(),
    mutate: Genemo.mutation.transformRandomGene(Genemo.mutation.flipBit()),
    mutationProbability: 0.02,
  }),
  evaluatePopulation: Genemo.evaluatePopulation({ fitnessFunction }), // You need to provide your own fitness function
  stopCondition: Genemo.stopCondition({ maxIterations: 100 }),
}).then(({ evaluatedPopulation }) => {
  // ...
}).catch(console.error);

Example of using GeneMO in the browser environment without blocking browser's main thread can be found in genemo-web-demo repository.

Getting Started

A single most important element of GeneMO library is a Genemo.run function. It runs a genetic algorithm by executing a number of user-specified functions, like for example: generation of initial population, selection, fitness function, etc.

By providing a rich collection of universal genetic operators, GeneMO lets you build an initial version of your genetic algorithm very quickly. Then you can refine your program by gradually replacing GeneMO's universal genetic operators with custom, problem specific operators.

Usually, it is enough to implement a custom function for generating random individual/solution and a fitness function. Rest of the required functions can be taken from the GeneMO library. However, keep in mind that problem specific operators usually give better results.

Read API Reference for detailed description of all the options required by Genemo.run.
See Example Usage to quickly get familiar with basic usage of GeneMO.

Genemo.run(options).then(result => {
  // ...
});

Genemo.run returns a promise, which resolves to an object:

{ evaluatedPopulation: EvaluatedPopulation, iteration: number, logs: object }

It contains information about the population (along with fitness values) from the final iteration, number of iterations and an object with logs (mostly with performance data).

Asynchronous execution

Each function passed to Genemo.run (selection, reproduce, fitness, etc.) can return a Promise (synchronous functions work as well). From time to time Genemo.run runs next iteration asynchronously to avoid blocking browser's main thread. However, if a single iteration takes too long to complete, it will still block the main thread. To control the frequency of asynchronous iteration executions, use maxBlockingTime option.

Multithreading

Currently, GeneMO does not have a lot of functionalities for multithreading built-in, but thanks to its highly flexible architecture, you can easily implement multithreading on your own. In the ./examples/example3-parallelExecution directory there is a full example of a genetic algorithm, which performs fitness function and crossover operation in parallel processes, using NodeJS child_process module.

Usually, the most computationaly intensive elements of a genetic algorithm are fitness function, crossover and mutation. evaluatePopulation parameter of Genemo.run is a function, which maps an array of individuals to an array of their fitness values. You can divide this array into a few chunks and evaluate each of them in parallel. To do the same with crossover and mutation, you can use reproduceBatch instead of reproduce. Instead of calling the crossover function for each pair of parents, it calls it only once, passing an array of pairs as an argument. Same with mutation - it is called only once with an array of individuals which should be mutated. Thanks to that, you can divide those arrays into chunks an process them in parallel.

I plan to add to GeneMO more utilities that make implementing multithreading easier, but I don't want to include any code which is strictly dependend on the environment. Therefore, things like WebWorkers or NodeJS child_process are not likely to appear in the library.

API Reference

GeneMO exports a Genemo object with properties listed in the hierarchy below.
Full description of each property can be found in API.md.

How To Contribute

If you found a bug, you have a feature request, or you just have a question, please open a new issue on Github. You can also contact me on Twitter (@lukaszjenczmyk). Linter and tests are configured to run on the CI (and locally with Husky). I appreciate your input ❤️