Discussion :

[camelia136]

Bonjour tout le monde,

J'ai une problématique par rapport aux liaisons téléphoniques.

Existe-t-il un algorithme qui permet de trouver plusieurs chemins (2 ou 3) selon deux critères :

• les chemins les moins encombrés entre 2 sites,
• les chemins ayant une capacité maximale entre 2 sites en même temps.

Ainsi, l'algorithme proposera plusieurs solutions, étant donné qu'il effectue une recherche multicritère.

L'algorithme de Dijkstra permet de trouver un seul chemin le plus court donc une seule solution, les algorithmes métaheuristiques permettent ce genre de recherche ? Ou un mélange entre Dijkstra et un algo métaheuristique ?

[pseudocode]

Pourquoi ne pas simplement refaire un recherche par Dijkstra, en supprimant le chemin trouvé précédemment (i.e. mettre un poids infini aux arcs utilisés) ?

[Franck Dernoncourt]

La difficulté est d'introduire plusieurs objectifs : supprimer le chemin trouvé précédemment permet juste d'avoir plusieurs solutions.

Je ne vois pas d'algorithme classique permettant de trouver les chemins satisfaisant plusieurs critères. Personnellement j'essaierai avec un algorithme évolutionniste multi-objectif mais je ne l'ai jamais appliqué pour de la recherche de chemin sur un graphe, je ne sais pas à quel point cela serait efficace. Une bonne idée serait probablement de mettre dans la population initiale des solutions trouvées par Dijkstra selon chacun des critères. L'algorithme évolutionniste te donnera ainsi un front de Pareto de solutions.



Voici un exemple d'implémentation d'un algorithme évolutionniste pour de la recherche de chemin, en l'occurence le problème du voyageur de commerce : http://khayyam.developpez.com/articl...rce/genetique/

Tu peux également chercher sur Google "path finding multi-criteria" ou quelque chose du genre si tu ne l'as pas déjà fait, en complément des idées proposées dans ce thread.

[camelia136]

La difficulté est d'introduire plusieurs objectifs : supprimer le chemin trouvé précédemment permet juste d'avoir plusieurs solutions.

Je ne vois pas d'algorithme classique permettant de trouver les chemins satisfaisant plusieurs critères. Personnellement j'essaierai avec un algorithme évolutionniste multi-objectif mais je ne l'ai jamais appliqué pour de la recherche de chemin sur un graphe, je ne sais pas à quel point cela serait efficace. Une bonne idée serait probablement de mettre dans la population initiale des solutions trouvées par Dijkstra selon chacun des critères. L'algorithme évolutionniste te donnera ainsi un front de Pareto de solutions.



Voici un exemple d'implémentation d'un algorithme évolutionniste pour de la recherche de chemin, en l'occurence le problème du voyageur de commerce : http://khayyam.developpez.com/articl...rce/genetique/

Tu peux également chercher sur Google "path finding multi-criteria" ou quelque chose du genre si tu ne l'as pas déjà fait, en complément des idées proposées dans ce thread.

j'ai essayé de voir comme vous m'avez conseillé pour l’optimisation multicritère et j'ai pensé à regrouper toutes les critères en une seule fonctions avec plusieurs variables par exemple

Maintenant reste à trouver un algorithme pour trouver une multitudes de solutions optimales sans avoir à supprimer les trajets.

[Franck Dernoncourt]

Regrouper tous les critères en une seule fonctions avec plusieurs variables par exemple est souvent sous-optimal :



Néanmoins effectivement cela te permettra d'utiliser directement l'algorithme de Dijkstra, ce qui sera probablement beaucoup plus simple pour toi.

[camelia136]

Regrouper tous les critères en une seule fonctions avec plusieurs variables par exemple est souvent sous-optimal :



Néanmoins effectivement cela te permettra d'utiliser directement l'algorithme de Dijkstra, ce qui sera probablement beaucoup plus simple pour toi.

Je ne pense pas que ça va être sous optimal , la fonction dont je parle me permettra juste de mettre un poids sur les segments et c’est à moi de définir comment ce poids sera calculé .

mais après quelque soit le poids des segments la recherche des chemins est la même

Je ne pense pas que ça va être plus simple puisque Dijkstra ne permet pas de trouver plusieurs solutions optimales

[camelia136]

Pourquoi ne pas simplement refaire un recherche par Dijkstra, en supprimant le chemin trouvé précédemment (i.e. mettre un poids infini aux arcs utilisés) ?

