2e:null 2f:["$","title",null,{"children":"Genetic Algorithm TSP (SVG) | John Clarke | Observable"}] 34:Tab0,svg_chart = { xtendArray; best; let el = this var extended_best_solution = mutable best.clone() extended_best_solution.push(extended_best_solution[0]) // duplicate first node to complete the path const links = d3.pairs(extended_best_solution).map(function(pair){ pair = pair.sort(); // maybe not necessary if (!points[pair[0]]) console.log(mutable best, pair) return { link: pair, x1: points[pair[0]].x, y1: points[pair[0]].y, x2: points[pair[1]].x, y2: points[pair[1]].y, id: pair.join('_'), } }) // Setup SVG if (!el || d3.select(el).selectAll("line").length==0) { mutable link_history = []; el = DOM.svg(width, height) const svg = d3.select(el) svg.append("g") .attr('class', 'cities') svg.append("g") .attr('class', 'edges') svg.append("g") .attr('class', 'labels') } mutable link_history.push(links.clone()); // update circles const cities = d3.select('.cities') .selectAll("circle") .data(points) cities.exit() .transition() .duration(100) .remove() cities .transition() .duration(100) .attr("r", 3) .attr('cy', d => d.y) .attr('cx', d => d.x) cities.enter() .append("circle") .attr('cy', d => d.y) .attr('cx', d => d.x) .transition() .duration(100) .attr("fill", '#555') const labels = d3.select('.labels') .selectAll("text") .data(points) labels.exit() .remove() labels.enter() .append("text") labels .attr('y', d => d.y) .attr('x', d => d.x) .text(d => d.id) .style("font-family", "sans-serif") .style("font-size", "8pt") .attr("fill", d => {return show_city_ids ? '#555' : 'transparent'}) // update edges const edges = d3.select('.edges') .selectAll("line") .data(links, d => d.id) edges.exit() .style("stroke", 'red') .transition() .duration(transition_duration/3) .style("stroke-opacity", '0') //.remove() edges .attr('x1', d => d.x1) .attr('y1', d => d.y1) .attr('x2', d => d.x2) .attr('y2', d => d.y2) .style("stroke-width", "1.5") .style("stroke", "#AAA") .style("stroke-opacity", '1') edges.enter() .append("line") .attr('x1', d => d.x1) .attr('y1', d => d.y1) .attr('x2', d => d.x2) .attr('y2', d => d.y2) .style("stroke", 'green') .style("stroke-width", 0) .transition() .delay(transition_duration/3) // wait until old edges removed .duration(transition_duration/3) .style("stroke-width", 1.5) .transition() .delay(transition_duration) .duration(transition_duration/3) .style("stroke", "#AAA") return el; }35: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"} } }] } ] })36:T759,// Keeping this here to compare with SVG rendering // 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); // TODO prevent main from re-firing on every change. await Promises.delay(transition_duration); // can slow down the loop for visual inspection } function initData() { mutable collisions = []; mutable UNCHANGED_GENS = 0; mutable bestValueHistory = []; mutable bestSolutionHistory = []; 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 var solution = population[currentBest.bestPosition].clone(); // ensure we always start with node 0 to help with visual inspection and visualizations mutable best = solution.concat(solution.splice(0, solution.indexOf(0))); mutable bestValue = currentBest.bestValue; mutable bestValueIndex = mutable bestValueHistory.length; mutable UNCHANGED_GENS = 0; mutable bestSolutionHistory.push(mutable best.clone()) } else { mutable UNCHANGED_GENS += 1; } mutable collisions = checkIntersections(); mutable bestValueHistory.push({'value': Math.min(mutable bestValue, 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