Last active
April 23, 2017 04:25
-
-
Save ebobby/7606ea926fa8db139668bfcdea2ac366 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * @author Francisco Soto <[email protected]> | |
| */ | |
| function Chromosome (genes, fitness) { | |
| this.genes = genes; | |
| this.fitness = fitness; | |
| } | |
| function Genetics (problem, options) { | |
| this.problem = problem; | |
| options = options || {}; | |
| this.options = { | |
| generations: options.generations || 1000, | |
| population_size: options.population_size || 100, | |
| mutation_chance: options.mutation_chance || 0.10, | |
| bias: options.bias || 2.0 | |
| }; | |
| this.pool = []; | |
| // Generate initial population | |
| for (var i = 0; i < this.options.population_size; i++) { | |
| var solution = this.problem.GenerateRandomSolution(), | |
| fitness = this.problem.CalculateFitness(solution); | |
| this.pool.push(new Chromosome(solution, fitness)); | |
| } | |
| this.pool.sort(this._compare); | |
| this.current_generation = 0; | |
| this.mutations = 0; | |
| } | |
| Genetics.prototype._compare = function(a, b) { | |
| if (a.fitness < b.fitness) return -1; | |
| else if (a.fitness > b.fitness) return 1; | |
| else return 0; | |
| }; | |
| /* _linear | |
| * random integer between 0 and input max number | |
| * using input linear bias | |
| * Ported from PostgreSQL's GA implementation | |
| */ | |
| Genetics.prototype._linear = function (pool_size, bias) { | |
| var index = | |
| pool_size * | |
| (bias - Math.sqrt((bias * bias) - 4.0 * (bias - 1.0) * Math.random())) / | |
| 2.0 / | |
| (bias - 1.0); | |
| return parseInt(index); | |
| }; | |
| Genetics.prototype._combine = function (mom, dad) { | |
| var first = this.pool[mom], | |
| second = this.pool[dad], | |
| size = first.genes.length, | |
| index = 0, | |
| tries = 0, | |
| new_genes = []; | |
| do { | |
| index = parseInt(Math.random() * size); | |
| tries++; | |
| } while (first.genes[index] > second.genes[index] && tries < 100); | |
| // If couldn't combine just return the best one | |
| if (tries == 100) { | |
| if (first.fitness < second.fitness) | |
| return first; | |
| else | |
| return second; | |
| } | |
| for (var i = 0; i <= index; i++) | |
| new_genes[i] = first.genes[i]; | |
| for (i = index + 1; i < size; i++) | |
| new_genes[i] = second.genes[i]; | |
| return new Chromosome(new_genes, this.problem.CalculateFitness(new_genes)); | |
| }; | |
| Genetics.prototype._insert = function (kid) { | |
| for (var i = 0; i < this.options.population_size; i++) { | |
| if (kid.fitness < this.pool[i].fitness) { | |
| // Insert the kid into the pool pushing every individual | |
| // less fit to the right. | |
| this.pool.splice(i, 0, kid); | |
| // The last element, the less fit of all, gets dropped. | |
| this.pool.splice(-1, 1); | |
| return; | |
| } | |
| } | |
| }; | |
| Genetics.prototype._selection = function () { | |
| // Selection of parents | |
| var mom = this._linear(this.options.population_size, this.options.bias), | |
| dad = this._linear(this.options.population_size, this.options.bias); | |
| while (mom == dad) { | |
| dad = this._linear(this.options.population_size, this.options.bias); | |
| } | |
| // New offspring | |
| return this._combine(mom, dad); | |
| }; | |
| Genetics.prototype.getBestSolution = function () { | |
| return this.pool[0].genes; | |
| }; | |
| Genetics.prototype.getBestFitness = function () { | |
| return this.pool[0].fitness; | |
| }; | |
| Genetics.prototype.getOverallFitness = function () { | |
| return this.pool.reduce( | |
| function (acc, ch) { | |
| return acc + ch.fitness; | |
| }, 0.0) / this.options.population_size; | |
| }; | |
| Genetics.prototype.getCurrentGeneration = function () { | |
| return this.current_generation; | |
| }; | |
| Genetics.prototype.getCurrentMutations = function () { | |
| return this.mutations; | |
| }; | |
| Genetics.prototype.step = function () { | |
| if (this.current_generation >= this.options.generations) | |
| return true; | |
| // "Natural" selection | |
| var kid = this._selection(); | |
| // Mutation | |
| if (Math.random() <= this.options.mutation_chance) { | |
| kid.genes = this.problem.GenerateNeighbor(kid.genes); | |
| kid.fitness = this.problem.CalculateFitness(kid.genes); | |
| this.mutations++; | |
| } | |
| // And gene dissemination | |
| this._insert(kid); | |
| this.current_generation++; | |
| return false; | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment