TP ALGORITME GENITIQUE Master Recherche Opérationnelle

2

INTRODUCTION

Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est

d'obtenir une solution approchée à un problème d'optimisation pour le résoudre en un temps

raisonnable. Les algorithmes génétiques utilisent la notion de sélection naturelle et l'appliquent à une

population de solutions potentielles au problème donné.

Origine :

L'utilisation d'algorithmes génétiques, dans la résolution de problèmes, est à l'origine le fruit des

recherches de John Holland et de ses collègues et élèves de l'Université du Michigan qui ont, dès1960,

travaillé sur ce sujet.

Problème de voyageur de commerce

Le problème du voyageur de commerce consiste, étant donné un ensemble de villes séparées par

des distances données, à trouver le plus court chemin qui relie toutes les villes et retourner à la ville de

départ .tel que chaque ville n’est visiter qu’une fois .

Il s'agit d'un problème d'optimisation pour lequel on ne connait pas d'algorithme permettant de trouver

une solution exacte en un temps polynomial.

3

Enoncée :

On se propose de résoudre le problème de voyageur de commerce par un AG .

On cherche à déterminer le plus court chemin Hamiltonien passant par les villes :

Agadir, Casablanca, Fès, Marrakech, Meknès, Rabat, Tanger.

CODE :

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<time.h>

int S[10][10]={{0,650,795,305,745,615,900},

{650,0,290,240,230,95,370},

{795,290,0,485,60,200,305},

{305,240,485,0,475,335,610},

{745,230,60,475,0,140,295},

{615,95,200,335,140,0,280},

{900,370,305,610,295,280,0}};

4

int N=7;

const int taille_pop=10;

/*

cette fonction affiche la matrice des cout (distance)

*/

void afficher(int N,int M,int S[10][10])

{

for(int i=0;i<N;i++)

{

for(int j=0;j<M;j++)

printf("%d\t",S[i][j]);

printf("\n");

}

}

/*

cette fonction génère un individu aléatoirement et en même temps fait le codage de l'individu

en des nombres compris entre 0 et 6

*/

void generer_ind(int ind[])

{

for(int i=0;i<N;i++)

{

ind[i]=rand()%7;

for(int j=0;j<i;j++)

if(ind[j]==ind[i])

i--; // on s'assurent que l’individu soit réalisable (le meme nombre(ville)ne se répètent pas)

}

}

/*

génère la population

5

*/

void generer_pop(int pop[taille_pop][10])

{

for(int i=0;i<taille_pop;i++)

generer_ind(pop[i]);

}

/*

afficher un individu

*/

void afficher(int n,int T[])

{

for(int i=0;i<n;i++)

printf("%d\t",T[i]);

}

/*

affiche un individu par nom de ville

*/

void afficher_ville(int n,int ind[])

{

for(int i=0;i<n;i++)

switch(ind[i])

{

case 0:printf("Agadir ");break;

case 1:printf("Casablanca ");break;

case 2:printf("Fes ");break;

case 3:printf("Marrakech ");break;

case 4:printf("Meknes ");break;

case 5:printf("Rabat ");break;

case 6:printf("Tanger ");break;

default:printf("Erreur, ville inconnue");

}

}

6

/*

calcule la distance (le cout ) d'un individu

*/

float distance(int ind[])

{

float Dist=0;

for(int i=0;i<N-1;i++)

Dist+=S[ind[i]][ind[i+1]];

Dist+=S[ind[0]][ind[N-1]];// on ajoute le cout de retour

return Dist;

}

/*

calcule de fitness qui ne permettra d' évaluer l'individu

*/

float fitness(int ind[])

{

return 1./distance(ind);

}

/*

fonction qui retourne le meilleure individu de la population

*/

int meilleur_ind(int pop[taille_pop][10])

{

int id=0;

for(int i=1;i<taille_pop;i++)

if(fitness(pop[i])>fitness(pop[id]))

id=i;

return id;

}

/*

fonction qui permet de sélectionner aléatoirement l'indice d'un individu de la population

on fera appelle a cette fonction dans selection_tournois

*/

int selection_alia()

{ int id;

7

id= rand()%10;

return id;

}

/*

la fonction selection_tournois selectionne le meilleure individu

parmi des individu selectioner aliatiorement

*/

