Remerciez-le!

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

Introduction On pourrait dire que la logique floue, les réseaux de neurones et

Introduction On pourrait dire que la logique floue, les réseaux de neurones et les algorithmes génétiques constituent des approches qui, tou compte fait, ne sont pas nouvelless. Leur développement se fait à travers les méthodes par lesquelle l’homme essaye de copier la nature et de reproduie des modes de raismeoonemnt et de compormtent qui lui sont propores. Ben que ces approches paraissent « naturelles », et si elles se sont mposées dans des domaines allant du traitent à l’image à la gestion financiére, elles commencent à peine à etre utilisées dans les domaines de ‘industrie afin de résoudre les problèmes d’identification de régulation de processus, d’optimisation, de cassification, de détection de défauts ou de prise de décision Principes généraux Les algorithmes génétiques sont des algorithmes d’optimisation s’appuyant sur des techniques dérivées de la génétique et de l’évolution naturelle1 : croisements, mutations, sélection, etc. Les algorithmes génétiques ont déjà une histoire relativement ancienne, puisque les premiers travaux de John Holland sur les systèmes adaptatifs remontent à 1962 [Hol62]. L’ouvrage de David Goldberg [Gol89c] a largement contribué à les vulgariser. Un algorithme génétique recherche le ou les extrema d’une fonction définie sur un espace de données. Pour l’utiliser, on doit disposer des cinq éléments suivants : 1. Un principe de codage de l’élément de population. Cette étape associe à chacun des points de l’espace d’état une structure de données. Elle se place généralement après une phase de modélisation mathématique du problème traité. Le choix du codage des données conditionne le succès des algorithmes génétiques. Les codages binaires ont été très employés à l’origine. Les codages réels sont désormais largement utilisés, notamment dans les domaines applicatifs, pour l’optimisation de problèmes à variables continues. 2. Un mécanisme de génération de la population initiale. Ce mécanisme doit être capable de produire une population d’individus non homogène qui servira de base pour les générations futures. Le choix de la population initiale est important car il peut rendre plus ou moins rapide la convergence vers l’optimum global. Dans le cas où l’on ne connaît rien du problème à résoudre, il est essentiel que la population initiale soit répartie sur tout le domaine de recherche. 3. Une fonction à optimiser. Celle-ci prend ses valeurs dans R+ et est appelée fitness ou fonction d’évaluation de l’individu. Celle-ci est utilisée pour selectionner et reproduire les meilleurs individus de la population. 4. Des opérateurs permettant de diversifier la population au cours des générations et d’explorer l’espace d’état. L’opérateur de croisement recompose les gènes d’individus existant dans la population, l’opérateur de mutation a pour but de garantir l’exploration de l’espace d’état. 5. Des paramètres de dimensionnement : taille de la population, nombre total de générations ou critère d’arrêt, probabilités d’application des opérateurs de croisement et de mutation. Le principe général du fonctionnement d’un algorithme génétique est représenté sur la figure 1.1. On commence par engendrer une population d’individus de façon aléatoire. Pour passer d’une génération k à la génération k + 1, les trois opérations suivantes sont répétées pour tous les éléments de la population k. Des couples de parents P1 et P2 sont sélectionnés en fonction de leurs adaptations. L’opérateur de croisement leur est appliqué avec une probabilité Pc (généralement autour de 0.6) et engendre des couples d’enfants C1 et C2. D’autres éléments P sont sélectionnés en fonction de leur adaptation. L’opérateur de mutation leur est appliqué avec la probabilité Pm (Pm est généralement très inférieur à Pc) et engendre des individus mutés P0. Les enfants (C1,C2) et les individus mutés P0 sont ensuite évalués avant insertion dans la nouvelle population (la figure 1.1 présente le cas où les enfants et les individus mutés remplacent les parents). Différents critères d’arrêt de l’algorithme peuvent être choisis : – Le nombre de générations que l’on souhaite exécuter peut être fixé a priori. C’est ce que l’on est tenté de faire lorsque l’on doit trouver une solution dans un temps limité. – L’algorithme peut être arrêté lorsque la population n’évolue plus ou plus suffisamment rapidement. Algorithme génétique Les algorithmes génétiques (GA) proposés par Holland [Adaptation in Natural and Artificial Systems, 1975] ont été utilisés avec un succès croissant en optimisation combinatoire. Un GA opère sur une population d'individus codés par des chaînes de symboles appelées chromosomes. Ces chaînes sont munies d'une fonction d’évaluation appelée fonction de fitness, qui correspond à une mesure d'adaptation au milieu. Un GA procède par une multitude d’itérations où chaque itération consiste à tirer au sort deux parents selon une distribution favorisant les individus les plus adaptés. Un opérateur de croisement combine ensuite les deux chromosomes parents pour construire un ou deux enfants, pouvant à leur tour être modifiés aléatoirement par un opérateur de mutation. Les enfants servent à construire la génération suivante ou remplacent directement des individus de la population. Le processus est répété jusqu'à ce qu'un critère d'arrêt, défini par l’utilisateur, soit vérifié. Les sections suivantes présentent les caractéristiques essentielles des GA : les chromosomes, leur évaluation, les méthodes de croisements et les mutations. Ces caractéristiques peuvent se décliner en différents GA selon l'implémentation de la population initiale, la gestion des générations et les critères d'arrêt. Les Algorithmes Génétiques (AG) sont des méthodes d’optimisation stochastiques qui ont été initialement développées par [Holland, 1975] et popularisées grâce à l’ouvrage de [Goldberg, 1989] . Les algorithmes génétiques sont proposés comme des heuristiques pour résoudre des problèmes complexes. Ils sont basés sur l’analogie avec le mécanisme Darwinien de la sélection naturelle dans laquelle les individus les mieux adaptés d’une population ont plus de chances de survivre dans les générations suivantes. Cela se traduit par le fait que les meilleurs individus d’une population doivent se reproduire pour engendrer de nouveaux individus de plus en plus adaptés. En revanche les individus les moins adaptés sont condamnés à disparaître. L’objectif des algorithmes génétiques est de déterminer l’évaluation d’une fonction objectif (appelée parfois fonction d’évaluation ou fonction d’aptitude) f : X → R où X est un ensemble de points qui définissent l’espace de recherche. Un point de cet espace représente un individu. La fonction objectif alors est définie pourmesurer la performance de chaque individu. Les algorithmes génétiques sont normalement utilisés comme une bonne alternative pour l’optimisation de fonctions. La procédure stochastique utilisée dans un AG repose sur les points suivants : un principe de codage pour chaque individu d’une population, – une fonction à optimiser, – un mécanisme de sélection, – des opérateurs génétiques tels que : le croisement, la mutation ou l’élitisme, – des paramètres initiaux tels que la taille initiale de la population, le(s) critères(s) d’arrêt, et la probabilité d’application des opérateurs génétiques. Un AG est défini par une population initiale qui au cours de son évolution tend à converger, c’est-à-dire que les individus les plus forts tendent à se ressembler de plus en plus entre eux. Dans ce cas, nous avons une population dominée en grande partie par des individus les plus forts qui sont capables de fournir une bonne approximation de la solution du problème à résoudre. Bien entendu, l’approximation optimale fournie peut être locale ou globale (voir Figure 4.1) car la nature des algorithmes génétiques est stochastique. Logique Floue Ensemble flou 3.2.1. Définition La notation d’ensembles flous a été introduite pour la première fois par Zadeh (1965) afin de représenter mathématiquement l'imprécision relative à certaines classes d'objets. Un ensemble flou est un ensemble de valeurs qui appartiennent à une certaine classe avec une certaine certitude (Zadeh, 1965). La logique floue permet de faire le lien entre modélisation numérique et modélisation symbolique. Ce qui a permis des développements industriels spectaculaires à partir d'algorithmes très simples assurant la transformation des connaissances symboliques en entités numériques et inversement. De plus, la théorie des ensembles flous a également donnée naissance à un traitement original de l'incertitude fondé sur l'idée d'ordre. Cette idée d’ordre permet de formaliser le traitement de l'ignorance partielle et de l'inconsistance dans les systèmes d'informations avancés. Les ensembles flous ont eu également un impact sur les techniques de classification automatique et ont contribué à un certain renouvellement des approches existantes de l'aide à la décision. Variables linguistiques Pour bien mettre en évidence le principe fondamental de la logique floue, nous présentons dans cette section, un exemple explicatif. Nous classons la taille des personnes en trois catégories: "petit", "entre les deux " et "grand". Selon les deux figures 9 et 10, la classification des personnes en trois catégories est bien claire mais différente. En effet, par rapport à la logique classique, toutes les personnes avec une taille de moins de 1.50m sont considérées comme "petit" et celles de 1.70m appartiennent à la catégorie des grands. Le passage du petit au grand ce fait progressivement et par cas, ce qui implique qu'une telle classification n'est pas logique Cependant, en utilisant la logique floue, la fonction d'appartenance f permet de tenir compte du fait qu'une personne de 1.45 m est considérée comme petite avec f =0.7, et comme étant entre les deux avec f =0.3. Pour décrire une certaine situation, nous utilisons souvent des expressions floues comme : rapide ; grand ; beaucoup uploads/Industriel/ algorithme-genetique.pdf