Les Algorithmes Génétiques Charline Voinot Soutenance de Stage IUT de Reims DUT Informatique – Option IN Promotion 2006

Les Algorithmes Génétiques

Charline Voinot

Soutenance de Stage

IUT de Reims

DUT Informatique – Option IN

Promotion 2006

Plan

Introduction

Présentation et Définition du Principe

Utilisations en Imagerie Numérique

Avantages et Inconvénients

Conclusion


3


Entreprise : Visucolor®

Domaine : Contrôle de la Couleur

Choix du stage :

- Connaissance de l’Entreprise

et du Personnel

- Applications en Imagerie Numérique

Plusieurs missions, dont la principale est le développement d’un système de détection automatique de couleurs grâce à

l’utilisation d’un algorithme génétique.

Introduction

Logo de la société Visucolor®

Introduction | Définition & Principe | Utilisations | Avantages & Inconvénients | Conclusion

4


• Soucis d’optimisation (physique, biologie économie, sociologie)

→ Utilisation des Mathématiques

• Méthodes analytiques ont fait preuve de leur efficacité

→ Pas semblable à la nature

Définition & Principe


5


• Théorie de l’Évolution et concept de Sélection Naturelle de Charles Darwin

• Dès 1962, Dr John Henry Holland et ses travaux sur les systèmes adaptatifs : Crossing-Over en complément des mutations

• Années 1990, vulgarisation des algorithmes génétiques avec la publication de David Golberg



6


• Intelligence Artificielle de bas niveau (« Intelligence » de la nature)

• 3 Types d’Algorithmes Évolutionnaires, aujourd’hui regroupés:

◦ Algorithmes Génétiques

◦ Stratégies d’Évolution

◦ Programmation Évolutionnaires

Notons également les domaines de la Programmation Génétique et de la Vie Artificielle.



7


• Il n’existe pas de preuve générale de l’efficacité des Algorithmes Génétiques / Évolutionnaires

→ Constater l’efficacité de la sélection naturelle dans le monde vivant :

Les individus sont adaptés à leur environnement



8


• Principe : Simuler l’évolution d’une population d’individus divers



9


• Ne nécessite pas une connaissance du problème : Boîte Noire

Manipulation des entrées, lecture des sorties, et à nouveau manipulation des entrées afin d’améliorer les sorties.



10


Les Algorithmes Évolutionnaires sont inspirés du concept de sélection naturelle de Charles Darwin.

→ Vocabulaire calqué :

◦ Population

◦ Individus

◦ Gènes

◦ Chromosomes

◦ Mutations

◦ Parents

◦ Descendants

◦ Reproduction

◦ Croisements

Analogies avec des phénomènes biologiques



11


Algorithmes issues de la biologie : Génétique

Cellules → Chromosomes → ADN

• ADN = Chaîne de Gènes

• Variantes d’un Gène = Allèle

• Emplacement du Gène sur le Chromosome = Locus

• Ensemble des Chromosomes = Génome

Un Individu est composé de:



12


Les Outils :

• Sélection (sélection naturelle)

→ Amélioration globale de l’adaptation

• Recombinaison (crossing-over)

→ Opération prépondérante, simple ou multiple

• Mutation

→ Pas de convergence prématurée, minimums et maximums locaux



13


Différents types de sélection:

• Par rang (élitiste)

• Roue de la fortune (roulette)

• Par tournoi

• Uniforme



14

Recombinaison (crossing-over)

Chromosome Contenu

A 00 : 11 00 10

B 01 : 01 01 00

A’ 00 : 01 01 00

B’ 01 : 11 00 10

Chromosome Contenu

A 00 : 11 00 : 10

B 01 : 01 01 : 00

A’ 00 : 01 01 : 10

B’ 01 : 11 00 : 00

Simple Multiple




15


Les mutations :

• Taux relativement faible et évolutif

• Permet d’éviter les problèmes d’optimums locaux



Minimum Local

Minimum Global

16


Schéma Récapitulatif

Cycle qui se répète jusqu’à la condition d’arrêt :

• Nombre de générations fini

• Score des Individus



17


Applications multiples :

→ Optimisations de fonctions numériques difficiles, d’emplois du temps, de design, traitement d’image, contrôle de systèmes industriels …

Les Algorithmes Génétiques peuvent être utilisés pour contrôler un système évoluant dans le temps :

→ Adaptation de la population à des conditions changeantes

Utilisations


18


Le commis de voyage

Recherche du chemin le plus court

• Méthode exhaustive exclue :

→ Pour N villes, (n-1)! combinaisons possibles

• Exemple suivant :

◦ Comporte 40 villes

→ Environ 2e46 solutions à tester

◦ Si on test 1 000 000 000 de solutions par seconde…

→ 1e19 fois l’âge de l’univers !

Utilisations


19


Le commis de voyage

Utilisations


20


Visucolor : Détection Mire

Utilisations


21


Compression d’images

Utilisations


22


Sous certaines conditions :

• Nombre de solutions important

• Pas d’algorithme déterministe adapté et raisonnable

• Relativité de la solution

→ Bonne rapidement plutôt que parfaite pendant un temps indéfini

Avantages & Inconvénients


23


Les Plus

• Faculté d’adaptation, réactivité et prise en compte de l’environnement (les autres individus sont compris)

• Permet de traiter des espaces de recherche important (beaucoup de solutions, pas de parcourt exhaustif envisagé)

• Relativité de la qualité de la solution selon le degré de précision demandé



24


Les Moins

• Nécessitent plus de calculs que les autres algorithmes méta heuristiques (notamment la fonction évaluation)

• Paramètres difficiles à fixer (taille population, % mutation)

• Choix de la fonction d’évaluation délicat

• Pas assuré que la solution trouvée est la meilleure, mais juste une approximation de la solution optimale

• Problèmes des optimums locaux si paramètres mal évalués



25


L’utilisation d’algorithmes génétiques:

• Bien si on sait à quoi s’attendre et pas de solution classique au problème posé

• Modularité et adaptation

• Attention à l’aléatoire, moins grande précision que systèmes classiques et déterministes

• Machines d’aujourd’hui ont une puissance suffisante pour de tels calculs/algorithmes

• Visucolor® : différents types de mires et petites variations, bonne solution, et qui fonctionne.

Conclusion


26


Le Stage m’a apporté:

• Application pratique de connaissances théoriques

• Polyvalence et faculté d’adaptation

• Évolution sur le plan professionnel et social

• Utilisation d’une Senseo

• Flatter l’ego de Romain Meunier

A l’issu du DUT :

• Intégration au monde professionnel

• Poursuite d’études

Conclusion


27


Commentaires

&

Questions

Documents

Les Algorithmes Génétiques Charline Voinot Soutenance de Stage IUT de Reims DUT Informatique – Option IN Promotion 2006