int selection_tournois(int pop[10][10])

{int i1,i2,i3,imax;

i1=selection_alia();

i2=selection_alia();

i3=selection_alia();

imax=i1;

if(fitness(pop[i2])>fitness(pop[imax]))

imax=i2;

if(fitness(pop[i3])>fitness(pop[imax]))

imax=i3;

return (imax);

}

/*

on utilise la selection_tournois pour selectionner

des individus de telles sortent a ne pas dépasser le pourcentage des individus à sélectionner ici 0,7.

*/

void selection_croisement(int*nc,int C[],int pop[10][10])

{

float sommeFitness=0;

int i;

for(i=0;i<taille_pop;i++)

sommeFitness+=fitness(pop[i]);

int j=0;

float pc=0;

while(pc<=0.7)

{int id;

8

id=selection_tournois( pop);

pc+=fitness(pop[id])/sommeFitness;/* ici on associe a chaque individu selectioner un segment

relatif a sa fitness */

C[j]=id;// on stok les indices des individus selectionner dans un tabeau pour les croiser aprés

*nc=j+1;/*on incremente chaque fois la taille du tableau des ind selectioner que on selectionent pr

savoir dans le croisment combien on va croiser*/

j++;

}

}

/*

le même principe pour la selection pour la mutation

*/

int* selection_mutation(int*nm,int M[],int pop[10][10])

{

float sommeFitness=0;

int i;

for(i=0;i<taille_pop;i++)

sommeFitness+=fitness(pop[i]);

int j=0;

float pm=0;

while(pm<=0.3)

{int id;

id=selection_tournois(pop);

pm+=fitness(pop[id])/sommeFitness;

M[j]=id;

*nm=j+1;

j++;

}

return M;

}

9

/*

on fait le croisement un point des ind sélectionner pour le croisement

*/

void croisement (int P1[],int P2[],int E1[],int E2[])

{int i,j;

int k;

do {

k=rand()%7;// on sélectionne un point de croisement aléatoirement de façon qui il soit entre 1 et 6

}while(k==6);// pour seulement assurer que le croisement est fait si non si k=6 en tombe sur les mêmes individu

for(i=0;i<=k;i++)

{ E1[i]=P1[i];

E2[i]=P2[i];

}

// Jusqu’a ici on a met la partie 1 de parent 1 dans enfant 1

// Et la partie 2 de parent 2 dans enfant 2

/* maintenant on va faire le croisement avec correction

*/

int id=k+1;

/* on va compléter l'enfant 1 par les gènes du parent 2 qui sont déférent de

ce qui existe déjà dans l'enfant 1*/

for(i=0;i<N;i++)

{

int nb=0;/* on déclare un variable pour savoir si chaque gêne de P1

Existe ou non dans tt E1*/

/* la variable vas prendre a la fin le nombre de comparaison faite

et si le nombre est k+1 alors la gêne n'apparu pas dans E1*/

for (j=0;j<=k;j++)

{if (P2[i]!=E1[j])

nb++;

else

10

break;// Si il y a égalité pas la paine de continuité la comparaison

}

/* voila maintenant on va vérifier si notre variable à pris k+1 ou

On a sortie de la boucle sans terminer toutes les comparaisons est

Donc avec une valeur inferieur à k+1 */

if (nb==k+1)

{E1[id]=P2[i];// si on a fait k+1 comparaisons donc la gêne n'apparu pas et donc en l'ajoute a E1

id++;}

}

// le mm principe se fait pour E2

int ide=k+1;

for(i=0;i<N;i++)

{

int nb=0;

for (j=0;j<=k;j++)

{ if (P1[i]!=E2[j])

nb++;

else

break; }

if (nb==k+1)

{E2[ide]=P1[i];

ide++;}

}

}

/*

On fait maintenant la mutation

*/

void mutation(int P[], int E[])

{

int i;

for(i=0;i<7;i++)

11

E[i]=P[i];

int a,b,c;

// on choisi les point de mutation aléatoirement

do

{ a=rand()%7;

b=rand()%7;

}while(a==b);

c=E[a]; //on pose le contenu de E[a] dans un variable pour ne pas le perdre

E[a]=E[b];

E[b]=c;

}

