Algorithme génétique(code)

//main.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct
{
char nom[20];
long x;
long y;
}ville;


void erreurFichier()
{
printf("L'ouverture du fichier ne peut avoir lieu car il n'est pas au bon format.\n\n");
printf("RAPPEL - Le fichier doit \x88tre format\x82 comme suit :\n\n");
printf(" Nombre de Villes (long)\n");
printf(" Nom_de_la_ville X(long) Y(long)\n");
printf(" Nom_de_la_ville X(long) Y(long)\n");
printf(" ...\n\n");
}

int formatFichier ()
{
int ret = 0;
int i;
long nombre, tailleCh;
long nbVilles, x, y;
char ligne[100];

FILE *carte;

//Tentative d'ouverture du fichier.
carte = fopen("villes.txt", "r");
if(carte == NULL)
{
printf("Erreur lors de l'ouverture du fichier.\n");
ret=-1;
}

//Vérification de la cohérence du nombre de villes annoncées.
else
{
nombre=fscanf(carte,"%ld",&nbVilles);
if((nombre!=1) || (nbVilles<4))
{
printf("Le nombre de villes est incorrect.\n");
ret=-1;
}

//Vérification des types d'informations concernant les villes.
else
{
for(i=0 ; i<nbVilles ; i++)
{

nombre=fscanf(carte,"%s %ld %ld", &ligne, &x, &y);
if(nombre != 3)
{
printf("Les informations concernant au moins une des villes ne sont pas au bon format.\n");
ret=-1;
}
//Vérification que la ville ne comporte pas plus de 20 caractères.
tailleCh=strlen(ligne);
if(tailleCh>19)
{
printf("Les nom des villes doivent faire moins de 20 caractères.\n");
ret=-1;
}
}
//Si il y a quelque chose d'autre à la fin du fichier...
if((fscanf(carte,"%s", &ligne))!=EOF)
{
printf("Le fichier contient plus d'informations que convenu.\n");
ret =-1;
}
//Si on arrive la, le format du fichier est valide !.\n");
}
}
fclose(carte);
return ret;
}

int attrapeVille (long nbVilles, ville *v)
{
int i, tampon ;
int ret=0;

if (v==0) return -1;

//Pointeur sur le fichier carte.
FILE *carte ;

//Ouverture du fichier texte
if( (carte = fopen("villes.txt", "r")) == NULL )
{
printf("Erreur d'ouverture de fichier");
ret=-1;
}

else
{
//On met de coté le nombre de villes.
fscanf(carte,"%d",&tampon);
//Mise des informations dans le tableau de structures.
for(i=0;i<nbVilles;i++)
{
fscanf(carte,"%s",v[i].nom);
fscanf(carte,"%ld",&v[i].x);
fscanf(carte,"%ld",&v[i].y);
}
//Fermeture du fichier.
fclose(carte);
}
return ret;
}
int afficheVil(long nbVilles, ville *v)
{
long i;
long longueurChaineVille;
int ret=0;

if (v == 0) return -1;

//Affichage de l'en tête du tableau des villes.
printf("\n Ville : X : Y : \n");
for(i=0;i<35;i++)
{
printf("%c",196); //Ligne horizontale (soulignement)
}
printf("\n");

//Affichage des villes et de leurs coordonnées.
for (i=0 ; i<nbVilles ; i++)
{
//On affiche la liste en tenant compte de la longueur des chaines.
longueurChaineVille=strlen(v[i].nom);

if((longueurChaineVille>0) && (longueurChaineVille<8))
{
printf("%s\t\t\t%ld\t%ld\n", v[i].nom, v[i].x, v[i].y);
}
else if((longueurChaineVille>7) && (longueurChaineVille<14))
{
printf("%s\t\t%ld\t%ld\n", v[i].nom, v[i].x, v[i].y);
}
else
{
printf("%s\t%ld\t%ld\n", v[i].nom, v[i].x, v[i].y);
}
}
return ret;
}

