News :: Erreur :: Statistiques :: ClearType :: Imprimer ::

MÉTHODES NUMÉRIQUES | FRACTALES | SYSTÈMES LOGIQUES | CODES CORRECTEURS CRYPTOGRAPHIE | AUTOMATES | INFORMATIQUE QUANTIQUE

LISTE DES SUJETS TRAITÉS SUR CETTE PAGE

ANALYSE EN COMPOSANTES PRINCIPALES (A.C.P.)

L'analyse en composantes principales (A.C.P.) est une méthode mathématique d'analyse graphique de données qui consiste à rechercher les directions de l'espace qui représentent le mieux les corrélations entre n variables aléatoires (relation linéaire entre elles).

Simplement dit, une A.C.P. permet de trouver des similitudes de comportement d'achat entre les classes des données observées.

Même si l'A.C.P. est majoritairement utilisée pour visualiser des données, il ne faut pas oublier que c'est aussi un moyen :

- De décorréler ces données. Dans la nouvelle base, constituée des nouveaux axes, les points ont une corrélation nulle (nous le démontrerons).

- De classifier ces données en amas (clusters) corrélés (dans l'industrie c'est surtout cette possibilité qui est intéressante!).

Lorsque nous ne considérons que deux effets, il est usuel de caractériser leurs effets conjoints via le coefficient de corrélation. Lorsque l'on se place en dimension deux, les points disponibles (l'échantillon de points tirés suivant la loi conjointe) peuvent être représentés sur un plan. Le résultat d'une A.C.P. sur ce plan est de déterminer les deux axes qui expliquent le mieux la dispersion des points disponibles.

Lorsqu'il y a plus de deux effets, par exemple trois effets, il y a trois coefficients de corrélations à prendre en compte. La question qui a donné naissance à l'A.C.P. est : comment avoir une intuition rapide des effets conjoints?

En dimension plus grande que deux, une A.C.P. va toujours déterminer les axes qui expliquent le mieux la dispersion du nuage des points disponibles..

L'objectif de l'A.C.P. est de décrire graphiquement un tableau de données d'individus avec leurs variables quantitatives de grande taille :

Afin de ne pas alourdir l'exposé de cette méthode et de permettre au lecteur de refaire complètement les calculs, nous travaillerons sur un exemple.

Considérons pour l'exemple une étude d'un botaniste qui a mesuré les dimensions de 15 fleurs d'iris. Les trois variables  mesurées sont :

-  : longueur du sépale

-  : largeur du sépale

-  : longueur du pétale

Les données sont les suivantes :

Pour nous un tel tableau de données sera tout simplement une matricée réelle à n lignes (les individus) et à p colonnes (les variables) :

  (57.1)

Par suite l'indice i correspondra à l'indice ligne et donc aux individus. Nous identifierons donc l'individu i avec le point ligne  qui sera considéré comme un point dans un espace affine (cf. chapitre de Calcul Vectoriel) de dimension p. L'indice j correspondra à l'indice colonne donc aux variables. Nous identifierons la variable j avec le vecteur colonne :

  (57.2)

c'est donc un vecteur dans l'espace vectoriel de dimension n dans .

Nous nous placerons dans la suite suivant deux points de vue : Soit nous prendrons le tableau de données comme n points dans un espace affine de dimension p, soit nous prendrons ce tableau comme p points d'un espace vectoriel de dimension n. Nous verrons qu'il y a des dualités entre ces deux points de vue.

L'outil mathématique que nous allons utiliser ici est l'algèbre linéaire (cf. chapitre d'Algèbre Linéaire), avec les notions de produit scalaire, de norme euclidienne et de distance euclidienne.

Afin de simplifier la présentation, nous allons dans un premier temps considérer que chaque individu, comme chaque variable, a la même importance, le même poids. Nous ne considérerons aussi, que le cas de la distance euclidienne.

Nous allons commencer en centrant les données, c'est-à-dire mettre l'origine du système d'axes au centre de gravité du nuage de points. Ceci ne modifie pas l'aspect du nuage, mais permet d'avoir les coordonnées du point M égales aux coordonnées du vecteur  et donc de ce placer dans l'espace vectoriel pour pouvoir y faire les calculs! Comme nous supposons dans toute la suite que le poids des individus sont identiques, nous prendrons donc  avec .

Nous considérons le repère orthonormé  dans la bas canonique  de . Soit donc G le centre de gravité du nuage de point, Comme nous considérons ici chaque variable, comme chaque individu, ayant le même poids, G a alors pour coordonnées dans le repère  :

  (57.3)

avec :

  (57.4)

Nous avons alors pour l'instant sous forme graphique :

  (57.5)

Nous appelons "matrice centrée" la matrice :

  (57.6)

Remarque: La matrice des données centrées contient les coordonnées centrées (que nous noterons ) des individus dans le repère . Nous nous placerons dans la suite toujours dans ce repère pour le nuage de points des individus et nous prendrons .

Pour notre exemple, nous avons :

  (57.7)

et pour la matrice centrée :

  (57.8)

et sous forme graphique :

  (57.9)

Pour donner une importance identique à chaque variable afin que le type d'unités des mesures n'influence pas l'analyse, nous travaillerons avec les données centrées réduites (cf. chapitre de Statistiques). Pour cela, nous noterons d'abord:

  (57.10)

la variance d'échantillon de la variable est donc égale à un facteur 1/n près à la norme de cette même variable mais centrée. La matrice des données centrées réduites (sans dimensions) est alors :

  (57.11)

Si nous notons  la matrice diagonale suivante :

  (57.12)

Nous avons alors :

  (57.13)

Remarque: La moyenne de la variable  est nulle et donc sa variance est alors 1 (ce qui revient à dire que la norme de la variable centrée réduite est de norme unitaire comme nous allons de suite le démontrer).

Nous définissons la "matrice des données centrées normées" par :

  (57.14)

Soit encore (il s'agit simplement de l'erreur quadratique moyenne que nous avions introduit dans le chapitre de Statistiques) :

  (57.15)

La terminologie vient bien évidemment du fait que la variable (vecteur)  est de norme unitaire. En effet :

  (57.16)

Ce qui donne:

  (57.17)

Nous avons graphiquement :

  (57.18)

Représenter le nuage de points des données centrées réduites ou centrées normées ne modifie rien à la forme de celui-ci. En effet, la différence entre les deux n'est qu'un changement d'échelle.

L'information intéressante pour les individus est la distance entre les points! En effet plus cette distance sera grande entre deux individus  et  plus les deux individus seront différents et mieux on pourra les caractériser. Mais il faut d'abord choisir une distance. Nous prendrons la distance euclidienne (cf. chapitre de Topologie) :

  (57.19)

Les figures suivantes montrent les projections orthogonales dans l'espace de ce nuage de points respectivement dans les plans  et enfin dans  qui est la meilleure projection, appelé "plan factoriel" (ou parfois "diagramme des scores"), dans le sens où elle respecte le mieux les distances entre les individus (in extenso, elle déforme moins le nuage de points dans l'espace). L'objectif de l'A.C.P. est de déterminer ce meilleur plan et nous démontrerons comment.

  (57.20)

  (57.21)

  (57.22)

Et la vue plane de chacune des projections :

  (57.23)

