Otus

A modular JavaScript API for programming with genetic algorithms.

Installation

npm install otus

Features

• Support for three modular exchangeable genetic operators (selection, crossover, mutation)
• A ready-to-use implementation of each of the supported genetic operators:
  • Fitness proportionate selection (via stochastic acceptance)
  • Uniform crossover
  • Uniform mutation
• Genetic representation using plain JavaScript objects
• Support for elitism
• Support for adaptive parameters (adaptive genetic algorithms)
• Immutable/functional API
• Built-in support for TypeScript
• No dependencies

Terminology

Genotype

The genotype defines all genes and their possible values using alleles. It is so to speak the blueprint for the construction of phenotypes.

interface Genotype {
  readonly [geneName: string]: Allele<any>;
}

Allele

The possible values of a particular gene are called alleles. An allele is a function with which the initial value of a gene is generated as well as all further values of a gene in the course of mutations.

type Allele<TValue> = () => TValue;

Phenotype

The phenotype represents a candidate solution and contains all genes defined by the genotype with concrete values.

type Phenotype<TGenotype extends Genotype> = {
  readonly [TGeneName in keyof TGenotype]: Gene<TGenotype, TGeneName>;
};

Gene

A gene represents a concrete property of a solution which can be mutated and altered.

type Gene<
  TGenotype extends Genotype,
  TGeneName extends keyof TGenotype,
> = ReturnType<TGenotype[TGeneName]>;

Selection operator

The selection operator is used to select individual solutions from a population for later breeding (using the crossover operator). The selection is usually based on the fitness of each individual, which is determined by a fitness function.

type SelectionOperator<TGenotype extends Genotype> = (
  phenotypes: readonly Phenotype<TGenotype>[],
  fitnessFunction: FitnessFunction<TGenotype>,
) => Phenotype<TGenotype>;

Fitness function

A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given solution is to achieving the set aims.

type FitnessFunction<TGenotype extends Genotype> = (
  phenotype: Phenotype<TGenotype>,
) => number;

Crossover operator

The crossover operator is used in the process of taking two parent solutions and producing a child solution from them. By recombining portions of good solutions, the genetic algorithm is more likely to create a better solution.

type CrossoverOperator<TGenotype extends Genotype> = (
  phenotypeA: Phenotype<TGenotype>,
  phenotypeB: Phenotype<TGenotype>,
) => Phenotype<TGenotype>;

Mutation operator

The mutation operator encourages genetic diversity amongst solutions and attempts to prevent the genetic algorithm converging to a local minimum by stopping the solutions becoming too close to one another.

type MutationOperator<TGenotype extends Genotype> = (
  phenotype: Phenotype<TGenotype>,
  genotype: TGenotype,
) => Phenotype<TGenotype>;

Usage example

import {
  cacheFitnessFunction,
  createFitnessProportionateSelectionOperator,
  createFloatAllele,
  createIntegerAllele,
  createUniformCrossoverOperator,
  createUniformMutationOperator,
  geneticAlgorithm,
  getFittestPhenotype,
} from 'otus';

const smallNumberGenotype = {
  base: createFloatAllele(1, 10), // float between 1.0 (inclusive) and 10.0 (exclusive)
  exponent: createIntegerAllele(2, 4), // integer between 2 (inclusive) and 4 (inclusive)
};

function isAnswerToEverything(smallNumberPhenotype) {
  const number = Math.pow(
    smallNumberPhenotype.base,
    smallNumberPhenotype.exponent,
  );

  return number === 42 ? Number.MAX_SAFE_INTEGER : 1 / Math.abs(42 - number);
}

const state = {
  genotype: smallNumberGenotype,
  phenotypes: [],
  populationSize: 100,
  elitePopulationSize: 2,
  fitnessFunction: cacheFitnessFunction(isAnswerToEverything),
  selectionOperator: createFitnessProportionateSelectionOperator(),
  crossoverOperator: createUniformCrossoverOperator(0.5),
  mutationOperator: createUniformMutationOperator(0.1),
};

for (let i = 0; i < 100; i += 1) {
  state = geneticAlgorithm(state);
}

const answerToEverythingPhenotype = getFittestPhenotype(state);

console.log(
  `The answer to everything:`,
  Math.pow(
    answerToEverythingPhenotype.base,
    answerToEverythingPhenotype.exponent,
  ),
  answerToEverythingPhenotype,
);

The answer to everything: 42.00057578051458 { base: 3.4760425291663264, exponent: 3 }

API reference

Genetic algorithm function

function geneticAlgorithm<TGenotype extends Genotype>(
  state: GeneticAlgorithmState<TGenotype>,
): GeneticAlgorithmState<TGenotype>;

interface GeneticAlgorithmState<TGenotype extends Genotype> {
  readonly genotype: TGenotype;
  readonly phenotypes: readonly Phenotype<TGenotype>[];
  readonly populationSize: number;
  readonly elitePopulationSize?: number;
  readonly fitnessFunction: FitnessFunction<TGenotype>;
  readonly selectionOperator: SelectionOperator<TGenotype>;
  readonly crossoverOperator: CrossoverOperator<TGenotype>;
  readonly mutationOperator: MutationOperator<TGenotype>;
}

Genetic operator factory functions

function createFitnessProportionateSelectionOperator<
  TGenotype extends Genotype,
>(randomFunction?: () => number): SelectionOperator<TGenotype>;

function createUniformCrossoverOperator<TGenotype extends Genotype>(
  probability: number,
  randomFunction?: () => number,
): CrossoverOperator<TGenotype>;

function createUniformMutationOperator<TGenotype extends Genotype>(
  probability: number,
  randomFunction?: () => number,
): MutationOperator<TGenotype>;

Allele factory functions

function createFloatAllele(
  min: number,
  max: number,
  randomFunction?: () => number,
): Allele<number>;

The created allele returns a random float between min (inclusive) and max (exclusive).

function createIntegerAllele(
  min: number,
  max: number,
  randomFunction?: () => number,
): Allele<number>;

The created allele returns a random integer between min (inclusive) and max (inclusive).

Utility functions

function getFittestPhenotype<TGenotype extends Genotype>(
  state: GeneticAlgorithmState<TGenotype>,
): Phenotype<TGenotype> | undefined;

function cacheFitnessFunction<TGenotype extends Genotype>(
  fitnessFunction: FitnessFunction<TGenotype>,
): FitnessFunction<TGenotype>;

function createRandomPhenotype<TGenotype extends Genotype>(
  genotype: TGenotype,
): Phenotype<TGenotype>;