Code viewer for World: Travelling salesman (exhau...

// Cloned by anish kumar on 19 Dec 2020 from World "Travelling salesman (random search)" by anish kumar 
// Please leave this clone trail here.
 


// Cloned by anish kumar on 19 Dec 2020 from World "GA (TSP)" by "Coding Train" project 
// Please leave this clone trail here.
 

// simple port of 
// GA for Traveling Salesman Problem
// https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_035.4_TSP_GA/P5
// by Daniel Shiffman 


// Daniel Shiffman
// The Coding Train
// Traveling Salesperson with Genetic Algorithm

// https://thecodingtrain.com/CodingChallenges/035.4-tsp.html
// https://youtu.be/M3KTWnTrU_c
// https://thecodingtrain.com/CodingChallenges/035.5-tsp.html
// https://youtu.be/hnxn6DtLYcY

// https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9



 

var totalCities =  AB.randomIntAtoB ( 5, 10 );
//var totalCities =  10;
var possibleRoutes = factorial(totalCities-1);

var popSize = 500;

var backImageFile = "/uploads/anish85/world.map.png";
var backImage;
// 1606 map of Ireland 
// https://digital.ucd.ie/view/ucdlib:22694 


var gen = 1;
var routesLookedAt = 0;

var cities = [];
var population = [];
var fitness = [];

var recordDistance = Infinity;
var currentDistance;
var tempDistance;

var bestEver;
var currentBest;

var statusP;
var order = [];
var count = 0;

var totalPermutations;

function factorial (x)     
// return x factorial
// assume only give it an integer 1,2,...
{
  if (x == 1)   return ( 1 );
  else          return ( x * factorial(x-1) );
}



    // set fixed width run header 
    AB.headerWidth ( 600 );
    
    

function setup() 
{
  backImage = loadImage ( backImageFile );

  createCanvas (  800, 800   );     // think other code assumes square 
  for (var i = 0; i < totalCities; i++) {
    var v = createVector(random(width), random(height / 2));
    cities[i] = v;
    order[i] = i;
  }

  var d = calcDistance(cities, order);
  recordDistance = d;
  bestEver = order.slice();
  
  totalPermutations = factorial(totalCities);
  AB.msg("<br>Number of cities: "+totalCities, 4);
  AB.msg("<br>Total permutations: "+totalPermutations, 2);
}


function draw() 
{
   //background('lightsalmon');
  background ( backImage );
  
   // Exhaustive search
 fill(0);
  noStroke();
  textSize(12);
  AB.msg("<br>Shortest route: " + floor(recordDistance));

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

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

  var d = calcDistance(cities, order);
  if (d < recordDistance) {
    recordDistance = d;
    bestEver = order.slice();
  }

  textSize(32);
  // var s = '';
  // for (var i = 0; i < order.length; i++) {
  //   s += order[i];
  // }
  fill(255);
  var percent = 100 * (count / totalPermutations);
  AB.msg("<br>"+nf(percent, 0, 2) + '% completed', 3);

  nextOrder();  
}


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

// This is my lexical order algorithm

function nextOrder() {
  count++;

  // STEP 1 of the algorithm
  // https://www.quora.com/How-would-you-explain-an-algorithm-that-generates-permutations-using-lexicographic-ordering
  var largestI = -1;
  for (var i = 0; i < order.length - 1; i++) {
    if (order[i] < order[i + 1]) {
      largestI = i;
    }
  }
  if (largestI == -1) {
    noLoop();
    console.log('finished');
  }

  // STEP 2
  var largestJ = -1;
  for (var j = 0; j < order.length; j++) {
    if (order[largestI] < order[j]) {
      largestJ = j;
    }
  }

  // STEP 3
  swap(order, largestI, largestJ);

  // STEP 4: reverse from largestI + 1 to the end
  var endArray = order.splice(largestI + 1);
  endArray.reverse();
  order = order.concat(endArray);
}



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

  stroke('black');
  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, 8, 8);      // 16
  }
  endShape();

  translate(0, height / 2);
  
  stroke('darkred');
  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, 8, 8);    
  }
  endShape();
  
  var frac =  routesLookedAt / possibleRoutes ;
  
  AB.msg ( "Number of cities: " + (totalCities) +
    "<br> Number of possible routes: " + (totalCities-1) + "! = " + possibleRoutes.toFixed(0) );
    
  // for small problems we actually can solve them exhaustively
  if ( routesLookedAt >= possibleRoutes )
        AB.msg ( "<br> Number of routes looked at: <b> All possible routes </b> " +
            "<br> Routes looked at as fraction of possible routes: <b> 1 </b> ", 2 );
  else
        AB.msg ( "<br> Number of routes looked at: " + routesLookedAt +
            "<br> Routes looked at as fraction of possible routes: " + frac.toFixed(20), 2 );
  
  AB.msg ( "<p> Generation: " + gen + 
    "<br> Top: Best ever route. Length: " + recordDistance.toFixed(2) +
    "<br> Bottom: Best route in this generation. Length: " + currentDistance.toFixed(2) + 
    "<br> Not shown: Testing new route. Length: " + tempDistance.toFixed(2), 3  );
    
}*/




// 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) {
  var sum = 0;
  for (var i = 0; i < points.length - 1; i++) {
    var d = dist(points[i].x, points[i].y, points[i + 1].x, points[i + 1].y);
    sum += d;
  }
  return sum;
}
/*
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;
}
*/



// Daniel Shiffman
// The Coding Train
// Traveling Salesperson with Genetic Algorithm

// https://thecodingtrain.com/CodingChallenges/035.4-tsp.html
// https://youtu.be/M3KTWnTrU_c
// https://thecodingtrain.com/CodingChallenges/035.5-tsp.html
// https://youtu.be/hnxn6DtLYcY

// https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9

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

    // This fitness function has been edited from the original video
    // to improve performance, as discussed in The Nature of Code 9.6 video,
    // available here: https://www.youtube.com/watch?v=HzaLIO9dLbA
    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;
  gen++;
}


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