aide implantation algorithme génétique en c

Le
afoufa
Bonjour,

J'aimerais implanter l'algorithme génétique (http://
khayyam.developpez.com/articles/algo/genetic/)en langage c pour
résoudre le problème du voyageur de commerce (objectif : minimisation
des distances).
La première partie consiste à déterminer tous les chemins possibles
entre les villes (par exemple on considère 7 villes):
{1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},
Je ne vois pas comment démarrer. Pourriez vous me donner quelques
indications?
Merci par avance.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
espie
Le #20935561
In article afoufa
La première partie consiste à déterminer tous les chemins possibles
entre les villes (par exemple on considère 7 villes):
{1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},...
Je ne vois pas comment démarrer. Pourriez vous me donner quelques



Tous les chemins possibles, c'est toutes les permutations de 1..7.
En cherchant un peu sur le mot-cle "permutation" tu devrais trouver
ton bonheur.

Ca doit etre dans a peu pres tous les bouquins d'algo. Entre autres dans
Knuth, bien sur, meme si c'est sans doute pas le bouquin le plus approprie
pour demarrer.

Nota bene: je ne suis pas trop convaincu que ca soit un bon depart pour
un algo genetique. Ca va vite faire une trop grosse population. Ce qu'il
te faut, c'est une population "assez grosse", suffisamment aleatoire, et
une fonction de mutation/crossover qui preserve la propriete "etre une
permutation de 1..7".
afoufa
Le #20936221
On 9 jan, 18:14, (Marc Espie) wrote:
In article
afoufa   >La première partie consiste à déterminer tous les chemins possible s
>entre les villes (par exemple on considère 7 villes):
>{1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},...
>Je ne vois pas comment démarrer. Pourriez vous me donner quelques

Tous les chemins possibles, c'est toutes les permutations de 1..7.
En cherchant un peu sur le mot-cle "permutation" tu devrais trouver
ton bonheur.

Ca doit etre dans a peu pres tous les bouquins d'algo. Entre autres dans
Knuth, bien sur, meme si c'est sans doute pas le bouquin le plus appropri e
pour demarrer.

Nota bene: je ne suis pas trop convaincu que ca soit un bon depart pour
un algo genetique. Ca va vite faire une trop grosse population. Ce qu'il
te faut, c'est une population "assez grosse", suffisamment aleatoire, et
une fonction de mutation/crossover qui preserve la propriete "etre une
permutation de 1..7".



Merci beaucoup pour votre réponse et votre conseil!
ca ne m'est pas venue à l'esprit!
Cependant, pourrait-on éviter de faire 7 boucles "for"?Si oui, de
quelle façon pourrais-je y arriver?
Merci par avance.
espie
Le #20936431
In article afoufa
Cependant, pourrait-on éviter de faire 7 boucles "for"?Si oui, de
quelle façon pourrais-je y arriver?



C'est un exemple "classique" ou il est plus naturel de proceder
recursivement. Si tu stockes toutes tes permutations dans un tableau,

pour generer une permutation:
- choisir le premier element
- trouver toutes les permutations qui n'incluent pas ce premier element
(d'ou la recursion).

Le plus rapide (mais pas forcement le plus intuitif), c'est de gener les
permutations a coups de petits echanges... e.g., on part de la liste
1 2 3 4 5 6 7

on garde le 1: on genere les permutations sur 2 3 4 5 6 7

puis on echange le 1 et le 2: 2 1 3 4 5 6 7
on garde le 2: on genere les permutations sur 1 3 4 5 6 7
puis on remet les choses en place et on echange 1 et 3: 3 2 1 4 5 6 7
on garde le 3: on genere les permutations sur 2 1 4 5 6 7
puis on remet les choses en place et on echange 1 et 4: 4 2 3 1 5 6 7
on garde le 4: on genere les permutations sur 2 3 1 5 6 7
...
Publicité
Poster une réponse
Anonyme