// Cloned by Jack O'Brien on 22 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, 8 );
var possibleRoutes = factorial(totalCities);
var totalPaths;
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;
var pathIndex = 1;
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;
}
totalPaths = combo(order);
// for (var i = 0; i < popSize; i++) {
// population[i] = shuffle(order);
// }
currentBest = totalPaths[0];
bestEver = totalPaths[0];
recordDistance = calcDistance(cities, totalPaths[0])
currentRecord = calcDistance(cities, totalPaths[0])
statusP = createP('').style('font-size', '16pt'); // 32pt
}
function draw()
{
background('lightsalmon');
// background ( backImage );
// GA
// calculateFitness();
// normalizeFitness();
// nextGeneration();
// bestEver = population[i];
if(pathIndex < totalPaths.length)
exhaustiveSearch();
else
routesLookedAt++;
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) + "! = " + possibleRoutes.toFixed(0), 2);
// 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> ", 3 );
else
AB.msg ( "<br> Number of routes looked at: " + routesLookedAt +
"<br> Routes looked at as fraction of possible routes: " + frac.toFixed(20), 3 );
AB.msg (
//
"<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 exhaustiveSearch(){
currentBest = totalPaths[pathIndex];
var d = calcDistance(cities, totalPaths[pathIndex]);
routesLookedAt++;
if (d < recordDistance)
{
recordDistance = d;
bestEver = totalPaths[pathIndex];
}
if (d < currentRecord)
{
currentDistance = d;
currentRecord = d;
}
pathIndex++;
}
function combo(c) {
var r = [],
len = c.length;
tmp = [];
function nodup() {
var got = {};
for (var l = 0; l < tmp.length; l++) {
if (got[tmp[l]]) return false;
got[tmp[l]] = true;
}
return true;
}
function iter(col,done) {
var l, rr;
if (col === len) {
if (nodup()) {
rr = [];
for (l = 0; l < tmp.length; l++)
rr.push(c[tmp[l]]);
r.push(rr);
}
} else {
for (l = 0; l < len; l ++) {
tmp[col] = l;
iter(col +1);
}
}
}
iter(0);
return r;
}
// 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);
}
}
}