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

my cup of tea

I wanted to make the best tea ever

Two cups of tea

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

Blurred tea mixture

And started to mix and match

Blurred tea mixture

Using different recipes

Recipes

I took notes and scored them

Notes

Until I found OpenTea

OpenTea packaged

I liked it well enough

OpenTea packaged

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

OpenTea leaves

Evolution works by random changes and natural selection

Darwin

Image by Jared Zimmerman, taken from Darwin's book

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

Darwin

Image by Jared Zimmerman, taken from Darwin's book

Like finding the best bridge structure

Bridge by Johannes Bader

Image by Johannes Bader, from his PhD Thesis

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

Population Johannes Bader

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

Newspaper layout optimization

automatic newspaper layout

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

How many users can you get?

Getting users by the bushel

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

nodeo in npm

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?

peer of 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

Fulfilling promises

TODO list

Where's the beef?

Javascript is great for computer science && distributed evolutionary computation && massively scalable browser-based volunteer computing stuff

That's all

Questions?

Check out MUSES, mobile corporate security- Follow our research at @geneura (or look us up for European H2020 projects) or buy my novels at Amazon

Download this presentation from git.io/uniajq

Use arrows for navigation