2e:null 2f:["$","title",null,{"children":"Evolving Tadpoles: Learning using Neural Networks coupled with Genetic Algorithms | Guillaume Calmettes | Observable"}] 34:T147a,md`## How do the tadpoles "think"? Each tadpole organism is controlled by a simple, fully connected neural network implemented using the [Tensorflow](https://www.tensorflow.org/) library. The input for the neural network of each tadpole consists of the spacial information its nearest particle: - how far on the x axis (horizontal) is the food particle (dx) - how far on the y axis (vertical) is the food particle (dy) This information is processed by a hidden layer consiting of 10 neurons, and the neural network then outputs two values scaled in the interval [-1, +1] that will dictate a change in velocity (acceleration/deceleration) in the x and y axis. Below is the diagram of the neural network that each tadpole is equipped with:
## Optimization of the neural network The "learning" process of a tadpole is based on the optimization of the weights of each of its neurons. Here, this optimization is not performed by backpropagation but using a genetic algoritmm approach instead. Genetic algorithms fall under the larger umbrella of evolutionaty algorithms and are designed to imitate the natural biological process of evolution: starting off with an initial population, and through selection, crossover, and mutations over many generations, an optimal solution emerges. Note that this approach does not guaranty to find the global minimum of our optimization problem, but given proper initial conditions they are in fact quite good at searching through the problem space and finding near optimal solutions. #### Selection The simplest form of selection is called elitism, and consits at carrying over to the next generation only the top n% performing individuals. #### Breeding/Crossover Using this pool of top individuals, new offsprings will be generated by randomly pairing two individuals. Several strategies are implemented here to create the new weights for the neurons of the offspring: - Weighted contribution: The neurons's weights of the offsprings are the result of a weighted contribution of the corresponding neuron of each parent. The weighted contribution of the parents is randomly picked for each layer. - Swapping neurons: Each neuron in a layer is a random pick of the corresponding neuron of either parents. - Neural layer crossover: Each layer of neurons of the offspring is the concatenation of the n first neurons of one parent and (layer length - n) last neurons of the other parent. The crossover point is randomly drawn for each layer of neurons. - Neuron's weights crossover: Each neuron in a layer is generated by crossover of the weights the corresponding neurons of both of its parents. The crossover point is randomly drawn for each neuron. #### Mutations After a new neural network is created for an offspring, random mutation of some of the weights are applied. This is vital as it allows to traverse the search space of the problem we are trying to optimize. The mutated values are randomly picked from a uniform distribution so that they'll still be within +/- 10% of the original value. This will create just a slight variation within the organism that could potentially lead to a fitter organism (or to a less fit organism ... but the variation is limited to +/- 10% to avoid catastrophic changes in the network that could be deletarious for our tadpole). `35:T80d,class Simulation { constructor(settings={}){ const { populationSize = 5, foodAmount = 30, worldWidth = 975, worldHeight = 500, foodParticlesRadius = 5, agentVMax = 3, } = settings const worldProps = { worldWidth, worldHeight, populationSize, foodAmount, foodParticlesRadius, agentVMax } this.world = new World(worldProps) this.ga = new GeneticAlgorithm(this.world.population) this.currentGeneration = 0 this.renderingEngine = null } *generation() { let i = 0; while (true) yield i++; } runStep(i=null, updatePeriod=10){ // run a single time step for (const t of this.world.population) { // Each agent process clues from environment and reacts t.updateHeading(i, updatePeriod) t.move() // if food particle get eaten if (t.getDistanceToNearestFood().get() < this.world.foodParticlesRadius) { t.fitness += t.nearestFood.energy t.nearestFood.respawn() this.world.computeDelaunay(this.width) this.renderingEngine && this.renderingEngine.updateDelaunayVoronoi() } // Agent moved (and environment could have changed) // so update nearest food let delaunay = this.world.delaunay let x = t.x.get() let y = t.y.get() // Use scaled position/voronoi displayed by renderingEngine if virtual world is rendered if ( this.renderingEngine ) { x = this.renderingEngine.xScale(t.x.get()) y = this.renderingEngine.yScale(t.y.get()) delaunay = this.renderingEngine.delaunay } t.nearestFood = this.world.foodReserve[delaunay.find(x, y)] } } runManySteps(n){ // run multiples time steps for (let i=0; id.x.get(), d=>d.y.get()) this.voronoi = this.computeVoronoi(worldWidth) // this.computeDelaunay(sceneWidth) this.initFoodSearch() } /////////////////////////////// // Initialization functions /////////////////////////////// createPopulation(n){ const self = this return [...new Array(n)].map(d => new Tadpole({world: self})) } createFoodReserve(n){ const self = this return [...new Array(n)].map(d => new Food({world: self})) } initFoodSearch(){ // make agents aware of their closest food particle this.population.forEach(d => d.nearestFood = this.foodReserve[this.delaunay.find(d.x.get(), d.y.get())] ) } computeVoronoi(currentWidth=this.width, currentHeight=this.height){ return this.delaunay.voronoi([0, 0, currentWidth, currentHeight]) } computeDelaunay(currentWidth=this.width, currentHeight=this.height){ this.delaunay = d3.Delaunay.from( this.foodReserve, d=>d.x.get(), d=>d.y.get() ) this.voronoi = this.delaunay.voronoi([0, 0, currentWidth, currentHeight]) } }37:T1549,class Tadpole { constructor(props={}) { const { world = {width: 500, height: 500, agentVMax: 3}, weights=null, x, y, vx, vy } = props this.world = world this.x = x || tf.tidy(() => tf.randomUniform([]).mul(world.width)) // position (x) this.y = y || tf.tidy(() => tf.randomUniform([]).mul(world.height)) // position (y) this.vx = vx || tf.tidy(() => tf.randomUniform([], -1, 1).mul(world.agentVMax)) // velocity (x direction) this.vy = vy || tf.tidy(() => tf.randomUniform([], -1, 1).mul(world.agentVMax)) // velocity (y direction) this.fitness = 0 // fitness (food count) this.nearestFood = null // nearest food particle // for swimming behavior this.px = new Array(10).fill(Math.random() * world.width), this.py = new Array(10).fill(Math.random() * world.height) this.count = 0 // utilities tensors to prevent recreation each time this.utils = { move: { xMin: tf.tidy(() => tf.zeros([])), xMax: tf.tidy(() => tf.ones([]).mul(world.width)), yMin: tf.tidy(() => tf.zeros([])), yMax: tf.tidy(() => tf.ones([]).mul(world.height)) }, } ////////////////////////////////////////////////////// // simple multilayer perceptron as brain // 1 variables as input (angle to nearest food) // 1 hidden layer with n perceptrons // output layer with 2 perceptrons (change in vx, change in vy) ////////////////////////////////////////////////////// this.brainStructure = [2, 10, 2] this.brain = this.buildModel(this.brainStructure) if (simStart == 'trained') this.loadTrainedWeights() if (weights) { // assign given weights to brain weights.forEach((w,i) => { this.brain.weights[i] = this.brain.weights[i].write(w) }) } } /////////////////////////////// // The brain!!! /////////////////////////////// buildModel([input, ...layers]){ // declare sequential model const model = tf.sequential(); model.add(tf.layers.dense({ units: layers[0], inputShape: [input], activation: 'tanh', // biasInitializer: tf.initializers.randomUniform({minval: -1, maxval: 1}) })) layers.slice(1).forEach(layer => model.add(tf.layers.dense({ units:layer, activation: 'tanh', // biasInitializer: tf.initializers.randomUniform({minval: -1, maxval: 1}) })) ) // prepare the model for training: Specify the loss and the optimizer. model.compile({optimizer: 'sgd', loss: 'meanSquaredError', lr: 0.1}) return model } think(){ // process the input information and return an action return tf.tidy(() => { const input = this.getXYDistancesToNearestFood() // 2 inputs, dx/dy return this.brain.predict(input) }) } loadTrainedWeights(){ // load saveWeights and mutates them randomly so every agent is a bit different const trainedWeights = savedModel.getWeights() .map(w => { const ga = new GeneticAlgorithm() return ga.mutate(w, {mutationThreshold:0.2, mutationChangeVariance:0.1}) }) this.setWeights(trainedWeights) } /////////////////////////////// // Utilities functions /////////////////////////////// move(){ this.x = tf.tidy(() => { let newX = this.x.add(this.vx) // ensure x is in space boundaries newX = newX.where(newX.greater(0), this.utils.move.xMin) newX = newX.where(newX.less(this.world.width), this.utils.move.xMax) return newX }) this.y = tf.tidy(() => { let newY = this.y.add(this.vy) // ensure x is in space boundaries newY = newY.where(newY.greater(0), this.utils.move.yMin) newY = newY.where(newY.less(this.world.height), this.utils.move.yMax) return newY }) } updateHeading(i, updatePeriod=10){ if (i % updatePeriod == 0) { const [newvx, newvy] = tf.tidy(()=> { const action = this.think() const dv = action.mul(this.world.agentVMax) let response = tf.stack([this.vx, this.vy]).add(dv) return response.split(2, 1) }) // ensure the new velocities are within vMax boundaries this.vx = tf.tidy(() => tf.scalar(newvx.get(0, 0) % this.world.agentVMax)) this.vy = tf.tidy(() => tf.scalar(newvy.get(0, 0) % this.world.agentVMax)) } } getDistanceToNearestFood(){ return tf.tidy(() => { const distance = tf.sqrt( tf.add( tf.square(this.x.sub(this.nearestFood.x)), tf.square(this.y.sub(this.nearestFood.y)) ) ) return distance }) } getXYDistancesToNearestFood(){ return tf.tidy(() => { let dx = this.nearestFood.x.sub(this.x) let dy = this.nearestFood.y.sub(this.y) return tf.stack([dx, dy]).reshape([1, 2]) // need shape [1, 2] as input for brain }) } setWeights(weights){ weights.forEach((w,i) => { this.brain.weights[i] = tf.tidy(() => this.brain.weights[i].write(w)) }) } resetParameters(relocate=false){ this.fitness = 0 this.vx = tf.tidy(() => tf.randomUniform([], -1, 1).mul(this.world.agentVMax)) this.vy = tf.tidy(() => tf.randomUniform([], -1, 1).mul(this.world.agentVMax)) if (relocate) { this.x = tf.tidy(() => tf.randomUniform([]).mul(this.world.width)) this.y = tf.tidy(() => tf.randomUniform([]).mul(this.world.height)) } } }38:T2d98,class GeneticAlgorithm { constructor(population){ this.population = population } // evolves the population by performing selection, crossover and mutations on the units evolvePopulation(opts={}){ const {keepTop=0.4, type='NeuronSwap'} = opts if (keepTop * this.population.length >=2) { const elites = this.getElites({keepTop:keepTop}) console.log( `## Average fitness of generation:`, this.population.map(agent => agent.fitness).reduce((a, b) => a + b )/this.population.length ) console.log( `## Average fitness of elites:`, elites.map(agent => agent.fitness).reduce((a, b) => a + b )/elites.length ) const elitesWeights = elites.map(elite => elite.brain.getWeights()) // maintain population size const numberOfOffsprings = this.population.length - elites.length const offspringsWeigths = this.generateOffspringsWeightsFrom(elites, numberOfOffsprings, type) const newGenerationWeights = [...elitesWeights, ...offspringsWeigths] this.population.forEach((agent, i) => { agent.setWeights(newGenerationWeights[i]) // reset fitness and redistribute agent randomly in plane agent.resetParameters() }) } } drawRandomUniform (min, max) { return Math.random() * (max - min) + min } // selects the best units from the current population getElites(opts={}){ const { keepTop=0.4 } = opts const nToKeep = Math.floor(keepTop*this.population.length) const top = this.population .map((agent, i) => ([i, agent.fitness])) .sort((a,b) => b[1] - a[1]) .map(d => this.population[d[0]]) return top.slice(0, nToKeep) } generateOffspringsWeightsFrom(group, n, type='NeuronSwap'){ const size = group.length const offspringsWeigths = [] // generate a mutation form top two elites let offspringTopTwo = this.generateNewWeigthsFrom(group[0], group[1], type) offspringTopTwo = offspringTopTwo.map(w => this.mutate(w)) offspringsWeigths.push(offspringTopTwo) for (let i=0; i Math.floor(Math.random()*size)) while (indices[0] == indices[1]){ indices = [...new Array(2)].map(d => Math.floor(Math.random()*size)) } let newWeights = this.generateNewWeigthsFrom(group[indices[0]], group[indices[1]], type) // randomly mutate some weights newWeights = newWeights.map(w => this.mutate(w, {mutationThreshold:0.2, mutationChangeVariance:0.1})) offspringsWeigths.push(newWeights) } return offspringsWeigths } generateNewWeigthsFrom(parent1, parent2, type='NeuronSwap') { let generatedWeights switch (type) { case 'WeightedContribution': // Each neuron's weights/biases is the result of a weighted // contribution of the corresponding neuron of each parent. // The contribution factor is randomly picked for each layer. generatedWeights = tf.tidy(() => { const p1Layers = parent1.brain.getWeights() const p2Layers = parent2.brain.getWeights() const offspringLayers = p1Layers.map((p1Layer, i) => { const p2Layer = p2Layers[i] // random contribution of each parent // (their contribution weights adds to 1) const p1ContributionWeight = Math.random() const p2ContributionWeight = 1 - p1ContributionWeight const p1Contribution = p1Layer.mul(p1ContributionWeight) const p2Contribution = p2Layer.mul(p2ContributionWeight) return p1Contribution.add(p2Contribution) }) return offspringLayers }) break; case 'LayerCrossOver': // Each layer of neurons is the result of the n first neurons of one parent // and (layer length - n) last neurons of the other parent. // The crossover point is randomly drawn for each layer. generatedWeights = tf.tidy(() => { const p1Layers = parent1.brain.getWeights() const p2Layers = parent2.brain.getWeights() const offspringLayers = p1Layers.map((p1Layer, i) => { const p2Layer = p2Layers[i] // randomly choose which parent will give its neuron to each part of the resulting layer const pLayers = Math.random() < 0.5 ? [p1Layer, p2Layer] : [p2Layer, p1Layer] const layerShape = p1Layer.shape if (layerShape.length == 1) { // those are biases // Choose an index to cut the layer of neurons at const idx = Math.floor(Math.random()*layerShape[0]) const layerPart1 = pLayers[0].slice(0, idx) const layerPart2 = pLayers[1].slice(idx) return tf.concat([layerPart1, layerPart2]) } else if (layerShape.length == 2) { // Choose an index to cut the layer of neurons at const idx = Math.floor(Math.random()*layerShape[1]) const layerPart1 = pLayers[0].slice([0, 0], [layerShape[0], idx]) const layerPart2 = pLayers[1].slice([0, idx], [layerShape[0], layerShape[1]-idx]) return tf.concat([layerPart1, layerPart2], 1) } }) return offspringLayers }) break; case 'NeuronSwap': // Each neuron in a layer is a random pick of the corresponding neuron of either parents generatedWeights = tf.tidy(() => { const p1Layers = parent1.brain.getWeights() const p2Layers = parent2.brain.getWeights() const offspringLayers = p1Layers.map((p1Layer, i) => { const p2Layer = p2Layers[i] const pLayer = [p1Layer, p2Layer] const layerShape = p1Layer.shape if (layerShape.length == 1) { // those are biases // for each index, randomly pick either one parents neuron const neurons = [...new Array(layerShape[0])].map((d,i) => { const pickedParent = Math.random() < 0.5 ? 0 : 1 return pLayer[pickedParent].slice([i], [1]) }) return tf.concat([...neurons]) } else if (layerShape.length == 2) { // for each index, randomly pick either one parents neuron const neurons = [...new Array(layerShape[1])].map((d,i) => { const pickedParent = Math.random() < 0.5 ? 0 : 1 return pLayer[pickedParent].slice([0, i], [layerShape[0], 1]) }) return tf.concat([...neurons], 1) } }) return offspringLayers }) break; case 'NeuronCrossOver': // Each neuron in a layer is the result of the n first weights of the corresponding neuron // of one parent and (neuron weights length - n) last weights of the corresponding neuron // of the other parent. // The crossover point is randomly drawn for each neuron. generatedWeights = tf.tidy(() => { const p1Layers = parent1.brain.getWeights() const p2Layers = parent2.brain.getWeights() const offspringLayers = p1Layers.map((p1Layer, i) => { const p2Layer = p2Layers[i] const pLayer = [p1Layer, p2Layer] const layerShape = p1Layer.shape if (layerShape.length == 1) { // those are biases // because there is only one variable for each weight, pick // randomly either one parents neuron bias at each index const neurons = [...new Array(layerShape[0])].map((d,i) => { const pickedParent = Math.random() < 0.5 ? 0 : 1 return pLayer[pickedParent].slice([i], [1]) }) return tf.concat([...neurons]) } else if (layerShape.length == 2) { // for each index, construct a neuron by crossovering weights const neurons = [...new Array(layerShape[1])].map((d,i) => { const p1Weights = p1Layer.slice([0, i], [layerShape[0], 1]) const p2Weights = p2Layer.slice([0, i], [layerShape[0], 1]) // randomly choose which parent will give its weights to each part of the resulting neuron const pWeighs = Math.random() < 0.5 ? [p1Weights, p2Weights] : [p2Weights, p1Weights] // Pick an index to cut the weighs array at const idx = Math.floor(Math.random()*layerShape[0]) const neuronWeightsPart1 = pWeighs[0].slice([0, 0], [idx, 1]) // there is only one col (nx1) const neuronWeightsPart2 = pWeighs[1].slice([idx, 0], [layerShape[0]-idx, 1]) return tf.concat([neuronWeightsPart1, neuronWeightsPart2], 0) }) return tf.concat([...neurons], 1) } }) return offspringLayers }) break; } return generatedWeights } // performs random mutations on the offspring mutate(weights, opts={}){ const {mutationThreshold=0.2, mutationChangeVariance=0.1} = opts const mutate = Math.random() < mutationThreshold let finalWeights = weights if (mutate) { finalWeights = tf.tidy(() => { // The mutated weights are a copy of the weights in which a specific location // is multiplied by a factor in the interval [1-mutationVariance, 1+mutationVariance]. // A safety check at the end ensure that the weights are capped // to [-1, 1] after mutation. // the change in value that will be applied at the mutation point let mutationChange = this.drawRandomUniform(1-mutationChangeVariance, 1+mutationChangeVariance) // construct multiplier tensor. Multiplier shape = weights shape. // Multiplier is filled with ones, except for a randomly drawn coordinate // for which it's filled with the mutation change. let multiplierCoefs const shape = weights.shape if (shape.length == 1) { // those are biases (1 dimension, [n]) // random coordinate x to mutate const mutIdx = Math.floor(Math.random()*shape[0]) // construct multiplier tensor multiplierCoefs = [...new Array(shape[0])].map((d, i) =>( i == mutIdx ? mutationChange : 1 )) } else if (shape.length == 2) { // those are weights (2 dimensions, [m x n]) // random coordinate [x, y] to mutate const mutRow = Math.floor(Math.random()*shape[0]) const mutCol = Math.floor(Math.random()*shape[1]) // construct the multiplier tensor multiplierCoefs = [...new Array(shape[0])].map((d, i) => { const row = [...new Array(shape[1])].fill(1) if (i == mutRow) row[mutCol] = mutationChange return row }) } const multiplierTensor = tf.tensor(multiplierCoefs, shape) let mutatedWeights = weights.mul(multiplierTensor) // ensure weights are in interval [-1, 1] const lowLim = tf.onesLike(weights).mul(-1) const highLim = tf.onesLike(weights) mutatedWeights = mutatedWeights.where(mutatedWeights.greater(-1), lowLim) mutatedWeights = mutatedWeights.where(mutatedWeights.less(1), highLim) return mutatedWeights }) } return finalWeights } }39:T14b9,class RenderingEngine { constructor(props={}){ const { simulation=new Simulation(), canvas: { xScale, yScale, canvasWidth=975, canvasHeight=500 }, agents: { head=true, body=true, tail=true }, } = props this.context = this.initializeContext(canvasWidth, canvasHeight) this.simulation = simulation this.world = simulation.world this.canvasDimensions = [canvasWidth, canvasHeight] this.xScale = xScale ? xScale : d3.scaleLinear().domain([0, this.world.width]).range([0, canvasWidth]) this.yScale = yScale ? yScale : d3.scaleLinear().domain([0, this.world.height]).range([0, canvasHeight]) this.delaunay = this.computeDelaunay() this.voronoi = this.computeVoronoi() this.drawingSettings = { agents: { head, body, tail } } } ///////////////////////////////////////// // Drawing functions ///////////////////////////////////////// renderScene(props={}){ const { centroidsColor='#00BFFF', voronoiColor='#ccc' } = props this.context.clearRect(0, 0, this.canvasDimensions[0], this.canvasDimensions[1]); if (displayOptions.includes("v")) this.renderVoronoi(voronoiColor); this.renderPoints(centroidsColor) this.renderAllAgents() } renderPoints(color='#00BFFF'){ // draw centroids of voronoi this.context.beginPath(); this.delaunay.renderPoints(this.context, this.world.foodParticlesRadius); this.context.fillStyle = color this.context.fill(); } renderVoronoi(color='#ccc'){ // draw voronoi tessellation this.context.beginPath(); this.voronoi.render(this.context); this.context.strokeStyle = color; this.context.lineWidth = 1 this.context.stroke(); } /////////////////////////////// // Agents /////////////////////////////// renderAgent(agent) { const x = this.xScale(agent.x.get()) const y = this.yScale(agent.y.get()) let xtemp = x let ytemp = y let dx = agent.vx.get() let dy = agent.vy.get() let speed if (this.drawingSettings.agents.body || this.drawingSettings.agents.tail){ speed = Math.sqrt(dx * dx + dy * dy) const count = speed * 10; const k1 = -5 - speed / 3; // Swim! for (let i = 0; i < agent.px.length; ++i) { const vx = xtemp - agent.px[i]; const vy = ytemp - agent.py[i]; const k2 = Math.sin(((agent.count += count) + i * 3) / 300) / speed; agent.px[i] = (xtemp += dx / speed * k1) - dy * k2; agent.py[i] = (ytemp += dy / speed * k1) + dx * k2; speed = Math.sqrt((dx = vx) * dx + (dy = vy) * dy); } } if (this.drawingSettings.agents.head){ this.context.beginPath(); const angle = tf.tidy(()=> tf.atan2(agent.vy.get(), agent.vx.get())) this.context.ellipse(x, y, 6.5, 4.5, angle.get(), 0, 2 * Math.PI); this.context.fillStyle="black" this.context.fill(); } if (this.drawingSettings.agents.body){ this.context.strokeStyle="black" this.context.beginPath(); this.context.moveTo(x, y); for (let i = 1; i < 3; ++i) this.context.lineTo(agent.px[i], agent.py[i]); this.context.lineWidth = 4; this.context.stroke(); } if (this.drawingSettings.agents.tail){ this.context.beginPath(); this.context.moveTo(x, y); for (let i = 1; i < agent.px.length; ++i) this.context.lineTo(agent.px[i], agent.py[i]); this.context.lineWidth = 2; this.context.stroke(); } if (displayOptions.includes("t")){ // angle to nearest food const theta = this.getAngleToNearestFood(agent, x, y) const angleCos = Math.cos(theta) const angleSin = Math.sin(theta) const length = 50 this.context.beginPath(); this.context.moveTo(x, y) this.context.strokeStyle="#FF8B22" this.context.lineWidth=1 this.context.lineTo(x + length * angleCos, y + length * angleSin) this.context.stroke() } } renderAllAgents(){ for (const a of this.world.population) { this.renderAgent(a) } } ///////////////////////////////////////// // Utility functions ///////////////////////////////////////// extractPointsFrom(delaunay){ return delaunay.points.reduce((acc, cur, i) => { i%2 == 0 ? acc.push([cur]) : acc[acc.length-1].push(cur) return acc }, []) } initializeContext(cWidth, cHeight){ // Initialize canvas const context = DOM.context2d(cWidth, cHeight); context.lineJoin = "round"; context.lineCap = "round"; return context } computeDelaunay(){ return d3.Delaunay.from( this.extractPointsFrom(this.world.delaunay), d=>this.xScale(d[0]), d=>this.yScale(d[1]) ) } computeVoronoi(){ return this.delaunay.voronoi([0, 0, this.canvasDimensions[0], this.canvasDimensions[1]]) } updateDelaunayVoronoi(){ this.delaunay = this.computeDelaunay() this.voronoi = this.computeVoronoi() } getAngleToNearestFood(agent, x, y){ const foodX = this.xScale(agent.nearestFood.x.get()) const foodY = this.yScale(agent.nearestFood.y.get()) return Math.atan2(foodY-y, foodX-x) } }3a:[] 32:{"id":"b38b51d1daa132c2","slug":"evolging-tadpoles-learning-using-neural-networks-coupled","title":"Evolving Tadpoles: Learning using Neural Networks coupled with Genetic Algorithms","thumbnail":"d5dd38bdd190febcc1b3a9b79030272b83baa6cc8fd5758a316e61098fed4316","access_level":"public","create_time":"$D2018-11-28T17:05:55.782Z","update_time":"$D2020-01-21T15:39:31.890Z","view_time":null,"first_public_time":"$D2018-12-03T02:43:15.568Z","has_unpublished_edits":null,"fork":false,"stars":33,"starred":false,"owner":{"type":"team","id":"7a9467e213647138","login":"gcalmettes","name":"Guillaume Calmettes","avatar_url":"https://avatars-next.observableusercontent.com/426c6f918b9c27504cf041e6b11d867612a06eb087c9a72becdd7c7e9edcf4b8","tier":"starter_2024"},"version":3624,"publish_version":3624,"role":null,"authored":false,"authors":[{"type":"individual","id":"55eb667a3cdd700b","login":"gcalmettes","name":"Guillaume Calmettes","avatar_url":"https://avatars-next.observableusercontent.com/426c6f918b9c27504cf041e6b11d867612a06eb087c9a72becdd7c7e9edcf4b8","tier":null}],"members":[{"type":"individual","id":"55eb667a3cdd700b","login":"gcalmettes","name":"Guillaume Calmettes","avatar_url":"https://avatars-next.observableusercontent.com/426c6f918b9c27504cf041e6b11d867612a06eb087c9a72becdd7c7e9edcf4b8","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":14,"collection":null,"type":"notebook","body":{"title":"Evolving Tadpoles: Learning using Neural Networks coupled with Genetic Algorithms","cells":[{"id":0,"value":"md`# Evolving Tadpoles: Learning using Neural Networks coupled with Genetic Algorithms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3583,"value":"md`This notebook intents to equip [@mbostock's Tadpoles](https://beta.observablehq.com/@mbostock/tadpoles) with a \"brain\" to explore their environment and collect food particles.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3350,"value":"viewof simStart = radio({\n title: 'Start a new simulation:',\n // description: 'Please select how you want the simulation to be initialized',\n options: [\n { label: 'Using a pre-trained model', value: 'trained' },\n { label: 'From scratch', value: 'scratch' },\n ],\n value: 'trained'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3414,"value":"viewof evolutionStrategy = radio({\n title: 'Evolution strategy:',\n description: 'Which genetic algorithm strategy to use to breed the new generation (see description below)',\n options: [\n { label: 'Weighted contribution', value: 'WeightedContribution' },\n { label: 'Swapping neurons', value: 'NeuronSwap' },\n { label: \"Neural layer's neurons crossover\", value: 'LayerCrossOver' },\n { label: \"Neuron's weights crossover\", value: 'NeuronCrossOver' }\n ],\n value: 'NeuronSwap'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3365,"value":"viewof displayOptions = checkbox({\n title: 'Rendering options',\n options: [\n { value: 'v', label: 'Show voronoi' },\n { value: 't', label: \"Show targeted particle\" },\n ],\n value: ['v']\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3161,"value":"currentGeneration = {\n while (true) {\n yield md`## Current generation: ${simulation.currentGeneration}`\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"scene = {\n \n // Initialize a new renderingEngine for the simulation\n const renderingEngine = new RenderingEngine({\n simulation: simulation, \n canvas: {canvasWidth:width, canvasHeight:500},\n agents: {}\n })\n // Bind renderingEngine to simulation.\n // This is needed for correct computation of agent's nearest food\n // since voronoi tessellation of rendering engine is different than \n // the one of the virtual world in the simulation\n simulation.renderingEngine = renderingEngine\n \n let i=0\n while (true) {\n i += 1\n simulation.runStep(i, 8)\n renderingEngine.renderScene({ centroidsColor: '#ce4ad0', voronoiColor: '#ccc' })\n \n // evolve population\n if (i%1200 == 0 ) {\n // New generation based on 40% top performers\n // Options to create new generation: WeightedContribution/LayerCrossOver/NeuronSwap/NeuronCrossOver\n simulation.evolvePopulation({keepTop:0.4, type: evolutionStrategy})\n }\n \n yield renderingEngine.context.canvas\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3580,"value":"simulation = {\n const settings = {\n populationSize: (simStart == 'trained') ? 6 : 10, \n foodAmount: 30,\n foodParticlesRadius: 5,\n agentVMax: 2,\n }\n return new Simulation(settings)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3427,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2632,"value":"md`## Simulation Classes`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2648,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":735,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"class Food {\n constructor(props={}){\n const { world = {width: 500, height: 500}, x, y } = props\n this.world = world\n this.x = x || this.randomizeX()\n this.y = y || this.randomizeY()\n this.energy = 1\n }\n \n randomizeX(){\n return tf.tidy(() => tf.randomUniform([]).mul(this.world.width))\n }\n \n randomizeY(){\n return tf.tidy(() => tf.randomUniform([]).mul(this.world.height))\n }\n \n respawn(){\n this.x = this.randomizeX()\n this.y = this.randomizeY()\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1022,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2751,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":265,"value":"md`## Imports and utils`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3329,"value":"downloadBest = {\n const best = simulation.world.population.reduce((curr, val, i) => {\n return val > curr[1] ? [i, val] : curr\n }, [0, 0])[0]\n const element = html``;\n element.onclick = () => {\n simulation.world.population[best].brain.save('downloads://')\n };\n return element;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3348,"value":"savedModel = tf.loadModel('https://raw.githubusercontent.com/gcalmettes/ls40-slides/master/content/rdm/model.json')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3351,"value":"import { radio } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2565,"value":"import {checkbox} from \"@jashkenas/inputs\"\n// checkbox = ({label = '', value = false} = {}) => {\n// let wrapper = html``\n// let check = html``\n// wrapper.append(check)\n// wrapper.append(label || '')\n \n// check.checked = value\n \n// check.addEventListener('change', (e) => {\n// wrapper.value = check.checked\n// wrapper.dispatchEvent(new CustomEvent('input'))\n// })\n \n// // we need to have a starting value\n// wrapper.value = check.checked\n \n// return wrapper\n// }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":262,"value":"d3 = {\n const delaunay = await require(\"d3-delaunay@4\")\n const scale = await require(\"d3-scale\")\n const { scaleLinear } = scale\n return { ...delaunay, scaleLinear }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"// tf = require('@tensorflow/tfjs')\ntf = require('@tensorflow/tfjs@0.13')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3a","stdlib":"1","titling":"auto"}} 33:"$32:body"