GenAlgo.js

Genetic and evolutionary algorithms in Javascript made simple !

Motivation

This package was written in order to provide a JS genetic algorithm boilerplate. Older libraries were not maintained, had flaws in their documentation or implementation.

This library is inspired by :

• My work at Sterblue
• Tobias Blickle and Lothar Thiele, A Comparison of Selection Schemes used in Genetic Algorithms
• Sub Protocol Genetic.js

Installation

npm install genalgo

Examples

Website with examples in progress (polynomial extrema, bin packing, maybe travelling salesman)

Polynomial extrema is available in the storybook :

npm install
cd examples/storybook
npm install
npm run storybook

Usage

Creation of a GenAlgo object

const algo = new GenAlgo({})

Parameters

All of the following parameters can be set during the GenAlgo object creation, or using the corresponding setter.

Crossover function and pair selection function are linked and must both be set in order to create a genetic algorithm.

Doing only crossovers or mutations can result in slow convergence or being stuck in local extrema.

| Parameter | Type | Default | Required | Description | | -------------------- | :------------------------------------------------------------------------------------------------------------: | :---------: | :------: | -------------------------------------------------------------------------------------------------------------------------------------------------- | | crossoverFunction | (Individual, Individual) => [Individual, Individual] | undefined | | function used when crossover of two Individuals occurs | | crossoverProbability | number | 0.8 | | probability of crossover | | fitnessComparator | (number, number) => boolean | Greater | | function used to compare two fitness and return whether the first is better or not | | fitnessEvaluator | (Individual) => number | undefined | X | function used to evaluate fitness of an Individual | | iterationCallback | ({iterationNumber:number, elapsedTime:number, bestIndividual: {entity:Individual, fitness:number}}) => boolean | undefined | X | function called after each iteration giving some information to the main program. Should return false if the algorithm has to stop, true otherwise | | iterationNumber | number | 1000 | | number of iterations to do | | mutationFunction | (Individual) => Individual | undefined | X | function used when mutation of an Individual occurs | | mutationProbability | number | 0.8 | | probability of mutation | | resultSize | number | undefined | | the number of individuals that should be returned. If it is not set, GenAlgo will return the entire population | | selectPairFunction | (Array<{entity:Individual, fitness:number}>, (number, number) => boolean) => [Individual, Individual] | tournament3 | | function taking the population and a fitnessComparator as parameters, returning a pair of individual | | selectSingleFunction | (Array<{entity:Individual, fitness:number}>, (number, number) => boolean) => [Individual] | fittest | X | function taking the population and a fitnessComparator as parameters, returning a single individual | | spareFittest | boolean | true | | spare the fittest individual during each iteration or not | | seed | Array<Individual> | undefined | X | first population of the algorithm |

Selection Function

GenAlgo provides a set of selection function that can be used by setting them to the corresponding attribute of the GenAlgo object.

Single Selectors

Select a single individual.

| Selector | Description | | ---------------- | ---------------------------------------------------- | | fittest | select the fittest individual | | random | select a random individual | | randomLinearRank | select a random individual based on a linear ranking | | sequential | select the individual in the order of the array | | tournament2 | select the best individual between two | | tournament3 | select the best individual between two |

Pair Selectors

Select a pair of individuals.

| Selector | Description | | ---------------- | ------------------------------------------------------------- | | fittestRandom | select a pair composed of the fittest and a random individual | | random | select a pair of random individuals | | randomLinearRank | select a pair of random individuals based on a linear ranking | | sequential | select a pair of individuals in the order of the array | | tournament2 | select the best two individuals of two tournament2 | | tournament3 | select the best two individuals of two tournament3 |

Fitness Comparators

GenAlgo allows you to maximize or minimize the fitness by setting the comparator to the corresponding attribute

| Comparator | Description | | ---------- | -------------------- | | greater | maximize the fitness | | lesser | minimize the fitness |

Polynomial extremum example

import { GenAlgo, lesser, tournament3Single, tournament3Pair } from "genalgo";
import rangeStep from "lodash/fp/rangeStep";

function tryToFindPolynomialExtremum(func: number => number, min: boolean) {
  // Create a GenAlgo object with simple parameters
  const algo = new GenAlgo({
    mutationProbability: 0.2,
    crossoverProbability: 0.8,
    iterationNumber: 100
  });

  // Function used to mutate an individual
  const mutation = number => {
    return number + Math.random();
  };

  // Function used to crossover two individuals
  const crossover = (number1, number2) => {
    return [(number1 + number2) / 2, number1 + number2];
  };

  // Will be called at each iteration
  const iterationCallback = ({
    bestIndividual,
    elapsedTime,
    iterationNumber
  }) => {
    console.log("Iteration " + iterationNumber);
    console.log("Best fitness : " + bestIndividual.fitness);
    console.log("Elapsed time : " + elapsedTime);
    return true;
  };

  // Seed generation
  const seed = rangeStep(10, -10000, 10000);

  algo.setSeed(seed);

  algo.setFitnessEvaluator(func);

  if (min) {
    algo.setFitnessComparator(lesser);
  }

  algo.setMutationFunction(mutation);

  algo.setCrossoverFunction(crossover);

  algo.setSelectSingleFunction(tournament3Single);

  algo.setSelectPairFunction(tournament3Pair);

  algo.setIterationCallback(iterationCallback);

  algo.start();
}