Algorithme génétique et algèbre linéaire

Quand on pense aux algorithmes génétiques on pense d'abord au problème du voyageur de commerce (PVC). Pourtant d'un point de vue pédagogique il existe des problèmes plus simples pour débuter avec la manipulation des algorithmes génétiques, par exemple la résolution de systèmes d'équations linéaires. Voici un petit exemple de résolution approchée d'un système linéaire d'équations $Ax=y$  basé sur cette méthode :

résolution d'un système d'équations linéaires par algorithme génétique

Comme vous pouvez le voir l'algorithme génétique converge bien vers la solution du système ... même si cette convergence est assez lente. Pour comprendre cet exemple commençons par souligner les avantages d'étudier  la résolution d'un système d'équations linéaires plutôt qu'un problème du type PVC :

• d'abord c'est un problème bien mieux connu de celui qui veut  comprendre le fonctionnement des algorithmes génétiques que ne l'est le PVC, ce qui permet de se concentrer sur les caractéristiques des algorithmes génétiques. 
• ensuite on dispose ici de moyens efficaces pour produire des données de tests, dont on peut connatre la solution exacte contrairement au PVC, ce qui permet de bien mieux évaluer la qualité de la solution donnée par l'algorithme génétique.

Algorithme Génétique
Au départ
      on  génère aléatoirement une Population = un ensemble de solutions au problème
A chaque étape 

• on opère une sélection  des meilleurs individus de cette Population (l'élite) suivant le critère qu'on veut optimiser
• on génère une nouvelle Population par Croisement des membres de l'élite 
• on modifie t%  des individus de la nouvelle Population par Mutation  
  

A la fin
      on ne garde  que la meilleure solution de la Population

Pour adapter l'algorithme génétique à la résolution d'un système d'équations linéaires  il faut comprendre qu'ici la population sera représenté par une matrice  dont chaque colonne représente un vecteur x potentiellement solution du système. En reprenant les conventions du billet problème du voyageur de commerce  voici comment modifier l'implémentation des trois étapes principales :

• La quantité à optimiser serait la précision relative de la solution $d ={ \Vert A x-y \Vert \over \Vert x\Vert }$ avec $\Vert . \Vert$ une norme vectorielle sur ${\mathbb R}^n$
  

  function D=CalculAdapt(P)
      D=max(abs(A*P-y))./max(abs(y))
  endfunction

• La recombinaison de deux solutions approchées de $Ax = y$ (disons $x_1$ et $x_2$) en deux autres solutions ($x_3$ et $x_4$) peut être faite avec les formules:
  $x_3 = {x_1 + x_2\over 2} ~~~~~~ x_4 = {3 x_1-x_2\over 2}$
  

  function [P1, P2]=Croisement(E1, E2)
      P1=(E1+E2)/2
      P2=(3*E1-E2)/2
  endfunction

• L'étape de mutation peut être obtenue par l'ajout d'une partie aléatoire à la solution
  $x '= x + rand (x) $ avec une partie aléatoire telle que $\Vert rand (x) \Vert <\Vert x \Vert$
  

  function M=Mutation(P)
       l=max(abs(P))
       M=P+grand(P,'unf',-l,l)
  endfunction

On pourra remarquer que c'est beaucoup plus simple à programmer que dans le cas du PVC!  Bien évidement, un tel système d'équations peut être résolu plus rapidement en utilisant la méthode de Gauss, mais comme vous pouvez le voir sur l'animation , en partant d'une population assez nombreuse (400 vecteurs quand même!), l'algorithme génétique trouve une solution approchée (à moins de 0,1% près) en moins de 100 étapes (et un taux de mutation de 2%). 

Avec la même méthode il est aussi possible de trouver un(e) vecteur(valeur) propre d'une matrice. Pour cela il suffit de trouver un moyen d'évaluer (approximativement) la valeur propre $\lambda$ à partir du vecteur propre associé $x$ ... la bonne idée est de faire l'approximation : $$\lambda \approx {\langle x, Ax\rangle \over \Vert x \Vert ^ 2 + \varepsilon^ 2}$$ avec $\Vert z \Vert^2 = \langle z,z \rangle $, est la norme-vectorielle associée au produit scalaire $\langle .,.\rangle $ sur ${\mathbb R}^n$, et en utilisant un $\varepsilon> 0$ assez petit pour éviter la division par 0. L'algorithme génétique s'adapte alors facilement en remplaçant la quantité à optimiser par $d = {\Vert A x-\lambda x \Vert \over \Vert x\Vert} $ avec $\lambda$ la valeur propre (approchées) correspondant à $x$.

function D=CalculAdapt(P)
    x=P
    L=((x.')*(A*x))/(%eps+sum(x.^2))// %eps=10^(-16)
    D=max(abs(A*x-L*x))./max(abs(x))
endfunction

Voici un autre exemple montrant la progression du calcul d'un(e) vecteur(valeur) propre avec un algorithme génétique :

recherche de valeur/vecteur propre par algorithme génétique

Notez que l'algorithme génétique ne peut trouver qu'un(e) vecteur(valeur) propre réelle, même si ils en existent d'autres, qui sont éventuellement à valeurs complexes. Dans le cas particulier  étudié ici on peut retrouver les valeurs propres et les vecteurs propres correspondants (avec la commande spec dans  scilab). On verrait alors qu'il y en a 5 (dont 2 complexes) et que l'algorithme génétique trouve ici facilement et assez précisément  la valeur $\lambda_5= - 4.3710668$ :

•  $$\lambda_1= 6.5275868 ,~~x_1= {\begin{pmatrix}-0.4276754\cr 0.2877932\cr -0.1525824\cr 0.5346638\cr 0.6520138\cr \end{pmatrix}} $$    
• $$ \lambda_2= -3.67522+3.5349699i ,~~x_2= {\begin{pmatrix}0.6191384\cr 0.1109582-0.1685853i\cr -0.0139682-0.4454377i\cr 0.3810490+0.0954854i\cr 0.2391684-0.4071949i\cr \end{pmatrix}}  $$ 
• $$ \lambda_3= -3.67522-3.5349699i ,~~x_3= {\begin{pmatrix}0.6191384\cr 0.1109582+0.1685853i\cr -0.0139682+0.4454377i\cr 0.3810490-0.0954854i\cr 0.2391684+0.4071949i\cr \end{pmatrix}}    $$
• $$\lambda_4= -1.80608 ,~~x_4= {\begin{pmatrix}-0.3165088\cr 0.1060281\cr -0.2444219\cr -0.6895917\cr 0.5943917\cr \end{pmatrix}} $$ 
• $$\lambda_5= -4.3710668 ,~~x_5= {\begin{pmatrix}0.4761602\cr -0.2180820\cr 0.3387970\cr 0.7708902\cr 0.1290608\cr \end{pmatrix}}    $$