Evolutionary algorithms In the browser and in the server and multi-threaded and everywhere

Por JJ Merelo

FOSDEM 2014

`cc-by-sa` license; get it from `http://goo.gl/lJ0909`

I love tea

I wanted to make the best tea ever

Chose four different base teas: Keemun Congou, Maud, Golden Yunnan and Kandy

And started to mix and match

Using different recipes

I took notes and scored them

Until I found OpenTea

I liked it well enough

But you can't beat hundreds of years of tea-growing

Evolution works by random changes and natural selection

Image by Jared Zimmerman, taken from Darwin's book

And we can use that as an inspiration to solve search and optimization problems

Image by Jared Zimmerman, taken from Darwin's book

Like finding the best bridge structure

Image by Johannes Bader, from his PhD Thesis

First key is random variation: use a population of possible solutions

Image by Matt Kowal

Random mutation introduces more variations

11111111000000001111111100000000

But that's a mutie!

Mutant dog, check out origin at 374791126_f18089a883_b.jpg

Population-based mutation is not much better than random search

It takes you nowhere, and does so very slowly

Is sex still on the table?

11111111000000001111111100000000

00000000111111110000000011111111

It's a blind watchmaker

Crossover creates genetic variability and combines solutions

But who's the king of the hill?

Originally by 14517351_a0efb34914_b_d.jpg

Every individual is evaluated and assigned a fitness. Only the fittest survive

Unfit for JavaScript. Will not survive even if the Red Bull dose is increased.

To every one its own

Only the fittest leave a mark

Let's see how all this plays together

Check it out at http://goo.gl/yXpcKG

Evolution is not forever

(function do_ea() {
	eo.generation();
	generation_count++;
	if ( (generation_count % 100 === 0) ) {
           do_periodic_stuff()
	}
	if( (eo.fitness_of[eo.population[0]] < traps*conf.fitness.b ) 
	    && ( generation_count*conf.population_size < conf.max_evaluations)) {
	    setTimeout(do_ea, 5);
	} else {
	    we_are_done();
	}
    })();

Why would I want anything evolved in the browser?

Same reason you want anything done in the browser

Offload server
Distribute computational loads
Interact with user

Newspaper layout optimization

Jorge González, Juan J. Merelo Guervós, Pedro A. Castillo Valdivieso, Víctor Manuel Rivas Santos, Gustavo Romero: Optimizing Web Newspaper Layout Using Simulated Annealing. IWANN (2) 1999: 759-768

Volunteer || unwitting computation

With button: volunteer. Without: unwitting

Get the browser to compute stuff and send it via XHR to the server.
Send with response more stuff to compute.
Do it until the experiment is finished.

How many users can you get?

Merelo-Guervós, J. J., Castillo, et al. Asynchronous distributed genetic algorithms with Javascript and JSON. In IEEE Congress on Evolutionary Computation, 2008 pp. 1372-1379. IEEE.

Server pains

First version of node.js in 2009. We had SpiderMonkey, but not the same.

Further versions using FluidDB and CouchDB. Not bad, but not excellent. Main problem, dealing with latency

Fast forward to 2014

Available at http://github.com/JJ/nodeo (+ experimental data)

And we also have MOOTools

jsEO is an object-oriented implementation of an evolutionary algorithm using MooTools

var jsEOGA = new Class({
    Extends: jsEOAlgorithm, /** more stuff after this **/
    privateRun: function(_fitFn, _numGenerations, _showing) {
        var popSize = this.population.length();
        this.population.sort();
        for (var j = 0; (j < _numGenerations); ++j) {
            var newPop = this.indivSelector.operate(this.population);
            for (var i = 0; i < newPop.length(); ++i) {
                var tmpPop = new jsEOPopulation();
                tmpPop.add(newPop.getAt(i)).join(newPop);
                tmpPop = this.operSelector.
                        operate().
                        operate(tmpPop).
                        evaluate(_fitFn);
                newPop.setAt(i, tmpPop.getAt(0));
            }
            this.population.join(newPop).sort().crop(popSize);
            if (typeof this.opSend != 'undefined' && this.opSend != null) {
                this.opSend.operate(this.population);
            }
        } //for numGenerations
    },
    run: function() {
        this.privateRun();
    }
});

Code @http://git.io/jseo by @vrivas.

But we need to put evolutionary algorithms to REST


do {
  eo.generation();
  generation_count++;
} while ( eo.not_finished() && eo.current_run());
if ( conf.peers ) {
    var peer_url = conf.peers[ Math.floor(Math.random()*conf.peers.length )];
	rest.get( peer_url+"/best" ).on('success', function(result) {
           eo.incorporate( result.chromosome );
      });
    }
    total_generations += generation_count;
    if ( eo.way_to_go()  ) {
	setImmediate( generations );
    } else {
        eo.we_re_done();
	process.exit();
    }

I want to be just a client

    generation_count++;
    eo.generation();
    if ( generation_count % conf.generation_run === 0 ) {
	rest.put( pool_url+"/one/" + eo.population[0])
	    .on('complete', function(result) {
		    if ( result instanceof Error ) {log_errer(); } 
		});
	rest.get( pool_url+"/random" )
	    .on('complete', function(result) {
		    if ( result instanceof Error ) { log_error(); } 
                    else {
			if ( result.chromosome) {
			    eo.incorporate( result.chromosome );
			}
		    }
		});

Better a peer or a client?

>Submitted to GECCO'2014 conference; and Open Science in GitHub .

And back to the browser

Using browserify and with help from #browserify @irc.freenode.net

Actually used in this persentation, in the live demo.
Same code on the client and on the server oh my!

Fulfilling promises

TODO list

Write papers.
Websockets, sockets.io.
Volunteer computing setup, PaaS.
Re-think the underlying evolutionary algorithm using promises
Continue developing nodeo.
Any suggestion?