Remerciez-le!

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

Les Algorithmes génétiques Les Algorithmes génétiques Institut Supérieur des te

Les Algorithmes génétiques Les Algorithmes génétiques Institut Supérieur des techniques avancées de Saint-Etienne S.ROBERT Module MB1 3ème année 2003-2004 S.Robert algorithmes génétiques 2 Sommaire Sommaire I. I. Méthodes d’optimisation classiques Méthodes d’optimisation classiques II. II. Présentation des A.G. Présentation des A.G. III. III. Fonctionnement d’un A.G. simple : l’A.G. binaire Fonctionnement d’un A.G. simple : l’A.G. binaire IV. IV. Exemple d’A.G. binaire Exemple d’A.G. binaire V. V. Améliorations de la technique de base Améliorations de la technique de base VI. VI. L L ’A.G. à valeurs continues ’A.G. à valeurs continues VII. VII. Fondements mathématiques Fondements mathématiques IX. IX. Applications Applications S.Robert algorithmes génétiques 3 I. Méthodes d’optimisation classiques I. Méthodes d’optimisation classiques Définition: processus d’ajustement de différents paramètres x1, x2, …, xN qui permettent de minimiser ou de maximiser un critère issu d’un procédé théorique ou expérimental symbolisé par f fortement dépendante de ces entrées. On appelle f la fonction coût, d’adaptation ou d’évaluation. Catégorie: Unidimensionnelle ou multidimensionnelle Statique ou dynamique Discrète ou continue Sans contrainte ou avec contraintes De type « essai et erreur » dite expérimental ou de type mathématique Stochastique ou déterministe La forme la plus générale: N x x tel que: Min f (x,t) pour x ; vérifiant G(x) 0 et / ou K(x) 0; ∈ = > r r r r r ¡ A. Définition Il est facile d transformer une maximisation en une minimisation et vice versa par : Maximisation de f Minimisation de -f S.Robert algorithmes génétiques 4 I. Méthodes d’optimisation classiques I. Méthodes d’optimisation classiques B. Techniques classiques Restriction: Optimisation statique et sans contrainte Performances : Temps de calcul, efficacité et Robustesse 3 grands types de méthodes d’exploration 1 Méthodes énumératives On note les différentes valeurs prises par f pour chaque point ={ x1, x2, …xN } compris dans un espace fini, ou infini mais discrétisé. Puis, on extrait la valeur qui correspond au minimum de f. x r •Simple •Trouvent le minimum global •Extrêmement longues •Limitées aux problèmes simples (unidimensionnelles) -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 1.2 -0.5 0 0.5 1 1.5 2 2.5 x f Minimum global Minima locaux S.Robert algorithmes génétiques 5 I. Méthodes d’optimisation classiques I. Méthodes d’optimisation classiques B. Techniques classiques 2 Méthodes basées sur le calcul ¬ Méthode indirecte ou analytique Résolution des équations imposées par les conditions d’optimalité du premier et du second ordre. Pour un min: Pour un max: i D 0 pour i=1,2,...,N > f (x) 0 ∇ = r i i D 0 pour i=2,4,6... D 0 pour i=1,3,5... > < f (x) 0 ∇ = r 2 2 2 1 1 1 2 1 i 2 2 i 2 1 2 i 2 2 i 1 i i f f f x x x x x x f f D x x x x f f x x x x ∂ ∂ ∂ ∂∂ ∂∂ ∂∂ ∂ ∂ = ∂ ∂ ∂ ∂ ∂ ∂ ∂∂ ∂∂ L O M O M L L Di : Déterminant de la matrice Hessienne •Exacte •Plus ou moins Rapide •Ne donne pas la qualité l’ optimum trouvé (à moins de calculer to us les minima et d’ en extraire le plus petit ou grand !!!) •Formulation mathématique du procédé à optimiser •Nécessite l’ existence de dérivées •Devient vite complexe (variables non séparables) S.Robert algorithmes génétiques 6 I. Méthodes d’optimisation classiques I. Méthodes d’optimisation classiques ¬ Méthodes directes de type « ascension de colline » (très employées) On part d’un point choisi aléatoirement dans le domaine de variation de ; puis, à chaque itération, on se déplace dans une direction privilégiée: x r k 1 k k k x x d + = + α dk représente la direction de la recherche αk >0 un scalaire choisi tel que : f(xk+1) < f(xk). Variantes de la méthode: Méthode du gradient. dk=-∇f(xk) ; Si αk est constant on a : Si αk varie on parle de méthodes à pas déterminé. k 1 k k x x f (x ) + = −α∇ Méthode des plus fortes pentes. αk est choisi suivant une minimisation unidimensionnelle: k k k k g( ) f (x f (x )) α = −α ∇ Méthode du gradient conjugué (plus rapide). Les directions de recherches ne sont plus orthogonales mais conjuguées entre elles. La nouvelle direction dk est donnée par: k 1 T k 1 k 1 k 1 k k k k T k f(x ) f(x ) d - f (x ) d avec f(x ) f(x ) + + + + ∇ ∇ = ∇ +β β = ∇ ∇ (Fletcher et Reeves) B. Techniques classiques 2 S.Robert algorithmes génétiques 7 Méthodes de Gauss-Newton :Mettent en jeu, en plus de la dérivée, la matrice Hessienne. On suppose que f est de forme quadratique: T k k k 1 k k T k k k 1 f(x s ) f(x ) f(x ) f(x ) s s H.s 2 + + = ≈ + ∇ + où sk = xk+1-xk = αkdk k 1 f (x ) 0 + ∇ = Ainsi, k k H.s f(x ) = −∇ k k k k+1 k -1 k s = d = x x = H f(x ) α − − ∇ Toutefois le matrice H est très longue à calculer. Certaines méthodes la construise donc itérativement. C’ est la méthode BFGS ( Broyden-Fletcher-Goldfarb-Shanno): ( ) T k k 1 k 1 k T k k k 1 k T T T 1 1 k 1 k k k k T k T k 1 k k k H s H s q q H H s H s v v s H s q s − − + − − − −   = − + + φ   [ ] k k 1 k k k T T k k k k 1 k q H s 0,1 et v q s s H s − −   φ ∈ = −       et sk=xk+1-xk=αkdk et qk=∇f(xk+1)-f(xk) avec •Rapide (Méthodes de Newton) •Efficace (pour certains problème) •Formulation mathématique du procédé à optimiser •Nécessité de l’existence des dérivées et de la matrice Hessienne •f doit être de forme quadratique (pour les méthodes de Newton) • Non robuste (dépend du point de départ choisi) Méthode de Levenberg-Marquardt B. Techniques classiques 2 I. Méthodes d’optimisation classiques I. Méthodes d’optimisation classiques S.Robert algorithmes génétiques 8 B. Techniques classiques 3 Méthodes purement aléatoires Elles explorent l’espace de recherche dans des directions choisies aléatoirement en mémorisant le meilleur élément rencontré à chaque itération. •Simple •Minimum global • Extrêmement longues •N’ exploite pas les régions prometteuses rencontrées Toutes les méthodes présentées n’offrent aucune garantie de trouver le minimum global dans un délais raisonnable: Elles ne sont donc pas robustes. Toutefois, elles ne sont pas inutiles. Elles ont déjà fait leurs preuves pour un certain nombre de problèmes spécifiques. Leur rapidité, pour la plupart, n’est plus à démontrer. Cependant, lorsqu’on s’attaque à des problèmes plus physiques ou plus proche de la « réalité » à savoir multidimensionnel, multimodal, discontinue, etc… d’autres méthodes sont nécessaires. Conclusion I. Méthodes d’optimisation classiques I. Méthodes d’optimisation classiques S.Robert algorithmes génétiques 9 II. Présentation des A.G. II. Présentation des A.G. A. Une méthode d’optimisation « naturelle » Il existe une 4ème catégorie: 4 Méthodes pseudo-aléatoires : méthodes d’optimisation basées sur des processus physiques et biologiques. Par exemple, processus de recuit bien connu des métallurgistes le comportement humain et le principe d’é volution des espèces humaines Recuit simulé A.G. Principe de fonctionnement: « Ils utilisent un choix aléatoire comme outil pour guider une recherche hautement intelligente » (Goldberg) Historique: • Les A.G. sont des méthodes qui permettent à une population de solutions (appelées individus) d’ é voluer par l’intermédiaire d’un certain nombre d’opérateurs vers un état qui optimise l’ensemble de leur « aptitude » (ou fonction coût notée F). • Cette évolution est fondée sur les mécanismes de la sélection naturelle et de la génétique: elle repose, à la fois sur les principes de survie des structures les mieux adaptées, et sur les échanges d’information pseudo-aléatoire entre individus. 1975 : création des A.G. par J. Holland 1989 : Popularisation par son élève D. Goldberg S.Robert algorithmes génétiques 10 II. Présentation des A.G. II. Présentation des A.G. B. Notations ( Analogies avec la biologie ) Individu Chaînes artificielles (Chromosomes) Structure (génotype) : ensemble de l’ information que possède l’ individu par ex : x1=1; x2=2.1; …; xN=5.3 Individu haploïde x1 1 Individu =1 Chaîne artificielle = 1 structure Trait ou détecteur (Gène) Représente une variable : ici, x1 1 2 3 4 5 Position (locus) Ici, 3ème position xi = 5.3 Etat ou Valeur (allèle) Ici, 5.3 Solution ou point (phénotype) Ici, f(x1, x2, …, xN) Information décodée de l’ individu Evaluation De l’ individu S.Robert algorithmes génétiques 11 II. Présentation des A.G. II. Présentation des A.G. C. Propriétés et différences fondamentales avec les méthodes classiques Ils utilisent un codage de paramètres et uploads/Litterature/ cours-les-algorithmes-genetiques.pdf