Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Probleme de voyage de commerce asymetrique

Problème de voyage de commerce Histoire le problème de voyageur de commerce à été évoqué pour la première fois en par le mathématicien viennos Karl Menger il a intrigué bon nombre de chercheurs depuis ce temps Sans doute par ce qu ? il est facile à énoncer mais di ?cile à résoudre Ce problème cache de nombreuses ?nesses et di ?cultés qui nous emmènerons dans les développements récents de la théorie des recherches CDomaines d ? application ? le domaine de logistique la livraison des marchandises ? optimisation de trajectoires de machines outil ? Problème de ?lage d ? ordinateur ? Problème de coupage et de perçage ? Développement algorithmiques et théories importantes C L ? objectif principal Le problème de voyageur de commerce asymétrique consiste à trouver un circuit C passant une et une seule fois par chaque sommet du graphe G circuit hamiltonien dont le coût total cij est minimal dépôt dépôt dépôt CAlgorithme de colonie de fourmi pour le problème de voyageur de commerce O n considère un problème de voyageur de commerce à N villes pour chaque fourmi k le trajet d ? une ville i à une ville j dépend de ? La liste des villes déjà visitées ? La visibilité qui est l ? inverse de la distance entre les villes nij ? La quantité de phéromone déposée sur l ? arête reliant deux villes ij t appelée l ? intensité de la piste C Pour chaque fourmi k le trajet d ? une ville i à une ville j dépend de La formule sont les parametres qui controllent l ? importance relatives entre phéromones et visibilité CAlgorithme de colonie de fourmi pour le problème de voyageur de commerce Si et ont la même quantité de phéromones Donc la probabilité de choisir et plus grande que celle de C Après un tour complet chaque fourmi dépose une quantité de phéromone Cette quantité dépend de la qualité du solution trouvée qui est La formule La formule est la tournée fait par le fourmi k à l ? itération t la longueur du trajet et Q un paramètre de réglage C Les arcs - - et - est un chemin commun entre les deux graphes C A partir de est plus probable en raison de la distance et la quantité de phéromone A partir de peut être sélectionnés en raison de la Phéromone et en raison de La distance C Si l ? une des fourmis choisit - puis par la suite elle va Choisir en raison de la Distance et de la phéromone La plus élevée Le meilleur trajet est ?? ?? ?? ?? CFonctionnement de l ? algorithme Tant le critère d ? arrêt n ? est pas atteint faire pour k à m faire choisir une ville au hasard pour chaque ville non visitée faire choisir une ville j dans la liste des villes restantes selon la formule ?n pour déposer une piste sur le trajet t conformément à la formule ?n pour