Simple Genetic Algorithm in JavaScript

genetic-algorithm.js

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

export const Random = {
  /** @returns {number} */
  getRandom() {
    return Math.random();
  },
  /**
   * The maximum is exclusive and the minimum is inclusive
   *
   * @param {number} min
   * @param {number} max
   * @returns {number}
   */
  getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min) + min);
  },
  /**
   * Returns true with given probability
   *
   * @param {number} [probability]
   * @returns {boolean}
   */
  flip(probability = 0.5) {
    return this.getRandom() < probability;
  },
  /** @returns {0 | 1} */
  getRandomBit() {
    return this.flip() ? 0 : 1;
  },
};

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

/**
 * @param {number} chromosomeSize
 * @returns {(0 | 1)[]}
 */
function getRandomChromosome(chromosomeSize) {
  const chromosome = [];
  for (let i = 0; i < chromosomeSize; i++) {
    chromosome[i] = Random.getRandomBit();
  }
  return chromosome;
}

/**
 * @param {(0 | 1)[]} chromosome
 * @returns {number}
 */
export function decode(chromosome) {
  let accum = 0;
  for (let i = 0; i < chromosome.length; i++) {
    accum = (accum << 1) + chromosome[i];
  }
  return accum;
}

/**
 * @param {(0 | 1)[]} chromosome
 * @returns {number}
 */
export function getFitness(chromosome) {
  const x = decode(chromosome);
  const coeff = 1073741823;
  return Math.pow(x / coeff, 10);
}

/**
 * @param {(0 | 1)[]} parent1
 * @param {(0 | 1)[]} parent2
 * @param {(min: number, max: number) => number} [randomInt]
 * @returns {[(0 | 1)[], (0 | 1)[]]}
 */
export function crossover(parent1, parent2, randomInt = Random.getRandomInt) {
  const crossPoint = randomInt(0, parent1.length - 1) + 1;
  return [
    [...parent1.slice(0, crossPoint), ...parent2.slice(crossPoint)],
    [...parent2.slice(0, crossPoint), ...parent1.slice(crossPoint)],
  ];
}

/**
 * @param {(0 | 1)[]} chromosome
 * @param {number} mutationProb
 * @returns {(0 | 1)[]}
 */
export function mutate(chromosome, mutationProb = 0.001) {
  const mutatedChrom = [...chromosome];
  for (let i = 0; i < chromosome.length; i++) {
    if (Random.flip(mutationProb)) {
      mutatedChrom[i] = mutatedChrom[i] === 1 ? 0 : 1;
    }
  }
  return mutatedChrom;
}

/** @param {{ chromosome: (0 | 1)[] }[]} population */
function evaluatePopulation(population) {
  for (const individual of population) {
    individual.fitness = getFitness(individual.chromosome);
  }
}

/**
 * @param {number} populationSize
 * @param {number} chromosomeSize
 * @returns {{ chromosome: (0 | 1)[]; fitness: number }[]}
 */
function generatePopulation(populationSize, chromosomeSize) {
  const population = [];
  for (let i = 0; i < populationSize; i++) {
    population.push({
      chromosome: getRandomChromosome(chromosomeSize),
    });
  }
  evaluatePopulation(population);
  return population;
}

/**
 * @param {{ chromosome: (0 | 1)[]; fitness: number }[]} population
 * @returns {{
 *   sumFitness: number;
 *   avgFitness: number;
 *   bestIndividual: {
 *     chromosome: (0 | 1)[];
 *     fitness: number;
 *   };
 *   worstIndividual: {
 *     chromosome: (0 | 1)[];
 *     fitness: number;
 *   };
 * }}
 */
function getStatistics(population) {
  const sumFitness = sumBy(population, "fitness");
  const bestIndividual = maxBy(population, "fitness");
  const worstIndividual = minBy(population, "fitness");
  const avgFitness = sumFitness / population.length;
  return {
    sumFitness,
    avgFitness,
    bestIndividual,
    worstIndividual,
  };
}

function printPopulationSummary(generation, population, statistics) {
  const bestChromosome = statistics.bestIndividual.chromosome.join("");
  const worstChromosome = statistics.worstIndividual.chromosome.join("");
  // eslint-disable-next-line no-console
  console.log(
    `Generation ${generation}: avgFitness = ${statistics.avgFitness},` +
      ` best: ${bestChromosome}, bestFitness:  ${statistics.bestIndividual.fitness}` +
      ` worst: ${worstChromosome}, worstFitness:  ${statistics.worstIndividual.fitness}`
  );
}

/**
 * @param {{ chromosome: (0 | 1)[]; fitness: number }[]} population
 * @param {number} sumFitness
 * @param {{ crossProb: number; mutProb: number }} settings
 * @returns {{ chromosome: (0 | 1)[]; fitness: number }[]} NewPopulation
 */
function reproduce(
  population,
  sumFitness,
  settings = {
    crossProb: 0.95,
    mutProb: 0.001,
  }
) {
  const newPopulation = [];
  for (let i = 0; i < population.length; i += 2) {
    const mate1 = population[selectByRoulette(population, sumFitness)];
    const mate2 = population[selectByRoulette(population, sumFitness)];
    if (Random.flip(settings.crossProb)) {
      const [chromosome1, chromosome2] = crossover(mate1.chromosome, mate2.chromosome);
      newPopulation.push(
        { chromosome: mutate(chromosome1, settings.mutProb) },
        { chromosome: mutate(chromosome2, settings.mutProb) }
      );
    } else {
      newPopulation.push(
        { chromosome: mutate(mate1.chromosome, settings.mutProb) },
        { chromosome: mutate(mate2.chromosome, settings.mutProb) }
      );
    }
  }
  evaluatePopulation(newPopulation);
  return newPopulation;
}

function run() {
  const popSize = 100;
  const chromSize = 30;
  const settings = {
    crossProb: 0.6,
    mutProb: 0.0333,
  };

  let population = generatePopulation(popSize, chromSize);
  let statistics = getStatistics(population);
  printPopulationSummary(0, population, statistics);

  for (let generation = 1; generation <= 500; generation++) {
    const newPopulation = reproduce(population, statistics.sumFitness, settings);
    statistics = getStatistics(newPopulation);
    printPopulationSummary(generation, newPopulation, statistics);
    population = newPopulation;
  }
}

run();