Skip to content

Instantly share code, notes, and snippets.

@ebobby

ebobby/genetic.js

Last active April 23, 2017 04:25
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ebobby/7606ea926fa8db139668bfcdea2ac366 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ebobby/7606ea926fa8db139668bfcdea2ac366 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ebobby revised this gist Apr 23, 2017. 1 changed file with 13 additions and 2 deletions.
    15 changes: 13 additions & 2 deletions genetic.js
    View file
    Original file line number Diff line number Diff line change
    @@ -87,8 +87,12 @@ Genetics.prototype._combine = function (mom, dad) {

    Genetics.prototype._insert = function (kid) {
    for (var i = 0; i < this.options.population_size; i++) {
    if (kid.fitness <= this.pool[i].fitness) {
    this.pool[i] = kid;
    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;
    }
    }
    @@ -114,6 +118,13 @@ 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;
    };
  2. ebobby created this gist Apr 22, 2017.
    146 changes: 146 additions & 0 deletions genetic.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,146 @@
    /**
    * @author Francisco Soto <ebobby@gmail.com>
    */

    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) {
    this.pool[i] = kid;
    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.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;
    };