//Une graine pour randomiser correctement et avoir des valeur toujours differentes
int graineRandom = 0 ;

int tirage(long valeurMax)
{
int resultat;
//On fabrique une nouvelle graine pour le tirage au sort
srand(graineRandom += time(NULL));
//On soustrait 1 à nbVilles car le tableu démarre à 0.
resultat=((rand()+1)%(valeurMax--));

return resultat;
}

void classerDistances (double *distancesIndividus,const long nbIndividu, long *classementDistances)
{
int i, j;
double maxTemp=0;
long indiceTemp=0;
//Tableau de vérification des distances déjà classées.
int verifDoublon[nbIndividu];

//Initialisation des tableaux de classement et de vérification à 0.
for (i=0 ; i<nbIndividu ; i++) classementDistances[i]=0;
for (i=0 ; i<nbIndividu ; i++) verifDoublon[i]=0;


for (i=0 ; i<nbIndividu ; i++)
{
for (j=0 ; j<nbIndividu ; j++)
{
if ((distancesIndividus[j]>=maxTemp) && (verifDoublon[j]!=1))
{
maxTemp=distancesIndividus[j];
indiceTemp=j;
}
}

classementDistances[i]=indiceTemp;
verifDoublon[indiceTemp]=1;
maxTemp=0;
indiceTemp=0;
}
printf("\nDistances classees par ordre decroissant :\n");
printf("(dernier chiffre correspond à l'indice de l'individu dans la population 1).\n\n");
for (i=0 ; i<nbIndividu ; i++) printf("Individu %i : %lf - %ld\n", i, distancesIndividus[classementDistances[i]], classementDistances[i]);
}


void calculDistances (ville *v, long *population,const long nbVilles,const long nbIndividu, double *distancesIndividus)
{
long x1, x2, y1, y2;
long diffX, diffY;
long i, j;


//Initialisation des distances à 0.0 (double).
for (i=0 ; i<nbIndividu ; i++) distancesIndividus[i]=0.0;

for (i=0 ; i<nbIndividu ; i++)
{
//Calcul de la distance de la ville de départ à la dernière ville.
for (j=1 ; j<nbVilles ; j++)
{
x1=v[*(population+i*nbVilles+j-1)].x;
x2=v[*(population+i*nbVilles+j)].x;
y1=v[*(population+i*nbVilles+j-1)].y;
y2=v[*(population+i*nbVilles+j)].y;

//Différence des abscisses puis des ordonnées.
diffX=x1-x2;
diffY=y1-y2;
//Elévation au carré de la différence.
diffX*=diffX;
diffY*=diffY;
distancesIndividus[i]+=sqrt(diffX+diffY);
}
//Ajout de la distance pour rentrer à la maison...
x1=v[*(population+i*nbVilles)].x;
x2=v[*(population+i*nbVilles+(nbVilles-1))].x;
y1=v[*(population+i*nbVilles)].y;
y2=v[*(population+i*nbVilles+(nbVilles-1))].y;
//Différence des abscisses puis des ordonnées.
diffX=x1-x2;
diffY=y1-y2;
//Elévation au carré de a différence.
diffX*=diffX;
diffY*=diffY;
distancesIndividus[i]+=sqrt(diffX+diffY);
}

printf("Calcul des distances des individus de la population 1 :\n\n");
for (i=0 ; i<nbIndividu ; i++)
{
printf("Distance individu %i : %lf\n", i, distancesIndividus[i]);
}


}

