2f:null 30:["$","title",null,{"children":"Genetic algorithm to compute a grid map of United States | Sylvain Lesage | Observable"}] 35:T573,md`# Genetic algorithm to compute a grid map of United States In [a previous notebook](https://beta.observablehq.com/@severo/square-grid-maps-of-the-usa) we reproduced the quality measures established by [Krist Wongsuphasawat](https://twitter.com/kristw). Here we will use a combination of them as the cost function of a genetic algorithm in order to produce an "optimal" gird cartogram. ## TL;DR Here we show that using a genetic algorithm, we are able to generate grid maps with better quality measures than the ones published by [The New York Times and other newspapers](https://beta.observablehq.com/@severo/square-grid-maps-of-the-usa) (71.9) but... it does not make sense as a grid map, the states are totally misplaced. Thus, we will have to work on better measures to compute grid maps automatically ## Representing a cartogram as a vector The genetic algorithms use an evolving poblation of vectors. There are N polygons to represent in the genetic algorithm, and we allow the grid cells to live in a canvas of size (ymax * xmax). N cells contain a value representing one of the polygons, and the other ones are empty. The vector will be composed of the concatenation of the columns of the canvas, from left to right. ### Vector of the New York Times' grid cartogram The grid map by the New York Times (removing Alaska and Hawaii, since their positions are not relevant) is: `36:Te72,crossover = function(parent1, parent2) { /* we assume the two vectors are a permutation of each other, and they may include empty cells: "" */ let child1 = new Array(parent1.length).fill("") let child2 = child1.slice() /* See http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/CycleCrossoverOperator.aspx */ /* We adapt it to manage the empty cells */ /* Initialize flags to false. These will be used to flag a value of parent1 as 'considered' */ let flags = new Array(parent1.length).fill(false) /* We need fast lookups of a parent2's index, given a value -- so build a hash table entry key & value2 will house the allele value index2 will hold the index of the allele value1 will hold the value of parent1 at index2 */ let equalIndexes = [] let ht1 = {} let ht2 = {} for (var i = 0; i < parent1.length; i++) { /* [new] First look for the cells equal in both arrays */ if (parent1[i] === parent2[i]) { /* Ignore if they are empty */ if (parent1[i] !== "") { equalIndexes.push(i) } flags[i] = true } else { if (parent2[i] !== "") { ht1[parent2[i]] = { index: i, value1: parent1[i], value2: parent2[i] } } /* [new] Fill a lookup for parent1's index */ if (parent1[i] !== "") { ht2[parent1[i]] = { index: i, value1: parent1[i], value2: parent2[i] } } } } /* 1. identify all cycles */ let cycles = [] let cycleStart = 0 // refers to parent 1 index of cycle start /* [new] only loop on the keys of ht2 */ Object.keys(ht2).forEach(function(key) { let tempCycle = [] let i = ht2[key].index // If this value isn't already a part of another cycle: if (!flags[i]) { /* [new] advance in the cycle both sides */ /* Side 1 */ // A1. Record cycle start index of parent1 cycleStart = i // B1. Advance one step in the cycle let tempPair = ht1[parent1[cycleStart]] tempCycle.push(tempPair) flags[tempPair.index] = true // C1. Advance until the cycle is complete /* [new] we also stop the loop if we find an empty string */ while (tempPair.index !== cycleStart && tempPair.value1 !== "") { // Advance one more step in the cycle tempPair = ht1[tempPair.value1] tempCycle.push(tempPair) flags[tempPair.index] = true } /* Side 2 */ /* [new] we explore the second side, only if the cycle has not been completed, and the value in parent2 in not empty: "" */ tempPair = ht2[parent1[cycleStart]] if (!flags[tempPair.index]) { tempCycle.push(tempPair) flags[tempPair.index] = true while (tempPair.value2 !== "") { // Advance one more step in the cycle tempPair = ht2[tempPair.value2] tempCycle.push(tempPair) flags[tempPair.index] = true } } // D. Add this cycle to the list of cycles cycles.push(tempCycle) } }) /* 2. Copy alternate cycles to kids */ let counter = 0 cycles.forEach(function (c) { // Alternate with each cycle which kid receives the values c.forEach(function (p) { if (counter % 2 == 0) { child1[p.index] = p.value1 child2[p.index] = p.value2 } else { child1[p.index] = p.value2 child2[p.index] = p.value1 } }); counter += 1 }); /* 3. Copy equal cells */ equalIndexes.forEach(function (i) { child1[i] = parent1[i] child2[i] = parent1[i] }) return [child1, child2] }37:T563,function randomGridMapVector(g) { let gl = gridMapLookup(g) let N = g.length; //let vLength = 4*N*N+4*N+1 let vLength = xyToIdx(xmax, ymax) + 1 //let centerId = 2*N*N + 2*N let keys = _.keys(gl) //let keys = _.keys(gl).sort() //let centerKey = keys[0] //let otherKeys = keys.slice(1) let v = new Array(vLength).fill("") /* sort the position of every polygon anywhere in the plan */ let indexSubset = _.sampleSize(_.range(0, v.length), N) for (let i = 0; i < keys.length; i++) { v[indexSubset[i]] = keys[i] } /* First idea: sort the position of every polygon anywhere in the plan */ // let indexSubset = _.sampleSize(_.range(0, centerId).concat(_.range(centerId + 1, v.length)), N-1) /* Second idea: only sort inside a center square, to promote compactness of the grid maps */ /*let squareN = Math.floor(Math.sqrt(N)) + 1 if (squareN % 2 == 0) { squareN = squareN/2 } else { squareN = (squareN+1)/2 } squareN += 2 let squareIndexes = [] for (let i = N-squareN; i < N+squareN+1; i++) { for (let j = N-squareN; j < N+squareN+1; j++) { if (i !== N || j !== N) { squareIndexes.push(i*(2*N+1)+j) } } } let indexSubset = _.sampleSize(squareIndexes, N-1) v[centerId] = centerKey for (let i = 0; i < otherKeys.length; i++) { v[indexSubset[i]] = otherKeys[i] } */ return v }38:T64e,function showGridMap (gridMapVector) { /* From http://bl.ocks.org/kristw/2f628465e36f9821325d */ let gridMap = vectorToGridMap(gridMapVector) let L = gridMapVector.length let xMin = d3.min(gridMap.map(e => e.x)) let xMax = d3.max(gridMap.map(e => e.x)) let yMin = d3.min(gridMap.map(e => e.y)) let yMax = d3.max(gridMap.map(e => e.y)) let cols = xMax - xMin + 1 let rows = yMax - yMin + 1 let maxColsRows = ((cols > rows) ? cols: rows) let height = 360 var options = { rectWidth: height/maxColsRows, rectHeight: height/maxColsRows }; const svg = d3.select(DOM.svg(width, height)) .attr("class", "gridmap") // Define color scale var color = d3.scaleQuantize() .domain([1, 20]) .range(['#b2ddf0', '#92bcd8', '#769cbf', '#5d7da7', '#46608f', '#334577', '#232d5f']); var sEnter = svg.append('g') .selectAll('g') .data(gridMap) .enter().append('g') .attr('transform', function(d){ return 'translate('+((d.x-xMin)*options.rectWidth)+','+((d.y-yMin)*options.rectHeight)+')'; }); sEnter.append('rect') .attr('width', options.rectWidth) .attr('height', options.rectHeight) .attr('vector-effect', 'non-scaling-stroke') .style('opacity', 0.5) .style('stroke', '#aaa') .style('fill', function(d){return color(d.key.length);}); sEnter.append('text') .attr('x', options.rectWidth/2) .attr('y', options.rectHeight/2 + 2) .style('text-anchor', 'middle') .style('font-size', '10px') .style('font-family', 'sans-serif') .text(function(d){return d.key;}); return svg.node(); }39:T4c9,function generateCrossoverPopulation(population, crossoverNumber) { let tempElement = crossoverNumber % 2 let crossoverPairs = (crossoverNumber + tempElement) / 2 /* In order to avoid clones/twins in the children, we have to avoid: - children with parent1 = parent2 - various crossovers for the same pair of (parent1,parent2) But we allow the same parent to be involved in various crossovers */ let allPossiblePairs = [] for (let i = 0; i < population.length; i++) { for (let j = 0; j < i; j++) { allPossiblePairs.push([i,j]) } } if (allPossiblePairs.length < crossoverNumber) { throw("Cannot generate crossover population, since it would generate clones. Decrease crossoverNumber, or increase the population size") } let parentsPairs = _.sampleSize(allPossiblePairs, crossoverPairs) let crossoverPopulation = [] let child1 let child2 for (let i = 0; i < crossoverPairs; i++) { [child1, child2] = crossover(population[parentsPairs[i][0]], population[parentsPairs[i][1]]) crossoverPopulation.push(child1) crossoverPopulation.push(child2) } crossoverPopulation = crossoverPopulation.slice(0, crossoverNumber) return crossoverPopulation }3a:[] 33:{"id":"e17a9e0168a2145f","slug":"genetic-algorithm-to-compute-a-grid-map-of-united-states","title":"Genetic algorithm to compute a grid map of United States","thumbnail":"35a596bffd23f341dce1c02671216e80fa245242d705cdac851e7caeeec0fa87","access_level":"public","create_time":"$D2018-06-06T14:25:12.868Z","update_time":"$D2018-06-11T19:30:43.588Z","view_time":null,"first_public_time":"$D2018-06-10T15:14:49.693Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"5c7b4ebed88da11a","login":"severo","name":"Sylvain Lesage","avatar_url":"https://avatars-next.observableusercontent.com/7713195c83e5bfd8090ffe70c871c23e743c711e9e712675c99a8960ca8c7944","tier":"starter_2024"},"version":1342,"publish_version":1342,"role":null,"authored":false,"authors":[{"type":"individual","id":"bf1872cca880d345","login":"severo","name":"Sylvain Lesage","avatar_url":"https://avatars-next.observableusercontent.com/7713195c83e5bfd8090ffe70c871c23e743c711e9e712675c99a8960ca8c7944","tier":null}],"members":[{"type":"individual","id":"bf1872cca880d345","login":"severo","name":"Sylvain Lesage","avatar_url":"https://avatars-next.observableusercontent.com/7713195c83e5bfd8090ffe70c871c23e743c711e9e712675c99a8960ca8c7944","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"c3e848f22419d597","slug":"grid-maps","title":"Grid maps","owner":{"id":"5c7b4ebed88da11a","login":"severo","name":"Sylvain Lesage"}},"type":"notebook","body":{"title":"Genetic algorithm to compute a grid map of United States","cells":[{"id":0,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"NYTGridMap = usGridMapsData.filter(g => g.name=\"New York Times\")[0].gridData.filter(p => p.key !== 'AK' && p.key !== 'HI')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"md`Its representation as a vector is:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"NYTVector = gridMapToVector(NYTGridMap)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"md`## Crossover and mutation operations\n\nWe will try with the exchange mutation (EM) operator, that switches a non-null cell with another cell, null or non-null, avoiding the center cell:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1131,"value":"function mutate(v, mutationsPerMutatedElement) {\n switch (mutateOption){\n case \"mutateNeighbors\":\n return mutateNeighbors(v, mutationsPerMutatedElement)\n case \"mutateEM\":\n default:\n return mutateEM(v, mutationsPerMutatedElement)\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"function mutateEM (v, mutationsPerMutatedElement) {\n /* We switch a non-null cell with another cell, null or non-null */\n let nonnullV = v.reduce(function(a, e, i) {\n if (e !== \"\") {\n a.push(i);\n }\n return a;\n }, [])\n\n /* First idea: sort the position of the mutated polygon anywhere in the plan */\n let firstId = _.sample(nonnullV)\n let secondId = _.sample(_.range(0, v.length))\n let mutatedV = v.slice()\n mutatedV[firstId] = v[secondId]\n mutatedV[secondId] = v[firstId]\n \n return mutatedV\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1330,"value":"md`Another option is to only switch one cell with one of its neighbors.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1088,"value":"function mutateNeighbors (v, mutationsPerMutatedElement) {\n /* We switch a non-null cell with a neighbor cell, avoiding the center cell */\n \n let nonnullV = v.reduce(function(a, e, i) {\n if (e !== \"\") {\n a.push(i);\n }\n return a;\n }, []);\n\n let numMutations = _.range(1,mutationsPerMutatedElement+1)\n let mutatedV = v.slice()\n let tmp = \"\"\n for (let i=0; i \"Permutation Encoding\"\n- Mutation\n- [scijs permutation](http://scijs.net/packages/#scijs/random-permutation)\n- [sarbacane](https://beta.observablehq.com/@tarte0/genetics-with-sarbacane-js)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":247,"value":"md`## Genetic algorithm\n\n- we generate a population of ${populationSize} random gridmaps\n- for each iteration (${maxIterations} iterations):\n - compute the fitness function of each gridmap\n - select the ${selectedNumber} best ones (${selectedPercentage}%), in the sense of the fitness function, as the base for the next generation\n - generate the next generation, from the selection:\n - elite: keep the best ${eliteNumber}\n - mutation: mutate ${mutationNumber} random ones\n - crossover ${crossoverNumber} ones, by pairs\n - remove the duplicates, in order to promote the diversity\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":608,"value":"populationSize = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":709,"value":"selectedPercentage = 60","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":711,"value":"selectedNumber = populationSize * selectedPercentage / 100","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":701,"value":"eliteNumber = 1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":612,"value":"mutationPercentage = 12","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":703,"value":"mutationNumber = Math.floor(populationSize * mutationPercentage / 100)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":707,"value":"crossoverNumber = populationSize - mutationNumber - eliteNumber","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":674,"value":"mutationsPerMutatedElement = 1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1199,"value":"mutationMaxShift = 4","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":616,"value":"maxIterations = 500000","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1105,"value":"N = NYTGridMap.length","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1204,"value":"ymin = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1206,"value":"ymax = 7","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1208,"value":"xmin = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1210,"value":"xmax = 13","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1125,"value":"viewof mutateOption = html`\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":414,"value":"md`### Initialization`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":714,"value":"population = generatePopulation(populationSize)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":400,"value":"showGridMap(population[0].gridMap)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":417,"value":"md`### First iteration`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":784,"value":"selectedPopulation = population.slice(0,selectedNumber).map(e => e.gridMap)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":788,"value":"elitePopulation = selectedPopulation.slice(0,eliteNumber)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":791,"value":"crossoverPopulation = generateCrossoverPopulation(selectedPopulation, crossoverNumber)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":793,"value":"mutatedPopulation = generateMutatedPopulation(selectedPopulation, mutationNumber, mutationsPerMutatedElement)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":795,"value":"populationIt1 = {\n let p = elitePopulation.concat(crossoverPopulation).concat(mutatedPopulation).map(function (a) {return {gridMap: a} })\n \n /* Compute the fitness score */\n p = addFitnessScoreToPopulation(p, usGeoPairs)\n \n /* Order the elements by fitness score */\n p = orderPopulation(p)\n return p\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":489,"value":"showGridMap(populationIt1[0].gridMap)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":521,"value":"md`## Iterations`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":923,"value":"viewof paused = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":505,"value":"current = {\n let current = this || {iteration: 0, population: population};\n if (paused) return yield current;\n while (true) {\n current = {\n iteration: current.iteration+1,\n population: createNextGeneration(current.population, selectedNumber, eliteNumber, crossoverNumber, mutationNumber, mutationsPerMutatedElement)}\n yield current;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":965,"value":"l = current.population.length","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":557,"value":"iteration = current.iteration","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":555,"value":"bestGridMapScore = current.population[0].costs.cost","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":870,"value":"secondGridMapScore = current.population[1].costs.cost","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":873,"value":"thirdGridMapScore = current.population[2].costs.cost","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":901,"value":"fifthGridMapScore = current.population[4].costs.cost","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":903,"value":"tenthGridMapScore = current.population[9].costs.cost","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1312,"value":"gridMapScore = current.population[0].costs.cost","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":509,"value":"bestGridMapPopulation = showGridMap(current.population[0].gridMap)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"md`## Tests`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"BoliviaGridMap = [\n {x:0, y:0, key: \"PA\", name: \"Pando\"},\n {x:1, y:0, key: \"BN\", name: \"Beni\"},\n {x:0, y:1, key: \"LP\", name: \"La Paz\"},\n {x:1, y:1, key: \"CB\", name: \"Cochabamba\"},\n {x:2, y:1, key: \"SC\", name: \"Santa Cruz\"},\n {x:0, y:2, key: \"OR\", name: \"Oruro\"},\n {x:1, y:2, key: \"CH\", name: \"Chuquisaca\"},\n {x:0, y:3, key: \"PT\", name: \"Potosí\"},\n {x:1, y:3, key: \"TJ\", name: \"Tarija\"}\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"BoliviaVector = gridMapToVector(BoliviaGridMap)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":281,"value":"BoliviaVectorToGridMap = vectorToGridMap(BoliviaVector, {x: 1, y: 0, key: \"BN\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":"BoliviaVectorToGridMapWithoutCenter = vectorToGridMap(BoliviaVector)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"BoliviaMutatedVector = mutate(BoliviaVector)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"BoliviaCrossoverVector = crossover(BoliviaVector, BoliviaMutatedVector)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":261,"value":"BoliviaRandomGridMap = randomGridMapVector(BoliviaGridMap)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"v1 = [\"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\", \"9\"]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":191,"value":"v2 = [\"2\", \"4\", \"6\", \"8\", \"5\", \"9\", \"7\", \"3\", \"1\"]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":193,"value":"mutatedV1 = mutate(v1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":217,"value":"v3 = [\"8\", \"4\", \"7\", \"3\", \"6\", \"2\", \"5\", \"1\", \"9\", \"0\"]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":220,"value":"v4 = [\"0\", \"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\", \"9\"]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":200,"value":"cx = crossover(v3, v4)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1302,"value":"gridMapToVector(NYTGridMap)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"md`## Utilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":718,"value":"md`TODO:\n\n- Pass the list of elements as a parameter\n- Pass the list of geoPairs as a parameter`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":716,"value":"function generatePopulation(populationSize) {\n /* Generate the elements */\n let p = []\n //p.push({\"gridMap\": gridMapToVector(NYTGridMap)})\n for (let i=0; i < populationSize; i++) {\n p.push({\"gridMap\": randomGridMapVector(NYTGridMap)})\n }\n \n /* Compute the fitness score */\n p = addFitnessScoreToPopulation(p, usGeoPairs)\n \n /* Order the elements by fitness score */\n p = orderPopulation(p)\n \n return p\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":737,"value":"function createNextGeneration(population, selectedNumber, eliteNumber, crossoverNumber, mutationNumber, mutationsPerMutatedElement) {\n \n /* Create the next generation */\n let selectedPopulation = population.slice(0,selectedNumber).map(e => e.gridMap)\n let elitePopulation = selectedPopulation.slice(0,eliteNumber)\n let crossoverPopulation = generateCrossoverPopulation(selectedPopulation, crossoverNumber)\n let mutatedPopulation = generateMutatedPopulation(selectedPopulation, mutationNumber, mutationsPerMutatedElement)\n let p = elitePopulation.concat(crossoverPopulation).concat(mutatedPopulation).map(function (a) {return {gridMap: a} })\n\n /* In order to promote diversity, we delete the duplicates */\n p = removeDuplicates(p)\n \n /* Compute the fitness score */\n p = addFitnessScoreToPopulation(p, usGeoPairs)\n \n /* Order the elements by fitness score */\n p = orderPopulation(p)\n \n return p\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":251,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"function gridMapToVector(g) {\n let gl = gridMapLookup(g)\n let N = g.length;\n //let vLength = 4*N*N+4*N+1\n let vLength = xyToIdx(xmax, ymax) + 1\n //let centerKey = _.keys(gl).sort()[0]\n //let centerX = gl[centerKey].x\n //let centerY = gl[centerKey].y\n let v = new Array(vLength).fill(\"\");\n \n g.forEach(function (e){\n /*let col = N + e.x - centerX\n let row = N + e.y - centerY*/\n v[xyToIdx(e.x, e.y)] = e.key\n })\n return v\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":272,"value":"function vectorToGridMap(v, center) {\n //let N = (Math.sqrt(v.length)-1)/2\n let g = v.reduce(function(a, e, i) {\n if (e !== \"\") {\n let x, y\n [x,y] = idxToXY(i)\n a.push({\n x: x,\n y: y,\n key: e});\n }\n return a;\n }, [])\n\n /* Correct with the central element*/\n /*if (center !== undefined) {\n let centerKey = center.key\n let centerX = center.x\n let centerY = center.y\n let vectorCenterX = g.filter(e => e.key === centerKey)[0].x\n let vectorCenterY = g.filter(e => e.key === centerKey)[0].y\n g.map(function (e) {\n e.x += (centerX - vectorCenterX)\n e.y += (centerY - vectorCenterY)\n return e\n })\n }*/\n\n return g\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":308,"value":"function addFitnessScoreToPopulation (population, geoPairs) {\n population.forEach(e => e.costs = computeCostFunction(computeGridMapMetricsWithGeoPairs(vectorToGridMap(e.gridMap),geoPairs)))\n return population\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":377,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1320,"value":"function idxToXY(idx) {\n let x = idx % (xmax+1)\n let y = (idx - x) / (xmax+1)\n return [x,y]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1322,"value":"function xyToIdx(x, y) {\n if (xxmax)\n x = xmax\n if (y>ymax)\n y = ymax\n return y*(xmax+1) + x\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":387,"value":"function orderPopulation(population) {\n return population.sort((a,b) => a.costs.cost - b.costs.cost)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":424,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":743,"value":"function generateMutatedPopulation(population, mutationNumber, mutationsPerMutatedElement) {\n let mutatedPopulation = []\n for (let i = 0; i < mutationNumber; i++) {\n mutatedPopulation.push(mutate(population[_.sample(_.range(0, population.length))], mutationsPerMutatedElement))\n }\n return mutatedPopulation\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":962,"value":"function removeDuplicates(population) {\n let duplicates = new Array(population.length).fill(false)\n let numDuplicates = 0\n for (let i=1; i