ALGORITHMIQUE

Carte mentale

Élargissez votre recherche dans Universalis

Algorithmes génétiques

Les algorithmes génétiques (A.G.) constituent un exemple représentatif d'un ensemble de méthodes connues sous le nom d'algorithmes évolutionnaires (A.E.). Ces méthodes servent à implanter sur des systèmes artificiels les mécanismes néo-darwiniens de l'évolution naturelle. Cette approche initiée dans les années 1970 par John Holland connaît depuis le début des années 1990 une forte croissance. Les A.E. sont des algorithmes itératifs fondés sur la notion de génération ; mais ils sont, également, par nature, hautement parallèles dans la mesure où ils simulent l'évolution de tout un ensemble de solutions.

Concepts de base

Un A.G. manipule des chaînes de symboles. Chaque chaîne représente une solution potentielle complète à un problème donné. De façon métaphorique, une chaîne est assimilée à un chromosome, la valeur d'un symbole à un allèle et l'ensemble des chaînes manipulées à une population. Le plus souvent, la population est de taille constante, les chromosomes sont de longueur fixe et l'alphabet des symboles est binaire. D'autres représentations sont également utilisées : structure arborescente, taille de chromosome variable, ou encore codage fondé sur les nombres réels. Un des problèmes cruciaux pour appliquer un A.G. réside dans le codage des solutions sous la forme d'une chaîne de symboles. On peut établir un parallèle entre cette correspondance et le processus de morphogenèse qui produit un phénotype à partir du génotype. Les chromosomes sont soumis à un processus directement inspiré par l'évolution. L'algorithme de base est à la fois simple et général : il implante une boucle évolutionniste dans laquelle chaque itération correspond à une génération.

Le plus souvent, la population initiale est engendrée de façon aléatoire mais il peut être judicieux de biaiser cet échantillonnage dès lors que l'on dispose d'informations a priori sur la qualité de certaines solutions. Afin d'améliorer, de génération en génération, les performances de la population, une pression sélective est exercée sur les solutions. La sélection est fondée sur une valeur d' [...]


1  2  3  4  5
pour nos abonnés,
l’article se compose de 11 pages

Médias de l’article

Algorithmes de calcul de p

Algorithmes de calcul de p
Crédits : Encyclopædia Universalis France

tableau

Arbre binaire

Arbre binaire
Crédits : Encyclopædia Universalis France

dessin

Échelle de complexité

Échelle de complexité
Crédits : Encyclopædia Universalis France

tableau

Afficher les 3 médias de l'article


Écrit par :

Classification

Autres références

«  ALGORITHMIQUE  » est également traité dans :

CALCUL, mathématique

  • Écrit par 
  • Philippe FLAJOLET
  •  • 1 782 mots

Dans le chapitre « Calculabilité et algorithmique »  : […] Dans les années 1930 s'élabore, sous l'impulsion notamment du logicien Alan Turing, une théorie abstraite de la calculabilité, ce avant même l'avènement de l'ordinateur. Tout n'est pas calculable en mathématique et, par exemple, il ne saurait exister de procédé systématique permettant de distinguer par calcul, parmi l'infini des assertions mathématiques possibles, celles qui sont vraies : il s'agi […] Lire la suite

INDE (Arts et culture) - Les mathématiques

  • Écrit par 
  • Agathe KELLER
  •  • 5 558 mots
  •  • 4 médias

Dans le chapitre « Mathématiciens à l’échelle du monde »  : […] À l’indépendance, la création de centres d’excellence pour les mathématiques et une école indienne très forte, notamment en algorithmique théorique, placent définitivement l’Inde nouvellement créée sur la carte mondiale des sciences mathématiques. Si un certain nombre de mathématiciens fameux émigrent vers les États-Unis et le Royaume-Uni (notamment Harish-Chandra), des liens particuliers sont au […] Lire la suite

ITÉRATION, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE, 
  • Universalis
  •  • 876 mots

Itérer signifie recommencer, faire à nouveau. Construire les nombres entiers peut être vu comme l'opération consistant à partir de zéro à itérer indéfiniment l'ajout d'une unité. Plus généralement, en mathématiques, lorsqu'une fonction ou opération est disponible, il est fréquent d'en envisager l'itération, celle-ci conduisant soit à de nouvelles fonctions ou opérations, soit à des structures ou p […] Lire la suite