void creerIndividus (ville *v, const long vDepart, const long nbVilles, const long nbIndividu, long *population)
{
int i, j, tempVerif;

//Tableau où l'on mettra 1 si la ville a déja été positionnée.
long verifDoublon[nbIndividu][nbVilles];

//Initialisation du tableau de vérifications à 0.
for (i=0 ; i<nbIndividu ; i++)
{
for (j=0 ; j<nbVilles ; j++) verifDoublon[i][j]=0;
}

//On place la ville de départ en première position de l'individu.
for (i=0 ; i<nbIndividu ; i++)
{
*(population+i*nbVilles)=vDepart;
verifDoublon[i][vDepart]=1;
}

//Tirage aléatoire des villes suivantes des individus.
for (i=0 ; i<nbIndividu ; i++)
{
for (j=1 ; j<nbVilles ; j++)
{
do
{
tempVerif = tirage(nbVilles);
}
while (verifDoublon[i][tempVerif]!=0);

*(population+i*nbVilles+j)=tempVerif;

verifDoublon[i][tempVerif]=1;
}
}

printf("Population d'individus 1 :\n");

for (i=0 ; i<nbIndividu ; i++)
{
for (j=0 ; j<nbVilles ; j++)
{
printf("%i - %i - %ld - %s\n", i, j, *(population+i*nbVilles+j), v[*(population+i*nbVilles+j)].nom);
}
printf("\n");
}
}
void moitieIndividu (const long nbIndividu, long *moitieIndiv)
{
(*moitieIndiv)=nbIndividu/2;

//Si nbIndividu est impair, on en garde la moitié + 1.
if(nbIndividu%2!=0)
{
++(*moitieIndiv);
}
printf("\nLa moitie des individus correspond a : %ld individus\n", (*moitieIndiv));
}

void selectionElitiste(long *population, const long nbVilles, const long nbIndividu, long moitieIndiv, long *classementDistances, long *population2)
{
int i, j;

//On place La mailleure moitié des individus dans la population 2.
for (i=0 ; i<moitieIndiv ; i++)
{
for (j=0 ; j<nbVilles ; j++)
{
*(population2+(i*nbVilles)+(j))=*(population+((*(classementDistances+(moitieIndiv)+i))*nbVilles)+j);
printf("\n[%i][%i] = %ld",i,j,*(population2+(i*nbVilles)+(j)));
}
}

//On remplit les individus suivants avec -1.
for (i=moitieIndiv ; i<nbIndividu ; i++)
{
for (j=0 ; j<nbVilles ; j++)
{
*(population2+i*nbVilles+j)=-1;
}
}

printf("\n\nPopulation d'individus 2 après sélection élististe :\n\n");

for (i=0 ; i<nbIndividu ; i++)
{
for (j=0 ; j<nbVilles ; j++)
{
printf("%i - %i - %ld\n", i, j, *(population2+i*nbVilles+j));
}
printf("\n");
}
}
void croisement(long maman, long papa, long fille, long fils, long debutCroisement, long largeurCroisement, const long nbVilles, const long nbIndividu, long *population2)
{
long i, j, k, l;
long villeDouble;

if (population2 != 0)
{
//On commence par copier les gênes des parents dans les cellules de leurs enfants.
for(i=0 ; i<nbVilles ; i++)
{
//Dabord la maman offre ses gènes à sa fille (galanterie oblige)
*(population2+(fille*nbVilles)+i)=*(population2+(maman*nbVilles)+i);
//Puis papa en fait de même avec son fils (tel père tel fils !)
*(population2+fils*nbVilles+i)=*(population2+papa*nbVilles+i);
}

printf("\n\n papa et maman ont donnes leurs genes :\n");

for (i=0 ; i<nbIndividu ; i++)
{
for (j=0 ; j<nbVilles ; j++)
{
printf("%i - %i - %ld\n", i, j, *(population2+i*nbVilles+j));
}
printf("\n");
}


//On opère ensuite au croisement des gènes.
for (i=debutCroisement ; i<(debutCroisement+largeurCroisement) ; i++)
{
*(population2+fille*nbVilles+i)=*(population2+papa*nbVilles+i);
*(population2+fils*nbVilles+i)=*(population2+maman*nbVilles+i);
}

printf("\n\nPopulation d'individus 2 croises :\n");

for (i=0 ; i<nbIndividu ; i++)
{
for (j=0 ; j<nbVilles ; j++)
{
printf("%i - %i - %ld\n", i, j, *(population2+i*nbVilles+j));
}
printf("\n");
}

//On recherche les villes en double et on les remplace par celles manquantes.
for(i=debutCroisement ; i<(debutCroisement+largeurCroisement) ; i++)
{
for(j=0 ; j<nbVilles ; j++)
{
if( (*(population2+fils*nbVilles+i)==*(population2+fils*nbVilles+j)) && ( (j<debutCroisement) || (j>=(debutCroisement+largeurCroisement)) ) )
{
for(k=debutCroisement ; k<(debutCroisement+largeurCroisement) ; k++)
{
for(l=0 ; l<nbVilles ; l++)
{
if( ( (*(population2+fille*nbVilles+k))==(*(population2+fille*nbVilles+l)) ) && ( (l<debutCroisement) || (l>=(debutCroisement+largeurCroisement)) ) )
{
villeDouble=*(population2+fille*nbVilles+l);
*(population2+fille*nbVilles+l)=*(population2+fils*nbVilles+j);
*(population2+fils*nbVilles+j)=villeDouble;
}
}
}
}
}
}

printf("\n\nPopulation d'individus 2 croisee :\n");
for (i=0 ; i<nbIndividu ; i++)
{
for (j=0 ; j<nbVilles ; j++)
{
printf("%i - %i - %ld\n", i, j, *(population2+i*nbVilles+j));
}
printf("\n");
}
}
else printf("pointeur nul !");

}

