Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Exposé Système - IR3 Algorithmes génétiques Ivan Boelle Joffrey T ourret Ingé

1 Exposé Système - IR3 Algorithmes génétiques Ivan Boelle Joffrey T ourret Ingénieurs 2000 – IR3 2 Exposé Système - IR3 Algorithmes génétiques Présentation • Problèmes « non classiques » • Algorithmes basés sur les heuristiques • Algorithmes génétiques Fonctionnement • Principes de base • Optimisation Utilisation • Modélisation • Démos • Cas réels Conclusion Bibliographie 3 Exposé Système - IR3 Présentation Problèmes « non classiques » • Pas de méthode pour résoudre - Déplacement d’un robot • Modélisation trop complexe - Comportement social • Évolution / Adaptation / T olérance à l’erreur - Systèmes de perception, d’analyse 4 Exposé Système - IR3 Présentation Une solution basée sur les heuristiques • Approche différente du problème - Recherche de la meilleure solution (moins mauvaise) - Exploration du domaine de solutions 5 Exposé Système - IR3 Présentation R = {x,y} tel que g( f(x,y) ) est optimal avec (x,y) є I - R: Meilleure solution - (x,y): Solution - I: Ensemble des solutions - f(x,y) : Fonction coût - g(): Fonction objectif 6 Exposé Système - IR3 Présentation Une solution: les heuristiques • Principaux algorithmes - Brute force (Monte Carlo) - Hill climbers(gradient descent , annealing, tabu search) - Evolutionary algorithm (Genetic, ant colony, neurals networks) - Constraints algorithms (Local consistency, hybrid algorithms) Présentation Algorithmes génétiques • Origine : Théorie Darwinienne de l’évolution - Struggle for life - Sélection naturelle • AG inspirés du paradigme - Terminologie identique (population, individu, chromosome, gène) - Traduction du phénomène • Opérateurs d’évolution - Sélection - Croisement - Mutation Présentation Algorithmes génétiques • Gène et génotype • Crossing over Présentation Algorithmes génétiques • Individus différents • Sélection des mieux adaptés • Hérédité Fonctionnement Principes de base • Modélisation de la sélection naturelle - Etape d’évaluation • C’est donc une sélection artificielle - Intervention humaine Fonctionnement Principes de base • Génération - Création d’un population aléatoire • Evaluation - Comparaison des individus • Sélection - On ne garde que les meilleurs • Croisement/Mutation - On les fait se reproduire / Évoluer • Retour à l’évaluation 12 Exposé Système - IR3 Fonctionnement Optimisations: Algorithmiques • Critère d’arrêt • Algorithmes hybrides (Hill climbers) • Élitisme • Configuration du degré mutation / croisements • Modélisation 13 Exposé Système - IR3 Fonctionnement Optimisations: Implémentation • Gestion mémoire - Problèmes: – Algorithmes avec de très nombreuses itérations – Variables temporaires nombreuses - Solutions: – Utilisation de tampons (buffers) – Stratégies de réutilisation – Design pattern Flyweight Utilisation Modélisation • Cas concret : Problème - f(x1, x2, x3, …, xn) = x1 * x2 + x3 - … / xn - f(x1, x2, x3, …, xn) = 1000 - x1 = ?, x2 = ?, x3 = ?, …, xn = ? - La suite des opérations aléatoirement choisie en début d’algorithme • Comment modéliser le problème ? - Que cherche-t-on ? - On définit la population, les individus, les gènes Utilisation Modélisation • Population - Ensemble de suites de valeurs (solutions potentielles) • Individu - Suite de valeurs • Gène - Une des valeurs • On définit alors les opérateurs nécessaires à l’algorithme Utilisation Modélisation • Evaluation - Calcul de f(x,y,z,…) avec les opérandes de la fonction - Ecart du résultat / résultat attendu • Sélection - On ne retient que les meilleurs solutions en les triant • Croisement - Deux suites parent donnent deux suites enfant - Le début de l’une devient le début de l’autre en coupant aléatoirement • Mutation - On modifie une des valeurs de certaines suites de manière aléatoire Utilisation Modélisation générer population Pour i de 0 a nb_essai_max{ pour tous les individus{ evaluer(individu) } Si meilleur_individu == resultat_attendu{ arret } sélectionner(population) croiser(population) muter(population) } • Solution = meilleur_individu • Il est possible de ne pas exiger l’égalité et de se contenter d’une valeur approchée 18 Exposé Système - IR3 Utilisation Exemple JAVA avec JGAP • JGAP: Algorithme génétique « fin » • Problème: f(x,y,z,…) = x / y * z + … f(x,y,z,…) = 10000 x = ?, y = ? z = ?, … • Modélisation Java: - CalculChromosome - CalculGene - CalculFitnessFunction - Operation Utilisation Démo • Problème classique : le voyageur de commerce: • Recherche d’un cycle hamiltonien de plus courte distance dans un graphe • Comparaison de l’algorithme Monte Carlo avec un algorithme génétique. 20 Exposé Système - IR3 Utilisation Démo: biobloc • Évolution • Problème: Apprendre a un robot a effectuer des opérations sans connaître ses capacités exactes. • Modélisation subodorée: - Robot - « Biobloc » - Fonctions d’adéquations simples (meilleur performance retenue) 21 Exposé Système - IR3 Utilisation Cas réels • T otal: Sismage - Introduction: Réservoir pétroliers - Problème: Petro Elastic Model PEM(statiques, inconnus) = IP/IS mesurés Inconnus = PEM_Inverse(statiques,IP/IS) - Problématiques supplémentaire: performances 22 Exposé Système - IR3 Conclusion Conclusion • Algorithmes génétiques: - Une solution basée sur l’optimisation - Un algorithme évolutionniste • Problématiques associées - Modélisation - Optimisation – Algorithmique – Implémentation • Applications / Avenir 23 Exposé Système - IR3 Bibliographie • Démonstrations - http://www.caplet.com/MannaMouse.html - http://www.rennard.org/alife/french/gav.html - http://www.lalena.com/AI/Ant/Ant.aspx - http://math.hws.edu/xJava/GA/ - http://magnin.plil.net/anciensite/coursag/voyageur/vo yageur.html 24 Exposé Système - IR3 Bibliographie • Sites explicatifs - http://cs.felk.cvut.cz/~xobitko/ga/ - http://en.wikipedia.org/ - http://animatlab.lip6.fr/papers/Mouret_LMag_05_ga.p df - http://magnin.plil.net/spip.php?rubrique8 - http://fr.wikipedia.org/wiki/Algorithme_g%C3%A9n %C3%A9tique 25 Exposé Système - IR3 Bibliographie • Sites pour le développement / API - http://www.genetic-programming.org/ - http://jaga.sourceforge.net/ - http://jgap.sourceforge.net/ uploads/Litterature/ pr-ese-ntation 2 .pdf