#### Howdy, Stranger!

We are about to switch to a new forum software. Until then we have removed the registration on this forum.

# How would i amend the TSP GA made by Daniel in order to take in Long and Lat of cities?

edited November 2017

I am currently following the tutorial on the TSP problem in which Daniel uses the genetic approach to solve it. I am currently trying to implement a way in which i can feed in a list of cities with their Longitudes and Latitudes instead of creating a number of vectors with random height and width and then send it to a calculating function that uses the haversine approach. How would i change the algorithm so this could be done? I dont need a visual representation just the final result in console.

SKETCH .JS

``````var cities = [];
var totalCities = 12;

var popSize = 500;
var population = [];
var fitness = [];

var recordDistance = Infinity;
var bestEver;
var currentBest;

var statusP;

function setup() {
createCanvas(800, 800);
var order = [];
for (var i = 0; i < totalCities; i++) {
var v = createVector(random(width), random(height / 2));
cities[i] = v;
order[i] = i;
}

for (var i = 0; i < popSize; i++) {
population[i] = shuffle(order);
}
statusP = createP('').style('font-size', '32pt');
}

function draw() {
background(0);

// GA
calculateFitness();
normalizeFitness();
nextGeneration();

stroke(255);
strokeWeight(4);
noFill();
beginShape();
for (var i = 0; i < bestEver.length; i++) {
var n = bestEver[i];
vertex(cities[n].x, cities[n].y);
ellipse(cities[n].x, cities[n].y, 16, 16);
}
endShape();

translate(0, height / 2);
stroke(255);
strokeWeight(4);
noFill();
beginShape();
for (var i = 0; i < currentBest.length; i++) {
var n = currentBest[i];
vertex(cities[n].x, cities[n].y);
ellipse(cities[n].x, cities[n].y, 16, 16);
}
endShape();

}

// function shuffle(a, num) {
//   for (var i = 0; i < num; i++) {
//     var indexA = floor(random(a.length));
//     var indexB = floor(random(a.length));
//     swap(a, indexA, indexB);
//   }
// }

function swap(a, i, j) {
var temp = a[i];
a[i] = a[j];
a[j] = temp;
}

function calcDistance(points, order) {
var sum = 0;
for (var i = 0; i < order.length - 1; i++) {
var cityAIndex = order[i];
var cityA = points[cityAIndex];
var cityBIndex = order[i + 1];
var cityB = points[cityBIndex];
var d = dist(cityA.x, cityA.y, cityB.x, cityB.y);
sum += d;
}
return sum;
}

//ga.js
function calculateFitness() {
var currentRecord = Infinity;
for (var i = 0; i < population.length; i++) {
var d = calcDistance(cities, population[i]);
if (d < recordDistance) {
recordDistance = d;
bestEver = population[i];
}
if (d < currentRecord) {
currentRecord = d;
currentBest = population[i];
}

fitness[i] = 1 / (pow(d, 8) + 1);
}
}

function normalizeFitness() {
var sum = 0;
for (var i = 0; i < fitness.length; i++) {
sum += fitness[i];
}
for (var i = 0; i < fitness.length; i++) {
fitness[i] = fitness[i] / sum;;
}
}

function nextGeneration() {
var newPopulation = [];
for (var i = 0; i < population.length; i++) {
var orderA = pickOne(population, fitness);
var orderB = pickOne(population, fitness);
var order = crossOver(orderA, orderB);
mutate(order, 0.01);
newPopulation[i] = order;
}
population = newPopulation;

}

function pickOne(list, prob) {
var index = 0;
var r = random(1);

while (r > 0) {
r = r - prob[index];
index++;
}
index--;
return list[index].slice();
}

function crossOver(orderA, orderB) {
var start = floor(random(orderA.length));
var end = floor(random(start + 1, orderA.length));
var neworder = orderA.slice(start, end);
// var left = totalCities - neworder.length;
for (var i = 0; i < orderB.length; i++) {
var city = orderB[i];
if (!neworder.includes(city)) {
neworder.push(city);
}
}
return neworder;
}

function mutate(order, mutationRate) {
for (var i = 0; i < totalCities; i++) {
if (random(1) < mutationRate) {
var indexA = floor(random(order.length));
var indexB = (indexA + 1) % totalCities;
swap(order, indexA, indexB);
}
}
}
``````
Tagged:

Kf

• Apologies for that !

• i can feed in a list of cities with their Longitudes and Latitudes instead of creating a number of vectors with random height and width

This would mean that in your setup(), you need to re-defined v from `var v = createVector(random(width), random(height / 2));` to you city data. How would you feed this data? Would you read it from an external file, from another array or directly from the user?

Kf

• Hi, I would be getting it from another array for now, something along the lines of this : `var allPoints = [22.234,-345.343,34.5456,-35.5446,12.46,-13.343];` Thank you!

• If you load your array yourself, then it should be trivial, something along these lines (I am not modifying all your code, just what is within setup):

``````var cities = [];
//var totalCities = 12;   //OBSOLETE

var popSize = 500;
var population = [];
var fitness = [];

var recordDistance = Infinity;
var bestEver;
var currentBest;

var statusP;
function setup() {
createCanvas(800, 800);
var allPoints = [22.234,-345.343,34.5456,-35.5446,12.46,-13.343];
var order = [];

//NEXT; I am assuming you have a non-zero array of points corresponding to lat-lon pairs.

for (var i = 0; i < allPoints.length/2; i++) {
var v = createVector(allPoints[i],allPoints[i+1]);
cities[i] = v;
order[i] = i;
}

for (var i = 0; i < popSize; i++) {
population[i] = shuffle(order);
}
statusP = createP('').style('font-size', '32pt');
}
``````