void accouplement(long *population, const long nbVilles, const long nbIndividu, long meilleurIndividu, long moitieIndiv, long *classementDistances, long *population2)
{
long debutCroisement=-1;
long largeurCroisement=-1;
long maman, papa, fille=moitieIndiv, fils=moitieIndiv+1 ;
int i, j;

//Nombre d'individus à créer afin de réétablir le nombre fixé au paramétrage.
long indivACreer=nbIndividu-moitieIndiv;
/*
//On met de coté l'indice du meilleur individu afin de la préserver.
*meilleurIndividu=*(classementDistances+nbIndividu-1);
*/
//Tant qu'on a un nombre plus de deux individus à créer...
for (i=0 ; i<(indivACreer/2) ; i++)
{
//random de la valeur d'indice de début ; comprise entre 1 et (nbVilles-2).
debutCroisement=tirage(nbVilles-3)+1;

//random de la largeur de croisement.
largeurCroisement=tirage(nbVilles-debutCroisement)+1;

//répartition des individus parents en couples.
do //Tirage aléatoire des parents utilisés pour effectuer le croisement.
{
maman=tirage(moitieIndiv-1);
papa=tirage(moitieIndiv-1);
}
while (maman==papa);

printf("Lancement de l'op\x82rateur de croisement :");
printf("%i - Maman : %ld ; Papa : %ld ; Fille : %ld ; Fils : %ld \n", i, maman, papa, fille, fils);
printf("%i - Début du croisement : %ld ; Largeur du croisement : %ld.\n", i, debutCroisement, largeurCroisement);

croisement(maman, papa, fille, fils, debutCroisement, largeurCroisement, nbVilles, nbIndividu, &(*population2));

//Incrémentation de l'indice des enfants dans la population 2 pour la prochaine itération.
fille+=2;
fils+=2;
}
//Si indivACreer est impaire, on rajoute le dernier individu.
//Nous choisirons de recopier notre meilleur individu à l'emplacement vide.
if ( ((indivACreer/2)*2)!=indivACreer)
{
for(i=0 ; i<nbVilles ; i++)
{
*(population2+((nbIndividu-1)*nbVilles+i))=*(population+((meilleurIndividu*nbVilles)+i));
}
}

printf("Nombre d'individus a creer : %ld.\n", indivACreer);
printf("Meilleur individu : indice %ld de la population 1.\n", meilleurIndividu);

printf("\n\nPopulation d'individus 2 :\n");

for (i=0 ; i<nbIndividu ; i++)
{
for (j=0 ; j<nbVilles ; j++)
{
printf("%i - %i - %ld\n", i, j, *(population2+i*nbVilles+j));
}
printf("\n");
}
}
void meilleurIndiv (long *classementDistances, long nbIndividu, long *meilleurIndividu)
{
//On met de coté l'indice du meilleur individu afin de la préserver.
*meilleurIndividu=*(classementDistances+nbIndividu-1);
}
void mutation (long *population2, double tauxMutation, long nbVilles, long nbIndividu, long meilleurIndividu)
{
long i, j, villeMut1, villeMut2, villeTemp;
long nbIndividuAMuter=(tauxMutation*nbIndividu);
long indiceAMuter[nbIndividuAMuter];

printf("Taux de mutation : %lf\n nbVilles : %ld\n", tauxMutation, nbIndividu);
printf("Nombre de villes a muter : %ld\n", nbIndividuAMuter);

for (i=0 ; i<nbIndividuAMuter ; i++)
{
do
{
indiceAMuter[i]=tirage(nbIndividuAMuter);
printf("i=%ld ; Indice a muter : %ld\n", i, indiceAMuter[i]);
}
while (indiceAMuter[i]==meilleurIndividu);
}

for (i=0 ; i<nbIndividuAMuter ; i++)
{
do
{
villeMut1=(tirage((nbVilles)));
villeMut2=(tirage((nbVilles)));
printf("%ld - vmut1=%ld - vmut2=%ld\n", i, villeMut1, villeMut2);
}
while ((villeMut1==villeMut2) &&(villeMut1=0) || (villeMut2=0)) ;
}


}

