main = { xtendArray; r; // ensure SeedRandom is loaded var dis; var currentBest; var population; var values; var fitnessValues; var roulette; var start_time = performance.now(); Math.seedrandom('a13219765bc7c488a3a47') // ensure same random number stream each time initData(); GAInitialize(); // TODO: improve stopping conditions // Could use collisions to help guess which nodes to swap? for (var x=0; x < max_iterations; x++) { //if (!running) { break }; if (mutable UNCHANGED_GENS>=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; i