Shrinking Blob calcule des solutions pour les vendeurs itinérants

Le problème du voyageur de commerce est l'un des défis les plus célèbres des mathématiques. C'est le problème de trouver le chemin le plus court pour visiter une fois plusieurs villes et revenir ensuite au lieu d'origine.

Bien sûr, il est simple de trouver des itinéraires qui visitent chaque ville de cette manière. Le grand défi est de trouver le plus court.

Il existe un moyen infaillible de le faire - par la force brute pure. Cela signifie mesurer la durée de chaque tournée et déterminer laquelle est la plus courte. Le problème est que cette tâche devient de plus en plus longue à mesure que le nombre de villes augmente. En effet, pour un grand nombre de villes, c'est informatiquement irréalisable.

Il est facile d'imaginer qu'il pourrait y avoir une sorte de raccourci mathématique intelligent qui résout ce problème. Pas si. En fait, les mathématiciens ont tendance à convenir qu'un raccourci général ne sera jamais trouvé (c'est ce qu'on appelle le débat P=NP).

Au lieu de cela, ils doivent s'appuyer sur des processus d'optimisation qui recherchent des solutions courtes mais sont incapables de prouver que ce sont bien les plus courtes.

Ainsi, le défi à toutes fins pratiques est de trouver des algorithmes qui produisent de bons résultats et qui soient efficaces en termes de calcul.

Aujourd'hui, Jeff Jones et Andrew Adamatzky de l'Université de l'Ouest de l'Angleterre au Royaume-Uni révèlent une approche inhabituelle. Ces gars disent qu'une solution raisonnable peut être trouvée en représentant les villes comme une série de points dans une boîte de Pétri virtuelle, en immergeant les points dans une goutte de glu virtuelle, puis en réduisant la goutte.

En termes simplifiés, la goutte s'accroche aux points au fur et à mesure qu'elle rétrécit, les reliant à une surface minimale, un peu comme une surface de bulle de savon. Au fur et à mesure que le blob rétrécit, il s'adapte morphologiquement à la configuration des villes, disent-ils.

Lorsque tous les points se trouvent à la surface du blob, la surface résultante est une solution au problème du voyageur de commerce qui est généralement assez bonne.

L'ingrédient magique dans tout cela est le goo spécial. Il se compose de nombreuses particules qui se déplacent chacune selon un ensemble de règles simples, à la manière d'agents autonomes. Ceux-ci reposent dans une mer de chimioattractant, une odeur virtuelle vers laquelle les particules sont attirées. A chaque étape du calcul, chaque particule détecte le chimioattractant qui l'entoure puis se déplace vers la région de concentration la plus élevée. En se déplaçant, il laisse derrière lui sa propre trace de chimioattractant pour que d'autres particules suivent.

Le résultat est une sorte de blob intelligent qui montre un comportement émergent, comme la capacité de minimiser sa surface.

Jones et Adamatzky ont mis ce goo intelligent à l'épreuve en lui faisant perdre des problèmes de voyageur de commerce consistant en 20 villes réparties au hasard dans une boîte de Pétri virtuelle. ils ont placé vidéos du processus de rétrécissement ici .

Les résultats sont bons mais pas parfaits. Ils ont créé 20 scénarios différents de 20 villes et ont exécuté le blob 6 fois sur chacun. Ils ont ensuite comparé le chemin le plus court du blob au chemin le plus court trouvé par la force brute. Jones et Adamatzky disent que si cet itinéraire le plus court est de longueur 1, le blob intelligent a trouvé des circuits avec une meilleure longueur moyenne de circuit de 1,04, une longueur moyenne de circuit de 1,07 et une durée moyenne de pire circuit de 1,09.

C'est pas mal. Mais le véritable avantage réside dans la simplicité de l'approche qui est essentiellement émergente et n'implique pas de processus d'optimisation particuliers. Il produit également une carte de l'itinéraire à la fin (bien qu'une certaine interprétation humaine soit nécessaire pour lui donner un sens).

Il y a des inconvénients, bien sûr. Il existe certaines configurations de villes auxquelles le blob ne peut pas faire face. Ceux-ci se produisent lorsque la route la plus courte forme une sorte de détroit entre deux villes plutôt qu'une connexion, comme le détroit de Gibraltar entre l'océan Atlantique et la mer Méditerranée. Au lieu de cela, le blob a tendance à les connecter.

Néanmoins, il s'agit d'une forme intéressante d'informatique non conventionnelle qui produit une alternative fascinante aux algorithmes conventionnels du voyageur de commerce. Il ressemble le plus aux approches élastiques qui entourent les villes d'un élastique, puis tentent progressivement d'étirer l'élastique pour relier les villes à l'intérieur. La grande différence est que les propriétés matérielles du blob sont émergentes plutôt que préprogrammées.

Jones et Adamatzky disent que la prochaine étape serait de créer un modèle physique de ce système dans lequel un vrai blob fait le travail, peut-être en utilisant une minimisation viscoélastique et de l'énergie libre. Cependant, la conception d'un tel matériau peut être délicate.

Une autre approche, qui pourrait avoir une application plus large, serait de distiller les propriétés de ce calcul non conventionnel dans un algorithme classique.

Le meilleur de tous est la perspective que les responsables logistiques planifient les itinéraires de livraison en plongeant des modèles de réseau routier dans des cuves de boue intelligente. Attendons donc avec impatience cette nouvelle science de l'alchimie du voyageur de commerce.

Réf : arxiv.org/abs/1303.4969 : Calcul du problème du voyageur de commerce par une goutte qui rétrécit

cacher