Genetic algorithm in TypeScript with linear fitness scaling; example problem solved is maximization of f(x) = x^10

genetic-algorithm.ts

/* Random utilities */
export class Random {
  static getRandom() {
    return Math.random();
  }

  static getRandomInt(min: number, max: number) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min) + min);
  }

  static flip(probability = 0.5): boolean {
    return Random.getRandom() < probability;
  }

  static getRandomBit(): 0 | 1 {
    return Random.flip() ? 0 : 1;
  }
}

/* Genetic algorithm */

import { maxBy, minBy, sumBy } from "lodash-es";

export type Bit = 0 | 1;

export interface Individual<Phenotype> {
  chromosome: Bit[];
  phenotype: Phenotype;
  fitness: number;
  scaledFitness?: number;
}

interface Statistics<Phenotype> {
  fitnessSum: number;
  scaledFitnessSum?: number;
  avgFitness: number;
  bestIndividual: Individual<Phenotype>;
  worstIndividual: Individual<Phenotype>;
}

interface Population<Phenotype> {
  individuals: Individual<Phenotype>[];
  statistics: Statistics<Phenotype>;
}

export interface Settings {
  populationSize: number;
  chromosomeSize: number;
  maxGenerations: number;
  crossoverProb: number;
  mutationProb: number;
  scaleFitness: boolean;
}

const DefaultSettings: Settings = {
  populationSize: 100,
  chromosomeSize: 30,
  maxGenerations: 300,
  crossoverProb: 0.95,
  mutationProb: 0.001,
  scaleFitness: true,
};

export type DecodeFunction<Phenotype> = (chromosome: Bit[]) => Phenotype;
export type FitnessFunction<Phenotype> = (phenotype: Phenotype) => number;
export type FixingChromosomeFunction<Phenotype> = (
  phenotype: Phenotype,
  chromosome: Bit[]
) => Bit[];

export class GeneticAlgorithm<Phenotype> {
  private fitnessMultiple = 2.0;

  public constructor(
    private decodeFunction: DecodeFunction<Phenotype>,
    private evaluateFitness: FitnessFunction<Phenotype>,
    private settings: Settings = DefaultSettings,
    private fixChromosome?: FixingChromosomeFunction<Phenotype>
  ) {}

  public run(): { bestIndividual: Individual<Phenotype>; bestGeneration: number } {
    let population = this.generatePopulation();
    let bestIndividual = population.statistics.bestIndividual;
    let bestGeneration = 0;
    this.generationSummary(0, population.statistics);
    for (let generation = 1; generation <= this.settings.maxGenerations; generation++) {
      const newPopulation = this.reproduce(population);
      if (bestIndividual.fitness < newPopulation.statistics.bestIndividual.fitness) {
        bestIndividual = newPopulation.statistics.bestIndividual;
        bestGeneration = generation;
      }
      this.generationSummary(generation, newPopulation.statistics);
      population = newPopulation;
    }
    return { bestIndividual, bestGeneration };
  }

  private newIndividual(chromosome: Bit[]): Individual<Phenotype> {
    const phenotype = this.decodeFunction(chromosome);
    const fitness = this.evaluateFitness(phenotype);
    return {
      chromosome: this.fixChromosome?.(phenotype, chromosome) || chromosome,
      phenotype,
      fitness,
    };
  }

  private generatePopulation(): Population<Phenotype> {
    const individuals: Individual<Phenotype>[] = [];
    for (let i = 0; i < this.settings.populationSize; i++) {
      individuals.push(this.generateIndividual());
    }
    const statistics = this.getStatistics(individuals);
    const population = { individuals, statistics };
    if (this.settings.scaleFitness) {
      this.scalePopulation(population);
    }
    return population;
  }

  private generateIndividual() {
    const chromosome = this.generateChromosome();
    return this.newIndividual(chromosome);
  }

  private generateChromosome(): Bit[] {
    const chromosome: Bit[] = [];
    for (let i = 0; i < this.settings.chromosomeSize; i++) {
      chromosome.push(Random.getRandomBit());
    }
    return chromosome;
  }

  private scalePopulation(population: Population<Phenotype>): void {
    const { a, b } = prescale(
      population.statistics.bestIndividual.fitness,
      population.statistics.avgFitness,
      population.statistics.worstIndividual.fitness,
      this.fitnessMultiple
    );
    let scaledFitnessSum = 0.0;
    for (const individual of population.individuals) {
      individual.scaledFitness = a * individual.fitness + b;
      scaledFitnessSum += individual.scaledFitness;
    }
    population.statistics.scaledFitnessSum = scaledFitnessSum;
  }

  private selectIndividual(population: Population<Phenotype>): Individual<Phenotype> {
    const sumFitness = population.statistics.fitnessSum;
    const index = selectByRoulette(
      population.individuals.map((individual) =>
        this.settings.scaleFitness ? (individual.scaledFitness as number) : individual.fitness
      ),
      sumFitness
    );
    return population.individuals[index];
  }