Merci pseudocode pour votre réponse

La solution que vous avez proposé n'est pas optimale parceque si on supprime le chemin completement la autres alternative ne réutiliseront aucun des segments supprimés . Cependant si le chemin avait 6 segments par exemple il se peut q'un bon chemin alternatif en reutilise 1 ou 2

[Branch]

Bonjour tout le monde,

J'ai une problématique par rapport aux liaisons téléphoniques.

Existe-t-il un algorithme qui permet de trouver plusieurs chemins (2 ou 3) selon deux critères :

• les chemins les moins encombrés entre 2 sites,
• les chemins ayant une capacité maximale entre 2 sites en même temps.

Ainsi, l'algorithme proposera plusieurs solutions, étant donné qu'il effectue une recherche multicritère.

L'algorithme de Dijkstra permet de trouver un seul chemin le plus court donc une seule solution, les algorithmes métaheuristiques permettent ce genre de recherche ? Ou un mélange entre Dijkstra et un algo métaheuristique ?

Il existe (sauf erreur de ma part ) un moyen pour résoudre ce problème de manière exacte à l'aide d'un algorithme de labelling :

Un label va définir un chemin partiel. Un label est composé de différent éléments :
-un pointeur vers le noeud ou ce chemin partiel fini : $N$
-un pointeur vers le label représentant ce chemin partiel finissant sur le noeud précédent du chemin partiel : $Lp$
-une variable $c_i$ qui va stocker le cout de ce chemin partiel pour chacun de tes critères $i$

On va définir le concept de domination, un label L domine un label L' si n'importe quel chemin issue de L' aura un cout supérieur ou égale pour chaque critère au(x) meilleur(s) chemin issues de L une fois arrivé au noeud puits. Dans ce cas si tu considère que le parcours d'un arc à un coût positif ou nul tu peux dire que L domine L' si :
L et L' représentent un chemin partiel finissant sur le même noeud et le coût de chaque critère pour L est inférieur ou égale à celui de L' avec au moins une de ces égalité étant stricte.

Du coup ton algo va se dérouler de la manière suivante :
Initiallement tu part avec un seul Label étant sur ton noeuds source et ayant un coût de 0 pour chacun des critères.

A chaque pas tu étant tout les labels non dominés, n'ayant pas encore été étendu, à tout leur voisins n'appartenant pas déjà au chemin partiel représenté par le Label non dominé que tu étend.
Pour tout les label créés tu va les comparer à tous les label non dominé. Si tu détecte des label dominé tu peux les retirer.
Ton algorithme est terminé quand tu ne peux plus étendre aucun label non dominé. A ce moment tout les Label représentant un chemin terminant sur le noeud puit non dominé représentent ton front Pareto.

Bon, je suis pas sur d'avoir été clair, ni que cette approche soit la plus efficace pour trouver le front pareto pour ce problème...

Bon courage

[camelia136]

Il existe (sauf erreur de ma part ) un moyen pour résoudre ce problème de manière exacte à l'aide d'un algorithme de labelling :

Un label va définir un chemin partiel. Un label est composé de différent éléments :
-un pointeur vers le noeud ou ce chemin partiel fini : $N$
-un pointeur vers le label représentant ce chemin partiel finissant sur le noeud précédent du chemin partiel : $Lp$
-une variable $c_i$ qui va stocker le cout de ce chemin partiel pour chacun de tes critères $i$

On va définir le concept de domination, un label L domine un label L' si n'importe quel chemin issue de L' aura un cout supérieur ou égale pour chaque critère au(x) meilleur(s) chemin issues de L une fois arrivé au noeud puits. Dans ce cas si tu considère que le parcours d'un arc à un coût positif ou nul tu peux dire que L domine L' si :
L et L' représentent un chemin partiel finissant sur le même noeud et le coût de chaque critère pour L est inférieur ou égale à celui de L' avec au moins une de ces égalité étant stricte.

Du coup ton algo va se dérouler de la manière suivante :
Initiallement tu part avec un seul Label étant sur ton noeuds source et ayant un coût de 0 pour chacun des critères.

