Source: methods/genetic/Genetic.js

import Result from '../../_common/Result';
import BufferedReply from "../../_common/BufferedReply";
import { RouletteSelection, SelectionEnum, TournamentSelection } from './Selection'
import {
    CycleCrossover, CrossoverEnum,
    OnePointCrossover, OrderCrossover, PartiallyMatchedCrossover, TwoPointCrossover,
    UniformCrossover
} from './Crossover'

/**
 * Class for solving problems using genetic algorithm
 */
export class GeneticSolver {
    constructor(workerInterface) {
        this._workerInterface = workerInterface;
        // buffers messages to reduce communication overhead while sending computation progress every cycle
        this._bufferedReply = new BufferedReply(this._workerInterface, 'progressBuffered', 75);
    }

    /**
     * Main function method, solves the problem using genetic algorithm
     * @param  {Problem} problem instance of problem
     * @param  {object} params parameters for genetic algorithm
     * @return {Result} final configuration, its fitness and number of iterations
     */
    solve(problem, params) {
        //set params
        this.problem = problem;

        const populationSize = +params.populationSize;
        const noGenerations = +params.noGenerations;
        switch (params.selectionType) {
            case SelectionEnum.ROULETTE_RANK:
                this.selection = new RouletteSelection(SelectionEnum.ROULETTE_RANK, +params.scaleMin, +params.scaleMax);
                break;
            case SelectionEnum.ROULETTE_LINEAR:
                this.selection = new RouletteSelection(SelectionEnum.ROULETTE_LINEAR, +params.scaleMin, +params.scaleMax);
                break;
            case SelectionEnum.TOURNAMENT:
                this.selection = new TournamentSelection(+params.tournamentSize);
                break;
            default:
                throw new Error("Selection type " + params.selectionType + " is not supported.");
        }
        this.crossoverProb = +params.crossoverProb;
        switch (params.crossoverType) {
            case CrossoverEnum.ONE_POINT:
                this.crossover = new OnePointCrossover();
                break;
            case CrossoverEnum.TWO_POINT:
                this.crossover = new TwoPointCrossover();
                break;
            case CrossoverEnum.UNIFORM:
                this.crossover = new UniformCrossover();
                break;
            case CrossoverEnum.ORDER:
                this.crossover = new OrderCrossover();
                break;
            case CrossoverEnum.PMX:
                this.crossover = new PartiallyMatchedCrossover();
                break;
            case CrossoverEnum.CYCLE:
                this.crossover = new CycleCrossover();
                break;
            default:
                throw new Error("Crossover type " + params.selectionType + " is not supported.");

        }
        this.mutationRate = +params.mutationRate;
        const elitism = +params.elitism;


        this.result = [];
        this.bestFitness = Number.NEGATIVE_INFINITY;
        this.bestCost = 0;
        this.counter = 0;

        this._workerInterface.reply('init', { numberOfIterations: noGenerations/*, maxFitness: this.problemInput.params.numberOfClauses*/ });

        //init generation
        var generation = this._initGeneration(populationSize);

        //evolve solution
        for (var g = 0; g < noGenerations; g++) {
            var potentialParents = this.selection.selectIndividuals(generation, populationSize-elitism);
            generation = this._doNewGeneration(potentialParents).concat(generation.slice(populationSize-elitism, populationSize));
            this._evaluateGeneration(generation);
            this.counter++;
        }

        // make sure all messages in buffer are sent (if there are some in buffer, it will send them)
        this._bufferedReply.flush();

        return new Result(problem.getResult(this.result), this.bestCost, this.counter);
    }

    /**
     * Creates initial population.
     * @param populationSize size of population to create
     * @returns {Array} population of individuals
     * @private
     */
    _initGeneration(populationSize) {
        var generation = [];
        for (var i = 0; i < populationSize; i++) {
            generation.push(this.problem.createNewIndividual());
        }
        this._evaluateGeneration(generation);
        return generation;
    }

    /**
     * Evaluates generation and sends information to graph.
     * @param {Array} generation to evaluate
     * @private
     */
    _evaluateGeneration(generation) {
        var average = 0;
        for (var i = 0; i < generation.length; i++) {
            this.problem.evaluateIndividual(generation[i]);
            average += this.problem.transformMaximizationToRealCost(generation[i].getFitness());
        }
        average = average/generation.length;
        generation.sort(function(a, b){return a.getFitness() - b.getFitness()});

        var bestCost = this.problem.transformMaximizationToRealCost(generation[generation.length-1].getFitness());

        this._bufferedReply.addMessageWithAutoFlush({
            best: bestCost,
            average: average,
            mean: this.problem.transformMaximizationToRealCost(generation[Math.floor(generation.length/2)].getFitness()),
            worst: this.problem.transformMaximizationToRealCost(generation[0].getFitness()),
        });
        //update best solution
        if (this.bestFitness < generation[generation.length-1].getFitness()) {
            this.bestFitness = generation[generation.length-1].getFitness();
            this.bestCost = bestCost;
            this.result = generation[generation.length-1];
        }
    }

    /**
     * Creates new generation from potential parents.
     * @param {Array} potentialParents
     * @returns {Array} new generation of mutated offspring
     * @private
     */
    _doNewGeneration(potentialParents) {
        var newGeneration = [];
        var mate = null;
        for (var i = 0; i < potentialParents.length; i++) {
            if (Math.random() < this.crossoverProb) {
                if (mate === null) {
                    mate = potentialParents[i];
                } else {
                    //do crossover
                    newGeneration.push(... this.crossover.crossover(mate, potentialParents[i]));
                    mate = null;
                }
            } else {
                //dont go in crossover
                newGeneration.push(potentialParents[i].copy());
            }
        }
        if (mate !== null) {
            //add mate if it havent found another mate
            newGeneration.push(mate.copy())
        }
        //mutate all new individuals
        const mutationRate = this.mutationRate;
        newGeneration.forEach(function(individual){
            individual.mutate(mutationRate);
        });
        return newGeneration;
    }
}