vendredi 14 décembre 2012

Les Algorithmes Génétiques

Le Problème du Voyageur de Commerce  (abrégé en PVC ou TSP en anglais pour "Travelling Salesman Problem") est un problème fondamental de la théorie des graphes qui s'exprime par  :

"soit n villes, trouver le circuit le plus court possible passant exactement une fois par chaque ville"

 On ne sait résoudre le PVC que par une étude exhaustive de tous les circuits possibles, qui sont au nombre de n!,  ce qui en fait un problème de type NP-hard impossible à résoudre concrètement  dès que n dépasse quelques dizaines. La recherche d'heuristiques pour résoudre le PVC de manière approchée a conduit à s'intéresser aux Algorithmes Génétiques : une méta-heuristique surprenante permettant de résoudre de nombreux problèmes d'optimisation complexes et de natures différentes. Voici un petit exemple d'animation générée avec Scilab montrant comment cette approche permet de résoudre le PVC :
Résolution du PVC pour n=10 villes par algorithme génétique
le trajet optimal (en rouge) semble être de longueur 25.38....

Les algorithmes génétiques sont nées de l'étude du processus d'évolution des espèces découvert par Darwin.  On peut résumer leur fonctionnement comme suit :
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

Concrètement, pour mettre en œuvre un Algorithme Génétique il faut donc écrire les fonctions suivantes :
  • Populat qui génère une population (un ensemble de circuits partant de la ville 1 et parcourant une fois chaque villes pour le PVC)
  • CalculAdapt qui calcule une valeur numérique correspondant au critère que l'on veut optimiser (la longueur du circuit pour le PVC)
  • SelectElit  qui sélectionne les meilleurs individus de la Population  (les circuits les plus courts pour le PVC)
  • Croisement qui à partir de 2 individus en crée 2 nouveaux (pour le PVC celà consiste à intervertir 2 portions de circuit de deux solutions)
  • Mutation qui modifie aléatoirement un individu (échange deux villes du parcours dans le PVC)
  • Genetiq qui enchaine les différentes étapes de l’algorithme et renvoie la meilleure solution
