Basic Genetic Algorithm

by Scott Kaye

JavaScript

class Helpers {
	static randomProperty(obj) {
		let keys = Object.keys(obj);
		return keys[(Math.random() * keys.length)|0];
	}
}

class Population {
	constructor(initial) {
		this.initial = initial;
		this.chromosomes = [];
		this.elitism = 0.2;
		this.size = 10; // Minimum 10
		this.fill();
	};
	
	display() {
		let alpha = this.chromosomes[0];
		console.log("Done!", alpha, this.chromosomes);
		let actives = Object.keys(alpha.data).filter(key => alpha.data[key].active);
		console.log("Winning combination:", actives);
	};
	
	run() {
		let noImprovement = 0;
		let oldAlpha = 0;
		let threshold = 100;
		let i = 0;
		let limit = 500;
	
		while (noImprovement < threshold && ++i < limit) {
			oldAlpha = this.chromosomes[0].getFitness();
			this.generation();
			
			let newAlpha = this.chromosomes[0].getFitness();
			
			if (oldAlpha >= newAlpha) {
				++noImprovement;
			} else {
				noImprovement = 0;
			}
		}

		if (i === limit) {
			console.info("Stopping at the limit of", limit);
		}

		this.display();

		return this.chromosomes[0];
	};
	
	// Ensure chromosome pool is full
	fill() {
		while (this.chromosomes.length < this.size) {
			if (this.chromosomes.length < this.size / 3) {
				this.chromosomes.push(new Chromosome(Object.assign({}, this.initial)));
			} else {
				this.mate();
			}
		}
	};
	
	// Generation cycle
	generation() {
		this.sort();
		this.kill();
		this.mate();
		this.fill();
		this.sort();
	};
	
	// Create more chromosomes
	mate() {
		let key1 = Helpers.randomProperty(this.chromosomes);
		let key2 = key1;
		
		while (key1 === key2) {
			key2 = Helpers.randomProperty(this.chromosomes);
		}
		
		let children = this.chromosomes[key1].mateWith(this.chromosomes[key2]);
		this.chromosomes = this.chromosomes.concat(children);
	};
	
	// Kill weakest chromosomes
	kill() {
		let target = (this.elitism * this.chromosomes.length) | 0;
		this.chromosomes = this.chromosomes.splice(0, target);
	};
	
	// Sort by fitness
	sort() {
		this.chromosomes.sort((a, b) =>...