2c:null 2d:["$","title",null,{"children":"Genetic Algorithm TSP (Canvas) | John Clarke | Observable"}] 32:T669,vl({ "width": "600", "height": "100", "layer": [{ "data": { "values": data }, "layer": [{ "mark": "line", "encoding": { "x": { "field": "x", "type": "quantitative", "axis": {"labelAngle": 0}, "scale": {"domain": [0, 500]} }, "y": { "field": "y", "type": "quantitative", "title": "TSP length", "format": "s", } } }, { "mark": "line", "transform": [ {"filter": {"field": "y", "equal": mutable bestValue}}, ], "encoding": { "x": {"field": "x", "type": "quantitative"}, "y": {"field": "y", "type": "quantitative"}, "color": {"value": "green"} } } ]}, { "data": { "values": [ {"MaxInterations": max_iterations, "Threshold": "Max Iterations"} ] }, "layer": [{ "mark": "rule", "encoding": { "x": { "field": "MaxInterations", "type": "quantitative", "title": "Iterations", }, "color": {"value": "#e45755"} } }] }, { "data": { "values": data }, "layer": [{ "mark": "circle", "transform": [ {"filter": {"field": "x", "equal": mutable bestValueIndex}}, ], "encoding": { "x": {"field": "x", "type": "quantitative"}, "y": {"field": "y", "type": "quantitative"}, "color": {"value": "red"} } }] } ] })33:T66f,networkgraph = { best; const context = DOM.context2d(width, height); const ctx = context; $(context).attr('id', 'canvas'); let frame; function drawCircle(point, i) { ctx.fillStyle = '#BBB'; ctx.beginPath(); ctx.arc(point.x, point.y, 3, 0, Math.PI*2, true); ctx.closePath(); ctx.fill(); if (show_city_ids) { ctx.font = "10px Arial"; ctx.fillText(i, point.x+3, point.y-3); } } function drawLines(array) { ctx.strokeStyle = '#333'; ctx.lineWidth = 1; ctx.beginPath(); ctx.moveTo(points[array[0]].x, points[array[0]].y); for(var i=1; i 0) { for(var i=0; i=10 && mutable collisions.length==0) { break }; GANextGeneration(); mutable elapsedTime = Math.round(performance.now() - start_time); if (show_progress) {await Promises.delay(10)}; } function initData() { //console.log('init'); mutable collisions = []; mutable UNCHANGED_GENS = 0; mutable bestValueHistory = []; mutable bestValue = 9999999; mutable bestValueIndex = 0; mutable best = []; mutable mutationTimes = 0; mutable currentGeneration = 0; mutable elapsedTime = 0; population = []; values = new Array(POPULATION_SIZE); fitnessValues = new Array(POPULATION_SIZE); roulette = new Array(POPULATION_SIZE); } function checkIntersections(){ // We add the first node to the best solution so that all pairs are considered // Probably a much more elegant way to do this. var extended_best_solution = mutable best.clone() extended_best_solution.push(extended_best_solution[0]) const pairs = d3.pairs(extended_best_solution) var collisions = []; for (var i=0; i<=pairs.length; i++) { for (var j=i; j<=pairs.length-1; j++){ var a = points[pairs[i][0]].x var b = points[pairs[i][0]].y var c = points[pairs[i][1]].x var d = points[pairs[i][1]].y var e = points[pairs[j][0]].x var f = points[pairs[j][0]].y var g = points[pairs[j][1]].x var h = points[pairs[j][1]].y if (intersects(a, b, c, d, e, f, g, h)) collisions.push([pairs[i], pairs[j]]); }; } return collisions; } function tribulate() { for(var i=population.length>>1; i 1) { dx = px[fun](px.indexOf(c)); dy = py[fun](py.indexOf(c)); px.deleteByValue(c); py.deleteByValue(c); c = dis[c][dx] < dis[c][dy] ? dx : dy; solution.push(c); } return solution; } function mutation() { for(var i=0; i 0.5) { population[i] = pushMutate(population[i]); } else { population[i] = doMutate(population[i]); } i--; } } } function preciseMutate(orseq) { var seq = orseq.clone(); if(r() > 0.5){ seq.reverse(); } var bestv = evaluate(seq); for(var i=0; i<(seq.length>>1); i++) { for(var j=i+2; j= n) for(var i=0, j=(n-m+1)>>1; i>1); n = randomNumber(seq.length); i++; } while (m >= n) var s1 = seq.slice(0,m); var s2 = seq.slice(m,n) var s3 = seq.slice(n,seq.length); return s2.concat(s1).concat(s3).clone(); } function setBestValue() { for(var i=0; i currentBest.bestValue) { // changing best should trigger redraw mutable best = population[currentBest.bestPosition].clone(); mutable bestValue = currentBest.bestValue; mutable bestValueIndex = mutable bestValueHistory.length; mutable UNCHANGED_GENS = 0; } else { mutable UNCHANGED_GENS += 1; } mutable collisions = checkIntersections(); // The following is not firing a change to `data` -- we want to but also need to be able to mutable bestValueHistory.push({'value': currentBest.bestValue, 'collisions': mutable collisions.length}) } function getCurrentBest() { var bestP = 0, currentBestValue = values[0]; for(var i=1; ithis.length || y>this.length || x === y) {return} var tem = this[x]; this[x] = this[y]; this[y] = tem; } Array.prototype.roll = function () { var rand = randomNumber(this.length); var tem = []; for(var i = rand; i