Code viewer [Ancient Brain]

Code viewer for World: GA (TSP) (clone by test2)

// Cloned by test2 on 17 Jul 2019 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, 40 ); 
var possibleRoutes = factorial(totalCities-1);

var popSize = 500;

var backImageFile = "/uploads/codingtrain/map.ireland.800.jpg";
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;


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 
  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', '16pt');     // 32pt 
}


function draw() 
{
  // background('lightsalmon');
   background ( backImage );
  
  // 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, 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);
    }
  }
}