Source: methods/genetic/Crossover.js

import {getRandomBoolean, getRandomInt} from "./Random";
import { BinaryIndividual, PermutationIndividual } from './Individual'

export const CrossoverEnum = {
    UNIFORM: "Uniform",
    ONE_POINT: "One-point",
    TWO_POINT: "Two-point",
    ORDER: "Order",
    PMX: "Partially matched",
    CYCLE: "Cycle",
}

//binary crossovers

/**
 * Uniform crossover
 */
export class UniformCrossover {
    /**
     * Performs uniform crossover.
     * @param {BinaryIndividual} parent1 first parent
     * @param {BinaryIndividual} parent2 second parent
     * @returns {"[BinaryIndividual, BinaryIndividual]"} two offspring
     */
    crossover(parent1, parent2) {
        var size = parent1.getSize();
        var offSeq1 = [];
        var offSeq2 = [];
        const parSeq1 = parent1.getBitArray();
        const parSeq2 = parent2.getBitArray();
        for (var i = 0; i < size; i++) {
            if (getRandomBoolean()) {
                offSeq1.push(parSeq1[i]);
                offSeq2.push(parSeq2[i]);
            } else {
                offSeq1.push(parSeq2[i]);
                offSeq2.push(parSeq1[i]);
            }
        }
        return [new BinaryIndividual(offSeq1), new BinaryIndividual(offSeq2)];
    }
}

/**
 * Two point crossover
 */
export class TwoPointCrossover {
    /**
     * Performs two-point crossover.
     * @param {BinaryIndividual} parent1 first parent
     * @param {BinaryIndividual} parent2 second parent
     * @returns {"[BinaryIndividual, BinaryIndividual]"} two offspring
     */
    crossover(parent1, parent2) {
        var size = parent1.getSize();
        var first = getRandomInt(0, size+1);
        var second = getRandomInt(0, size+1);
        if (first > second) {
            var temp = first;
            first = second;
            second = temp;
        }
        var offSeq1 = [];
        var offSeq2 = [];
        const parSeq1 = parent1.getBitArray();
        const parSeq2 = parent2.getBitArray();

        for (var i = 0; i < size; i++) {
            if (i < first || i >= second) {
                offSeq1.push(parSeq1[i]);
                offSeq2.push(parSeq2[i]);
            } else {
                offSeq1.push(parSeq2[i]);
                offSeq2.push(parSeq1[i]);
            }
        }
        return [new BinaryIndividual(offSeq1), new BinaryIndividual(offSeq2)];
    }
}

/**
 * One point crossover
 */
export class OnePointCrossover {
    /**
     * Performs one-point crossover.
     * @param {BinaryIndividual} parent1 first parent
     * @param {BinaryIndividual} parent2 second parent
     * @returns {"[BinaryIndividual, BinaryIndividual]"} two offspring
     */
    crossover(parent1, parent2) {
        var size = parent1.getSize();
        var point = getRandomInt(0, size+1);
        var offSeq1 = [];
        var offSeq2 = [];
        const parSeq1 = parent1.getBitArray();
        const parSeq2 = parent2.getBitArray();

        for (var i = 0; i < size; i++) {
            if (i < point) {
                offSeq1.push(parSeq1[i]);
                offSeq2.push(parSeq2[i]);
            } else {
                offSeq1.push(parSeq2[i]);
                offSeq2.push(parSeq1[i]);
            }
        }
        return [new BinaryIndividual(offSeq1), new BinaryIndividual(offSeq2)];
    }
}

//permutation crossovers

/**
 * Order crossover
 */
