Méta-heuristiques: Voisinage

Discutez d'informatique ici !
Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

Méta-heuristiques: Voisinage

par Rockleader » 01 Déc 2016, 00:13

Bonsoir,

pourriez-vous si possible m'éclaircir sur ce sujet qu'est la notion de voisinage dans les méta-heuristiques, et plus particulièrement ici dans le cas du problème type Voyageur de commerce

En pratique, j'ai une liste de clients, et je dois élaborer une solution qui livrent tous les clients en minimisant les distances totales parcouru par l'ensemble de mes camions de livraison.

Le problème étant ici que j'ai l'impression de confondre la notion de voisins (des clients peuvent être voisins dans le sens où ils sont proches niveau distance); une solution peut être voisine dans le sens où en changeant un point de l'algo on obtient une solution proche.

Voici le transparent de mon cours illustrant le problème

Image

Mon incompréhension vient à la base du fait que je n'ai pas de définition claire de ce qu'est une solution.

Est-ce qu'une solution correspond au traitement complet du problèmes et donc une liste de camions qui livrent une liste de clients.
Ou bien une solution correspond à une étape seulement du traitement du problème de base. Et donc ici une solution serait plutôt l'état courant des livraisons.

Je pense que déjà ce point là est la source de ma confusion sur la notion de voisinage.


Pour recoller au problème, voici l'intitulé de début

On vous demande pour commencer d’implémenter un algorithme de recherche local simple – type montée selon la plus grande pente – avec redémarrages, mais sans mémoire. Dans cette partie on ignorera les contraintes de temps des livraisons et de capacité des camions. Il vous faudra donc réaliser les tâches suivantes :


1. Définir un type de données pour représenter les solutions : une fa¸con directe de représenter un état est un ensemble de k camions C1,C2,..Ck, chaque camion étant une séquence ordonnée de clients. Les camions doivent former une partition des clients : chaque client est visité une fois et une seule. Le nombre k pourra bien sûr varier.

2. Implémenter un algorithme de génération de solutions initiales aléatoires; Une notion cruciale pour les recherches locales est la notion de voisinage, c’est-à-dire les solutions que l’on peut définir qui sont “proches”, en modifiant légèrement une solution. Il faut pouvoir calculer rapidement les voisins d’une solution courante.

3. Réfléchir à la notion de voisinage, et implémenter des fonctions :
a) permettant d’énumérer tous les voisins d’une solution donnée;
b) permettant de tirer au hasard un nombre fixé de voisins d’une solution donnée;



Merci pour l'aide que vous pourrez apporter !
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !



Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Méta-heuristiques: Voisinage

par fatal_error » 02 Déc 2016, 02:31

salut,

je quote pas parce qur je galere un peu sur mobile...

une solution cest:
la liste des camions et leur clients attribues (et ordonnes); ce quils appelent un etat.

un voisin cest par exemple: tu changes lordre des clients dun camion, ou bien tenleves un client dun camion et tu le files a un autre camion.

je ne pense pas que une solution proche soit forcement une solution dont levaluation est proche.
le proche provient plus de similaire, idem tu as pas bcp change la configuration.
la vie est une fête :)

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

Re: Méta-heuristiques: Voisinage

par Rockleader » 02 Déc 2016, 14:32

Merci pour la réponse,

Mais du coup, ça laisse pas mal de libertés quand à la notion de voisinage si je ne me trompe pas ? Du coup, établir toutes les solutions voisines n'a de sens que si on considère un sous ensemble de voisins ? Autrement c'est quasi infini.

Par exemple si ma solution S0 c'est

Camion 1 livre C1 C2
Camion 2 livre C3 C4

Si je considère que les voisins sont les permutations possibles au sein d'un même camion

Les solutions voisines seraient

Camion 1 livre C2 C1
Camion 2 livre C3 C4


Camion 1 livre C1 C2
Camion 2 livre C4 C3

Mais je peux aussi considérer qu'on voisin c'est l'échange de client entre deux camions par exemple

Auquel cas mes solutions voisines sont totalement différentes.

Du coup, dans ce genre de problème il n'y a pas une solution exacte, on cherche l'optimisation en tâtonnant avec plusieurs essaies de contexte j'ai l'impression...
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Méta-heuristiques: Voisinage

par fatal_error » 02 Déc 2016, 17:14

c'est justement la difficulté de l'exercice, définir la définition de voisinage.
Si tu prends un camion qui sert 6 clients, si tu les permutes n'importe comment, tu peux considérer la solution comme loin.
Si tu migres un client d'un camion à un autre, si les deux camions sont "loins", alors tu peux considérer que ta solution est loin.
la vie est une fête :)

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 18:40

Re: Méta-heuristiques: Voisinage

par Zorro_X » 03 Déc 2016, 04:56

Il ne faut pas perdre de vue ce que tu cherches : optimiser la distance totale parcourue (pour économiser du carburant par exemple, ou gagner du temps, ...). L'objectif est donc, dans un premier temps de créer un modèle te permettant de décrire toutes les possibilités (états), même les plus farfelues. Ca ne veut pas dire que tu vas toutes les analyser, ton heuristique est là pour "guider" ce parcours.