/*

le remplacement et fait a l'intérieur du main

*/

int main(int argc, char *argv[])

{

time_t ti;

srand ((unsigned) time(&ti));

int ind[10],pop[taille_pop][10];

int r;

int solution[7]={4,1,2,3,6,5,0};

int h=0;

/*

on va répéter un nombre des itérations qu’on choisi

*/

while(h<10) {

generer_pop(pop);

int nc=0;

int nm=0;

int C[10];

int M[10];

selection_mutation(&nm,M,pop);

12

selection_croisement(&nc, C, pop);

int E[10];

int E1[10];

int E2[10];

int i=0;

while(i<nc-1)

{/* maintenant on vas faire la croisement de tt les individus de la population dans leur indices on été

selectioner par la sélection croisement */

croisement ( pop[C[i]], pop[C[i+1]], E1, E2);

/* on fait le remplacement pour garder que les meilleurs entre les

enfants est les parents*/

/* on a choisit de remplacer le pire des parents par le meilleur enfant si la fitness de ce dernier est plus

grande de celle du pire parent */

if(fitness(E1)>=fitness(E2))

{if(fitness(pop[C[i]])<fitness(E1)&&fitness(pop[C[i]])<=fitness(pop[C[i+1]]))

{int j;

for(j=0;j<7;j++)

pop[C[i]][j]=E1[j];

}

else if(fitness(pop[C[i+1]])<fitness(E1)&&fitness(pop[C[i+1]])<fitness(pop[C[i]]))

{int j;

for(j=0;j<7;j++)

pop[C[i+1]][j]=E1[j];

}

}

else

{if(fitness(pop[C[i]])<fitness(E2)&&fitness(pop[C[i]])<=fitness(pop[C[i+1]]))

{int j;

for(j=0;j<7;j++)

pop[C[i]][j]=E2[j];

}

else if(fitness(pop[C[i+1]])<fitness(E2)&&fitness(pop[C[i+1]])<fitness(pop[C[i]]))

{int j;

13

for(j=0;j<7;j++)

pop[C[i+1]][j]=E2[j];

}

}

i=i+2;

}

// on mute la individu de la population sélectionner en sélection mutation et on remplace si enfant est

meilleur

while(i<nm)

{

mutation( pop[C[i]], E);

if(fitness(pop[C[i]])<=fitness(E))

{int j;

for(j=0;j<7;j++)

pop[C[i]][j]=E[j];

}

i++;

}

// a chaque itération on trouve l'indice de meilleur individu après tous les étapes

r=meilleur_ind( pop);

if(fitness(solution)<fitness(pop[r]))

{

int j;

for(j=0;j<7;j++)

solution[j]=pop[r][j];

}

h++;

}

/*

après répéter le while un nombre d'itérations on a une solution

*/

// on affiche la solution

int i;

printf("\nLa distance parcourue par la meilleur solution trouver est: %.2f Km",distance(solution));

14

printf("\n");

printf("la soultion est ");

printf("\n");

for(i=0;i<7;i++)

printf("%d\t",solution[i]);

getch();

return 0;

}

Résultat trouvé avec 10 itérations

Remarque

15

La solution qu’on affiche à la fin n’est pas la seule avec une meilleure distance mais si la dernière

meilleure solution que le programme a trouvé.

On peut aussi améliorer le programme on stockant toutes les meilleures solutions égales en une

matrice et les afficher.

On peut aussi afficher l’historique de tous les résultats trouvés et donc en peut chercher les résultats

égales à la solution finale.

/* a chaque itération on affiche la meilleur solution trouver avant de faire les comparaison */

r=meilleur_ind( pop);

printf(" ------iteration %d------" ,h);

printf("\nLa distance parcourue est :%.2f Km",distance(pop[r]));

printf("\nL'individu est :\n");

for(i=0;i<7;i++)

printf("%d\t",pop[r][i]);

printf("\n");

printf("\n");

Avec 4 itérations :

16

Si on augmente le nombre des itérations par exemple plus que 40 la solution trouver est optimale (car le

nombre de ville est petit dans notre cas).

17

La solution toujours donner par le programme est 2030km qui la solution optimale.

Quelques étapes teste de notre programme :

Le croisement :