export class OrderCrossover {
    /**
     * Performs order crossover.
     * @param {PermutationIndividual} parent1 first parent
     * @param {PermutationIndividual} parent2 second parent
     * @returns {"[PermutationIndividual, PermutationIndividual]"} two offspring
     */
    crossover(parent1, parent2) {
        var size = parent1.getSize();
        var point = getRandomInt(0, size+1);

        var offSeq1 = [];
        var offSeq2 = [];
        const parSeq1 = parent1.getGenotype();
        const parSeq2 = parent2.getGenotype();
        // console.log("par", parSeq1);
        // console.log("par", parSeq2);
        // console.log("point", point);

        var off1Used = new Array(size).fill(false);
        var off2Used = new Array(size).fill(false);
        for (var i = 0; i < point; i++) {
            //copy start
            off1Used[parSeq1[i]] = true;
            offSeq1.push(parSeq1[i]);
            off2Used[parSeq2[i]] = true;
            offSeq2.push(parSeq2[i]);
        }
        //fill the rest
        var i = 0;
        while (offSeq1.length < size) {
            if (!off1Used[parSeq2[i]]) {
                off1Used[parSeq2[i]] = true;
                offSeq1.push(parSeq2[i]);
            }
            i++;
        }
        var i = 0;
        while (offSeq2.length < size) {
            if (!off2Used[parSeq1[i]]) {
                off2Used[parSeq1[i]] = true;
                offSeq2.push(parSeq1[i]);
            }
            i++;
        }
        // console.log("off", offSeq1);
        // console.log("off", offSeq2);
        return [new PermutationIndividual(offSeq1), new PermutationIndividual(offSeq2)];
    }
}

//Partially matched crossover

/**
 * Partially Matched crossover
 */
export class PartiallyMatchedCrossover {
    /**
     * Performs partially matched crossover.
     * @param {PermutationIndividual} parent1 first parent
     * @param {PermutationIndividual} parent2 second parent
     * @returns {"[PermutationIndividual, PermutationIndividual]"} two offspring
     */
    crossover(parent1, parent2) {
        var size = parent1.getSize();
        var first = getRandomInt(0, size+1);
        var second = getRandomInt(0, size+1);
        if (first > second) {
            var temp = first;
            first = second;
            second = temp;
        }
        var offSeq1 = [];
        var offSeq2 = [];
        const parSeq1 = parent1.getGenotype();
        const parSeq2 = parent2.getGenotype();
        // console.log("par", parSeq1);
        // console.log("par", parSeq2);
        // console.log("point", first, second);

        //create mapping
        var permMap = new Map();
        for (var i = first; i < second; i++) {
            //skip if key is already there
            if (!permMap.has(parSeq1[i]) && !permMap.has(parSeq2[i])) {
                permMap.set(parSeq1[i], parSeq2[i]);
                permMap.set(parSeq2[i], parSeq1[i]);
            }
        }
        //create offspring
        for (var i = 0; i < size; i++) {
            if (permMap.has(parSeq1[i])) {
                offSeq1.push(permMap.get(parSeq1[i]));
            } else {
                offSeq1.push(parSeq1[i]);
            }
            if (permMap.has(parSeq2[i])) {
                offSeq2.push(permMap.get(parSeq2[i]));
            } else {
                offSeq2.push(parSeq2[i]);
            }
        }
        // console.log("off", offSeq1);
        // console.log("off", offSeq2);
        return [new PermutationIndividual(offSeq1), new PermutationIndividual(offSeq2)];
    }
}


/**
 * Cycle crossover
 */
export class CycleCrossover {
    /**
     * Performs cycle crossover.
     * @param {PermutationIndividual} parent1 first parent
     * @param {PermutationIndividual} parent2 second parent
     * @returns {"[PermutationIndividual, PermutationIndividual]"} two offspring
     */
    crossover(parent1, parent2) {
        var size = parent1.getSize();
        var point = getRandomInt(0, size);

        var offSeq1 = [];
        var offSeq2 = [];
        const parSeq1 = parent1.getGenotype();
        const parSeq2 = parent2.getGenotype();

        // console.log("par", parSeq1);
        // console.log("par", parSeq2);
        // console.log("point", point);

        var inCycle = new Array(size).fill(false);
        //create cycle
        while (!inCycle[point]) {
            inCycle[point] = true;
            var i = 0;
            for (; i < size; i++) {
                if (parSeq1[i] === parSeq2[point]) {
                    break;
                }
            }
            point = i;
        }

        for (var i = 0; i < size; i++) {
            //copy start
            if (inCycle[i]) {
                offSeq1.push(parSeq1[i]);
                offSeq2.push(parSeq2[i]);
            } else {
                offSeq1.push(parSeq2[i]);
                offSeq2.push(parSeq1[i]);
            }
        }
        // console.log("off", offSeq1);
        // console.log("off", offSeq2);
        return [new PermutationIndividual(offSeq1), new PermutationIndividual(offSeq2)];
    }
}