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

IanSans

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);
    }
  }
}

kfrajer

Please format your code. Edit your post (gear on top right side of any of your posts), select your code and hit ctrl+o. Leave an empty line above and below your block of code. Details here: https://forum.processing.org/two/discussion/15473/readme-how-to-format-code-and-text

Kf

IanSans

Apologies for that !

kfrajer

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

IanSans

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!

kfrajer

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

(Copy and paste it in your website) More about this other approach here:

https://forum.processing.org/two/discussion/comment/107907/#Comment_107907
https://forum.processing.org/two/discussion/comment/93128/#Comment_93128

Kf

IanSans

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; }

kfrajer

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

Kf

IanSans

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 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;
    }

    // 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);
        }
      }
    }

kfrajer

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