void pointDepart (ville *v, long *vDepart, const long nbVilles)
{
char villeDepart[20];
char quit[20]="quitter";
int i, j=-1;

do
{
printf("\nDe laquelle de ces villes voulez-vous partir ?\n");
printf("Ville de d\x82part : ");
gets(villeDepart);

for (i=0 ; i<nbVilles ; i++)
{
j = strcmp (villeDepart, v[i].nom);

if (j == 0)
{
*vDepart=i;
printf("\n\nVous d\x82\x63idez de partir de %s, \n", villeDepart);
}

if ((strcmp (villeDepart, quit))==0) exit(0);
}

if (*vDepart == -1)
{
printf("\n\nCette ville n'existe pas dans votre parcours.\n");
printf("Attention ! Saisissez la ville telle qu'elle appara\x8ct dans le tableau !");
}
}
while (*vDepart == -1);
}
int genetikAlgo (ville *v, const long nbVilles)
{
int ret=0;

if (v == 0) ret=-1;

long vDepart=-1;
long moitieIndiv=-1;
long meilleurIndividu;

//En provenance des paramètres de l'algorithme.
//nbIndividu doit etre <nbIndividu<infini et paire --> paire = Modulo4 !!
long nbIndividu = 10 ; //nbIndividu --> PAIR !! ??
long selectionParametre = 1 ; //Mode de sélection des individus. 1=élitiste, 2=tournoi.
long nombreIteration=1; //Pas activé pour l'instant...
double tauxMutation=0.5;
//long nbIteration //Pas encore géré...

//La population sera un tableau à 2dim de taille [nbIndividu][nbVilles].
long population[nbIndividu][nbVilles];
long population2[nbIndividu][nbVilles];

//Tableau contenant les distances des individus.
double distancesIndividus[nbIndividu];

//Tableau contenant les indices des individus classés par ordre décroissant.
long classementDistances[nbIndividu];


//Choix de la ville de départ.
pointDepart(v, &vDepart, nbVilles);

//Création des individus.
creerIndividus (v, vDepart, nbVilles, nbIndividu, *population);

//Calcul des distances.
calculDistances (v, *population, nbVilles, nbIndividu, distancesIndividus);

//Classement des distances par ordre décroissant.
classerDistances (distancesIndividus, nbIndividu, classementDistances);

//Stockage de l'indice du meilleur individu.
meilleurIndiv (classementDistances, nbIndividu, &meilleurIndividu);

//Calcul de la moitié des individus.
moitieIndividu (nbIndividu, &moitieIndiv);

if(selectionParametre=1)
{
//Selection par la méthode élitiste.
selectionElitiste(*population, nbVilles, nbIndividu, moitieIndiv, classementDistances, *population2);
}

else if (selectionParametre=2)
{
//Selection par la méthode du tournoi. //Non réalisé !!

}

//Croisement des individus dans la population 2.
accouplement(*population, nbVilles, nbIndividu, meilleurIndividu, moitieIndiv, classementDistances, *population2);

//Calcul des distances.
calculDistances (v, *population2, nbVilles, nbIndividu, distancesIndividus);

//Classement des distances par ordre décroissant.
classerDistances (distancesIndividus, nbIndividu, classementDistances);

//Stockage de l'indice du meilleur individu.
meilleurIndiv (classementDistances, nbIndividu, &meilleurIndividu);

//Mutation des individus de la population 2.
mutation (*population2, tauxMutation, nbVilles, nbIndividu, meilleurIndividu); //Non fini !!

//Calcul des distances.
calculDistances (v, *population2, nbVilles, nbIndividu, distancesIndividus);

//Classement des distances des individus de la poulation 2.
classerDistances (distancesIndividus, nbIndividu, classementDistances);

//Gestion des informations renvoyées en cas de pluieures itéarations de l'algo.

//Ecriture des résultats dans un fichier texte


return ret;
}
void bienvenu(long nbVilles)
{
//Message de bienvenue.
printf("\nBienvenue, cher voyageur !\n\n");
printf("Vous avez choisi de visiter la Bretagne, c'est une belle initiative !\n");
printf("Si vous changez d'avis et d\x82\x63idez de quitter, tapez tout simplement 'quitter'.\n\n");
printf("Notre p\x82riple se composera de %ld \x82tapes :\n\n", nbVilles);

}


