30:T27cf,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; }31:[] 2e:{"title":"Travelling with a self-organizing map","cells":[{"id":0,"value":"md`# Travelling with a self-organizing map\n\nThe travelling salesperson problem (TSP), as approached by Johannes Beck with a self-organizing map (SOM).\nSee Joe’s blog post at http://blog.johannes-beck.name/?p=222 for details, or the more detailed write-up in https://diego.codes/post/som-tsp/ \n\nThe original algorithm is from\n> [AVT88] Bernhard Angeniol, Gael De La Croix Vaubois & Jean-Yves Le Texier\nSelf-Organizing Feature Maps and the Travelling Salesman\nProblem, Neural Networks, Vol. 1, pp. 289-293, 1988. Links: [doi](http://dx.doi.org/10.1016/0893-6080%2888%2990002-0)/[scihub](https://sci-hub.se/10.1016/0893-6080%2888%2990002-0).\n\nImplemented by a straightforward copy-paste of Joe’s code from [github.com/kifj/tsp-js](https://github.com/kifj/tsp-js/blob/master/salesman.js), with the addition of a d3-delaunay graph to map each point to the closest neuron of the SOM.\n\nSee also: [Sort stuff by similarity](https://observablehq.com/@fil/sort-stuff-by-similarity).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"points = (replay,\nArray.from({ length: 300 }, (_, i) =>\n Object.assign([Math.random(), Math.random()], { index: i })\n))","pinned":true,"hidden":false,"mode":"ojs"},{"id":173,"value":"viewof replay = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":76,"value":"{\n const context = DOM.context2d(height, height),\n path = d3.geoPath().context(context),\n x = d3.scaleLinear().range([10, height - 10]);\n\n context.beginPath();\n path({\n type: \"LineString\",\n coordinates: som.neurons.map(d => d.map(x))\n });\n context.strokeStyle = \"red\";\n context.lineWidth = 1;\n context.stroke();\n\n context.beginPath();\n path({ type: \"MultiPoint\", coordinates: points.map(d => d.map(x)) });\n context.fillStyle = \"white\";\n context.fill();\n context.strokeStyle = \"black\";\n context.stroke();\n\n context.beginPath();\n const l = points\n .slice()\n .sort((a, b) => order[a.index] - order[b.index])\n .map(d => d.map(x));\n l.push(l[0]);\n path({\n type: \"Polygon\",\n coordinates: [l]\n });\n context.lineWidth = 2;\n context.strokeStyle = \"lightblue\";\n context.stroke();\n\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":131,"value":"order = {\n const D = d3.Delaunay.from(som.neurons);\n const order = points.map(d => D.find(d[0], d[1]));\n // return the new order — if something goes wrong (we receive -1), use the previous value\n return order[0] === -1 ? this : order;\n\n /*\n\n // Quadtree version\n const D = d3\n .quadtree()\n .addAll(som.neurons.map((d, i) => Object.assign(d, { index: i })));\n const order = points.map(d => D.find(d[0], d[1]).index);\n return order[0] === -1 ? this : order;\n\n */\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":17,"value":"som = {\n const tsp = new TravelingSalesman();\n\n tsp.maxCycles = 400;\n\n tsp.createFirstNeuron();\n tsp.cities = points.map((d, i) => ({ x: d[0], y: d[1] }));\n\n var done, pos;\n do {\n done = tsp.surveyRun();\n let n = tsp.neurons.start;\n pos = [[n.x, n.y]];\n for (let i = 0; i < tsp.neurons.length; i++) {\n n = n.right;\n pos.push([n.x, n.y]);\n }\n if (tsp.cycle > 3)\n yield {\n cycle: tsp.cycle,\n length: tsp.neurons.tourLength(),\n neurons: pos\n };\n } while (!done && tsp.cycle < tsp.maxCycles);\n yield {\n cycle: tsp.cycle,\n length: tsp.neurons.tourLength(),\n neurons: pos\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":3,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":80,"value":"d3 = require(\"d3-scale@2\", \"d3-geo@1\", \"d3-delaunay@4\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":78,"value":"height = Math.min(width, 600)","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}