Traveling Sales Person solution via GeneticAlgorithm

ga.js

var fs = require('fs');

//run with
//node ga.js inputfile
//this is a example of badly written code :D, dont use javascript for this kind of problems. python is much better

var args = process.argv.slice(2);

getIndex = function functionName(index) {

    switch (index) {
        case 0:
            return "populationCount"
        case 1:
            return "len"
        case 2:
            return "generations"
        case 3:
            return ["crossover", "prob"]
        case 4:
            return ["mutation", "prob"]
        case 5:
            return "output"

        default:
            return "matrix"
    }
}

var input = fs.readFileSync(args[0], 'utf8').trim().split('\n')
    .reduce((accumulator, currentValue, currentIndex, array) => {
        index = getIndex(currentIndex)

        if (index === "matrix") {
            accumulator[index] = accumulator[index] || []
            accumulator[index].push(currentValue.trim().split(' ')
                .map((item) => +item))
        } else if (index instanceof Array) {
            accumulator[index[0]] = accumulator[index[0]] || {}
            accumulator[index[0]][index[1]] = +currentValue
        } else if (index !== "output") {
            accumulator[index] = +currentValue
        } else {
            accumulator[index] = currentValue

        }

        return accumulator

    }, {})


console.log(input)

function getRandomIntInclusive(min, max) {
    var min = Math.ceil(min);
    var max = Math.floor(max);
    return Math.floor(Math.random() * (max - min + 1)) + min;
}


function exists(array, node) {
    return array.filter((n) => n === node).length > 0
}

diversity = function(index) {

    let pops = genetics.population.map((item) => item.pop)
    let pop = genetics.population[index].pop

    return pops.reduce((accumulator, currentValue, currentIndex, array) => {

        if (currentValue === pop) {
            return accumulator
        }

        let divers = pop.reduce((ac, cv, ci, ar) => {

            let temp = 0

            if (cv === currentValue[ci]) {
                temp = 1

            }

            return ac + temp

        }, 0)

        return accumulator + divers

    }, 0)
}

rank = function(pop) {
    return pop.reduce((accumulator, currentValue, currentIndex, array) => {

        if (currentIndex === 0) {
            return accumulator + input.matrix[array[array.length - 1]][currentValue]
        }



        return accumulator + input.matrix[array[currentIndex - 1]][currentValue]


    }, 0)
}

genetics = {

    population: [],
    generatePopulation: null,
    crossover: null,
    mutation: null,
    generation: 0,
    rank: null

}



genetics.rank = rank

genetics.generatePopulation = () => {


    var len = input.len
    for (var i = 0; i < input.populationCount; i++) {
        var pop = []
        var tries = 0
        while (pop.length < len) {
            let index = getRandomIntInclusive(0, len - 1)
            tries++;
            if (tries === 50) {
                tries = 0
                pop = []
            }
            if (!exists(pop, index) &&
                (pop.length == 0 || input.matrix[pop[pop.length - 1]][index] !== -1)) {
                pop.push(index)
            }
        }

        genetics.population.push({
            pop,
            rank: genetics.rank(pop)
        })
    }

    genetics.population.sort((lhs, rhs) => lhs.rank - rhs.rank)
}

genetics.generatePopulation()

function boundValue(value, max) {
    if (value < 0) {
        value = max - 1
    }
    if (value === max) {
        value = 0
    }
    return value
}

function isThereConflictToSwap(pop, i, j) {
    if (i === j) {
        return true
    }

    var beforeI = pop[boundValue(i - 1, pop.length)]
    var afterI = pop[boundValue(i + 1, pop.length)]

    var beforeJ = pop[boundValue(j - 1, pop.length)]
    var afterJ = pop[boundValue(j + 1, pop.length)]

    return input.matrix[beforeI][pop[j]] === -1 ||
        input.matrix[pop[j]][afterI] === -1 ||
        input.matrix[beforeJ][pop[i]] === -1 ||
        input.matrix[pop[i]][afterJ] === -1

}




