// Cloned by Extra test on 28 Nov 2023 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 = 10; // 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);
}
}
}