La création de ce "modèle" est justement la question que t'es en train de nous poser, et à mon tour je te pose la question : est-ce-que tu crois que ta définition de "voisins" permet, par ces uniques permutations, de définir tous les cas possibles ?
La réponse est non, parce que dans ton modèle il n'y a pas de permutation/échanges possibles entre les camions. Ni la possibilité qu'un camion ait plus de paquets qu'un autre.
Donc je pense qu'une possibilité de définition des "états voisins" d'un état serait le simple déplacement d'un colis. Ce déplacement peut induire une permutation s'il se fait dans le même camion. Pour ne pas avoir uniquement un seul état voisin, tu peux dire par exemple que tes états voisins est constitué par le déplacement de chaque colis une fois dans son camion et une fois vers un autre camion.
En fait quand tu penses à l'arbre d'états que tu obtiens pour ton système, en définissant ce qu'est un "état voisin" tu définis combien de branches peuvent partir de caque nœud/état. L'heuristique n'est là que pour te concentrer sur les états/solutions qui semblent les plus prometteurs, en les comparant aux autres/ceux que t'as déjà analysé.
Enfin, il ne faut pas oublier qu'en utilisant une méthode de parcours par heuristique tu n'as aucune garantie d'avoir LE meilleur résultat mais uniquement de trouver un "bon" résultat.

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 20:42

Re: Méta-heuristiques: Voisinage

par Rockleader » 03 Déc 2016, 19:30

Enfin, il ne faut pas oublier qu'en utilisant une méthode de parcours par heuristique tu n'as aucune garantie d'avoir LE meilleur résultat mais uniquement de trouver un "bon" résultat.


On est d'accord sur ce point, pas de confusion.


Dans mon algo, on me demande de générer une solution aléatoire, ce que j'ai fais.

En général je trouve quelque chose du style

15 camions pour livrer 100 clients, qui sont répartis entre les camions de façon plus ou moins logiques puisque aléatoire à la base.

Mais j'ai l'impression que faire l'état de tous les voisins est assez costaud en terme de donnée à traiter.

Par exemple sur 15 camions si le camion 1 livre 10 clients.
Pour chaque client je peux transférer le client dans les 14 autres camions.

J'ai donc 10x14 = 140 voisins possibles en ne modifiant que le camion 1 sans permutation.

Si je modifie que le camion 2 et que je prends l'hypothèses que tout mes camions ont le même nombre de client dans cette solution (ce qui est faux bien entendu mais pour simplifier le calcul ici on va dire que oui...140 voisins.

...

Donc au final j'ai 15*140=2100 voisins ne comportant que des transferts d'un client d'un camion A vers un camion B.

A tout ça on ajoute les éventuelles permutations.

Pour un camion j'ai donc 10*9 =90 permutations possibles.
Soit pour les 15 camions 1350.

Ce qui nous donnerait dans un tel cas pas moins de 3450 solutions voisines "proches"

Sa me parait assez élevé quand même d'évaluer un si grand nombre de solutions (ok ok c'est pas grand d'un point de vue du processeur); mais quand même à chaque voisin, il faut vérifier la validité de ce voisin.

Parce que le fait faire un transfert/permutation change l'ensemble du modèle et oblige à la revérification de toutes les données.

Du coup beaucoup seront éjectés car même si ce sont des voisins proches ils seront invalides par rapport à la solution.


Bref, tout ça c'était pour un niveau, mais après j'imagine qu'il faut réitérer l'opération en prenant le voisin comme la nouvelle solution...etc etc. Donc la complexité du machin augmente très vite.

Je peux essayer de toute façon, mais j'avoue ne pas être très convaincu de devoir appliquer ces deux définissions en même temps, j'aurais tendance à dire soit l'une soit l'autre.
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 18:40

Re: Méta-heuristiques: Voisinage

par Zorro_X » 08 Déc 2016, 05:55

Lorsque t'utilises le même principe dans le cadre de la théorie du jeu pour déterminer ce que l'ordinateur devrait jouer pour avoir plus de chances de gagner c'est plus simple, car les règles d'un jeu, donc des possibilités du "prochain coup" sont déjà définies. N'empêche que ce que t'appelles la "complexité" qui n'est rien d'autre que le nombre de possibilités à envisager, croît d'une manière exponentielle. Et c'est justement l'objectif des parcours d'état guidés par une heuristique : ne se concentrer que sur les solutions qui semblent "les meilleures". C'est ainsi que plus tu auras réussi à "t'enfoncer" dans ton arbre de recherche, meilleures seront tes chances de trouver une meilleure solution.
Une approche semblable est utilisée par exemple dans les GPS pour calculer le meilleur trajet depuis là où tu te trouves pour aller là où tu lui as demandé. Dans ce cas, à chaque intersection entre deux routes tes "voisins" sont les directions possibles à prendre, et ca peut aller aussi très vite. L'heuristique sera là pour favoriser le fait de rester sur ta route, mais aussi pour tenir compte de la vitesse maxi et bien entendu de la distance.
Les deux choses vont donc bien ensemble, elles sont même étroitement liées si tu veux que ca fonctionne correctement ! ;)

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite