TravelingSalesman = { // copy-pasted from github.com/kifj/tsp-js const $ = "we don't jQuery and a lot of this code is just ignored"; /* Sample of a city */ function Sample() { this.x = 0.0; this.y = 0.0; } Sample.prototype.draw = function(canvas) { var centerX = this.x * canvas.width; var centerY = canvas.height - this.y * canvas.height; var ctx = canvas.ctx; ctx.fillStyle = "#C06060"; ctx.beginPath(); ctx.arc(centerX, centerY, 3, 0, Math.PI * 2, true); ctx.closePath(); ctx.fill(); }; /* a node in the neural network */ function Node(x, y) { this.x = x; this.y = y; this.right = this; this.left = this; this.life = 3; this.inhibitation = 0; this.isWinner = 0; } /* the distance of the euklidian points */ Node.prototype.potential = function(sample) { return ( (sample.x - this.x) * (sample.x - this.x) + (sample.y - this.y) * (sample.y - this.y) ); }; /* moves a single node in direction to the sample */ Node.prototype.move = function(city, value) { this.x += value * (city.x - this.x); this.y += value * (city.y - this.y); }; /* computes the number of nodes between the to nodes on the ring */ Node.prototype.distance = function(other, length) { var right = 0; var left = 0; var current = other; while (current != this) { current = current.left; left++; } right = length - left; return left < right ? left : right; }; Node.prototype.draw = function(canvas) { var centerX = this.x * canvas.width + 0.5; var centerY = canvas.height - this.y * canvas.height + 0.5; var ctx = canvas.ctx; ctx.fillStyle = "#208020"; ctx.fillRect(centerX, centerY, 1, 1); if (this.right != null) { ctx.lineTo( this.right.x * canvas.width + 0.5, canvas.height - this.right.y * canvas.height + 0.5 ); } }; /* the neural network as a ring of neurons */ function Ring(start) { this.start = start; this.length = 1; } /* moves all nodes to in direction of the sample */ Ring.prototype.moveAllNodes = function(city, gain) { var current = this.start; var best = this.findMinimum(city); for (var i = 0; i < this.length; i++) { current.move(city, this.f(gain, best.distance(current, this.length))); current = current.right; } }; /* finds the node with the least distance to the sample */ Ring.prototype.findMinimum = function(city) { var actual; var node = this.start; var best = node; var min = node.potential(city); for (var i = 1; i < this.length; i++) { node = node.right; actual = node.potential(city); if (actual < min) { min = actual; best = node; } } best.isWinner++; return best; }; /* deletes a node */ Ring.prototype.deleteNode = function(node) { var previous = node.left; var next = node.right; if (previous != null) { previous.right = next; } if (next != null) { next.left = previous; } if (next == node) { next = null; } if (this.start == node) { this.start = next; } this.length--; }; /* a node is duplicated & inserted into the ring */ Ring.prototype.duplicateNode = function(node) { var newNode = new Node(node.x, node.y); var next = node.left; next.right = newNode; node.left = newNode; node.inhibitation = 1; newNode.left = next; newNode.right = node; newNode.inhibitation = 1; this.length++; }; /* length of tour */ Ring.prototype.tourLength = function() { var dist = 0.0; var current = this.start; var previous = current.left; for (var i = 0; i < this.length; i++) { dist += Math.sqrt( (current.x - previous.x) * (current.x - previous.x) + (current.y - previous.y) * (current.y - previous.y) ); current = previous; previous = previous.left; } return dist; }; Ring.prototype.f = function(gain, n) { return 0.70710678 * Math.exp(-(n * n) / (gain * gain)); }; /* the simulator containing all the data */ function TravelingSalesman() { this.N = 100; /* Number of cities. */ this.cycle = 0; /* Number of complete survey done */ this.maxCycles = 1000; /* Number of complete suerveys */ this.cities = null; /* the samples */ this.neurons = null; /* the neurons */ this.alpha = 0.05; /* learning rate */ this.gain = 50.0; /* gain */ this.lastLength = null; /* length of tour */ this.isRunning = false; this.update = 5; /* screen update */ } /* creates the first node (ring) */ TravelingSalesman.prototype.createFirstNeuron = function() { var start = new Node(0.5, 0.5); this.neurons = new Ring(start); }; /* deletes all nodes */ TravelingSalesman.prototype.deleteAllNeurons = function() { if (this.neurons != null) { while (this.neurons.start != null) { this.neurons.deleteNode(this.neurons.start); } this.neurons = null; } }; /* prints positions of cities & nodes */ TravelingSalesman.prototype.print = function() { console.log( "TSP: N= " + this.N + ", cycle=" + this.cycle + ", lastLength=" + this.lastLength ); for (var i = 0; i < this.cities.length; i++) { var c = this.cities[i]; console.log("City: " + i + " (" + c.x + "," + c.y + ")"); } var n = this.neurons.start; for (i = 0; i < this.neurons.length; i++) { console.log("Node: " + i + "(" + n.x + "," + n.y + ")"); n = n.right; } }; /* creates & displaces randomly a given number of cities, returns the first */ TravelingSalesman.prototype.createRandomCities = function() { this.cities = new Array(this.N); for (var i = 0; i < this.N; i++) { var c = new Sample(); c.x = Math.random(); c.y = Math.random(); this.cities[i] = c; } }; TravelingSalesman.prototype.stop = function() { this.isRunning = false; this.repaint(); this.cities = null; this.deleteAllNeurons(); }; TravelingSalesman.prototype.start = function() { this.stop(); this.init(); this.isRunning = true; this.run(); }; TravelingSalesman.prototype.init = function() { this.cycle = 0; this.lastLength = null; this.createFirstNeuron(); this.createRandomCities(); this.canvas = new Canvas(document.getElementById("canvas")); this.repaint(); }; TravelingSalesman.prototype.run = function() { if (this.neurons != null) { if (this.cycle < this.maxCycles && this.isRunning) { var done = this.surveyRun(); if (!done) { var self = this; window.setInterval(function() { self.run(); }, 100); return; } } if (this.isRunning) { //this.print(); this.isRunning = false; this.repaint(); } } }; /* one cycle in the simulation */ TravelingSalesman.prototype.surveyRun = function() { var done = false; if (this.neurons != null) { for (var i = 0; i < this.cities.length; i++) { this.neurons.moveAllNodes(this.cities[i], this.gain); } } this.surveyFinish(); this.gain = this.gain * (1 - this.alpha); if (this.cycle++ % this.update == 0) { var length = this.neurons.tourLength(); //this.print(); this.repaint(); if (length == this.lastLength) { done = true; } else { this.lastLength = length; } } return done; }; /* after moving creating & deleting is done */ TravelingSalesman.prototype.surveyFinish = function() { if (this.neurons == null) { return; } var node = this.neurons.start; for (var i = 0; i < this.neurons.length; i++) { node.inhibitation = 0; switch (node.isWinner) { case 0: node.life--; if (node.life == 0) { this.neurons.deleteNode(node); } break; case 1: node.life = 3; break; default: node.life = 3; this.neurons.duplicateNode(node); break; } node.isWinner = 0; node = node.right; } }; TravelingSalesman.prototype.repaint = function() { if (!this.canvas) { return; } this.canvas.ctx.clearRect(0, 0, this.canvas.width, this.canvas.height); if (this.cities) { for (var i = 0; i < this.cities.length; i++) { var c = this.cities[i]; c.draw(this.canvas); } } if (this.neurons) { this.canvas.ctx.strokeStyle = "#80D080"; this.canvas.ctx.beginPath(); var n = this.neurons.start; this.canvas.ctx.moveTo( n.x * this.canvas.width + 0.5, this.canvas.height - n.y * this.canvas.height + 0.5 ); for (i = 0; i < this.neurons.length; i++) { n.draw(this.canvas); n = n.right; } this.canvas.ctx.lineWidth = 1; this.canvas.ctx.stroke(); this.canvas.ctx.closePath(); } $("#cycle").val(this.cycle); $("#length").val(this.lastLength); $("#done").prop("checked", !this.isRunning); if (this.isRunning) { $("#run").attr("disabled", "disabled"); $("#stop").removeAttr("disabled"); } else { $("#stop").attr("disabled", "disabled"); $("#run").removeAttr("disabled"); } }; TravelingSalesman.prototype.setupForm = function() { var self = this; $("#cities").val(this.N); $("#maxCycles").val(this.maxCycles); $("#alpha").val(this.alpha); $("#gain").val(this.gain); $("#run").bind("click", function(event) { self.N = $("#cities").val(); self.maxCycles = $("#maxCycles").val(); self.alpha = $("#alpha").val(); self.gain = $("#gain").val(); self.start(); }); $("#stop").bind("click", function(event) { self.stop(); }); }; function Canvas(elem) { this.elem = elem; this.ctx = elem.getContext("2d"); this.height = elem.height; this.width = elem.width; } return TravelingSalesman; }