Développer des applications scalables implémentant des algorithmes génétiques

@GeneticIO Cassandra Day Paris 2015 #Cassandra

Cassandra Day Paris – 16 juin 2015

Genetic.io

Yves CorsaireJulien Sebrien

[email protected]

Développer des applications scalables implémentant des algorithmes génétiques


Algorithmes génétiques

• Appartiennent à la famille des algorithmes évolutionnistes.

• Permettent d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en un temps raisonnable


Domaines d’application

• Aéronautique• Bio-Informatique• Marketing• Finance• Reseaux neuronaux• Ingénieurie mécanique• Imagerie• Linguistique• Etc.

Sources:http://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications


Certainement…


Qora mae! *

* Seize him!


Sélection d’orbite de satellite

Vraiment! http://goo.gl/eauC32

philae

tchoury


Besoins

• Une modélisation génétique de chaque solutionChaque individu possède les caractéristiques matérialisant les données du problème (poids, vitesse).

• Une méthode de sélection: Détermine de quelle manière les individus seront sélectionnés (proportion au score de fitness, Tournoi, Classement).

• Une fonction de fitnessEvalue la qualité de chaque individu, son adaptation au contexte du problème donné.

.


Processus d’évolution

Génération de la population initiale Evaluation

Terminé

Mutation

Croisement

Selection

Fini!

Oui

Non


Modélisation du problème

Déterminer une trajectoire optimale vers la comète « tchoury ».

Une séquence de n chromosomes, chacun d’entre eux représentant un mouvement unitaire sur un plan 2D.

Le score d’un individu sera d’autant plus élevé qu’il est proche de la comète.

f(x) = 1/ R (R=distance restante par rapport à la comète)

• Pré-requis

• Implémentation des candidats

• Fonction de fitness


Selection

Plusieurs manières de sélectionner des individus existent: proportion au score de fitness, Tournoi, Classement, etc.

Exemple Tournoi

1.Sélectionne aléatoirement 2 individus de la population.

2.Génère une valeur aléatoire afin de décider si l’on sélectionne l’individu le plus faible ou le plus fort (selon leur score).

3.Ajoute l’individu choisi à la sélection courante. Les 2 individus précédents sont ré-insérés dans la population initiale afin de pouvoir être re-sélectionnés par la suite.


Croisement

NE N E NE S W SW E

E NE N NW W E E NW

1 point de croisement 1 point de croisement

parent 1 parent 2

enfant 1 enfant2

NE N E NE S E E NW

E NE N NW W W SW E


MutationObjectif : injecter de la diversité au sein de la population, permettant de réduire le risque de stagner au sein d’un optimum local.

Description : générer un nombre aléatoire. Si le nombre est inférieur au taux de mutation préalablement défini, on effectue la mutation, sinon l’algorithme continue son exécution.

Graphique extrait de: http://www.codeproject.com/Articles/707505/Genetic-Algorithms-Demystified

enfant 2

… W …

… E …


Evaluation

Fonction de fitness = distance restante

tchoury

philaephilae

philae

philaephilae

philae

philae

philae

philae

philae

philaephilae


Terminé?

L’algorithme se termine si l’une des conditions de terminaison suivantes est satisfaite:

1. Un nombre maximum d’itérations de générations est atteint.

2. Un candidat a un score de fitness supérieur ou égal à un seuil préalablement défini.

3. L’algorithme s’exécute depuis une trop longue durée.

…


Si je veux essayer, que

dois-je choisir?


Solutions existantes

• De nombreuses librairies existent, mais de très bas niveau, nécessitant un investissement important sur le plan technique, et sur la théorie des algorithmes génétiques.

• Exemples : JGAP, ECJ, EpochX, dans plusieurs langages (Java, C++, Python, etc.)

• Aucune n’entre elles:

- Ne fournit d’interface web moderne de configuration…

- Ne permet l’implémentation d’algorithmes à l’aide de plusieurs langages simultanément…

- N’exploite des architectures distribuées…


Mais ça, c’était avant;)


Installation simplifiée• Installer Genetic.io à l’aide des scripts fournis (windows, unix, mac)

• Créer les comptes utilisateur

• Importer vos données à l’aide de diverses méthodes d’importation (fichier local, téléversement, base de données distante, etc.)

• Configurer les paramètres du job (type de moteur d’évolution, classes dépendentes, conditions de terminaison, etc.)

• Eventuellement, paramétrer la méthode de parallélisation du score de fitness (spark, jppf, multitheadé)

• Démarrer et visualiser l’avancement de l’exécution de l’algorithme en temps réel!


Pile logicielle

Serveur d’Application Web

Client Web

HTTPWebSocket

Base de données

Grille d’exécution de jobs

Batch

CQL

CQL

Wire

Wire Cluster de calcul de données


Infrastructure

Démarrage des jobs, ré

cupération des résultats

Gestions des comptes utilisateur, sources de données, etc.

calcul des scores de fitness

Charg

emen

t des

can

dida

ts (a

vec

data

loca

lité)Chargem

ents des confs des jobs


Importation des données


Conversion des données


Calcul du fitness

public class PhilaeFitnessCalculator implements FitnessCalculator{@Overridepublic double calculate(IndividualBean bean, ...) {

double remainingDistance = computeRemainingDistance(bean);

return 1/remainingDistance;}@Overridepublic boolean isNatural() {

return true;}

private double computeRemainingDistance(IndividualBean bean){return ...;

}}


Operateur de croisementpublic class PhilaeCrossoverOperator implements CrossoverOperator {

...@Overridepublic List<IndividualBean> crossover(IndividualBean firstParent, IndividualBean

secondParent, Random rng) {IndividualBean firstChild = new IndividualBean(firstParent);IndividualBean secondChild = new IndividualBean(secondParent);int numberOfCrossoverPoints = getNbCrossoverPoints(); for (int i = 0; i < numberOfCrossoverPoints; i++){ int max = Math.min(firstChild.getNbAttributes(),

secondChild.getNbAttributes()); if (max > 1){

int crossoverIndex = (1 + rng.nextInt(max - 1)); for (int j = 0; j < crossoverIndex; j++){ Object temp = firstChild.getValue(j); firstChild.setValue(j, secondChild.getValue(j)); secondChild.setValue(j, temp); } }}return Arrays.asList(firstChild, secondChild);

}@Overridepublic int getNbCrossoverPoints() {

return this.nbCrossoverPoints;}...

}


Operateur de mutation

public class PhilaeMutationOperator implements MutationOperator{...@Overridepublic IndividualBean mutate(IndividualBean individual, Random rng) {

individual.setValue("direction", mutateDirection(individual.getValue("direction"),

rng));return individual;

}private String mutateDirection(String direction, Random rng) {

return ...;}

}


Configuration des jobs


Evolution des scores de fitness


Représentation configurable des candidats


Caractéristiques• Gestion de comptes utilisateur sécurisée

• Data localité sur les bases de données distribuées les plus populaires (Cassandra, …)

• Parallélisation du calcul du score de fitness avec Spark, JPPF ou multithreadé

• Distribution de l’exécution des jobs via JPPF

• Représentation personnalisée des individus avec D3.js SVG

• Possiblité de re-jouer les jobs afin de diagnostiquer leurs évolutions

• Multilanguage (Java, Scala…), multiplatforme (Windows, Unix, Mac)

• Open source!


Demo!


Questions?

Technology

Développer des applications scalables implémentant des algorithmes génétiques