KOLMOGOROV ANDREÏ NIKOLAÏEVITCH (1903-1987)

  • Écrit par 
  • Jean-Luc VERLEY
  •  • 1 416 mots
  •  • 1 média

Dans le chapitre « Mathématiques appliquées »  : […] Kolmogorov a consacré de nombreuses publications aux équations aux dérivées partielles de la physique. Les équations de Navier-Stockes étaient le prototype des équations qui interviennent dans l'étude de la réaction-diffusion, la turbulence et la mécanique statistique. En 1931, Kolmogorov a introduit une vaste classe d'équations aux dérivées partielles dont le champ naturel est l'espace de Hilber […] Lire la suite

NUMÉRIQUE ANALYSE

  • Écrit par 
  • Jean-Louis OVAERT, 
  • Jean-Luc VERLEY
  •  • 6 645 mots

Dans le chapitre « Le concept d'approximation »  : […] Dans toutes les questions de représentation des nombres et des fonctions, il faut distinguer la recherche de solutions « exactes » de celle d'algorithmes d'« approximation » d'une solution. Mais on notera que le champ du concept d'approximation recouvre non seulement les problèmes issus de l'analyse mais aussi certaines questions purement algébriques. Ainsi, en algèbre linéaire, les méthodes itéra […] Lire la suite

OPÉRATIONNELLE RECHERCHE

  • Écrit par 
  • Georges CULLMANN
  •  • 5 547 mots
  •  • 2 médias

Dans le chapitre « La théorie des graphes »  : […] La théorie des graphes s'introduit avec facilité dans la description de solutions concrètes où existent des combinaisons d'événements ou des successions temporelles (cf.  théorie des graphes ). Ses algorithmes sont de puissants auxiliaires pour l'analyste. D'abord parce que l'algorithme, prescription détaillée des opérations à réaliser pour obtenir avec certitude la solution d'un type de problème […] Lire la suite

PROGRAMMATION

  • Écrit par 
  • Jean-François MONIN
  •  • 7 832 mots

Dans le chapitre « Structures de contrôle et structures de données, systèmes de types »  : […] Un autre élément important en programmation se trouve dans la structuration des données à manipuler. L' algorithmique (science de la conception d'algorithmes) repose pour une bonne part sur la définition de structures de données efficaces et adaptées au problème ciblé. Les données élémentaires sont représentées par des mots mémoire de taille fixe : cela inclut les entiers (bornés), les caractères […] Lire la suite

RÉCURSIVITÉ, logique mathématique

  • Écrit par 
  • Kenneth Mc ALOON, 
  • Bernard JAULIN, 
  • Jean-Pierre RESSAYRE
  •  • 9 371 mots

Dans le chapitre « Définition logique »  : […] La définition arithmétique des fonctions récursives conduit à la définition logique. Soit L le langage de l'arithmétique, dont les symboles non logiques sont + pour désigner l'addition des entiers, × pour la multiplication, ≤ pour l'ordre, = pour l'égalité ; on ajoute, pour chaque entier n un symbole de constante n . Appelons formule de type Σ une formule dans laquelle n'apparaît ni négation, ni […] Lire la suite

RÉELS NOMBRES

  • Écrit par 
  • Jean DHOMBRES
  •  • 15 297 mots

Dans le chapitre « Une construction algorithmique »  : […] Voici enfin une autre construction de R qui ne passe pas par le corps des nombres rationnels, mais utilise une définition algorithmique de la soustraction sur le développement décimal illimité (cf. calcul infinitésimal  – Calcul à une variable, chap. 1). C'est un retour à Bombelli et à Stevin. Soit R l'ensemble de toutes les suites ( x n ) n ∈ Z (doublement infinies, c'est-à-dire indexées par Z […] Lire la suite

Voir aussi

Pour citer l’article

Philippe COLLARD, Philippe FLAJOLET, « ALGORITHMIQUE », Encyclopædia Universalis [en ligne], consulté le 13 octobre 2020. URL : https://www.universalis.fr/encyclopedie/algorithmique/