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