14
Geneticio Make something of your big data Use genetic algorithms to reach your business goals Les algorithmes génétiques dans tous leurs états

Les algorithmes génétiques dans tous leurs états

Embed Size (px)

Citation preview

Page 1: Les algorithmes génétiques dans tous leurs états

GeneticioMake something of your big data

Use genetic algorithms to reach your business goals

Les algorithmes génétiques dans tous leurs états

Page 2: Les algorithmes génétiques dans tous leurs états

Geneticio

• Autodidacte, passionné de développement.

• Java, Cassandra, Spark, JPPF.

• @jsebrien, [email protected]

• Développe et distribue des solutions IT (SaaS, On Premise) permettant l’implémentation d'algorithmes génétiques, permettant l’optimisation de processus métiers.

• Architecture nativement distribuée.

• Multi-plateforme (Windows, Unix, Mac), polyglotte (Java, Scala, Python, Javascript, R).

Geneticio

Make something of your big data

Julien Sebrien

Human Talks Paris, 11 octobre 2016

Page 3: Les algorithmes génétiques dans tous leurs états

Domaines d’applications

• 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.

GeneticioMake something of your big data

Définition

Marketing

Détermination des meilleures implantations de sites touristiques :https://goo.gl/aCc9SJDétection d’orbites de satellite :https://goo.gl/eauC32

AstronautiqueEt bien d’autres : Imagerie, Linguistique: https://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications

Human Talks Paris, 11 octobre 2016

Page 4: Les algorithmes génétiques dans tous leurs états

DéroulementSélection

Croisement

Mutation

Evaluation

Terminé ? Non

Génération de la population initiale

FINOui

GeneticioMake something of your big data

Human Talks Paris, 11 octobre 2016

Page 5: Les algorithmes génétiques dans tous leurs états

Sélection

GeneticioMake something of your big data

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

Exemple Tournoi :

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

• 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).

• 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.

Human Talks Paris, 11 octobre 2016

Page 6: Les algorithmes génétiques dans tous leurs états

Croisement

GeneticioMake something of your big data

 

NE N E NE S W SW E 

 

E NE N NW W E E NW 

 

NE N E NE S E E NW 

 

E NE N NW W W SW E 

parent 1 parent 2

enfant 1 enfant 2

1 point de croisement 1 point de croisement

Human Talks Paris, 11 octobre 2016

Page 7: Les algorithmes génétiques dans tous leurs états

Mutation

GeneticioMake something of your big data

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

• Taux de mutation de l'ordre de 1%.

… W …

… E …

enfant 2

Human Talks Paris, 11 octobre 2016

Page 8: Les algorithmes génétiques dans tous leurs états

Evaluation

GeneticioMake something of your big data

• Fonction de fitness, évaluant la qualité de chaque individu, son adaptation au contexte du problème donné.

• Le score attribué est idéalement indépendant des autres individus de la population.

• Primordial afin d’accroître la probabilité de convergence de l'algorithme.

Human Talks Paris, 11 octobre 2016

Page 9: Les algorithmes génétiques dans tous leurs états

Terminaison

GeneticioMake something of your big data

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

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

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

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

• Etc.

Human Talks Paris, 11 octobre 2016

Page 10: Les algorithmes génétiques dans tous leurs états

Cas « TOBEORNOTTOBE »

GeneticioMake something of your big data

Modélisation:

• Génome initial constitué d’une séquence de 13 caractères, générés aléatoirement.

Fonction de fitness:

• Somme des écarts entre la lettre du génome et la lettre cible, à chaque position:

Score = 131

Génome C Q Y T C Z K I H U E I TCible T O B E O R N O T T O B EEcart (valeur absolue) 17 2 23 15 12 8 3 6 12 1 10 7 15

Human Talks Paris, 11 octobre 2016

Page 11: Les algorithmes génétiques dans tous leurs états

Exécution

GeneticioMake something of your big data

Human Talks Paris, 11 octobre 2016

Page 12: Les algorithmes génétiques dans tous leurs états

Cas « Smart Rockets »

GeneticioMake something of your big data

Modélisation:

• Une séquence de 300 vecteurs d’accélération unitaires sur un plan 2D.

Fonction de fitness:

• Le score d’un individu sera d’autant plus élevé qu’il est proche de la cible, à la fin de son mouvement.

• Le score d’un individu sera fortement pénalisé s’il touche l’obstacle, au cours de son mouvement.

Score = 1/ R (avec R=distance restante par rapport à la cible) ; si Obstacle touché, Score = Score / 4 !

Human Talks Paris, 11 octobre 2016

Page 13: Les algorithmes génétiques dans tous leurs états

Exécution

GeneticioMake something of your big data

Human Talks Paris, 11 octobre 2016

Page 14: Les algorithmes génétiques dans tous leurs états

Questions?

Demo ! genetic.io/fr/demo

Twitter : @geneticio

Mail : [email protected]

Web : genetic.io/fr

GeneticioMake something of your big data