Avant de déterminer le plan factoriel, nous allons maintenant chercher à détecter les liens possibles entre les variables.

Nous rappelons (cf. chapitre de Statistiques) que la covariance entre deux variables  et  est donnée par :

  (57.24)

et que le coefficient de corrélation linéaire (cf. chapitre de Statistiques) est :

  (57.25)

Nous noterons par la suite:

 et   (57.26)

les matrices des covariances et de corrélations carrées (toutes deux étant pour rappel des matrices carrées et symétriques) avec .

Nous voyons facilement que la matrices des covariances et au coefficient 1/n près, la matrice des produit scalaires canoniques des vecteurs de la matrice des données centrées (en d'autres termes, chaque composante de la matrice des covariances est égale au produit scalaire des variables centrées). Nous en déduisons la relation suivante :

  (57.27)

La matrice des covariances-variances (puisque comme nous l'avons vu dans le chapitre de Statistiques, la diagonale contient les variances) est un outil connu d'interprétation sur ce site. Par contre ce qui est nouveau et va nous être très utile pour déterminer le plan factoriel est la matrice de corrélation linéaire qui peut aussi être écrite sous la forme suivante :

  (57.28)

Ce qui donne pour notre exemple où nous avons trois variables, la matrice carrée suivante (que les données soient centrées ou non les composantes de la matrice sont identiques):

  (57.29)

Pour continuer, toujours dans le but de déterminer le plan factoriel, définissons le concept d'inertie de nuage de point.

Définition: Nous appelons "inertie d'un nuage de points" la quantité :

  (57.30)

où G est le centre de gravité du nuage de point et  le point de  de coordonnées .

Ensuite, démontrons que nous avons la relation suivante :

  (57.31)

Démonstration:

  (57.32)

C.Q.F.D

Nous allons dans toute la suite travailler avec les données centrées normées, in extenso avec la matrice Z. Les points  auront donc ici comme coordonnées .

Le problème est maintenant de trouver le meilleur espace affine de dimension p dans le sens où il respecte au mieux les distances entre les points. Pour cela, nous allons rechercher la meilleure droite vectorielle  qui est parfaitement déterminée par le vecteur . Appelons  la projection orthogonale de  sur la droite . Alors notre problème est de trouver la droite (in extenso le vecteur u) qui fasse que la somme des carrés des distances entres les points  soit maximale. Nous écrirons le problème sous la forme d'un problème de programmation quadratique :

  (57.33)

Or ici, nous avons :

  (57.34)

En effet, le centre de gravité du nuage de point projeté est aussi l'origine. Par suite, notre problème peut s'écrire :

  (57.35)

Lui même équivalent donc à :

  (57.36)

Résolvons donc ce problème :

Tout d'abord, puisque  est la projection orthogonale du point  sur  nous avons  pour tout i avec . Par suite les coordonnées des points  sur la droite  sont :

  (57.37)

Par suite, nous avons :

  (57.38)

Ici nous cherchons le vecteur unitaire . La matrice Z nous est parfaitement connue. Or, nous avons :

  (57.39)

La matrice de corrélation R est symétrique donc, selon le théorème spectral vu dans le chapitre d'Algèbre Linéaire, elle est diagonalisable dans une base orthonormée de vecteurs propres. Ainsi, nous avions démontré dans le théorème spectral que :

  (57.40)

est diagonale si R est symétrique et S orthogonale (qui donc une matrice carrée  dans notre exemple!). Donc :

  (57.41)

et comme S avait été démontrée comme orthogonale, nous avons (cf. chapitre d'Algèbre Linéaire) :

  (57.42)

Donc :

  (57.43)

où nous choisissons pour la matrice diagonale des valeurs propres mises en ordre décroissant : .

Nous avons donc :

  (57.44)

Mais U étant orthogonale nous avons par conséquent :

  (57.45)

et ceci provient du fait que la matrice orthogonales est comme nous l'avions démontré dans le chapitre d'algèbre linéaire une isométrie (elle conserve donc la norme!).

Comme les valeurs propres sont dans l'ordre croissant nous avons :

  (57.46)

Or le terme entre parenthèses est strictement inférieur ou égal à1. Donc :

  (57.47)

Soit :

  (57.48)

Or rappelons que notre objectif est de maximiser cette inégalité. En d'autres termes de chercher  tel que l'égalité soit respectée. Or nous voyons immédiatement que cela est faire si . Ainsi, une solution de notre problème de maximisation est donc :

  (57.49)

soit puisque  qui est alors le premier vecteur propre de R (puisque R se diagonalise dans cette base) associé à la plus grande valeur propre . D'où le fait que cette solution soit notée souvent sous la forme  avec  (il est donc relativement aisé de déterminer S avec des logiciels lorsque R et sont connus).

Une fois que l'on a trouvée la première droite vectorielle, nous cherchons une deuxième droite dans le sous-espace vectoriel orthogonal à la droite vectorielle qui maximise l'inertie du nuage de point projeté. Nous démontrons, et devinons, que la solution est donnée par la droite vectorielle dirigée par le vecteur propre associé à la deuxième valeur propre de la matrice de corrélation est ainsi de suite...

Ainsi, nous obtenons une nouvelle base  dont un des plans constitue le plan factoriel. Cependant il nous faut connaître les composantes de Z dans cette base. Comme cette base a été construite sous la condition que R y est diagonalisable via la matrice S alors cette dernière matrice est l'application linéaire qui va nous permettre d'exprimer Z dans la base  via la relation :

  (57.50)

Ainsi, dans notre exemple les trois valeurs propres sont (cf. chapitre d'Algèbre Linéaire) :

  (57.51)

Nous avons alors comme cordonnées des points  dans la base  :

  (57.53)

Les coordonnées des projections du nuage de points dans le meilleur plan défini par les vecteurs  sont donc les deux premières colonnes de la matrice précédente (correspondant donc à la longueur du sépale et la largeur du sépale).

Effectivement nous voyons immédiatement que ce sont ces deux colonnes qui maximiseront la somme des normes dans le plan donné:

  (57.54)

Un logiciel comme Minitab 15.1 (référence dans l'industrie de la gestion de la qualité) donne les informations suivantes pour les valeurs propres (info pas très utile sous forme graphique... à mon avis):

  (57.55)

et le plan factoriel suivant (resterait à savoir comment les valeurs sont calculées car elles ne sont pas identiques à celles que nous avons obtenues ici... mais la forme graphique est bien juste et c'est le principal!):

  (57.56)

ANALYSE FACTORIELLE DES CORRESPONDANCES (A.F.C.)

L'analyse factorielle des correspondances, en abrégée AFC, est une méthode statistique d'analyse des données. La technique de l'AFC est essentiellement utilisée pour de grands tableaux de données toutes comparables entre elles (si possible exprimées toutes dans la même unité, comme une monnaie, une dimension, une fréquence ou toute autre grandeur mesurable). Elle peut en particulier permettre d'étudier des tableaux de contingence (ou tableau croisé de co-occurrence). Elle sert à déterminer et à hiérarchiser toutes les dépendances entre les lignes et les colonnes du tableau.

Voyons directement un exemple:

Considérons le tableau suivant des superficies des types de peuplements d'arbres en Picardie en 1984 en hectares:

Nous souhaitons analyser s'il existe les degrés de ressemblance et de différence entre les variables. Remarquons, que nous ne cherchons pas à comparer l'égalité des moyennes ou des variances donc les outils statistiques vus dans le chapitre du même nom ne sont pas adaptés à ce genre d'analyse.

Si nous choisissons la distance euclidienne:

  (57.57)

sur les données brutes pour mesurer ces différences entre départements, nous obtenons les écarts suivants :

  (57.58)

et ainsi de suite pour les autres régions. Nous obtenons alors:

  (57.59)

Nous voyons en regardant le tableau et avant tout calcul que les départements de l'Aisne et l'Oise se ressemblent alors que le département de la Somme se diffère nettement. Les distances obtenues mettent en évidence cette observation.

Mais! Pourtant, sur dans le tableau ci-dessus les profils de l'Oise et de la Somme, avec une forêt mixte très faible, sont pourtant très proches en proportion.

Dans ce contexte, nous voyons que la distance euclidienne transcrit les différences de masse entre les départements. En d'autres termes, l'Aisne et l'Oise se ressemblent car leurs superficies sont proches. Pour éliminer l'artefact lié aux ordres de grandeur, il nous faut transformer les données en pourcentage. Nous obtenons alors:

Si nous choisissons la distance euclidienne sur les proportions (données relatives), nous obtenons:

  (57.60)

soit:

  (57.61)

Cette fois, l'Oise et la Somme apparaissent bien comme se ressemblant le plus avec leurs forêts. Nous voyons que travailler avec les données relatives semblent donc plus pertinent dans ce cas!

Maintenant, nous allons emprunter une idée des économistes qui lorsqu'ils ont des tableaux du même genre que le précédent calculent ce qu'ils appellent "l'index" ou "élasticité" et qui est donné par:

  (57.62)

Voici un exemple obtenu avec les tableaux croisés dynamiques de MS Excel qui inclut la fonction Index:

  (57.63)

et en activant la fonction Index:

  (57.64)

Pour voir d'où viennent ces valeurs, regardons par exemple l'article Desk dans la région Alberta a un rendement de:

  (57.65)

par rapport à toutes les régions ce qui est au-dessus de la valeur de 33.33% qu'aurait comme rendement cette article dans toutes les régions confondues s'il n'y avait pas de préférences de région!

La région Alberta a elle un rendement de:

  (57.66)

par rapport à toutes les régions ce qui est en-dessous des 33.33% de rendement qu'elle aurait s'il n'y avait de préférences de région. Ainsi, ce tableau d'index permet de savoir si les différences sont significatives!!

Le rapport donne donc:

  (57.67)

ce qui montre un fort décalage entre la valeur obtenue et la valeur que nous aurions si les proportions étaient respectées.

C'est donc une sorte de calcul de conformité: si le rapport valait 1, c'est que le rendement régional des ventes de cet article particulier serait conforme au rapport de toutes les ventes de cette région relativement à un marché national. Il n'y aurait alors pas d'anomalies Voyons cela par exemple pour nos arbres où nous avions les effectifs observés:

et pour lequel nous obtenons le tableau des index effectifs observés suivant dans MS Excel:

  (57.68)

et nous voyons encore clairement à l'aide de ce tableau que ce sont l'Oise et la Somme qui se ressemblent le plus!

Avant de continuer, nous pourrions nous poser la question extrêmement importante suivante: Quels seraient les effectifs théoriques qui auraient été obtenus si les proportions des arbres dans les régions étaient rigoureusement équivalentes à la proportion d'ensemble (soit de telle manière à ce que les index soient tous unitaires)?

Eh bien simplement en faisant le calcul suivant:

Et nous obtenons avec ces nouvelles valeurs le tableau des index des effectifs théoriques suivant dans MS Excel:

  (57.69)

ce qui montre que les proportions sont maintenant respectées! Paranthèse fermée (mais sur laquelle nous reviendrons un peu plus loin)!

Eh bien quand nous voulons faire de l'analyse factorielle de correspondance, notre relation:

  (57.70)

devient alors:

  (57.71)

soit:

  (57.72)

Cette fois encore, l'Oise et la Somme apparaissent bien comme se ressemblant le plus.

La distance ci-dessus se nomme la "métrique du Khi-2" car elle ressemble (mais c'est tout!) à la distance utilisée dans le test d'ajustement du même nom (cf. chapitre de Statistiques) mais ici, elle permet seulement de mettre en place une hiérarchie dans le cadre d'un tableau de contingences et d'observer les variables similaires de manière plus aisée!!

KHI-2

Pendant l'introduction de la méthode précédente permettant de comparer des effectifs (valeurs) et détecter lesquels étaient les plus proches, nous avons donné le tableau des effectifs observés:

et nous avons montré comment trouver le tableau des effectifs théoriques (arrondis à l'entier le plus proche) dans les cas où les proportions auraient dû éventuellement être respectées:

La construction du dernier tableau ci-dessus présuppose par exemple que les trois régions sont dans des conditions identiques pour tout ce qui concerne la croissance et la multiplication des arbres et que le nombre d'arbres est en relation de cause à effet directe!!!! avec les régions et qu'il n'y a pas d'autres causes intermédiaires.... ce qui est une hypothèse forte!

Mais sous cette hypothèse, supposons que nous souhaiterions savoir si les différences observées entre le nombre d'arbres et les régions sont significatives ou purement aléatoires à cause de l'échantillon expérimental? Entre d'autres termes, nous voulons savoir si le nombre d'arbre dépend réellement des régions dans lesquelles ils poussent où si ces valeurs que ne sont que dues au hasard de l'échantillon?

Pour répondre à cette question il faut d'abord une référence. Et cette référence est justement l'hypothèse de lien causal direct (proportions respectées) que nous avons donné juste précédemment.

Si nous considérons que chaque case du tableau des effectifs observés correspond à l'issue d'une variable aléatoire de loi inconnue et que chaque cas du tableau théorique (du moins la classe d'effectifs) est considéré comme issu d'une variable aléatoire suivant une loi binomiale alors nous pouvons utiliser le test d'ajustement du Khi-2:

  (57.73)

(cf. chapitre de Statistiques) pour avoir une bonne idée (mais qui reste quand même approximative!) si les différences entre les valeurs des effectifs observés est dû au hasard ou sont réels. Or, si D est petit, la probabilité que ce soit dû au hasard est grande mais si D est grand alors nous avons une différence réelle (donc nous utilisons le test d'ajustement du Khi-2 mais dans le sens inverse!).

Reste à déterminer le nombre de dégrées de liberté de loi  que suit cette somme dans ce type de configuration!

Dans le cas particulier (mais facilement généralisable par récurrence) d'une table à deux entrées avec deux variables catégorisées X avec l niveaux et Y avec c niveaux aura respectivement l lignes et c colonnes.

Ainsi, la table aura bien évidemment  cellules. La table des effectifs théoriques (dont chaque cellule est considérée comme une variable aléatoire) aura chaque cellule entièrement déterminée par la somme des autres tel que les degrés de liberté s'écriront alors en toute logique comme nous l'avons vu dans le chapitre de Statistiques:

  (57.74)

Par exemple, en prenant notre exemple des forêts, c'est le total de totaux de 272'650 qui nous permet d'écrire cette dernière relation et ainsi de déterminer la valeur d'une cellule éventuellement vide, toutes les autres étant données!

Un test du khi-2 sur ce type de table teste l'hypothèse d'indépendance contre l'hypothèse alternative de dépendance. Sous l'hypothèse d'indépendance nous estimons qu'il ya besoin de seulement:

  (57.75)

valeurs sur les N pour pouvoir en déterminer la totalité (en supposant implicitement connues les sommes par ligne et par colonne).

Ainsi, si vous avec une table de 2 lignes par 2 colonnes, il vous suffit si vous connaissez les totaux des lignes et des colonnes, d'avoir 2 valeurs (soit (2-1)+(2-1)) pour déterminer les 2 manquantes. Le raisonnement s'applique aussi pour une table de 3 lignes par 3 colonnes où il vous suffit d'avoir au moins 4 valeurs (soit (3-1)+(3-1)) pour déterminer les 5 manquantes.

Les degrés de liberté pour le khi-2 sont alors:

  (57.76)

C'est cette relation qui nous dit (trivialement!) que si dans un tableau de 2 lignes par 2 colonnes comprenant donc 4 cellules (totaux des lignes et colonnes étant aussi connus!) que étant donnée une seule des valeurs (ddl valant 1), nous pouvons déterminer les 3 autres valeurs manquantes.

Voici donc une définition possible du nombre de degrés de libertés: C'est le nombre maximum de valeurs du modèle telles qu'aucune d'entre elle n'est calculable à partir des autres.

De même, pour un tableau de 3 lignes par 3 colonnes comprenant 9 cellules comme c'est le cas de notre exemple dans ce chapitre avec les forêts, la connaissance de 4 cellules seules permet grâce aux totaux en ligne et colonnes de déterminer les 5 autres qui seraient éventuellement non connues.

D'où la relation dans le cadre de l'application du khi-2 de la relation finale:

  (57.77)

en faisant usage des notations utilisées dans l'industrie.

Dans le cadre de notre exemple nous avons:

  (57.78)

et la p-value de cette valeur avec la loi du khi-2 à quatre degrés de liberté:

  (57.79)

est tellement proche de zéro (non significatif) que nous avons aucune chance de nous tromper en affirmant que les différences observées dans le tableau sont significatives entre les 3 forêts.

Nous obtenons un résultat similaire entre l'Oise et la Somme alors qu'avec l'AFC nous avons vu que ces deux forêts se ressemblaient beaucoup.

MÉTHODE DES DIFFÉRENCES FINIES

Dans le domaine des méthodes numériques, nous pouvons être amenés à rechercher la solution d'une équation aux dérivées partielles. Parmi les méthodes de résolutions couramment pratiquées, la méthode des différences finies ou M.D.F. est la plus facile d'accès, puisqu'elle repose sur deux notions : la discrétisation des opérateurs de dérivation/différentiation (assez intuitive) d'une part, et la convergence du schéma numérique ainsi obtenu d'autre part.

Prenons un exemple fameux (car très scolaire) qui n'est qu'un cas particulier et simpliste d'application de la M.D.F.

Rappelons que nous avons démontré dans le chapitre de Thermodynamique l'équation de la chaleur suivante (nous présentons ici cette équation réduite à une dimension spatiale):

  (57.80)

et remarquons que cette équation n'est pas très générale... (elle n'est pas relativiste et ne prend pas en compte la chaleur dégagée sous forme de rayonnement par le matériau considéré ni plein d'autres facteurs....).

Nous pouvons considérer (cf. chapitre de Calcul Différentiel Et Intégral) que:

  (57.81)

et:

  (57.82)

De même:

  (57.83)

L'équation de la chaleur devient alors:

  (57.84)

Après réarrangement nous avons:

  (57.85)

Si nous regardons cette relation de plus près, nous observons qu'il s'agit d'une simple récursivité. Il suffit de connaître la distribution  pour déterminer ensuite toutes les autres valeurs puisque:

  (57.86)

et :

  (57.87)

etc. Il est possible de mettre en oeuvre une telle simulation rien qu'avec un petit tableau et un peu de temps... h est appelé alors le "pas de maillage" du modèle.

Pour le lecteur souhaitant s'entraîner.... une barre de Fer longitudinale de 1 kilogramme a une capacité calorifique massique de , une densité de  et sa conductivité thermique est de .

RÉSEAUX DE NEURONES FORMELS

Les réseaux de neurones, fabriquées de structures cellulaires artificielles, constituent une approche permettant d'aborder sous des angles nouveaux les problèmes de perception, de mémoire, d'apprentissage et de raisonnement (en d'autres termes... d'intelligence artificielle ou abrégée "I.A.") au même titre que les algorithmes génétiques. Ils s'avèrent aussi des alternatives très prometteuses pour contourner certaines des limitations des méthodes numériques classiques. Grâce à leur traitement parallèle de l'information et à leurs mécanismes inspirés des cellules nerveuses (neurones), ils infèrent des propriétés émergentes permettant de solutionner des problèmes jadis qualifiés de complexes.

Nous aborderons ici les principales architectures des réseaux de neurones. Il ne s'agit pas de les étudier toutes, car elles sont trop nombreuses, mais plutôt d'en comprendre les mécanismes internes fondamentaux et de savoir comment et quant les utiliser. Nous aborderons également certaines notions relatives aux ensembles flous et à la logique (cf. chapitre de Logique Floue) dans la mesure où ces derniers sont incorporés dans certaines architectures de réseaux de neurones que nous étudierons.

Le cerveau humain contient environ 100 milliards de neurones. Ces neurones nous permettent entre autre, de lire un texte tout en maintenant une respiration régulière permettant d'oxygéner notre sang, en actionnant notre coeur qui assure une circulation efficace de ce sang pour nourrir non cellules, etc. Ils nous permettent même de comprendre certaines idées (…)

Chacun de ces neurones est par ailleurs fort complexe. Essentiellement, il s'agit de tissu vivant et de chimie. Les neurophysiciens commencent à peine à comprendre quelques uns de leurs mécanismes internes. On croit en général que leurs différentes fonctions neuronales, y compris celle de la mémoire sont stockées au niveau des connexions (synapses) entre les neurones. C'est ce genre de théorie qui a inspiré la plupart des architectures de réseaux de neurones artificiels (dits "formels"). L'apprentissage consiste alors soit à établir de nouvelles connexions, soit à en modifier des existantes (nous nous concentrerons en particulier sur cette dernière possibilité).

Ceci nous amène à poser une question fondamentale : en ce basant sur nos connaissances actuelles, peut-on construire des modèles approximatifs de neurones et les entraîner pour, éventuellement, réaliser des tâches utiles ? Eh bien, la réponse courte est : oui !, même si les réseaux que nous allons développer ne possèdent qu'une infime fraction de la puissance du cerveau humain, et c'est l'objectif ici de montrer comment nous pouvons y arriver.

Les réseaux de neurones servent aujourd'hui à toutes sortes d'application dans divers domaines. Par exemple, nous avons développé un autopilote pour avion, ou encore un système de guidage pour automobile, nous avons conçu des systèmes de lecture automatique de chèques bancaires et d'adresses postales, nous produisons des systèmes de traitement du signal pour différentes applications militaires, un système pour la synthèse de la parole, des réseaux sont aussi utilisés pour bâtir des systèmes de vision par ordinateur, pour faire des prévisions sur les marchés monétaires, pour évaluer le risque financier ou en assurance, pour différents processus manufacturiers, pour la diagnostic médical, pour l'exploration pétrolière ou gazière, en robotique, en télécommunication, et bien d'autres. Bref, les réseaux de neurones ont aujourd'hui un impact considérable et, il y a fort à parier, que leur importance ira grandissant dans le futur.

MODÈLE DE NEURONE

Le modèle mathématique d'un neurone artificiel, ou "perceptron", est illustré à la figure ci-dessous. Un neurone est essentiellement constitué d'un intégrateur qui effectue la somme pondérée de ses entrées (comme l'espérance statistique!). Le résultat n de cette somme ensuite transformée par une fonction de transfert f qui produit la sortie a du neurone.

Les R entrées du neurone correspondent au vecteur noté traditionnellement en ligne (mais au fait on prend la transposée d'où le T en suffixe) :

  (57.88)

alors que :

  (57.89)

représente le vecteur des poids du neurone (nous les distinguons pour préparer le terrain à des neurones un peu plus complexes).

  (57.90)

La sortie n de l'intégrateur est définie (car il s'agit d'une technique de l'ingénieur) par l'équation suivante :

  (57.91)

que nous pouvons aussi écrire sous forme matricielle (on pourrait aussi l'écrire sous forme tensorielle mais bon...) :

  (57.92)

Cette sorti correspond à une somme pondérée des poids et des entrées moins que ce nous nommons "le biais b du neurone" (facteur correctif décidé par tâtonnement). Le résultat n de la somme pondérée s'appelle le "niveau d'activation du neurone". Le biais b s'appelle aussi le "seuil d'activation du neurone". Lorsque le niveau d'activation atteint ou dépasse le seuil b, alors l'argument de f devient positif ou bien évidemment positif (ou nul). Sinon, il est négatif.

Nous pouvons faire un parallèle entre ce modèle mathématique et certaines informations que nous connaissons (ou que nous croyons connaître) à propos du neurone biologique. Ce dernier possède trois principales composantes : les dendrites, le corps cellulaire et l'axone :

  (57.93)

Les dendrites forment un maillage de récepteurs nerveux qui permettent d'acheminer vers le corps du neurone des signaux électriques en provenance d'autres neurones. Celui-ci agit comme une espèce d'intégrateur en accumulant des charges électriques. Lorsque le neurone devient suffisamment excité (lorsque la charge accumulée dépasse un certain seuil), par un processus électrochimique, il engendre un potentiel électrique qui se propage à travers son axone pour éventuellement venir exciter d'autres neurones. Le point de contact entre l'axone d'un neurone et la dendrite d'un autre neurone s'appelle le "synapse". Il semble que c'est l'arrangement spatial des neurones et leur axone, ainsi que la qualité des connexions synaptiques individuelles qui déterminent la fonction précise d'un réseau de neurones biologique. C'est en se basant sur ces connaissances que le modèle mathématique décrit ci-dessus a été défini.

Un poids d'un neurone artificiel représente donc en quelque sorte l'efficacité d'une connexion synaptique. Un poids négatif inhibe en quelque sorte une entrée, alors qu'un poids positif vient l'accentuer. Il importe de retenir que ceci est une grossière approximation d'une véritable synapse qui résulte en fait d'un processus chimique très complexe et dépendant de nombreux facteurs extérieurs encore mal connus. Il faut bien comprendre que notre neurone artificiel est un modèle pragmatique qui, comme nous le verrons plus tard, nous permettra d'accomplir des tâches intéressantes. La vraisemblance biologique de ce modèle nous importe peu. Ce qui compte est le résultat que ce modèle nous permettra d'atteindre.

Un autre facteur limitatif dans le modèle que nous nous sommes donnés concerne son caractère discret. En effet, pour pouvoir simuler un réseau de neurones, nous allons rendre le temps discret dans non équations. Autrement dit, nous allons supposer que tous les neurones sont synchrones, c'est-à-dire qu'à chaque temps t, ils vont simultanément calculer leur somme pondérée et produire une sortie . Dans les réseaux biologiques, tous les neurones sont en fait asynchrones.

Revenons donc à notre modèle tel que formulé par l'équation précédent et ajoutons la fonction d'activation f pour obtenir la sortie du neurone :

  (57.94)

Il est temps maintenant de remplacer (parce que la notation est un peu lourde à la longue) par une matrice d'une seule ligne que nous noterons . Nous obtenons alors une forme générale que nous adopterons tout le long de notre étude :

  (57.95)

Cette équation nous amène à introduire un nouveau schéma plus formel de notre RNF (ou perceptron) :

  (57.96)

Nous y représentons les R entrées comme un rectangle noir (le nombre d'entrées est indiqué sous le rectangle). De ce rectangle sort le vecteur dont la dimension matricielle est . Ce vecteur est multiplié par une matrice W qui contient les poids (synaptiques) du neurone. Dans le cas d'un neurone simple, cette matrice possède la dimension . Le résultat de la multiplication correspond au niveau d'activation qui est ensuite comparé au seuil b (un scalaire) par soustraction. Finalement, la sortie du neurone est calculée par la fonction f. La sortie d'un neurone simple est alors toujours un scalaire.

FONCTIONS DE TRANSFERT

Jusqu'à présent, nous n'avons pas spécifié la nature de la fonction d'activation de notre modèle. Il se trouve que plusieurs possibilités existent et celles-ci sont quasiment empiriques et à adapter en fonction des situations. Les plus courantes et les plus citées dans la littérature sont énumérées dans la figure ci-dessous :

Tableau: 57.9  - Types de fonctions de transfert pour R.N.F.

Les trois les plus utilisées dans le domaine de l'ingénierie sont les fonctions "seuil" (a) (en anglais "hard limit"), "linéaire" (b) et "sigmoïde" (c) comme représentées ci-dessous :

  (57.97)

Comme son nom l'indique, la fonction seuil applique un seuil sur son entrée. Plus précisément, une entrée négative ne passe pas le seuil, la fonction retourne la valeur 0 (faux), alors qu'une entrée positive ou nulle dépasse le seuil, et la fonction retourne 1 (vrai). Il est évidant que ce genre de fonction permet de prendre des décisions binaires (cette fonction peut aussi être assimilée à la fonction de Heaviside pour ceux qui connaissent...).

La fonction linéaire est quant à elle très simple, elle affecte directement son entrée à sa sortie selon la relation . Il est évidant que la sortie du neurone correspond alors à son niveau d'activation dont le passage à zéro (l'ordonnée à l'origine) se produit lorsque .

La fonction de transfert sigmoïde est quant à définie par la relation mathématique :

  (57.98)

elle ressemble soit à la fonction seuil, soit à la fonction linéaire, selon que nous somme loin ou près de b respectivement. La fonction seuil est très non linéaire car il y a une discontinuité lorsque . De son côté, la fonction linéaire est tout à fait linéaire. Elle ne comporte aucun changement de pente. La sigmoïde est un compromis intéressant entre les deux précédentes. Notons finalement que la fonction "tangente hyperbolique" est une version symétrique de la sigmoïde.

ARCHITECTURE DE RÉSEAU

Par définition, un réseau de neurones est un maillage de plusieurs neurones, généralement organisés en couches. Pour construire une couche de S neurones, il s'agit simplement des les assembler comme à la figure ci-dessous :

  (57.99)

Les S neurones d'une même couche sont tous branchés aux R entrées. Nous disons alors que la couche est "totalement connectée". Un poids est associé à chacune des connexions. Nous noterons toujours le premier indice par i et le deuxième par j (jamais l'inverse). Le premier indice (rangée) désigne toujours le numéro de neurone sur la couche, alors que le deuxième indice (colonne) spécifie le numéro de l'entrée. Ainsi, désigne le poids de la connexion qui relie le neurone i à sont entrée j. L'ensemble des poids d'une couche forme donc une matrice W de dimension :

  (57.100)

Il faut bien sûr prendre en compte que nous n'avons pas nécessairement dans le cas général (les nombres de neurones et d'entrées sont indépendants). Si nous considérons que les S neurones forment un vecteur de neurones, alors nous pouvons créer les vecteurs :

  (57.101)

Ceci nous amène à la représentation simplifiée illustrée ci-dessous :

  (57.102)

Finalement, pour construire un réseau de neurones (ou PMC pour "Perceptron Multi-Couches"), il ne suffit plus que de combiner des couches comme ci-dessous :

  (57.103)

Cet exemple comporte R entrées et trois couches de neurones comptant respectivement neurones. Dans le cas général, de nouveau ces nombres ne sont pas nécessairement égaux. Chaque couche possède aussi sa propre matrice de poids , où k désigne l'indice de couche. Dans le contexte des vecteurs et des matrices relatives à une couche, nous emploierons toujours un exposant pour désigner cet indice. Ainsi, les vecteurs sont aussi associés à la couche k.

Il importe de remarquer dans cet exemple que les couches qui suivent la première ont comme entrée la sortie de la couche précédente. Ainsi, nous pouvons enfiler autant de couches que nous voulons, du moins en théorie. Nous pouvons fixer un nombre quelconque de neurones sur chaque couche. En pratique, nous verrons plus tard qu'il n'est cependant pas souhaitable d'utiliser trop de neurones. Notons aussi que rien ne nous empêche de changer de fonction de transfert d'une couche à l'autre. Ainsi, dans le cas général nous n'avons pas nécessairement .

Définition: La dernière couche est nommée "couche de sortie". Les couches qui précèdent la couche de sortie son nommées "couches cachées".

Définition: "Entraîner" un réseau de neurones signifie modifier la valeur de ses poids et de ses biais pour qu'il réalise la fonction d'entrée sortie (I/O). Nous étudierons en détails différents algorithmes et méthodes d'approche heuristiques pour y parvenir dans différents contextes.

ALGORITHMES GÉNÉTIQUES

Les algorithmes génétiques (AGs) sont des algorithmes d'optimisation stochastiques itérés fondés sur les mécanismes de la sélection naturelle et de la génétique.

Leur fonctionnement est relativement simple :

1. Nous partons avec une population de solutions potentielles (chromosomes) initiales arbitrairement choisies

2. Nous évaluons leur performance (fitness) relative

3. Sur la base de ces performances, nous créons une nouvelle population de solutions potentielles en utilisant des opérateurs évolutionnaires simples : la sélection, le croisement et la mutation.

4. Nous recommençons ce cycle jusqu'à ce que nous trouvions une solution satisfaisante.

Les AGs ont été initialement développés par John Holland (1975). C'est au livre de Goldberg (1989) que nous devons leur popularisation. Leurs champs d'application sont très vastes. Outre l'économie (minimisation du risque des portefeuilles), ils sont utilisés pour l'optimisation de fonctions, en finance, en théorie du contrôle optimal (recherche opérationnelle), ou encore en théorie des jeux répétés et différentiels (en l'occurence dans les jeux évolutionnaires et le dilemme du prisonnier) et la recherche d'information (Google) ainsi que la recherche des plus courts chemins en théorie des graphes (routages Internet ou GPS). La raison de ce grand nombre d'applications est claire : simplicité et efficacité. Bien sûr, d'autres techniques d'exploration stochastiques existent, la méthode de Monte-Carlo peut-être considéré comme un concept similaire.

Pour résumer, Lerman et Ngouent (1995) distinguent quatre principales propriétés qui font la différence fondamentale entre ces algorithmes et les autres méthodes :

P1. Les algorithmes génétiques utilisent un codage des paramètres, et non les paramètres eux-mêmes.

P2. Les algorithmes génétiques travaillent sur une population de points, au lieu d'un point unique.

P3. Les algorithmes génétiques n'utilisent que les valeurs de la fonction étudiée, pas sa dérivée, ou une autre connaissance auxiliaire.

P4. Les algorithmes utilisent des règles de transition probabilistes, et non déterministes.

La simplicité de leurs mécanismes, la facilité de leur mise en application et leur efficacité même pour des problèmes complexes ont conduit à un nombre croissants de travaux ces dernières années.

Définitions:

D1. Un "algorithme génétique" est défini par un individu/chromosome/séquence et une solution potentielle au problème donné.

D2. Une "population" est un ensemble de chromosomes ou de points de l'espace de recherche

D3. "L'environnement" est assimilé à l'espace de recherche

D4. La fonction que nous cherchons à optimiser est appelée "fonction de fitness"

Avant d'aller plus loin, il faut définir de manière plus formelle les concepts précédents (mais sous l'hypothèse particulière ! de codage binaire).

Définition: Les organismes en compétitions sont appelées "individus". Soit un alphabet , nous supposerons que chaque individu peut être représenté par un mot de longueur fixe l pris dans . Le mot A associé à un individu de la population sera appelé "chromosome" ou "séquence" (le terme n'est pas tout à fait équivalent à son homonyme biologique, cependant c'est une pratique courant que d'utiliser ce terme ici aussi) et donné donc par A de longueur l(A) avec (cause : hypothèse du codage binaire).

Dans la mesure où il n'y aura pas de risque de confusion, nous identifierons les termes individus et chromosome.

Les individus forment une population P de taille N, notée :

  (57.104)

Nous allons faire une autre assertion importante, c'est-à-dire, qu'il existe une fonction f d'une séquence à valeurs positives que nous noterons , dite "fonction de fitness" qui à tout associe un réel tel que :

  (57.105)

si et seulement si est mieux adapté au milieu que.

Remarquons que le terme "adapté" n'est pas défini. Pour cela, il faudrait caractériser le milieu dans lequel évoluent les individus, ce que nous ne ferons pas. En fait, puisque nous supposons l'existence d'une telle fonction et que nous posons l'équivalence avec le degré d'adaptation, celui-ci est automatiquement défini par la donnée de f.

Nous nommerons "génération" une population à un instant t, ce qu'il faut mettre en relation avec la notion de durée de vie ou d'âge. Cependant, nous nous placerons ici dans le cas particulier où chaque individu a une durée de vie égale à 1, donc la génération (t+1) est constituée d'individus différents de la génération t, nous les appellerons les "descendants". Réciproquement, les individus de la génération t seront les "ancêtres" des individus de la génération (t+1). Nous désignerons la génération t par P(t) soit la population à l'instant t.

Ainsi, un chromosome est vu comme une suite de bits en codage binaire appelé aussi "chaîne binaire". Dans le cas d'un codage non binaire, tel que le codage réel par exemple, alors la suite A ne contient qu'un point, nous avons avec

Le but d'un algorithme génétique est alors simplement de trouver la chaîne qui maximise cette fonction f. Bien évidemment, chaque problème particulier nécessitera ses propres fonctions d et f.

Les AGs sont alors basés sur les phases suivantes :

1. Initialisation : une population initiale de N chromosomes est tirée aléatoirement

2. Évaluation : chaque chromosome est décodé puis évalué

3. Sélection : création d'une nouvelle population de N chromosomes par l'utilisation d'une méthode de sélection appropriée.

4. Reproduction : possibilité de croisement et mutation au sein de la nouvelle population

5. Retour à la phase d'évaluation jusqu'à l'arrêt de l'algorithme

CODAGE ET POPULATION INITIALE

Il existerait trois principaux type de codage : (1) Binaire, (2) Gray, (3) Réel. Nous pouvons facilement passer d'un codage à l'autre. Certains auteurs n'hésitent pas, par ailleurs, à faire le parallèle avec la biologie en parlent de génotype (cf. chapitre de Dynamique Des Populations) en ce qui concerne la représentation binaire d'un individu, et de phénotype (cf. chapitre de Dynamique Des Populations) pour ce est de sa valeur réelle correspondante dans l'espace de recherche.

Rappelons que la transformation la plus simple (fonction de décodage d) d'une chaîne binaire A en nombre entier x s'opère par la règle suivante (cf. chapitre sur les Nombres) :

  (57.108)

Ainsi le chromosome vaut trivialement :

  (57.109)

Evidemment, la fonction d sera modifiée (par tâtonnements!) selon le problème. Ainsi, si nous cherchons à maximiser une fonction une méthode possible serait la suivante (la taille du chromosome dépendant bien évidemment de la précision voulue) :

  (57.110)

ce qui peut s'assimiler à une série harmonique. Pour une précision au cinquième chiffre après la virgule nous imposerons puisque :

  (57.111)

Une autre façon de faire serait de choisir d telle que :

  (57.112)

Petite explication :

  (57.113)

Posons :

  (57.114)

Ainsi, avec nous avons et :

  (57.115)

La précision demandée y étant toujours vérifiée puisque :

  (57.116)

Cette dernière règle peut se généraliser. Ainsi, admettons que nous cherchons à maximiser (normaliser serait un terme peut-être plus correct) f en fonction d'une variable réelle x. Soit , avec , l'espace de recherche permis avec et les bornes inférieures et supérieures. Soit prec la précision (chiffre après la virgule) avec laquelle nous cherchons x. Soit la longueur de l'intervalle D. Nous devons alors diviser cet intervalle au pire en :

  (57.117)

sous-intervalles égaux afin de respecter la précision. Par exemple, soit nous avons donc si nous voulions une précision , alors il nous faut diviser cet intervalle en sous intervalles.

Avec s l'entier naturel tel que (dans notre exemple, car ), la transformation d'une chaîne binaire en un nombre réel x peut alors s'exécuter en trois étapes :

1. Conversion (base 2 en base 10) :

  (57.118)

2. Normalisation :

  (57.119)

3. Maximisation :

  (57.120)

ou ce qui revient au même directement en une seule étape par :

  (57.121)

Ainsi pour , et nous retrouvons bien :

  (57.122)

Pour ce qui est de la phase d'initialisation, la procédure est assez simple. Elle consiste en un tirage aléatoire de N individus dans l'espace des individus permis. En codage binaire, selon la taille l de la chaîne, nous effectuons pour un chromosome l tirages dans avec équiprobabilité.

LES OPÉRATEURS

Les opérateurs jouent un rôle prépondérant dans la possible réussite d'un AG. Nous en dénombrons trois principaux : l'opérateur de sélection, de croisement et de mutation. Si le principe de chacun de ces opérateurs est facilement compréhensible, il est toutefois difficile d'expliquer l'importance isolée de chacun de ces opérateurs dans la réussite de l'AG. Cela tient pour partie au fait que chacun de ces opérateurs agit selon divers critères qui lui sont propres (valeur sélective des individus, probabilité d'activation de l'opérateur, etc.).

OPÉRATEUR DE SÉLECTION

Cet opérateur est peut-être le plus important puisqu'il permet aux individus d'une population de survivre, de se reproduire ou de mourir. En règle générale, la probabilité de survie d'un individu sera directement reliée à son efficacité relative au sein de la population.

Il existe plusieurs méthodes pour la reproduction .La méthode la plus connue et utilisée est sans nul doute, la roue de loterie biaisée (roulette wheel) de Goldberg (1989). Selon cette méthode, chaque chromosome sera dupliqué dans une nouvelle population proportionnellement à sa valeur d'adaptation. Nous effectuons, en quelque sorte, autant de tirages avec remises qu'il y a d'éléments dans la population. Ainsi, dans le cas d'un codage binaire, la fitness d'un chromosome particulier étant f(d(A)), la probabilité avec laquelle il sera réintroduit dans la nouvelle population de taille N est:

  (57.123)

Les individus ayant une grande fitness ont donc plus de chance d'être sélectionnées. Nous parlons alors de "sélection proportionnelle".

L'inconvénient majeur de cette méthode repose sur le fait qu'un individu n'état pas le meilleur pourrait tout de même dominer la sélection (imaginez la recherche du maxima d'une fonction dans , il peut y en a avoir plusieurs - de maxima - et donc mauvaise sélection...), nous parlerons alors à juste titre de "convergence prématurée" et c'est l'un des problèmes les plus fréquents lors de l'utilisation des algorithmes génétiques. Elle peut aussi donc engendrer une perte de diversité par la domination d'un super individu. Un autre inconvénient est sa faible performance vers la fin quand l'ensemble des individus se ressemblent.

Une solution à ce problème ne tient pas dans l'utilisation d'une autre méthode de sélection mais dans l'utilisation d'une fonction de fitness modifiée. Ainsi, nous pouvons utiliser un changement d'échelle (scaling) afin de diminuer ou accroître de manière artificielle l'écart relatif entre les fitness des individus.

Brièvement, il existe d'autres méthodes, la plus connue étant celle du tournoi (tournament selection) : nous tirons deux individus aléatoirement dans la population et nous reproduisons le meilleur des deux dans la nouvelle population. Nous refaisons cette procédure jusqu'à ce que la nouvelle population soit complète. Cette méthode donne de bons résultats. Toutefois, aussi important que soit la phase de sélection, elle ne crée pas de nouveau individus dans la population. Ceci est le rôle des opérateurs de croisement et de mutation.

OPÉRATEUR DE CROISEMENT

L'opérateur de croisement permet la création de nouveaux individus selon un processus fort simple. Il permet donc l'échange d'information entre les chromosomes (individus). Tout d'abord, deux individus, qui forment alors un couple, sont tirés au sein de la nouvelle population issue de la reproduction. Puis un (potentiellement plusieurs) site de croisement est tiré aléatoirement (chiffre entre 1 et l-1). Enfin, selon une probabilité que le croisement s'effectue, les segments finaux (dans le cas d'un seul site de croisement) des deux parents sont alors échangés autour de ce site :

  (57.124)

Cet opérateur permet la création de deux nouveaux individus. Toutefois, un individu sélectionné lors de la reproduction ne subit pas nécessairement l'action d'un croisement. Ce dernier ne s'effectue qu'avec une certaine probabilité. Plus cette probabilité est élevée et plus la population subira de changement.

Quoi qu'il en soit, il se peut que l'action conjointe de la reproduction et du croisement soit insuffisante pour assurer la réussite de l'AG. Ainsi, dans le cas du codage binaire que nous avons choisi jusqu'ici, certaines informations (in extenso : caractères de l'alphabet) peuvent disparaître de la population. Ainsi aucun individu de la population initiale ne contient de 1 en dernière position de la chaîne, et que ce 1 fasse partie de la chaîne optimale à trouver, tous les croisements possibles ne permettront pas de faire apparaître ce 1 initialement inconnu. En codage réel, une telle situation peut arriver si utilisant un opérateur simple de croisement, il se trouvait qu'initialement toute la population soit comprise entre 0 et 40 et que la valeur optimale était de 50. Toutes les combinaisons convexes possibles de chiffres appartenant à l'intervalle [0,40] ne permettront jamais d'aboutir à un chiffre de 50. C'est pour remédier entre autre à ce problème que l'opération de mutation est utilisée.

OPÉRATEUR DE MUTATION

Le rôle de cet opérateur est de modifier aléatoirement, avec une certaine probabilité, la valeur d'un composant de l'individu. Dans le cas du codage binaire, chaque bit est remplacé selon une probabilité par son inverse . C'est ce qu'il illustre la figure ci-dessous. Tout comme plusieurs lieux de croisement peuvent être possibles, nous pouvons très bien admettre qu'une même chaîne puisse subir plusieurs mutations.

  (57.125)

La mutation est traditionnellement considérée comme un opérateur marginal bien qu'elle confère en quelque sorte aux algorithmes génétiques la propriété d'ergodicité (in extenso : tous les points de l'espace de recherche peuvent être atteints). Cet opérateur est d'une grande importance. Il a de fait un double rôle : celui d'effectuer une recherche locale et/ou de sortir d'une trappe (recherche éloignée).

Les opérateurs de l'algorithme génétique sont guidés par un certain nombre de paramètres fixés à l'avance. La valeur de ces paramètres influence la réussite ou non d'un algorithme génétique. Ces paramètres sont les suivants :

- La taille de la population N, et la longueur du codage de chaque individu l (dans le cas de codage binaire). Si N est trop grand, le temps de calcul de l'algorithme peut s'avérer très important, et si N est trop petit, il peut converger trop rapidement vers un mauvais chromosome.

- La probabilité de croisement . Elle dépend de la forme de la fonction de fitness. Son choix est en général heuristique (tout comme pour ). Plus elle est élevée, plus la population subit évidemment de changements importants. Les valeurs généralement admises sont comprises entre 0.5 et 0.9.

- La probabilité de mutation . Ce taux est généralement faible puisqu'un taux élevé risque de conduire à une solution sous-optimale.

Plutôt que de réduite , une autre façon d'éviter que les meilleurs individus soient altérés est d'utiliser la reconduite explicite de l'élite dans une certaine proportion. Ainsi, bien souvent, les meilleurs 5%, par exemple, de la population sont directement reproduits à l'identique, l'opérateur de reproduction ne jouant alors que sur les 95% restant. Cela est appelé une "stratégie élitiste".

Parant du constat que les valeurs des paramètres des différents opérateurs sont eux-mêmes inconnus et ne peuvent être améliorés au fur et à mesure que de manière expérimentale, certains auteurs, tels que Novkovic et Sverko (1997), proposent d'utiliser une sorte de méta-AG : l'un pour trouver l'individu optimal et l'autre pour trouver la valeur optimale des paramètres. Ces deux algorithmes tourneraient alors simultanément ou séquentiellement. Toutefois, il est inévitable que le temps de calcul (la complexité algorithmique) s'alourdisse en conséquence.

Voyons maintenant un exemple d'AG (exemple de Goldberg - 1989). Il consiste à trouver le maximum de la fonction sur l'intervalle [0,31] où x est un entier. La première étape consiste à coder la fonction. Par exemple, nous utilisons un codage binaire de x, la séquence (chromosome) contenant au maximum 5 bits. Ainsi, nous avons , de même . Nous recherchons donc le maximum d'une fonction de fitness (nous choisirons lui-même dans cet exemple simple) dans un espace de 32 valeurs possible de x.

1. Tirage et évaluation de la population initiale

Nous fixons la traille de la population à . Nous tirons donc de façon aléatoire 4 chromosomes sachant qu'un chromosome est composé de 5 bits, et chaque bit dispose d'une probabilité ½ d'avoir une valeur 0 ou 1. Le maximum, (au hasard) 16 est atteint par la deuxième séquence. Voyons comment l'algorithme va tenter d'améliore ce résultat.

D'abord nous obtenons le tableau suivant :

N°	Chromosome	Valeur	Fitness f(x)	Pi %
1	00101	5	5	14.3
2	10000	16	16	45.7
3	00010	2	2	5.7
4	01100	12	12	34.3
Total			35	100

Nous tournons donc quatre fois cette roue pour obtenir la séquence suivante :

Nous voyons bien ici le risque que nous aurions à perdre la séquence N° 2 dès le départ... c'est le problème de cette méthode. Elle peut converger moins vite que d'autres. Cependant, le lecteur remarquera que nous avons perdu la séquence N° 3.

Nous passons maintenant à la partie du croisement : les parents sont sélectionnés au hasard. Nous tirons aléatoirement un lieu de croisement ("site" ou "locus") dans la séquence. Le croisement s'opère alors à ce lieu avec une probabilité . Le tableau ci-dessous donne les conséquences de cet opérateur en supposant que les chromosomes 1 et 3, puis 2 et 4 sont appariés et qu'à chaque fois le croisement s'opère (par exemple avec ).

Nous passons maintenant à la partie mutation : dans cet exemple à codage binaire, la mutation est la modification aléatoire occasionnelle (de faible probabilité) de la valeur d'un bit (inversion d'un bit). Nous tirons ainsi pour chaque bit un chiffre aléatoire entre 0 et 1 et si ce chiffre est inférieur à alors la mutation s'opère. Le tableau ci-dessous avec met en évidence ce processus :

Anc. Chr.	Tirage aléa.	Nouveau bit	Nouveau Chr.
10001	15 25 36 04 12	1	10011
00100	26 89 13 48 59	-	00100
01000	32 45 87 22 65	-	01000
10100	47 01 85 62 35	1	11100

Maintenant que la nouvelle population est entièrement créée, nous pouvons de nouveau l'évaluer :

Le maximum est maintenant 28 (N° 4). Nous sommes donc passés de 16 à 28 après une seule génération. Bien sûr, nous devons recommencer la procédure à partir de l'étape de sélection jusqu'à ce que le maximum global, 31, soit obtenu, ou bien qu'un critère d'arrêt ai été satisfait.