Nebulous Puffy Marshmallows

    otus
    TypeScript icon, indicating that this package has built-in type declarations

    0.1.4 • Public • Published

    Otus

    A modular JavaScript API for programming with genetic algorithms.

    Installation

    npm install otus --save
    

    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 * as otus from 'otus';
    const smallNumberGenotype = {
      base: otus.createFloatAllele(1, 10), // float between 1.0 (inclusive) and 10.0 (exclusive)
      exponent: otus.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);
    }
    let state = {
      genotype: smallNumberGenotype,
      phenotypes: [],
      populationSize: 100,
      elitePopulationSize: 2,
      fitnessFunction: otus.cacheFitnessFunction(isAnswerToEverything),
      selectionOperator: otus.createFitnessProportionateSelectionOperator(),
      crossoverOperator: otus.createUniformCrossoverOperator(0.5),
      mutationOperator: otus.createUniformMutationOperator(0.1),
    };
    for (let i = 0; i < 100; i += 1) {
      state = otus.geneticAlgorithm(state);
    }
    const answerToEverythingPhenotype = otus.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>;

    Development

    Publishing a new release

    npm run release patch
    
    npm run release minor
    
    npm run release major
    

    After a new release has been created by pushing the tag, it must be published via the GitHub UI. This triggers the final publication to npm.


    Copyright (c) 2020, Clemens Akens. Released under the terms of the MIT License.

    Install

    npm i otus

    DownloadsWeekly Downloads

    5

    Version

    0.1.4

    License

    MIT

    Unpacked Size

    193 kB

    Total Files

    85

    Last publish

    Collaborators

    • clebert