Upload
geneticio
View
211
Download
0
Embed Size (px)
Citation preview
GeneticioMake something of your big data
Use genetic algorithms to reach your business goals
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
Paris Datageeks, 5 octobre 2016
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
Paris Datageeks, 5 octobre 2016
Marketing
Détermination des meilleures implantations de sites touristiqueshttps://goo.gl/aCc9SJ
Détection d’orbites de satellitehttps://goo.gl/eauC32
AstronautiqueEt bien d’autres : Bio-Informatique, Imagerie, Linguistique, etc.https://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications
Déroulement
Sélection
Croisement
Mutation
Evaluation
Terminé ? Non
Génération de la population initiale
FINOui
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
Sélection
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
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.
Croisement
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
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
Mutation
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
• 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%.
Graphique extrait de: http://www.codeproject.com/Articles/707505/Genetic-Algorithms-Demystified
… W …
… E …
enfant 2
Evaluation
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
• 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.
Terminaison
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
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.
Exécutions
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
Architecture
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
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
cand
idats
(avec
data
locali
té)
Chargements des confs des jobs
Import de la population
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
• Import de la population dans Cassandra 3.x, pilote Datastax 3.0.x
• Gestion de différentes sources (JDBC, fichier, upload, etc.)
• Conversion à la volée en types natifs Cassandra
• Utilisation de BoundStatement avec appels asynchrones
Chargement de la population (spark)
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
• Utilisation du connecteur Datastax Spark/Cassandra
• Gestion de la data-localité
• Paramétrage :
spark.serializer : KryoSerializer.class.getName())
spark.io.compression.codec : "lzf"
spark.executor.memory : configurable
spark.cores.max : configurable
spark.cassandra.input.split.size_in_mb : configurable (wiki : "... reflects the approximate amount of Cassandra Data in any given Spark partition, défaut : 64mb)
Sélection des individus avec Spark
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
Rappel des implémentations courantes :
Tournoi
• Sélectionne aléatoirement 2 individus de la population, et choisi l’individu le plus faible ou le plus fort (selon une variable aléatoire).
Roulette
chaque individu a d’autant plus de chances d’être sélectionné, pour la génération suivante, que son score est élevé.
Spark ne propose pas d’opérations permettant d’implémenter ces sélections efficacement !
Simulation en îles !
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
Utilisation de mapPartitions :
• « Return a new distributed dataset formed by passing each element of the source through a function func.»
• « Similar to map, but runs separately on each partition (block) of the RDD, so func must be of type Iterator<T> => Iterator<U> when running on an RDD of type T. »
Implémentation :
• CassandraJavaRDD<CassandraRow> cassandraRowsRDD...
• List<...> orderedCandidates = cassandraRowsRDD.mapPartitions(FlatMapFunction<java.util.Iterator<Individual>,Iterator<CassandraRow> rows> f).takeOrdered(max, <comparator>);
Source : "A Parallel Genetic Algorithm Based on Spark for Pairwise Test Suite Generation"Rong-Zhi Qi 1 , Member, CCF, Zhi-Jian Wang 1 , Member, IEEE, and Shui-Yan Li 2College of Computer and Information, Hohai University, Nanjing 211106, ChinaCollege of Science, Hohai University, Nanjing 211106, ChinaReceived March 18, 2015; revised September 25, 2015.http://jcst.ict.ac.cn:8080/jcst/EN/article/downloadArticleFile.do?attachType=PDF&id=9932
Avantages
GeneticioMake something of your big data
Paris Datageeks, 5 octobre 2016
• Exécute l’algorithme sur des sous-ensembles de la population globale, avec taille paramétrable
• Scalable horizontalement
• Permets une configuration fine de la simulation, avec sélections interchangeables
• Suivi des simulations via la console Spark
Demo ! genetic.io/fr/demo
Twitter : @geneticio
Mail : [email protected]
Web : genetic.io/fr
GeneticioMake something of your big data