genetics.mutation = function() {



    let mutated = genetics.population
        .filter(popItem => {
            var mutationProb = input.mutation.prob
            var random = Math.random()
            return mutationProb > random
        })
        .map((popItem) => {
            var pop = popItem.pop.slice(0)
            var mutationProb = input.mutation.prob
            var len = input.len
            var step = mutationStep

            while (step !== 0) {

                let index = getRandomIntInclusive(0, len - 1)
                let otherIndex = getRandomIntInclusive(0, len - 1)
                if (!isThereConflictToSwap(pop, index, otherIndex)) {

                    let temp = pop[index]
                    pop[index] = pop[otherIndex]
                    pop[otherIndex] = temp
                    step--
                }

                return {
                    pop: pop,
                    rank: genetics.rank(pop)
                }

            }
        })

    mutated = mutated.filter(object => genetics.population.filter(pop2 => JSON.stringify(pop2.pop) === JSON.stringify(object.pop)).length === 0).filter((v, i, a) => a.indexOf(v) === i)


    var newPopulation = genetics.population.sort((lhs, rhs) => lhs.rank - rhs.rank).slice(0, input.populationCount - mutated.length).concat(mutated)

    genetics.population = newPopulation

}



function noConflictToAdd(child, index, value) {
    var nextIndex = boundValue(index + 1, input.len)
    var prevIndex = boundValue(index - 1, input.len)
    if (child[nextIndex] !== undefined) {
        if (input.matrix[value][child[nextIndex]] === -1) {
            return false
        }
    }

    if (child[prevIndex] !== undefined) {
        if (input.matrix[child[prevIndex]][value] === -1) {
            return false
        }
    }
    return true

}

function makeChild(parents) {
    var childs = []
    for (var i = 0; i < parents.length / 2; i += 2) {
        var mother = parents[i]
        var father = parents[i + 1]
        var child = []

        // console.log('make child, ' ,father , mother)

        while (child.filter((index) => index !== undefined).length !== input.len) {
            var startIndex = getRandomIntInclusive(0, input.len - 1)
            var endIndex = getRandomIntInclusive(0, input.len)
            if (startIndex < endIndex) {

                child = []
                for (var j = startIndex; j < endIndex; j++) {
                    child[j] = mother[j]
                }

                for (var j = 0; j < input.len; j++) {
                    if (child[j] === undefined) {
                        if (!exists(child, father[j]) && noConflictToAdd(child, j, father[j])) {
                            child[j] = father[j]
                        }
                    }
                }
                for (var j = 0; j < input.len; j++) {

                    if (child[j] === undefined) {
                        var tryNum = 20
                        while (tryNum > 0) {
                            tryNum--
                            let tempIndex = getRandomIntInclusive(0, input.len - 1)
                            if (!exists(child, tempIndex) && noConflictToAdd(child, j, tempIndex)) {
                                child[j] = tempIndex
                                break;
                            }
                        }

                    }
                }



            }

            // console.log(child)

        }

        childs.push(child)
    }

    return childs

}




geometricDistribution = function(p, rank, min, max) {

    // console.log( rank , min, max)
    if (max - min < (input.populationCount / 2)) {
        return Math.pow(1 - p, rank - min) * p
    }
    let step = (max - min) / (input.populationCount / 2)
    let prank = rank - min + 1
        // console.log(Math.pow(1-p, prank % step ), prank % step , prank , step)
    return Math.pow(1 - p, prank % step) * p

}

