otus

1.0.0 • Public • Published

Otus

A modular JavaScript API for programming with genetic algorithms.

Installation

npm install otus

Features

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.

Type definition
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 definition
type Allele<TValue> = () => TValue;

Phenotype

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

Type definition
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 definition
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 definition
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 definition
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 definition
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 definition
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>;

Versions

Current Tags

  • Version
    Downloads (Last 7 Days)
    • Tag
  • 1.0.0
    6
    • latest

Version History

Package Sidebar

Install

npm i otus

Weekly Downloads

6

Version

1.0.0

License

MIT

Unpacked Size

81.7 kB

Total Files

63

Last publish

Collaborators

  • clebert