2c:null 2d:["$","title",null,{"children":"Simple Genetic Algorithm | sw1227 | Observable"}] 32:T7bc,class Environment { constructor(population, fitness, crossProb=0.5, mutationProb=0.1, tournamentSize=3) { this.population = population; this.fitness = fitness; // Function of [Individual -> fitness value] this.crossProb = crossProb; this.mutationProb = mutationProb; this.sampler = createSampler(tournamentSize); } // List of fitnesses of all individuals in the environment get fits() { return this.population.map(p => this.fitness(p)); } // Update 1 generation update() { // Select offsprings based on their fitness const offspring = this.tournamentSelect(); // Crossover const males = offspring.slice(0, Math.floor(offspring.length / 2)); const females = offspring.slice(Math.floor(offspring.length / 2)); for (let [child1, child2] of d3.zip(males, females)) { if (Math.random() < this.crossProb) { this.twoPointMate(child1, child2); } } // Mutation for (let child of offspring) { if (Math.random() < this.mutationProb) { child.mutate(); } } this.population = [...offspring]; } // Select individuals with tournament tournamentSelect() { const selected = []; for (let i = 0; i < this.population.length; i++) { const sample = this.sampler(this.population); const fittest = d3.greatest( sample, (a, b) => this.fitness(a) - this.fitness(b) ); selected.push(fittest.clone()) } return selected; } // Mate individuals by 2-point crossover twoPointMate(ind1, ind2) { // Crossover points: random const r1 = Math.floor(Math.random() * (ind1.length + 1)); const r2 = Math.floor(Math.random() * (ind1.length + 1)); const [start, end] = [Math.min(r1, r2), Math.max(r1, r2)]; // Swap [start:end] of chromosome const tmp = ind1.chromosome.slice(start, end); ind1.replaceGene(start, ind2.chromosome.slice(start, end)); ind2.replaceGene(start, tmp); } }33:T62b,chart = { const height = 400; const margin = ({top: 20, right: 20, bottom: 30, left: 30}); const svg = d3.create("svg") .attr("viewBox", [0, 0, width, height]); // Scale const x = d3.scaleLinear() .domain(d3.extent(data, d => d.generation)) .range([margin.left, width - margin.right]); const y = d3.scaleLinear() .domain([0, d3.max(data, d => d.max)]).nice() .range([height - margin.bottom, margin.top]); // Axis const xAxis = g => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(x).ticks(width / 80).tickSizeOuter(0)); const yAxis = g => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y)) .call(g => g.select(".domain").remove()) .call(g => g.select(".tick:last-of-type text").clone() .attr("x", 3) .attr("text-anchor", "start") .attr("font-weight", "bold") .text(data.y)); svg.append("g") .call(xAxis); svg.append("g") .call(yAxis); // Area chart (min - max) const area = d3.area() .curve(d3.curveLinear) .x(d => x(d.generation)) .y0(d => y(d.min)) .y1(d => y(d.max)); svg.append("path") .datum(data) .attr("fill", "steelblue") .attr("fill-opacity", 0.3) .attr("d", area); // Line chart (mean) const line = d3.line() .x(d => x(d.generation)) .y(d => y(d.mean)); svg.append("path") .datum(data) .attr("fill", "none") .attr("stroke", "steelblue") .attr("stroke-width", 2) .attr("d", line); return svg.node(); }34:[] 30:{"id":"424e19694c395cf2","slug":"simple-genetic-algorithm","title":"Simple Genetic Algorithm","thumbnail":"761d45dda901f5634acb4876aa1123b314ffef21216e7ea274654dce5b5262a4","access_level":"public","create_time":"$D2020-09-12T03:49:38.978Z","update_time":"$D2020-09-12T06:45:45.911Z","view_time":null,"first_public_time":"$D2020-09-12T06:45:53.921Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"06475ae5027cde36","login":"sw1227","name":"sw1227","avatar_url":"https://avatars-next.observableusercontent.com/3e09ff2c49317e618eedc394f3b33dbb5c952acf0d9654683424e681e7857f8c","tier":"starter_2024","bio":"Vis / Geo / Generative / Simulation / AI / Math\n🥑\n\nPortfolio: https://sw1227.github.io/portfolio"},"version":380,"publish_version":380,"role":null,"authored":false,"authors":[{"type":"individual","id":"4a648b0bd17e2c08","login":"sw1227","name":"sw1227","avatar_url":"https://avatars-next.observableusercontent.com/3e09ff2c49317e618eedc394f3b33dbb5c952acf0d9654683424e681e7857f8c","tier":null,"bio":"Vis / Geo / Generative / Simulation / AI / Math\n🥑\n\nPortfolio: https://sw1227.github.io/portfolio"}],"members":[{"type":"individual","id":"4a648b0bd17e2c08","login":"sw1227","name":"sw1227","avatar_url":"https://avatars-next.observableusercontent.com/3e09ff2c49317e618eedc394f3b33dbb5c952acf0d9654683424e681e7857f8c","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"bf0b144b80365709","slug":"simulation","title":"Simulation","owner":{"id":"06475ae5027cde36","login":"sw1227","name":"sw1227"}},"type":"notebook","body":{"titling":"auto","title":"Simple Genetic Algorithm","cells":[{"id":0,"value":"md`# Simple Genetic Algorithm\n\nThis notebook provides a simple implementation of genetic algorithm.\n\nIn the latter half, [One max problem](https://deap.readthedocs.io/en/master/examples/ga_onemax.html) is solved using the implementation.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":198,"value":"md`## 1. Define individual\n\nFirst we define a class for individuals. Each individual has a chromosome, represented as an array of 0/1 value.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"class Individual {\n // Chromosome: array of 0/1\n constructor(size, mutationProb) {\n this.chromosome = [...Array(size)].map(d => Math.random() < 0.5 ? 1 : 0);\n this.mutationProb = mutationProb;\n }\n\n // Create new instance with the same attributes\n clone() {\n const copy = new Individual(this.chromosome.length, this.mutationProb);\n copy.chromosome = this.chromosome;\n return copy;\n }\n\n // Getter: length of chromosome\n get length() {\n return this.chromosome.length;\n }\n\n // Replace part of chromoseome with the given value\n replaceGene(start, values) {\n this.chromosome.splice(start, values.length, ...values);\n }\n \n // Random flip-bit mutation\n mutate() {\n this.chromosome = this.chromosome.map(d => (\n Math.random() < this.mutationProb ? 1 - d : d\n ));\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":201,"value":"md`## 2. Define environment\nNext, we define a class for environment where evolution happens.\n\nEnvironment has a population of individuals, and holds some parameters. Individuals create their offspring based on their fitness.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"// Creates a random sampling function given sample size\ncreateSampler = nSample => arr => {\n // Create and slice a shuffled copy of given array\n const shuffled = d3.shuffle([...arr]);\n return shuffled.slice(0, nSample);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":357,"value":"md`In this implementation, two-point crossover is used as crossover method.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":350,"value":"html`

$\"Computational.science.Genetic.algorithm.Crossover.Two.Point.svg\"$
CC BY-SA 3.0, Link

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"md`## 3. Execute\nNow let's run the genetic optimization of [One max problem](https://deap.readthedocs.io/en/master/examples/ga_onemax.html).\n\nSome parameter values are provided by the sliders in the next section.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":323,"value":"history = {\n const environment = new Environment(\n [...Array(population)].map(d => new Individual(100, mutationRate)),\n individual => 100 - d3.sum(individual.chromosome),\n crossProb,\n mutationProb,\n tournamentSize\n );\n\n const fits = []; // Save fitness of individuals in every generation\n for (let t = 0; t < maxGen; t++) {\n environment.update();\n fits.push(environment.fits)\n }\n\n return fits;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":335,"value":"// Calculate statistics of each generation\ndata = Object.assign(\n history.map((d, i) => ({\n generation: i,\n mean: d3.mean(d),\n min: d3.min(d),\n max: d3.max(d)\n })),\n {y: \"Fitness (min, max, mean)\"}\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":338,"value":"md`## 4. Visualize result\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":328,"value":"viewof population = {\n const form = html`\n`;\n form.i.oninput = () => form.o.value = `Population = ${form.value = form.i.valueAsNumber}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":250,"value":"viewof mutationRate = {\n const form = html`\n`;\n form.i.oninput = () => form.o.value = `Mutation Rate = ${form.value = form.i.valueAsNumber}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":308,"value":"viewof mutationProb = {\n const form = html`\n`;\n form.i.oninput = () => form.o.value = `Mutation Probability = ${form.value = form.i.valueAsNumber}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":265,"value":"viewof crossProb = {\n const form = html`\n`;\n form.i.oninput = () => form.o.value = `Crossover Probability = ${form.value = form.i.valueAsNumber}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":315,"value":"viewof tournamentSize = {\n const form = html`\n`;\n form.i.oninput = () => form.o.value = `Tournament Size = ${form.value = form.i.valueAsNumber}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"viewof maxGen = {\n const form = html`\n`;\n form.i.oninput = () => form.o.value = `Max generation = ${form.value = form.i.valueAsNumber}`;\n form.i.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":368,"value":"md`The graph below shows min/max/mean fitness (y-axis) at each generatation (x-axis).\n\nMove sliders above to see the change.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":373,"value":"md`#### import`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"d3 = require(\"d3@6\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 31:"$30:body"