Discussion :

[sassouna bel]

Je dois développer un programme capable de résoudre un problème de voyageur de commerce en C avec un algorithme Génétique.
Quelqu'un peut m'aider ???
Merci !!

[CliffeCSTL]

Ou est le problème ?

[sassouna bel]

le problème est, étant donné un ensemble de villes séparées par des distances données, à trouver le plus court chemin qui relie toutes les ville dont la ville de départ est la même ville d'arrivé et chaque ville est visité une et une selle fois.

[CliffeCSTL]

le problème est, étant donné un ensemble de villes séparées par des distances données, à trouver le plus court chemin qui relie toutes les ville dont la ville de départ est la même ville d'arrivé et chaque ville est visité une et une selle fois.

ahah ce troll

Je reformule ma question : Qu'est-ce que tu n'arrives pas à faire ?

Tu as juste besoin de coder une fonction de croisement génétique et une recherche locale (exemple : 2OPT).

[sassouna bel]

comment je peux transformer les fonctions de croisement, mutation,... en langage C. pouvez vous m'aider??

[tbc92]

Tu te présentes comme chercheur en informatique.
Et tu ne sais pas utiliser Google ?

http://fr.scribd.com/doc/175623425/a...ommerce#scribd

[CliffeCSTL]

Pour le croisement :

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Individu : public std::vector<int> {};
 
Individu croisement(const Individu & i1, const Individu & i2) {
    Individu i3; // Résultat du croisement de i1 et i2
    int n = i1.size(), random = rand() % n; // On coupe aléatoirement
    std::vector<bool> temp(n, false); // On mémorise les élements déjà insérer
 
    // On insère les éléments de i1
    for (int i = 0; i < random; ++i) { i3.push_back(i1[i]); temp[i1[i]] = true; }
 
    // On insère les éléments de i2
    int i = random;
    while (i3.size() != n) {
        if (temp[i2[i % n]] == false) i3.push_back(i2[i % n]);
        ++i;
    }
 
    return i3;
}

a tester

[sassouna bel]

Je vous remercie pour votre aide

[sassouna bel]

svp comment je peux déclarer la matrice des distances quand mon problème est a 50 villes pour les visiter. pouvez vous m'aider

[CliffeCSTL]

Tu peux par exemple faire un truc simple en statique :

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
int n_max = 100;
double d[n_max * n_max]; // Matrice distance

tu t'alloues une zone mémoire pour travailler dès le début.

[sassouna bel]

merci bien

[sassouna bel]

je cherche des instances pour le TSP et que concerne le contrainte de temps, pouvez vous m'aider??

[CliffeCSTL]

Perso j'utilise ça : lien

[sassouna bel]

merci bien

[sassouna bel]

Ce lien concerne le coût par unité de distance, mais je besoin de calculer le coût par unité de temps!!!
pouvez vous m'aider????

[CliffeCSTL]

bah tu choisis une vitesse pour le véhicule.

[sassouna bel]

mon code de croisement ne fonctionne pas, votre aides s'il vous plait...

/*fonction du croisement*/

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void croisement (int P1[1000],int P2[1000],int E1[1000],int E2[1000])
	{
 int N=1000;
		int random = rand()%7;//on coupe aleatoirement
		int K=random+1;
		for(int i=0;i<=random;i++)
		{
			E1[i]=P1[i];
			E2[i]=P2[i];
		}
 
for(int i=0;i<N;i++)
{
	for (int j=k;j<N;j++)
	{
			if(P2[j]!=E1[i])
			E1[j]=P2[j];
		else
			break;// s'il ya egalité pas la paine de continuité la comparaison et terminer l'execution de l'instruction
	}
		{
			if (P1[j]!=E2[i])
				E2[j]=P1[j];
 
		}
	}
}

[dourouc05]

mon code de croisement ne fonctionne pas, votre aides s'il vous plait...

C'est vrai, c'est pas interdit de rêver. Déjà, commence par indenter ton code correctement, il sera un peu plus lisible ; d'ailleurs, qu'est-ce que P ou E ? Ensuite, quel est le problème ? Qu'aimerais-tu que ce bout de code fasse ? (Par ailleurs, une petite recherche Google donne rapidement des résultats qui pourraient être intéressants pour une heuristique plus intelligente, en anglais.)

[sassouna bel]

le compilateur me donne comme erreur:

'k' undeclared (first use this function)

or je l'ai déclaré au dessus

je veux croiser le deux parents P1 et P2 pour obtenir deux enfants E1 et E2

[Invité]

Bonsoir,

K majuscule de la ligne 5 int K=random+1; n'est pas la même variable que k minuscule de la ligne 14 for (int j=k;j<N;j++).
Le langage C est sensible à la casse.