javascriptarraysgenetic-algorithmcrossover

Trying to "crossover" two arrays using subset of first array and maintaining order of second array where possible


I am trying to generate a new child array from two parent arrays (crossover) using the following process.

parentArr1 = [0,1,2,3,4,5,6,7,8,9]
parentArr2 = [9,8,7,6,5,4,3,2,1,0]
parent1Subset = [2,3,4,5]
childArr   = [9,8,2,3,4,5,7,6,1,0]

The crossover rules I'm defining are:

  1. Extract a contiguous subset from parentArr1 and insert it into a new childArr at the same position it was extracted from.
  2. Fill the remaining positions in the childArr with elements from parentArr2 and maintain the order of elements in parentArr2 around the subset.
  3. There should be no duplicates.

Here's another example:

parentArr1 = [0,1,2,3,4,5,6,7,8,9]
parentArr2 = [9,8,7,6,5,4,3,2,1,0]
parent1Subset = [7,8,9]
childArr   = [6,5,4,3,2,1,0,7,8,9]

I've had numerous failed attempts to do this. Here's the attempt that came the closest.

const parentArr1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const parentArr2 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
let parent1Subset = [2, 3, 4, 5];
let childArr = crossOver(parentArr1, parentArr2, parent1Subset);
// Expected ouput: 9, 8, 2, 3, 4, 5, 7, 6, 1, 0

function crossOver(pArr1, pArr2, pArr1Subset) {
    let _childArr = pArr1Subset.slice(); // suggestion from @r3wt
    for (let i = 0; i < pArr1.length; i++) {
        for (let j = 0; j < (pArr1.length - _childArr.length); j++) {
            if (!_childArr.includes(pArr2[i])) {
                _childArr.splice(i, 0, pArr2[i]);
            }
        }
    }
    return _childArr;
}
console.log("childArr: " + childArr);
// childArr: 9, 8, 7, 6, 2, 3, 4, 5, 1, 0

Solution

  • You could use another indexer for array 2 and check if the actual value is in the crossover array.

    function crossover(p1, p2, sub) {
        var j = 0;
        return p1.map(i => {
            if (sub.includes(i)) {
                return i;
            }
            while (sub.includes(p2[j])) ++j;
            return p2[j++];
        });
    }
    
    console.log(crossover([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [2, 3, 4, 5]).join(' '));
    console.log(crossover([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [7, 8, 9]).join(' '));