Multiprocessing Genetic Algorithm Implementation for TypeScript

Overview

This project provides a TypeScript implementation of a genetic algorithm that can be used for optimization problems. The algorithm is designed to be highly customizable and can be used for a wide range of applications.

Features

• Multiprocessing support: The algorithm can be run in parallel using multiple processes, making it suitable for large-scale optimization problems.
• Deep customization: The algorithm can be customized by providing custom implementations for various components:
  • base parameters (population size, survival rate, crossover rate);
  • strategies (population, phenome, fitness, sorting, selection, mutation, crossover, caching);
  • scheduler for dynamic tuning of all the macro parameters.
• Separation of phenome metrics and fitness calculation: The algorithm separates the computation of phenomes and fitness values, allowing normalization and other operations to be applied to the phenomes of all genomes prior to evaluating the fitness function.
• Type-safe: The project uses TypeScript, which provides type safety and helps catch errors at compile-time.

Setup

For single process (including browser apps) use:

npm i genetic-search
Copy

For multiprocessing in node environment use:

npm i genetic-search-multiprocess
Copy

Usage example

Let's get a max value of the parabola: y = -(x-12)^2 - 3.

import type {
  GeneticSearchConfig,
  GeneticSearchStrategyConfig,
} from "genetic-search";
import {
  GeneticSearch,
  SimplePhenomeCache,
  DescendingSortingStrategy,
  RandomSelectionStrategy,
} from "genetic-search";

const config: GeneticSearchConfig = {
  populationSize: 100,
  survivalRate: 0.5,
  crossoverRate: 0.5,
};

const strategies: GeneticSearchStrategyConfig<ParabolaArgumentGenome> = {
  populate: new ParabolaPopulateStrategy(),
  phenome: new ParabolaMultiprocessingPhenomeStrategy({
    poolSize: 4,
    task: async (data) => [-((data[0] - 12)**2) - 3],
    onTaskResult: () => void 0,
  }),
  fitness: new ParabolaMaxValueFitnessStrategy(),
  sorting: new DescendingSortingStrategy(),
  selection: new RandomSelectionStrategy(2),
  mutation: new ParabolaMutationStrategy(),
  crossover: new ParabolaCrossoverStrategy(),
  cache: new SimplePhenomeCache(),
}

const search = new GeneticSearch(config, strategies);

expect(search.partitions).toEqual([50, 25, 25]);

await search.fit({
  generationsCount: 100,
  beforeStep: () => void 0,
  afterStep: () => void 0,
});

const bestGenome = search.bestGenome;
console.log('Best genome:', bestGenome);
Copy

Strategies implementation:

import type {
  BaseGenome,
  BaseMutationStrategyConfig,
  CrossoverStrategyInterface,
  FitnessStrategyInterface,
  GenerationFitnessColumn,
  GenerationPhenomeMatrix,
  IdGeneratorInterface,
  PopulateStrategyInterface,
} from "genetic-search";
import type { MultiprocessingPhenomeStrategyConfig } from "genetic-search-multiprocess";
import { BaseMutationStrategy } from "genetic-search";
import { MultiprocessingPhenomeStrategyConfig } from "genetic-search-multiprocess";

export type ParabolaArgumentGenome = BaseGenome & {
  id: number;
  x: number;
}

export type ParabolaTaskConfig = [number];

export class ParabolaPopulateStrategy implements PopulateStrategyInterface<ParabolaArgumentGenome> {
  populate(size: number, idGenerator: IdGeneratorInterface<ParabolaArgumentGenome>): ParabolaArgumentGenome[] {
    const result: ParabolaArgumentGenome[] = [];
    for (let i=0; i<size; ++i) {
      result.push({ id: idGenerator.nextId(), x: Math.random() * 200 - 100 });
    }
    return result;
  }
}

export class ParabolaMutationStrategy extends BaseMutationStrategy<ParabolaArgumentGenome, BaseMutationStrategyConfig> {
  constructor() {
    super({ probability: 1 });
  }

  mutate(genome: ParabolaArgumentGenome, newGenomeId: number): ParabolaArgumentGenome {
    return { x: genome.x + Math.random() * 10 - 5, id: newGenomeId };
  }
}

export class ParabolaCrossoverStrategy implements CrossoverStrategyInterface<ParabolaArgumentGenome> {
  cross(parents: ParabolaArgumentGenome[], newGenomeId: number): ParabolaArgumentGenome {
    const [lhs, rhs] = parents;
    return { x: (lhs.x + rhs.x) / 2, id: newGenomeId };
  }
}

export class ParabolaMultiprocessingPhenomeStrategy extends BaseMultiprocessingPhenomeStrategy<ParabolaArgumentGenome, MultiprocessingPhenomeStrategyConfig<ParabolaTaskConfig>, ParabolaTaskConfig> {
  protected createTaskInput(genome: ParabolaArgumentGenome): ParabolaTaskConfig {
    return [genome.x];
  }
}

export class ParabolaMaxValueFitnessStrategy implements FitnessStrategyInterface {
  score(results: GenerationPhenomeMatrix): GenerationFitnessColumn {
    return results.map((result) => result[0]);
  }
}
Copy

Api Reference

For detailed documentation and usage examples, please refer to:

• Main API documentation
• Multiprocess API documentation

Unit testing

npm i
npm run test
Copy

License

Genetic Search TS is licensed under the MIT License.