main()
{
long nbVilles;
int i;
int ouverture=0, verif=0;

//Vérification que le fichier carte est au bon format.
ouverture = formatFichier();
if(ouverture==-1) erreurFichier();

else
{
do
{
//Création d'un pointeur sur la structure "v" de type struc ville.
ville *v=NULL;
//Création d'un pointeur sur le fichier "villes.txt".
FILE *carte;

//Stockage du nombre de villes sur lequel on travaillera dans long nbVilles.
//Ouverture du fichier contenant les informations sur les villes.
if( (carte = fopen("villes.txt", "r")) == NULL )
{
printf("Erreur lors de l'ouverture du fichier.");
}
//Interception du nombre de villes à parcourir à partir du fichier.
else
{
fscanf(carte,"%ld",&nbVilles);
}
//Fermeture du fichier carte.
fclose(carte);

//Allocation dynamique de la mémoire nécesaire à contenir le tableau de
//structure ou sont stockées les infos sur les villes en fonction de nbVilles.
v=(ville*)malloc((nbVilles)*sizeof(ville));

//Remplissage du tableau de structures contenant les infos sur les villes.
verif=attrapeVille(nbVilles, v);

//Message de bienvenue.
bienvenu(nbVilles);

//Affichage des villes et de leurs coordonnées.
verif=afficheVil(nbVilles, v);

//Appel de l'algorithme génétique.
genetikAlgo(v, nbVilles);

//Libération de la mémoire allouée.
if (v !=0) free(v);
}
while (verif==0);


}
printf("\n\nMerci et a bient\x93t.\n\n");
system("PAUSE");
return 0;
}