Algorithme génétique

avancée IUP 2 Frédéric Vivien 24 avril 2002 Table des matières 1 Introduction 1.1 Qu’est-ce que l’algorithmique ? . 1.2 Motivation : calcul de xn . . . . 1.2.1 Problème . . . . . . . . 1.2.2 Algorithme trivial . . . . 1.2.3 Méthode binaire . . . . 1.2.4 Algorithme des facteurs 1.2.5 Algorithme de l’arbre . . 1.2.6 Et après ? . . . . . . . . 1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . 3.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Complexit´ minimum d’un algorithme de tri . . . . . . . . . . . . e 4 Approche diviser pour regn´r e 4.1 Diviser pour r´gner . . . . . . . . . . . . . . . . . . . . . . . . . . e 4.2 Limites de l’approche diviser pour r`gner . . . . . . . . . . . . . . e 5 Complexit´ des algorithmes e 5.1 Expression du temps de calcul . . . . . . . . . 5.2 Notations . . . . . . . . . . . . . . . . . . . . 5.3 Calculs courants

Terminaison d’une boucle ............................................................................................23 Boucles for .................................................................................................................23 Un algorithme efficace .................................................................................................25 Exercices ......................................................................................................................27 Les fonctions

Exercice proposé 2 Chapitre 7 : Les Algorithmes de tri 2 1 Notion de tri 2 2 Quelques algorithmes classiques de tri 2 2.1 Le tri par sélection 2 2.2 Le tri par insertion simple 2 2.3 Le tri à bulles 2 2.4 Le tri à accès indirect 2 Chapitre 8 : La récursivité 2 1 Définition et exemples 2 2.1 Définition 2 1.1 Premier exemple : Calcul du factoriel d’un entier 2 1.2 Deuxième exemple : Somme des éléments d’un tableau 2 1.3 Troisième exemple : les tours de Hanoï 2 2 Un algorithme de tri récursif : le tri rapide

` ´ Algebre lineaire Algorithme du simplexe Algorithme du simplexe ` ´ Une solution a la programmation lineaire Hugues Talbot Laboratoire A2SI 18 mars 2008 ´ ´ Resume ` ´ Algebre lineaire Algorithme du simplexe Plan ` ´ Algebre lineaire Algorithme du simplexe Formulation et forme standard Notations Recherche d’une solution optimale ´ ´ Resume ` ´ Algebre lineaire Algorithme du simplexe Matrices, inverses etc • Il est necessaire de

la longueur d’un chemin quelconque comme la somme des longueurs des arcs qui le composent. Un problème fondamental, et qui se pose fréquemment dans les applications, est celui de la recherche de chemins de longueur minimale ou maximale. Les algorithmes, permettant d’obtenir de tels chemins, sont utiles pour la recherche de flots et d’ordonnancements optimaux. 1. Formulation du problème Soit G = (X, U) un 1-graphe orienté sans boucle comportant n sommets. A tout arc ( xi , x j )  U est associé

introduire un formalisme excessif, d’apporter des éléments de réponses aux questions fondamentales qui se posent en algorithmique: - Comment élaborer un algorithme ? L’algorithme s’arrête-t-il toujours ? Comment prouver qu’un algorithme résout effectivement le problème posé ? Une des principales difficultés dans l’élaboration d’un algorithme est de contrôler son aspect dynamique (c’est à dire la façon dont il se comporte en fonction des données qu’on lui fournit en entrée), en ne considérant

m´thode graphique ıve e 2. L’algorithme du simplexe 3. Simplexe : comment ´viter les pi`ges e e 4. Dualit´ e 5. Programmation lin´aire en nombres entiers e Bibliographe : [V. Chv´tal, Linear Programming] a des programmes lin´aires. e par certains algorithmes. • Les programmes lin´aires peuvent ˆtre r´solus efficacement e e e • Ce sont d’excellents exemples de questions pratiques dont la r´solution n´cessite une combinaison de m´thodes e e e algorithmiques, de math´matiques ´l´mentaires et de bon

R´esolution graphique I.1.5 G´en´eralisation . . . . . . . . . . . . . . . . . . . . . . . . . . I.2 M´ethode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . I.2.1 Probl`eme de programmation lin´eaire sous forme normale . . . I.2.2 Algorithme du simplexe I : pr´eparation . . . . . . . . . . . . I.3 R´esolution dans le cas g´en´eral . . . . . . . . . . . . . . . . . . . . . . I.3.1 Ecrire un probl`eme de maximisation sous forme normale . . . I.3.2 Dualit´e minimum/maximum . . . .

nous appliquerons la méthode exacte au problème de tournées des véhicules : « vehicle routing problem ». I - resolution heuristique 1. méthode 2-Opt 1.A) Principe La méthode 2-Opt est un algorithme de recherche locale qui améliore un circuit initial construit par une quelconque heuristique. Il s'agit d'un algorithme itératif : à chaque étape, on supprime 2 arcs de la solution établie par l'heuristique ; on crée 2 nouveaux arcs où les noeuds sont connectés différemment ; si la longueur du circuit est