crossover = function() {

    var p = input.crossover.prob
    var selected = []



    let minRank = Math.min.apply(Math, genetics.population.map((item) => item.rank))

    let maxRank = Math.max.apply(Math, genetics.population.map((item) => item.rank))

    let minDiv = Math.min.apply(Math, genetics.population.map((item, index) => diversity(index)))

    let maxDiv = Math.max.apply(Math, genetics.population.map((item, index) => diversity(index)))



    let winP = input.crossover.prob
    genetics.population = genetics.population.sort((lhs, rhs) => lhs.rank - rhs.rank)
        // console.log(maxDivers)
    let sortedPopulation = genetics.population.map((item, index) => {
        // console.log( item, "p")
        let probility = rankCoef * geometricDistribution(winP, item.rank, minRank, maxRank) + diversCoef * geometricDistribution(winP, diversity(index), minDiv, maxDiv)

        return {
            pop: item.pop,
            prob: probility,
            diversity: diversity(index),
            rank: item.rank
        }
    })

    // console.log(sortedPopulation)

    thisSelected = []

    while (selected.length < crossoverStep) {
        while (thisSelected.length < 2) {
            var i = getRandomIntInclusive(0, input.len - 1)

            var random = Math.random()
            var item = sortedPopulation[i]

            var notExists = thisSelected.filter((object) => {
                // console.log(item.pop, object.item.pop ,JSON.stringify(object.item.pop)==JSON.stringify(item.pop)  )
                return JSON.stringify(object.item.pop) == JSON.stringify(item.pop)
            }).length === 0
            if (item.prob > random && notExists) {
                thisSelected.push({
                        item,
                        i
                    })
                    // console.log(selected)
            }
        }
        selected.push(thisSelected[0])
        selected.push(thisSelected[1])
        thisSelected = []

    }

    var childs = makeChild(selected.map((item) => item.item.pop))

    // console.log(childs)

    childs = childs.map((pop) => {
            return {
                pop: pop,
                rank: genetics.rank(pop)
            }
        })
        .filter(object => genetics.population.filter(pop2 => JSON.stringify(pop2.pop) === JSON.stringify(object.pop)).length === 0).filter((v, i, a) => a.indexOf(v) === i)
        // console.log('childs' , childs)
    var newPopulation = genetics.population.sort((lhs, rhs) => lhs.rank - rhs.rank).slice(0, input.populationCount - childs.length).concat(childs)
        //
        // console.log('new pop')
        // console.log(newPopulation)
    genetics.population = newPopulation.map((pop) => {
        // console.log(pop)
        return {
            pop: pop.pop,
            rank: genetics.rank(pop.pop)
        }
    })


}

genetics.crossover = crossover

var history = []


mutationStep = input.len / 1.5

crossoverStep = input.populationCount / 3

genetics.generations = 0


let rankCoef = 0.65
let diversCoef = 0.35


bestAtGeneration = {
    gen: -1,
    rank: 9999
}



for (var i = 0; i < input.generations; i++) {



    if (bestAtGeneration.rank > genetics.population[0].rank) {
        bestAtGeneration = {}
        bestAtGeneration.rank = genetics.population[0].rank
        bestAtGeneration.gen = i
        bestAtGeneration.pop = genetics.population[0].pop
        bestAtGeneration.rank = rank(genetics.population[0].pop)
    }

    history.push({
        generation: genetics.generations,
        bestSoFar: bestAtGeneration,
        population: genetics.population,
    })
    genetics.mutation()
    genetics.crossover()


    genetics.generations += 1

}

if (bestAtGeneration.rank > genetics.population[0].rank) {
    bestAtGeneration = {}
    bestAtGeneration.rank = genetics.population[0].rank
    bestAtGeneration.gen = genetics.generations
    bestAtGeneration.pop = genetics.population[0].pop
    bestAtGeneration.rank = rank(genetics.population[0].pop)
}

history.push({
    generation: genetics.generations,
    bestSoFar: bestAtGeneration,
    population: genetics.population
})

console.log(genetics.population)

history = history.map((gen, pep) => {
    return {
        generation: gen.generation,
        population: gen.population.map((item) => {
            return {
                path: item.pop.join(' '),
                rank: item.rank
            }
        }),
        bestSoFar: {
            population: gen.bestSoFar.pop.join(' '),
            rank: gen.bestSoFar.rank,
            generation: gen.bestSoFar.gen
        }
    }

})



buffer = new Buffer(JSON.stringify(history, null, 1));
fs.open(input.output, 'w', (err, fd) => {
    fs.write(fd, buffer, 0, buffer.length, null, function(err) {
        if (err) throw 'error writing file: ' + err;
        fs.close(fd, function() {})
    });
})

// rankLog(genetics.population[0].pop)


console.log(bestAtGeneration)

inputfile

15
10
1000
0.9
0.01
outputfile
0 12 1 14 6 -1 17 -1 13 11
12 0 20 3 1 5 11 9 -1 -1
-1 20 0 17 5 2 19 14 1 -1
14 3 17 0 -1 1 -1 19 12 20
6 -1 5 1 0 9 -1 -1 3 3
-1 5 2 -1 9 0 13 1 6 2
17 11 19 -1 -1 13 0 3 -1 4
7 9 14 15 -1 -1 3 0 -1 11
13 1 -1 12 3 6 -1 -1 0 18
11 -1 -1 20 3 2 4 11 18 0