  private reproduce(population: Population<Phenotype>): Population<Phenotype> {
    const newIndividuals = [];
    for (let i = 0; i < population.individuals.length; i += 2) {
      const mate1 = this.selectIndividual(population);
      const mate2 = this.selectIndividual(population);
      const [child1, child2] = this.reproduceMates(mate1, mate2);
      newIndividuals.push(child1, child2);
    }
    const newStatistics = this.getStatistics(newIndividuals);
    const newPopulation = {
      individuals: newIndividuals,
      statistics: newStatistics,
    };
    if (this.settings.scaleFitness) {
      this.scalePopulation(newPopulation);
    }
    return newPopulation;
  }

  private reproduceMates(
    mate1: Individual<Phenotype>,
    mate2: Individual<Phenotype>
  ): [Individual<Phenotype>, Individual<Phenotype>] {
    const [chromosome1, chromosome2] = Random.flip(this.settings.crossoverProb)
      ? crossoverChromosomes(mate1.chromosome, mate2.chromosome)
      : [mate1.chromosome, mate2.chromosome];
    return [
      this.newIndividual(mutateChromosome(chromosome1, this.settings.mutationProb)),
      this.newIndividual(mutateChromosome(chromosome2, this.settings.mutationProb)),
    ];
  }

  private getStatistics(individuals: Individual<Phenotype>[]): Statistics<Phenotype> {
    const sumFitness = sumBy(individuals, "fitness");
    const bestIndividual = maxBy(individuals, "fitness") as Individual<Phenotype>;
    const worstIndividual = minBy(individuals, "fitness") as Individual<Phenotype>;
    const avgFitness = sumFitness / individuals.length;
    return {
      fitnessSum: sumFitness,
      avgFitness,
      bestIndividual,
      worstIndividual,
    };
  }

  private generationSummary(generation: number, statistics: Statistics<Phenotype>) {
    const bestChromosome = statistics?.bestIndividual?.chromosome.join("");
    const worstChromosome = statistics?.worstIndividual?.chromosome.join("");
    const result = {
      averageFitness: statistics.avgFitness,
      best: bestChromosome,
      bestFitness: statistics?.bestIndividual?.fitness,
      worst: worstChromosome,
      worstFitness: statistics?.worstIndividual?.fitness,
      bestLength: bestChromosome.length,
    };
    // eslint-disable-next-line no-console
    console.log(`Generation ${generation}: ${JSON.stringify(result, null, 2)}`);
  }
}

/* Genetic operators */
  
export function selectByRoulette(
  population: number[],
  sumFitness: number,
  random: () => number = Random.getRandom
): number {
  const rand = random() * sumFitness;
  let partSum = 0;
  for (let i = 0; i < population.length; i++) {
    partSum += population[i] || 0;
    if (partSum >= rand) {
      return i;
    }
  }
  throw population.length - 1;
}

export function mutateChromosome(
  chromosome: Bit[],
  mutationProb = 0.001,
  flip: (probability: number) => boolean = Random.flip
): Bit[] {
  const mutatedChrom = [...chromosome];
  for (let i = 0; i < chromosome.length; i++) {
    if (flip(mutationProb)) {
      mutatedChrom[i] = mutatedChrom[i] === 1 ? 0 : 1;
    }
  }
  return mutatedChrom;
}

export function crossoverChromosomes(
  parent1: Bit[],
  parent2: Bit[],
  randomInt: (min: number, max: number) => number = Random.getRandomInt
): [Bit[], Bit[]] {
  const crossoverPoint = randomInt(0, Math.min(parent1.length, parent2.length) - 1) + 1;
  return [
    [...parent1.slice(0, crossoverPoint), ...parent2.slice(crossoverPoint)],
    [...parent2.slice(0, crossoverPoint), ...parent1.slice(crossoverPoint)],
  ];
}

/* Computing linear coefficients */
function prescale(
  max: number,
  avg: number,
  min: number,
  fMultiple: number
): { a: number; b: number } {
  let a, b;
  if (min > (fMultiple * avg - max) / (fMultiple - 1.0)) {
    const delta = max - avg;
    a = ((fMultiple - 1.0) * avg) / delta;
    b = (avg * (max - fMultiple * avg)) / delta;
  } else {
    const delta = avg - min;
    a = avg / delta;
    b = (-min * avg) / delta;
  }
  return { a, b };
}
  
/* Usage */

function decode(chromosome: Bit[]): number {
  let accum = 0;
  for (let i = 0; i < chromosome.length; i++) {
    accum = (accum << 1) + chromosome[i];
  }
  return accum;
}

function getFitness(x: number): number {
  const coeff = 1073741823;
  return Math.pow(x / coeff, 10);
}

const { bestIndividual, bestGeneration } = new GeneticAlgorithm<number>(decode, getFitness, {
  populationSize: 100,
  chromosomeSize: 30,
  maxGenerations: 300,
  crossoverProb: 0.6,
  mutationProb: 0.0333,
  scaleFitness: true,
}).run();

console.log(
  `Best individual found: ${bestIndividual.chromosome.join("")}, fitness: ${
    bestIndividual.fitness
  } in generation ${bestGeneration}`
);