A chaque pas tu étant tout les labels non dominés, n'ayant pas encore été étendu, à tout leur voisins n'appartenant pas déjà au chemin partiel représenté par le Label non dominé que tu étend.
Pour tout les label créés tu va les comparer à tous les label non dominé. Si tu détecte des label dominé tu peux les retirer.
Ton algorithme est terminé quand tu ne peux plus étendre aucun label non dominé. A ce moment tout les Label représentant un chemin terminant sur le noeud puit non dominé représentent ton front Pareto.

Bon, je suis pas sur d'avoir été clair, ni que cette approche soit la plus efficace pour trouver le front pareto pour ce problème...

Bon courage

Merci Branch pour ta réponse

En fait j'ai décidé de reduire mes 2 critères en une seule fonction les rassemblant toutes les 2 avec des pourcentages que l'utilisateur va definir ,
ta methode que je n'ai pas tres bien compris permet-elle de trouver de multiples solutions ?

[Branch]

Merci Branch pour ta réponse

En fait j'ai décidé de reduire mes 2 critères en une seule fonction les rassemblant toutes les 2 avec des pourcentages que l'utilisateur va definir ,
ta methode que je n'ai pas tres bien compris permet-elle de trouver de multiples solutions ?

Oui, en fait cette méthode te permet de trouver l'ensemble des solutions non dominées de ton problème (une solution est non dominé s'il n'existe aucune autre solution meilleure ou équivalente sur tout les critères).

Après si ton graphe comporte un grand nombre de noeuds/arcs cette approche risque d'être très consommatrice en temps comme en mémoire. Cependant tu peux accélérer son execution (au prix de la garantie d'optimalité de la solution) en ne considérant pas certains arcs (parce que tu considère qu'ils ont a priori un coup trop important pour appartenir à une solution non dominé).

[camelia136]

Oui, en fait cette méthode te permet de trouver l'ensemble des solutions non dominées de ton problème (une solution est non dominé s'il n'existe aucune autre solution meilleure ou équivalente sur tout les critères).

Après si ton graphe comporte un grand nombre de noeuds/arcs cette approche risque d'être très consommatrice en temps comme en mémoire. Cependant tu peux accélérer son execution (au prix de la garantie d'optimalité de la solution) en ne considérant pas certains arcs (parce que tu considère qu'ils ont a priori un coup trop important pour appartenir à une solution non dominé).

Branch,

Comment definir un chemin partiel à partir de mon graphe initial ?

Mon graphe peut comporter 100 noeuds et plus

[Branch]

Branch,

Comment definir un chemin partiel à partir de mon graphe initial ?

Mon graphe peut comporter 100 noeuds et plus

Bon, voila un exemple simple pour illustrer le fonctionnement de l'algo que je propose. Tu considère le graphe présent sur l'image, pour chaque arc, on considère le cout de son parcourt pour chacun des criteres (cout critere 1, cout critere 2). On va chercher toutes les solutions non dominées de chemins entre le noeud S et le noeud P.



Etape 1 on part avec un seul Label :
L_0 = [S,{},0,0]

Etape 2, j'étend les Label non dominé non encore étendu (L_0) :

L_0 -> L_1 = [A, L_0, 1, 4]

L_1 n'est dominé et ne domine aucun Label

L_0 -> L_2 = [B, L_0, 4, 1]

L_2 n'est dominé et ne domine aucun Label.

j'étend les Label non dominé non encore étendu (L_1, L_2) :

L_1 -> L_3 = [D, L_1, 2, 5]

L_3 n'est dominé et ne domine aucun Label.

L_1 -> L_4 = [C, L_1, 2, 5]

L_4 n'est dominé et ne domine aucun Label.

L_2 -> L_5 = [C, L_2, 5, 2]

L_5 n'est dominé et ne domine aucun Label.

L_2 -> L_6 = [D, L_2, 14, 11]

L_6 est dominé par L_3 car ces deux chemins partiels finissent sur le même noeud et que L_6 a un cout supérieur à celui de L_3 pour tout les critères.

j'étend les Label non dominé non encore étendu (L_3, L_4, L_5) :

L_3 -> L_7 = [P, L_3, 2, 7]

L_7 n'est dominé et ne domine aucun Label.

L_4 -> L_8 = [P, L_4, 3, 6]

L_8 n'est dominé et ne domine aucun Label.

L_5 -> L_9 = [P, L_5, 6, 3]

L_9 n'est dominé et ne domine aucun Label.

Aucun Label non dominé ne peut être étendu. Les 3 chemins non dominés sont ceux représenté par les Label L_7, L_8 et L_9.