class Individual {
// Chromosome: array of 0/1
constructor(size, mutationProb) {
this.chromosome = [...Array(size)].map(d => Math.random() < 0.5 ? 1 : 0);
this.mutationProb = mutationProb;
}
// Create new instance with the same attributes
clone() {
const copy = new Individual(this.chromosome.length, this.mutationProb);
copy.chromosome = this.chromosome;
return copy;
}
// Getter: length of chromosome
get length() {
return this.chromosome.length;
}
// Replace part of chromoseome with the given value
replaceGene(start, values) {
this.chromosome.splice(start, values.length, ...values);
}
// Random flip-bit mutation
mutate() {
this.chromosome = this.chromosome.map(d => (
Math.random() < this.mutationProb ? 1 - d : d
));
}
}
// Creates a random sampling function given sample size
createSampler = nSample => arr => {
// Create and slice a shuffled copy of given array
const shuffled = d3.shuffle([...arr]);
return shuffled.slice(0, nSample);
}
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);
}
}
history = {
const environment = new Environment(
[...Array(population)].map(d => new Individual(100, mutationRate)),
individual => 100 - d3.sum(individual.chromosome),
crossProb,
mutationProb,
tournamentSize
);
const fits = []; // Save fitness of individuals in every generation
for (let t = 0; t < maxGen; t++) {
environment.update();
fits.push(environment.fits)
}
return fits;
}
// Calculate statistics of each generation
data = Object.assign(
history.map((d, i) => ({
generation: i,
mean: d3.mean(d),
min: d3.min(d),
max: d3.max(d)
})),
{y: "Fitness (min, max, mean)"}
)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