Ces fonctions sont assez faciles à réaliser avec Scilab. Voici quelques astuces pour modéliser le problème. D'abord pour représenter les données :
  • représenter les parcours par un vecteur colonne contenant les numéros des villes dans l'ordre de la visite et la population par une matrice dont chaque colonne représente un parcours. Par exemple une population de 2*4 parcours de 5 villes donnera
    $$ \begin{pmatrix}1&1&1&1&1&1&1&1\cr 2&3&5&4&5&2&4&5\cr 4&4&3&2&3&5&2&2\cr 5&2&2&3&4&3&3&3\cr 3&5&4&5&2&4&5&4\cr \end{pmatrix} $$
  • représenter les données du problème par une matrice symétrique Dist(i,j) donnant la distance entre les villes i et j (si on veut tracer les circuits obtenus il faut construire Dist à partir d'une liste de coordonnées pour les n villes). Par exemple pour 5 villes on aura :
    $$ Dist={\begin{pmatrix} 0&0.3120807&0.8476272&0.2990498&0.9577475\cr  0.3120807&0&0.8698077&0.0557149& 0 .8729774\cr 0.8476272&0.8698077&0&0.6714715&0.2605612\cr 0.2990498&0.0557149&0.6714715&0&0.6192178\cr 0.9577475&0.8729774&0.2605612&0.6192178&0\cr \end{pmatrix} }$$
Ensuite pour les fonctions à écrire
  • function P=Populat(n,m) qui génère 2m parcours des n villes, utiliser grand avec l'option 'perm' pour permuter les éléments d'un vecteur. Par exemple :
    -->P=Populat(5,4)
     P  =

        1.    1.    1.    1.    1.    1.    1.    1. 
        2.    3.    5.    4.    5.    2.    4.    5. 
        4.    4.    3.    2.    3.    5.    2.    2. 
        5.    2.    2.    3.    4.    3.    3.    3. 
        3.    5.    4.    5.    2.    4.    5.    4. 
  • function d=CalculAdapt(I,Dist)  qui calcule la longueur du circuit (sans oublier le retour au point de départ ): d=Dist(I(1),I(2))+...+Dist(I(n-1),I(n))+Dist(I(n),I(1)). Par exemple :$$I={\begin{pmatrix}1\cr 4\cr 3\cr 2\cr 5\cr \end{pmatrix}} \Rightarrow CalculAdapt(I)=3.6710539$$ 
  • function E=SelectElit(P)  calculer la "longueur" de chaque solution puis les ordonner en récupérant leur classement avec gsort. Par exemple Pour la population dont les longueurs sont
    -->longueurs
     longueurs  =

        2.0952019    3.4055385    2.4428811    2.4428811    2.2575758    2.4161407    2.4428811    3.6710539 
     on aura le classement
    -->[liste,ordre]=gsort(longueurs,'g','i')
     ordre  =

        1.    5.    6.    3.    4.    7.    2.    8. 
     liste  =

        2.0952019    2.2575758    2.4161407    2.4428811    2.4428811    2.4428811    3.4055385    3.6710539
    qui permet de réordonner la population :
    -->P(:,ordre)
     ans  =

        1.    1.    1.    1.    1.    1.    1.    1. 
        2.    5.    2.    5.    4.    4.    3.    5. 
        4.    3.    5.    3.    2.    2.    4.    2. 
        5.    4.    3.    2.    3.    3.    2.    3. 
        3.    2.    4.    4.    5.    5.    5.    4. 
  • function M=Mutation(I) choisir 2 indices i et j à échanger dans le parcours I. Par exemple : $$ I={\begin{pmatrix}1\cr 4\cr 3\cr 2\cr 5\cr \end{pmatrix}}\Rightarrow Mutation(I)={\begin{pmatrix}1\cr 5\cr 3\cr 2\cr 4\cr \end{pmatrix}} $$
La fonction la plus difficile à écrire est function [P1,P2]=Croisement(I1,I2) qui à partir de 2 individus (I1,I2) en crée 2 nouveaux(P1,P2)  en croisant deux portions de circuits car il faut s'assurer qu'après croisement les nouveaux circuits passent bien par chaque ville une et une seule fois ! C'est la partie la plus difficile à résoudre dans ce problème, voici une solution possible :

function [P1, P2]=Croisement(E1, E2)
    n=length(E1)// nombre de villes 
    I=grand(1,2,'uin',2,n),I=gsort(I,'g','i')// choix de 2 villes à permuter
    //sections à échanger
    S1=E1(I(1):I(2))
    S2=E2(I(1):I(2))
    //éléments manquants/en doublons
    T1=[],T2=S2
    for x=S1' // S1 doit être en ligne
        ind=find(T2==x)
        if ind==[] then T1=[T1 x]// ajoute dans T1
            else T2(ind)=[]//élimine de T2
        end
    end
    // corriger les défauts ....
    k=length(T1)
    for l=1:k
        x1=T1(l)//manquant dans P1
        x2=T2(l)//manquant dans P2
        ind1=find(S2==x2)// S2 mis dans P1
        ind2=find(S1==x1)// S1 mis dans P2
        S2(ind1)=x1
        S1(ind2)=x2
    end
    //enfants temporaires
    P1=E1,P1(I(1):I(2))=S2
    P2=E2,P2(I(1):I(2))=S1
endfunction

Il ne reste plus qu'à écrire la fonction qui enchaine les différentes étapes de l’algorithme et renvoie la meilleure solution  function S=Genetiq(Dist,m,t,N) avec par exemple :
  • Dist = données de départ du problème
  • n = nombre de villes  (n=10 à 20 pour garder un temps de calcul raisonnable)
  • m = demi-population donc 2*m = le nombre d'individus  ( m=50 à 100)
  • t= taux de mutation entre 0 et 1 (de 10 % à 30% ici)
  • N= nombre d'étape (20 à 30 pour être raisonnable)
voici le code de la fonction Genetiq :

function S=Genetiq(Dist, m, t,N)
    s=size(Dist), n=s(1)// n=nombre de villes
    P=Populat(n,m)// population de départ 2m individus
    for i=1:N
        E=SelectElit(P)//sélectionne les m meilleures solutions
        // pour affichage dans la consoleclassement des m meilleurs solutions
        S=E(:,1)// on prend la première
        d=CalculAdapt(S)// longueur du plus court circuit trouvé
        disp('à l''étape i= '+string(i)+' la meilleure solution a pour longueur d='+string(d))
      //croisement des meilleurs individus
        P=[]// nouvelle population
        for j=1:m
            I=grand(1,2,'uin',1,m)// choix de 2 individus
            E1=E(:,I(1)),E2=E(:,I(2))// les 2 individus
            [P1,P2]=Croisement(E1,E2)//croisement
            P=[P,P1,P2]// ajout à la nouvelle population
        end
        //mutation d'une partie des nouveaux individus
        nb_mut=round(t*2*m)// nombre d'individus à faire muter
        num=grand(1,2*m,'def'),[a,b]=gsort(num),ind=b(1:nb_mut)// choix de nb_mut individus
        for j=1:nb_mut
            P(:,j)=Mutation(P(:,j))
        end
    end
    E=SelectElit(P)// classement des m meilleurs solutions
    S=E(:,1)// on prend la première
    d=CalculAdapt(S)// longueur du plus court circuit trouvé
    disp('la meilleure solution a pour longueur d='+string(d))
endfunction

2 commentaires:

  1. Hi,
    la fonction SelectElit ne prend qu'un argument : la population. Or dans la description de cette fonction, vous dites qu'il faut calculer la longueur de chaque parcours (appel a calculadapt ?!). Je me demandais si il n'y avait donc pas une erreur dans les arguments de cette fonction qui serait plutot P (population) et dist (matrice des distances) qui permettrait de faire un appel a calculadapt.
    Sinon je n'ai rien compris.
    Merci pour votre aide

    Pourriez-vous me faire parvenir votre réponse a l'adresse email : axiiom.home@gmail.com

    RépondreSupprimer
    Réponses
    1. effectivement la fonction SelectElit appelle à chaque fois la fonction CalculAdapt, qui elle même fait appel à chaque fois à la matrice des distances Dist. On pourrait mettre Dist en paramètre d'entré de CalculAdapt mais comme ce paramètre sera le même à chaque appel c'est très lourd!!! Ici je considère que Dist est une variable "Globale" qui ne change pas durant tout l'algorithme. D'ailleurs c'est un paramètre de la fonction Genetiq à l'intérieur de laquelle sont appelés CalculAdapt et SelectElit, et ce sera toujours la même matrice Dist qui sera utilisé et jamais modifiée donc autant ne pas la placer en paramètre d'entré des différentes fonctions ...

      On pourrait voir ça comme une fonctionnalité très agréable du langage scilab de pouvoir considérer une variable comme Locale à une fonction (issue des paramètres d'entré) ou globale (définie au chargement de l'environnement) suivant qu'elle être modifiée ou pas. En fait c'est quelque chose d'intrinsèque à tous les langages de script, comme scilab, et il faut comprendre que lorsqu'on appelle une fonction à l'intérieur d'une autre fonction , la fonction appelée hérite de toutes les variables connues de la fonction appelante qui sont donc pour elle des variables globale (si elles ne sont pas redéfinies localement la valeur est récupérée de l'environnement appelant). La compréhension de ce mécanisme est importante dans tous les langages de script .

      Supprimer

Pour écrire des formules mathématiques vous pouvez utiliser la syntaxe latex en mettant vos formules entre des "dollars" $ \$....\$ $ par exemple :
- $\sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}$ s'obtient avec \sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}
- $\mathbb R$ s'obtient avec {\mathbb R} et $\mathcal D$ s'obtient avec {\mathcal D}
- pour les crochets $\langle .,. \rangle$ dans les commentaires utilisez \langle .,. \rangle
vous pouvez écrire du html dans les commentaires :
- italique <i> ... </i> gras <b> ... </b>
- lien <a href="http://adresse "> .... </a>