int p1[7]={6,2,0,4,5,3,1};

int p2[7]={3,0,1,2,6,5,4};

int E1[7];

int E2[7];

croisement ( p1,p2,E1,E2);

printf("--------------croisement1piont----------") ;

printf("\nP1:") ;

for (int i=0;i<7;i++)

printf("\t%d",p1[i]) ;

printf("\nP2:") ;

for (int i=0;i<7;i++)

printf("\t%d",p2[i]) ;

printf("\n") ;

printf("\nE1:") ;

for (int i=0;i<7;i++)

printf("\t%d",E1[i]) ;

printf("\nE2:") ;

for (int i=0;i<7;i++)

printf("\t%d",E2[i]) ;

18

Mutation:

int p[7]={3,2,5,4,0,6,1};

int E[7];

mutation (p,E);

printf("--------------Mutation deux ville qq ----------") ;

printf("\np:") ;

for (int i=0;i<7;i++)

printf("\t%d",p[i]) ;

printf("\n") ;

printf("\nE:") ;

for (int i=0;i<7;i++)

printf("\t%d",E[i]) ;

19

Tentative croisement deux points

Comme le croisement deux points consiste à prendre la partie entre les deux points de croisement pour

l’enfant1 du père2 et les autres parties du pére1, et vis versa pour l’enfant2.

On a pensé à faire un croisement 1pionts jusqu’à le deuxième point de croisement avec le point de

croisement ci la premier.

Après on a juste a compléter avec correction ce qui reste par les gênes du pére1.

Comme ca la première partie et la dernière seront pris du père 1 et celle de milieu du pére2 (pour

l’enfant 1).

20

Code :

/*

on a fait quelque changement dans le croisement ici il va recevoir K et m

et on vas considérer qd vas croiser en individu de taille m au point k

m et k son les de points qui vont être choisi dans le croisement2piont

et le reste si le même principe que on a fait dans le croisement 1piont

*/

void croisement (int*k,int*m,int P1[],int P2[],int E1[],int E2[])

{int i,j;

for(i=0;i<=*k;i++)

{ E1[i]=P1[i];

E2[i]=P2[i];

}

int id=*k+1;

for(i=0;i<=*m;i++)

{

int nb=0;

for (j=0;j<=*k;j++)

{if (P2[i]!=E1[j])

nb++;

else

break;}

if (nb==*k+1)

{E1[id]=P2[i];

id++;}

}

int ide=*k+1;

21

for(i=0;i<=*m;i++)

{

int nb=0;

for (j=0;j<=*k;j++)

{ if (P1[i]!=E2[j])

nb++;

else

break; }

if (nb==*k+1)

{E2[ide]=P1[i];

ide++;}

}

}

/*

ici on reçoit deux individu a croiser

on fait appelle au croisement 1point pour croiser jusqu’à la grande points de croisement

(le point de croisement et la plus petite) et on complète avec correction

*/

void croisement_2point (int P1[],int P2[],int E1[],int E2[])

{int i,j,h,m;

int k;

do{

k=rand()%7;

h=rand()%7;

}while(k+h>=6);

m=k+h;/* pour s’assurer de la plus petite et la plus grand on a choisi que la grande soit une somme de la plus

petite et une autre valeur aussi choisi aléatoirement et aussi que les deux point soit inferieur à 6*/

int p1[7];

int p2[7];

// on pose les 2 individus dans deux autre jusqu’à la plus grand point de croisement

for(i=0;i<=m;i++)

{p1[i]=P1[i];

p2[i]=P2[i];

22

}

//on fait le croisement un point le point de croisement et k la plus petite

croisement ( &k,&m,p1, p2, E1, E2);

// On complète avec correction E1 de P1 ET E2 de P2

int id=m+1;

for(i=0;i<N;i++)

{

int nb=0;

for (j=0;j<=m;j++)

{if (P1[i]!=E1[j])

nb++;

else

break;}

if (nb==m+1)

{E1[id]=P1[i];

id++;}

}

int ide=m+1;

for(i=0;i<N;i++)

{

int nb=0;

for (j=0;j<=m;j++)

{ if (P2[i]!=E2[j])

nb++;

else

break; }

if (nb==m+1)

{E2[ide]=P2[i];

ide++;}

} }

23