Angel \”Java\” Lopez on Blog

September 22, 2012

SimpleGA (1) Genetic Algorithms in Javascript/Node.js

Filed under: Algorithms, Genetic Algorithm, JavaScript, NodeJs, Open Source Projects — ajlopez @ 7:24 pm

Two week ago, I was writing:

https://github.com/ajlopez/SimpleGA

a Simple Genetic Algorithm base framework, that supports population, evaluation and mutator operators (I should add crossover operators). The base algorithm is based on

A Genetic Algorithm Tutorial (pdf)

You can create a population of genotypes, each one with an evaluation function. The library evaluates each genotypes and prepares another population, based on the value of each genotype, copying the best ones, and mutating some of the initial specimen based on fitness. The fitness value is v = fi / fa, where fi is the individual fitness evaluation, and fa is the fitness average. The integer part of v determines the count of copies of an individual that survives to the next generation. The fraction part is the probability of having a mutated copy in the next generation set of genotypes:

var newpopulation = [];

for (var k = 0; k < l; k++) {
	if (values[k] < 0)
		continue;
		
	var fitness = values[k] / total;
	
	if (fitness < 0)
		continue;
		
	var ntimes = Math.floor(fitness);
	var fraction = fitness - ntimes;
	
	for (var j = 0; j < ntimes; j++)
		newpopulation.push(population[k]);
		
	if (fraction > 0 && Math.random() <= fraction)
		newpopulation.push(population[k]);
}

if (mutators && mutators.length > 0) {
	l = newpopulation.length;
	var lm = mutators.length;
	
	for (k = 0; k < l; k++) {
		var mutator = mutators[Math.floor(Math.random() * lm)];
		newpopulation[k] = mutator.mutate(newpopulation[k]);
	}
}

(I should add crossover operator support). There is a sample implementing the Travelling Saleman Problem

https://github.com/ajlopez/SimpleGA/blob/master/samples/tsp/tsp.js

running in console using https://github.com/ajlopez/SimpleGA/blob/master/samples/tsp/program.js

It can run from the console, or you can launch a local web page:

https://github.com/ajlopez/SimpleGA/blob/master/samples/tsphtml/index.html

I wrote client/server version (web page at browser, Node.js server program) and a distributed version (the evaluation of many population running in many server nodes, coordinated by a Node.js server, showing results in a browser).

Next steps: add crossover operators, sample short descriptions, more samples.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

3 Comments »

  1. [...] week, I presented my distributed genetic algorithm example (Browser, JavaScript, Node.js, Socket.IO, TCP+JSON) at @udadev (see page). Now, more links about [...]

    Pingback by Genetic Algorithms: Links And Resources (2) « Angel ”Java” Lopez on Blog — November 8, 2012 @ 12:44 pm

  2. [...] working on my Node.js distributed examples (Genetic Algorithms), and my Python interpreter (Spanish Post, GitHub repo), I went back to work on AjTalk, my [...]

    Pingback by Working on AjTalk: Smalltalk VM, C# version « Angel ”Java” Lopez on Blog — November 29, 2012 @ 4:56 pm

  3. [...] de trabajar en ejemplos distribuidos con Node.js (ver Genetic Algorithms), y en mi intérprete Python en .NET (Post, GitHub repo), volví a trabajar en AjTalk, mi [...]

    Pingback by Trabajando de nuevo en on AjTalk: Smalltalk Virtual Machine, en C# - Angel "Java" Lopez — November 30, 2012 @ 4:18 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 56 other followers

%d bloggers like this: