Remerciez-le!

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

Algorithmes d'évolution pour les réseaux de neurones Mihail CRUCIANU Rapport de

Algorithmes d'évolution pour les réseaux de neurones Mihail CRUCIANU Rapport de recherche 187, Février 1997 Révisé Avril 1997 Laboratoire d'Informatique Ecole d'Ingénieurs en Informatique pour l'Industrie 64 avenue Jean Portalis 37200 TOURS télécopie : (+33) (0) 2 47 36 14 22 courrier électronique : crucianu@univ-tours.fr Résumé : Nous nous intéressons à l'utilisation des algorithmes d'évolution pour le développement et l'apprentissage de réseaux de neurones. Les multiples aspects qui interviennent sont présentés, avec référence à des travaux qui les concernent. Les différents problèmes qui se posent sont mis en évidence, ainsi que les solutions qui ont été apportées. Enfin, nous essayons d'extraire des nombreux travaux existants les techniques les plus prometteuses. Mots clés : réseaux de neurones, apprentissage, algorithmes d'évolution, algorithmes génétiques, algorithmes hybrides. Abstract : This paper deals with the design and training of neural networks using evolutionary algorithms. We present the manifold aspects involved, together with a review of part of the abundant literature on these topics. We highlight the problems one has to solve and the various solutions proposed. Among the various techniques exposed, we eventually try to select the most promising ones. Keywords : neural networks, learning, evolutionary algorithms, genetic algorithms, hybrid algorithms. 1. Introduction L'étude des réseaux de neurones artificiels (RNA) et l'étude des algorithmes d'évolution (AE) se sont développés en parallèle et ont souvent été en interaction durant cette dernière décennie. Nous avons distingué entre deux types d'interactions : l'utilisation conjointe des RNA et des AE pour la résolution d'un même problème, ou l'emploi des AE pour le développement de RNA. Nous nous arrêtons dans cette présentation sur ce deuxième aspect. Les RNA (voir [Hertz, Krogh et Palmer, 1991] ou [Jodouin, 1994] pour une introduction au domaine) peuvent être regardés comme des modèles non linéaires paramétriques1 possédant des propriétés d'approximation universelle (voir par exemple [Hornik et al., 1989], [Sontag, 1993], [Doya, 1993], [Siegelmann et Sontag, 1994]). Les RNA ont une (lointaine) inspiration biologique : un RNA est composé d'unités simples ("neurones") connectées à travers des liens caractérisés par des valeurs numériques ("poids synaptiques"). Pour résoudre (modéliser) un problème à l'aide de RNA il est nécessaire de trouver une architecture adéquate du réseau (identification du modèle) et des valeurs optimales pour les poids des connexions (estimation du modèle). Les AE (voir [Holland, 1975], [Goldberg, 1989] ou [Fogel, 1994] pour une introduction au domaine) sont des algorithmes de recherche (et sous certaines conditions des algorithmes d'optimisation) qui peuvent être utilisés, entre autres, pour déterminer le RNA capable de modéliser un problème. D'inspiration biologique, les AE ont un caractère stochastique et travaillent sur une population d'individus, chaque individu représentant une solution alternative. Un individu est décrit par une chaîne de valeurs numériques (génome). Les individus de la population sont évalués par rapport à un critère qui dépend du problème à résoudre. Une descendance est ensuite générée en privilégiant les meilleurs individus trouvés (sélection) et en utilisant des opérateurs comme la recombinaison et la mutation. La descendance remplace la population courante et l'algorithme continue. Différents types d'algorithmes sont connus actuellement sous l'appellation d'algorithmes d'évolution (voir [Fogel, 1994] pour des distinctions entre ces classes) : les algorithmes génétiques, les stratégies évolutives (evolution strategies) et la programmation évolutive (evolutionary programming). Dans ce rapport nous nous intéressons à l'utilisation des algorithmes d'évolution pour le développement et l'apprentissage de réseaux de neurones. Des connaissances élémentaires concernant les RNA ainsi que les AE sont nécessaires pour comprendre une majeure partie de la problématique présentée. Nous commençons par une discussion concernant l'intérêt que présentent les AE par rapport à d'autres algorithmes d'apprentissage pour les RNA. 1 Contrairement aux modèles paramétriques classiques, les RNA ne permettent pas en général de mettre en évidence la paramétrisation qui correspond à une classes de fonctions à approximer. 2 Les différentes caractéristiques des RNA pouvant bénéficier d'une optimisation par AE sont indiquées dans la section 3. Dans la section 4 nous regardons de plus près l'utilisation des AE pour les RNA, et notamment la représentation des RNA, les fonctions de coût utilisées, les opérateurs d'évolution appropriés ou les techniques mixtes. Les difficultés de mise en oeuvre sont étudiées et les meilleures solutions mises en avant. Nous concluons enfin en essayant de distinguer, dans la multitude de voies existantes, des chemins à suivre. La liste de références donnée est très restreinte par rapport au volume de travaux dans ce domaine ; une bibliographie plus complète bien que non exhaustive peut être trouvée dans [Alander, 1995]. Les différents articles cités dans notre texte le sont dans un but d'illustration et ne correspondent pas nécessairement aux travaux les plus représentatifs. Aussi, nous avons insisté sur les travaux récents. 2. Pourquoi les algorithmes d'évolution La plupart des algorithmes d'apprentissage employés pour les RNA sont déterministes, de type gradient. La dépendance entre les caractéristiques modifiables du réseau  nous les appellerons paramètres par un léger abus de langage  et le critère d'évaluation est une fonction différentiable. Optimiser de façon itérative le critère d'évaluation revient alors à apporter des modifications de faible amplitude aux paramètres dans la direction du gradient du critère d'évaluation par rapport à ces paramètres : dans le sens du gradient pour une maximisation et dans les sens contraire (descente de gradient) pour une minimisation. Une exigence fondamentale pour l'utilisation des algorithmes de gradient est donc bien évidemment la différentiablité de la dépendance mentionnée (l'existence du gradient). Bien souvent une telle dépendance est trop contraignante pour la recherche d'un modèle ou, tout simplement, ne peut pas être assurée : Si la fonction d'activation des unités est discontinue ou non différentiable, la dépendance de la performance du réseau des poids synaptiques ne peut être que non différentiable. Certaines caractéristiques du réseau, comme la présence ou absence d'une unité ou connexion, sont discrètes par leur nature et ne peuvent donc donner lieu à des dépendances continues. L'évaluation du réseau peut se réduire parfois soit à un critère qualitatif (par exemple fonctionnement satisfaisant ou non), soit à un critère quantitatif mais discontinu (par exemple nombre de classifications correctes). Même si le critère de base est quantitatif et différentiable, des critères d'évaluation complémentaires à domaines de variation discrets doivent parfois être employés (par exemple la complexité du réseau). Tous ces problèmes ne se posent pas pour les AE, qui n'utilisent pas explicitement la dépendance entre les caractéristiques modifiables des réseaux et le critère d'évaluation. Grâce à 3 la liberté offerte dans la définition de cette dépendance, les AE présentent un intérêt indiscutable pour l'apprentissage autonome (sans intervention humaine). L'utilisation d'algorithmes d'apprentissage déterministes pour les RNA impose aussi une autre exigence, l'absence d'optima locaux du critère d'évaluation du réseau par rapport aux paramètres. L'expérience montre que cette exigence est rarement satisfaite dans la pratique. En dehors de l'existence de solutions optimales multiples, peu gênante, nous rencontrons souvent un nombre important de solutions sous-optimales qui correspondent à des optima locaux du critère d'évaluation du réseau. Les algorithmes de recherche déterministes sont incapables de quitter un optimum local atteint et ne permettent donc pas d'assurer la complétude2 de la recherche. Grâce à leur caractère stochastique, les algorithmes d'évolution peuvent surmonter ce problème et, sous certaines conditions, atteindre avec une probabilité élevée un optimum global quelque soit l'ensemble des solutions initiales (voir par exemple [Fogel, 1994]). Il ne faut toutefois pas oublier qu'il existe d'autres algorithmes stochastiques n'utilisant pas des populations d'individus mais présentant pourtant la propriété de complétude mentionnée (voir par exemple [Solis et Wets, 1981]). Nous remarquerons aussi (se référer à la discussion plus détaillée de la section 4.4) que les caractéristiques des RNA rendent la fonction d'évaluation plutôt "inconfortable" pour les AE : des réseaux proches peuvent avoir des performances très différentes alors que des réseaux très différents peuvent avoir des performances similaires. Des résultats intéressants concernant les performances relatives d'algorithmes de recherche ont été publiés récemment sous l'étiquette NFL (No Free Lunch, voir [Wolpert et Macready, 1995], [Wolpert, 1996a, b]). Ces résultats montrent que tous les algorithmes  dont l'algorithme de recherche purement aléatoire  sont équivalents si nous regardons leur performance moyenne sur l'ensemble des problèmes possibles, considérés équiprobables. Un algorithme peut alors être estimé supérieur à d'autres si 1° Les problèmes possibles ne sont pas équiprobables et la distribution de probabilités a priori sur l'espace des problèmes possibles est explicitement utilisée dans l'algorithme (l'algorithme est explicitement adapté aux problèmes pour lesquels il sera employé). 2° L'algorithme possède une robustesse relative : il est nettement meilleur que ses concurrents sur une faible partie de l'espace des problèmes possibles et légèrement moins performant sur le reste de cet espace. N'oublions pas qu'un des concurrents est la recherche purement aléatoire ! Les résultats NFL confirment donc qu'on ne peut pas comparer les algorithmes sans faire d'hypothèse sur la classe des problèmes à résoudre. L'expérience nous montre que, pour une classe de problèmes souvent rencontrés, l'absence de complétude des algorithmes de recherche déterministes constitue un important handicap ; dans ces cas précis les AE peuvent être très 2 La probabilité d'atteindre un état-cible (état recherché) à partir de n'importe quel autre état est non nulle. 4 utiles. En uploads/Ingenierie_Lourd/ 03-algorithmes-d-x27-evolution-pour-les-reseaux-de-neurones.pdf