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
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 !