For another approach, use an API to request the info of your city. An example where you can replace the terms in the request is:

`http://maps.google.com/maps/api/geocode/json?address=\$Aalsmeer&sensor=false&region=Netherlands`

Kf

• Hi, Thank you for the code however i am having an issue, i am getting the error : Uncaught TypeError: Cannot read property 'x' of undefined

I am getting this on on this line : `var d = getDistanceFromLatLonInKm(cityA.x, cityA.y ,cityB.x, cityB.y);` I have added in the following code :

```function deg2rad(deg2rad) { return deg2rad * (Math.PI/180); } function getDistanceFromLatLonInKm(lat1,lon1,lat2,lon2) { var R = 6371; // Radius of the earth in km var dLat = deg2rad(lat2-lat1); // deg2rad below var dLon = deg2rad(lon2-lon1); var a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.sin(dLon/2) * Math.sin(dLon/2) ; var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); var d = R * c; // Distance in km return d; }```

• It is better if you post an MCVE. Not enough information there to figure out where or why you are getting an error.

Kf

• Thank you for taking the time in helping me kfrajer, code is below :

SKETCH.JS

``````    var cities = [];
//var totalCities = 3;

var popSize = 100;
var population = [];
var fitness = [];

var recordDistance = Infinity;
var bestEver;
var currentBest;

var statusP;
var allPoints = [22.234,-345.343,34.5456,-35.5446,12.46,-13.343,12.234,-45.343];

function setup() {
createCanvas(800, 800);

var order = [];
for (var i = 0; i < allPoints.length/2; i++) {
var v = createVector(allPoints[i],allPoints[i+1]);
cities[i] = v;
order[i] = i;
}

for (var i = 0; i < popSize; i++) {
population[i] = shuffle(order);
}
statusP = createP('').style('font-size', '32pt');
}

function draw() {
background(0);

// GA
calculateFitness();
normalizeFitness();
nextGeneration();

stroke(255);
strokeWeight(4);
noFill();
beginShape();
for (var i = 0; i < bestEver.length; i++) {
var n = bestEver[i];
vertex(cities[n].x, cities[n].y);
ellipse(cities[n].x, cities[n].y, 16, 16);
}
endShape();

translate(0, height / 2);
stroke(255);
strokeWeight(4);
noFill();
beginShape();
for (var i = 0; i < currentBest.length; i++) {
var n = currentBest[i];
vertex(cities[n].x, cities[n].y);
ellipse(cities[n].x, cities[n].y, 16, 16);
}
endShape();

}

function swap(a, i, j) {
var temp = a[i];
a[i] = a[j];
a[j] = temp;
}

function calcDistance(points, order) {
var sum = 0;
for (var i = 0; i < order.length - 1; i++) {
var cityAIndex = order[i];
var cityBIndex = order[i + 1];

var cityA = points[cityAIndex];
var cityB = points[cityBIndex];
//console.log(cityA.x);
//console.log(cityA.y);
//console.log(" b "+cityB.x);
var d = getDistanceFromLatLonInKm(cityA.x, cityA.y ,cityB.x, cityB.y);
sum += d;
}
return sum;
}

// Receives two points : Long Lat | Long Lat
{
}
function getDistanceFromLatLonInKm(lat1,lon1,lat2,lon2) {
var R = 6371; // Radius of the earth in km
var a =
Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.sin(dLon/2) * Math.sin(dLon/2)
;
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var d = R * c; // Distance in km
return d;
}

// GA.JS

function calculateFitness() {
var currentRecord = Infinity;
for (var i = 0; i < population.length; i++) {
var d = calcDistance(cities, population[i]);
if (d < recordDistance) {
recordDistance = d;
bestEver = population[i];
}
if (d < currentRecord) {
currentRecord = d;
currentBest = population[i];
}

fitness[i] = 1 / (pow(d, 8) + 1);
}
}

function normalizeFitness() {
var sum = 0;
for (var i = 0; i < fitness.length; i++) {
sum += fitness[i];
}
for (var i = 0; i < fitness.length; i++) {
fitness[i] = fitness[i] / sum;;
}
}

function nextGeneration() {
var newPopulation = [];
for (var i = 0; i < population.length; i++) {
var orderA = pickOne(population, fitness);
var orderB = pickOne(population, fitness);
var order = crossOver(orderA, orderB);
mutate(order, 0.01);
newPopulation[i] = order;
}
population = newPopulation;

}

function pickOne(list, prob) {
var index = 0;
var r = random(1);

while (r > 0) {
r = r - prob[index];
index++;
}
index--;
return list[index].slice();
}

function crossOver(orderA, orderB) {
var start = floor(random(orderA.length));
var end = floor(random(start + 1, orderA.length));
var neworder = orderA.slice(start, end);
// var left = totalCities - neworder.length;
for (var i = 0; i < orderB.length; i++) {
var city = orderB[i];
if (!neworder.includes(city)) {
neworder.push(city);
}
}
return neworder;
}

function mutate(order, mutationRate) {
for (var i = 0; i < allPoints.length/2; i++) {
if (random(1) < mutationRate) {
var indexA = floor(random(order.length));
var indexB = (indexA + 1) % allPoints;
swap(order, indexA, indexB);
}
}
}
``````
• Not familiar with this sort of code but simple console.log statements right at line 77: `console.log(order);` shows that this array has at least one undefined element after it has gone through some iterations. You will need to check your algorithm to see why your order array is being loaded with undefined values. You will need to check your nextGeneration() function as I think that is where your bug is.

Kf