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 ne garde que la meilleure solution de la Population
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
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
- 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} }$$
- 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}} $$
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)
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
Hi,
RépondreSupprimerla 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
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 ...
SupprimerOn 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 .