Neatly Positioned Magazines

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

    3.0.0 • Public • Published

    ga-island

    Genetic Algorithm with 'island' Diversity support

    npm Package Version

    Simplified implementation with zero dependency.

    Demo website

    Inspired from panchishin/geneticalgorithm

    Features

    • [x] Typescript Typing
    • [x] Support custom methods to improve efficiency
    • [x] Support dynamic adjustment on mutation rate
    • [x] Niche Island Support (anti-competitor to encourage diversity)
    • [x] Utilize multi-processor to speed up

    Usage Example

    import { RequiredOptions, GaIsland } from 'ga-island'
    
    type Gene = {
      pattern: string
    }
    
    let options: RequiredOptions<Gene> = {
      populationSize: 100, // should be even number, default 100
      randomIndividual: (): Gene => ({ pattern: '...' }),
      mutationRate: 0.5, // chance of mutation, otherwise will do crossover, default 0.5
      mutate: (input: Gene, output: Gene): void => {
        output.pattern = '...'
      },
      crossover: (aParent: Gene, bParent: Gene, child: Gene): void => {
        output.pattern = '...'
      },
      fitness: (gene: Gene) => 1, // higher is better
      doesABeatB: (a: Gene, b: Gene): boolean => true, // default only compare by fitness, custom function can consider both distance and fitness
      random: Math.random, // optional, return floating number from 0 to 1 inclusively
    }
    
    let ga = new GaIsland(options)
    for (let generation = 1; generation <= 100; generation++) {
      ga.evolve()
      let { gene, fitness } = best(ga.options)
      console.log({ generation, fitness, gene })
    }

    More examples:

    Typescript Signature

    Core types and class in `ga-island`:
    export class GaIsland<G> {
      options: FullOptions<G>
      constructor(options: RequiredOptions<G>)
      evolve(): void
    }
    
    export type RequiredOptions<G> = Options<G> &
      (
        | {
            population: G[]
          }
        | {
            randomIndividual: () => G
          }
      )
    
    export type FullOptions<G> = Required<Options<G>>
    
    export type Options<G> = {
      /**
       * The output should be updated in-place.
       * This design can reduce GC pressure with object pooling.
       *  */
      mutate: (input: G, output: G) => void
      /**
       * default 0.5
       * chance of doing mutation, otherwise will do crossover
       * */
      mutationRate?: number
      /**
       * The child should be updated in-place.
       * This design can reduce GC pressure with object pooling.
       *  */
      crossover: (aParent: G, bParent: G, child: G) => void
      /**
       * higher is better
       * */
      fitness: (gene: G) => number
      /**
       * default only compare the fitness
       * custom function should consider both distance and fitness
       * */
      doesABeatB?: (a: G, b: G) => boolean
      population?: G[]
      /**
       * default 100
       * should be even number
       * */
      populationSize?: number
      /**
       * default randomly pick a gene from the population than mutate
       * */
      randomIndividual?: () => G
      /**
       * return floating number from 0 to 1 inclusively
       * default Math.random()
       * */
      random?: () => number
    }
    Helper functions for ga-island in `ga-island`:
    /**
     * inplace populate the options.population gene pool
     * */
    export function populate<G>(options: FullOptions<G>): void
    
    /**
     * Apply default options and populate when needed
     * */
    export function populateOptions<G>(_options: RequiredOptions<G>): FullOptions<G>
    
    /**
     * generate a not-bad doesABeatB() function for kick-starter
     * should use custom implement according to the context
     * */
    export function genDoesABeatB<G>(options: {
      /**
       * higher is better,
       * zero or negative is failed gene
       * */
      fitness: (gene: G) => number
      distance: (a: G, b: G) => number
      min_distance: number
      /**
       * return float value from 0 to 1 inclusively
       * as chance to change the Math.random() implementation
       * */
      random?: Random
    }): (a: G, b: G) => boolean
    
    export function best<G>(options: {
      population: G[]
      fitness: (gene: G) => number
    }): {
      gene: G
      fitness: number
    }
    
    export function maxIndex(scores: number[]): number
    Helper functions for random in `ga-island`:
    /**
     * return float value from 0 to 1 inclusively
     * */
    export type Random = () => number
    
    /**
     * @param random  custom implementation of Math.random()
     * @param min     inclusive lower bound
     * @param max     inclusive upper bound
     * @param step    interval between each value
     * */
    export function randomNumber(
      random: Random,
      min: number,
      max: number,
      step: number,
    ): number
    
    export function randomElement<T>(random: Random, xs: T[]): T
    /**
     * @param random        custom implementation of Math.random()
     * @param probability   change of getting true
     * */
    export function randomBoolean(random: Random, probability?: number): boolean
    
    /**
     * in-place shuffle the order of elements in the array
     * */
    export function shuffleArray<T>(random: Random, xs: T[]): void
    Helper class for worker thread in `ga-island/thread-pool`:
    import { Worker } from 'worker_threads'
    
    export type WeightedWorker = {
      weight: number
      worker: Worker
    }
    
    /**
     * only support request-response batch-by-batch
     * DO NOT support multiple interlaced concurrent batches
     * */
    export class ThreadPool {
      totalWeights: number
    
      workers: WeightedWorker[]
    
      dispatch<T, R>(inputs: T[]): Promise<R[]>
      dispatch<T, R>(inputs: T[], cb: (err: any, outputs: R[]) => void): void
    
      constructor(
        options:
          | {
              modulePath: string
              /**
               * workload for each worker, default to 1.0 for all workers
               * */
              weights?: number[]
              /**
               * number of worker = (number of core / weights) * overload
               * default to 1.0
               * */
              overload?: number
            }
          | {
              workers: WeightedWorker[]
            },
      )
    
      close(): void
    }

    Remark

    panchishin/geneticalgorithm is a non-traditional genetic algorithm implementation.

    It doesn't sort the population by fitness when evolving into next generation.

    Instead, it randomly picks a pair of 'parent genes', and randomly choose one 'parent' to become the 'child', and merge two 'parents' into another 'child'.

    In ga-island, only the 'stronger parent' in the pair can survive to next generation. Another child is the mutation result of the 'stronger parent', or the crossover result of the 'stronger parent' and another random parent.

    Also, in panchishin/geneticalgorithm, the mutation v.s. crossover probability is 50%, which is much higher than traditional setting where mutation is relative rare. (Custom probability is supported in ga-island)

    Performance

    To better speed up the evolution iteration, the fitness of the population can be calculated in multiple processes or threads.

    However, node.js doesn't allow shared memory across process, the IO cost may become the bottleneck. Therefore, you're recommended to use worker threads when it is supported in your node version.

    Example Benchmark on ThreadPool (click to expand)

    Experiment setup:

    Fitness function: sha256 hash
    Population Size: 20,000
    Max Generation: 100 * [num of process/thread]
    

    Testing machine:

    Architecture:                    x86_64
    CPU op-mode(s):                  32-bit, 64-bit
    CPU(s):                          8
    Thread(s) per core:              2
    Core(s) per socket:              4
    Model name:                      Intel(R) Xeon(R) CPU E3-1230 V2 @ 3.30GHz
    CPU MHz:                         1615.729
    CPU max MHz:                     3700.0000
    CPU min MHz:                     1600.0000
    
    Node Version:                    v14.17.0
    

    source code: speed-test.ts

    Single-core baseline: 2.378 gen/sec

    Number of Process Speed* Speed Up Rate Parallelize Rate
    1 2.880 - -
    2 4.208 1.461 0.731
    3 5.024 1.744 0.581
    4 6.055 2.102 0.526
    5 6.197 2.152 0.430
    6 6.309 2.191 0.365
    7 7.443 2.584 0.369
    8 7.682 2.667 0.333
    Number of Thread Speed* Speed Up Rate Parallelize Rate
    1 2.884 - -
    2 4.749 1.647 0.823
    3 6.323 2.192 0.731
    4 6.057 2.100 0.525
    5 6.384 2.214 0.443
    6 7.284 2.526 0.421
    7 7.169 2.486 0.355
    8 7.512 2.605 0.326

    *: Generation per second, higher better

    License

    This project is licensed with BSD-2-Clause

    This is free, libre, and open-source software. It comes down to four essential freedoms [ref]:

    • The freedom to run the program as you wish, for any purpose
    • The freedom to study how the program works, and change it so it does your computing as you wish
    • The freedom to redistribute copies so you can help others
    • The freedom to distribute copies of your modified versions to others

    Install

    npm i ga-island

    DownloadsWeekly Downloads

    45

    Version

    3.0.0

    License

    BSD-2-Clause

    Unpacked Size

    31.2 kB

    Total Files

    13

    Last publish

    Collaborators

    • beenotung