// Cloned by Michael Ryan on 24 Nov 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 randomRoute = [];
var totalCities = AB.randomIntAtoB ( 10, 18 );
// This is wrong, should be factorial(totalCities)
// Causes a bug when fixed
var possibleRoutes = factorial(totalCities - 1);
// Using my own one to avoid breaking existing code
var totalRoutes = factorial(totalCities);
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 bestRandomDistance = Infinity;
var bestExhaustiveDistance = Infinity;
var randomRoutesCounted = 0;
var currentRandomRouteDistance = Number.MAX_VALUE;
var currentExhaustiveRouteDistance = Number.MAX_VALUE;
var currentPermuteIndex = 0;
var currentDistance;
var tempDistance;
var bestEver;
var currentBest;
var bestExhaustive;
var exhaustiveRoute;
var statusP;
var cityOrder = [];
var height;
var width;
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) );
}
// Code to Permute An Array
// https://stackoverflow.com/a/34238979/985012
function array_nth_permutation(a, n) {
var b = a.slice(); // copy of the set
var len = a.length; // length of the set
var res; // return value, undefined
var i, f;
// compute f = factorial(len)
for (f = i = 1; i <= len; i++)
f *= i;
// if the permutation number is within range
if (n >= 0 && n < f) {
// start with the empty set, loop for len elements
for (res = []; len > 0; len--) {
// determine the next element:
// there are f/len subsets for each possible element,
f /= len;
// a simple division gives the leading element index
i = Math.floor(n / f);
// alternately: i = (n - n % f) / f;
res.push(b.splice(i, 1)[0]);
// reduce n for the remaining subset:
// compute the remainder of the above division
n %= f;
// extract the i-th element from b and push it at the end of res
}
}
// return the permutated set or undefined if n is out of range
return res;
}
// set fixed width run header
AB.headerWidth ( 1600 );
function setup()
{
backImage = loadImage ( backImageFile );
height = window.innerHeight;
width = window.innerWidth;
createCanvas ( width, height ); // think other code assumes square
for (var i = 0; i < totalCities; i++) {
var v = createVector(random(width / 3), random(height / 3));
cities[i] = v;
cityOrder[i] = i;
}
for (var i = 0; i < popSize; i++) {
population[i] = shuffle(cityOrder);
}
statusP = createP('').style('font-size', '4pt'); // 32pt
}
function drawRoute(color, route)
{
stroke(color);
strokeWeight(4);
noFill();
beginShape();
for (var i = 0; i < route.length; i++)
{
var n = route[i];
vertex(cities[n].x, cities[n].y);
ellipse(cities[n].x, cities[n].y, 8, 8);
}
endShape();
}
function draw()
{
background('lightsalmon');
// background ( backImage );
// Get random route
randomRoute = [];
for (var i = 0; i < totalCities; i++)
{
randomRoute[i] = i;
}
randomRoute = shuffle(randomRoute);
// GA
calculateFitness();
normalizeFitness();
nextGeneration();
// Exhaustive
//Draw Ex
//BEST GA SEEN
drawRoute('black', bestEver);
// Current Best GA
translate(width / 2, 0);
drawRoute('darkred', currentBest);
// Best Random Seen
translate(0 - width / 2 , height / 3);
drawRoute('blue', bestRandom);
//translate(width / 2, height / 2 );
// Current Random
translate(width / 2, 0);
drawRoute('green', randomRoute);
// Best Exhaustive
translate(0 - width / 2, height / 3);
drawRoute('yellow', bestExhaustive);
// Current Exhaustive
translate(width / 2, 0);
drawRoute('white', exhaustiveRoute);
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 / Random Routes Tried: " + gen +
"<br><br> BLACK: Best ever GA route. Length: " + recordDistance.toFixed(2) +
"<br> RED: Best Current GA Route. Length: " + currentDistance.toFixed(2) +
"<br> BLUE: Best Random Route. Length: " + bestRandomDistance.toFixed(2) +
"<br> Green: Current Random Route. Length: " + currentRandomRouteDistance.toFixed(2) +
"<br> Yellow: Best Exhaustive Route. Length: " + bestExhaustiveDistance.toFixed(2) +
"<br> White: Current Exhaustive Route. Length: " + currentExhaustiveRouteDistance.toFixed(2) +
"<br><br>Exhaustive Routes:<br>" + currentPermuteIndex + "/" + totalRoutes);
}
// 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);
}
// Random
currentRandomRouteDistance = calcDistance(cities, randomRoute);
if (currentRandomRouteDistance < bestRandomDistance)
{
bestRandom = randomRoute;
bestRandomDistance = currentRandomRouteDistance;
}
// Exhaustive
if (currentPermuteIndex < totalRoutes)
{
exhaustiveRoute = array_nth_permutation(cityOrder, currentPermuteIndex);
currentPermuteIndex++;
currentExhaustiveRouteDistance = calcDistance(cities, exhaustiveRoute);
if (currentExhaustiveRouteDistance < bestExhaustiveDistance)
{
bestExhaustive = exhaustiveRoute;
bestExhaustiveDistance = currentExhaustiveRouteDistance;
}
}
}
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);
}
}
}