Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Chroniqueur Actualités

    Homme Profil pro
    Webmaster
    Inscrit en
    janvier 2014
    Messages
    867
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webmaster
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : janvier 2014
    Messages : 867
    Points : 21 801
    Points
    21 801

    Par défaut Des chercheurs utilisent une amibe pour résoudre le problème du voyageur de commerce énoncé avec huit villes

    Des chercheurs japonais utilisent une amibe pour résoudre le problème du voyageur de commerce énoncé avec huit villes,
    un problème d’optimisation très complexe

    Alors que la recherche dans le domaine de l’informatique quantique bat son plein afin de trouver des solutions aux problèmes classiques difficiles à traiter avec les ordinateurs actuels, des chercheurs ont préféré suivre un autre chemin afin de résoudre un problème de mathématique extrêmement difficile. En informatique, le problème du voyageur de commerce pose un problème d’optimisation. Pour un sujet donné, il s’agit de parcourir un ensemble de villes séparées par des distances et trouver le plus court chemin pour parcourir ces villes une seule fois et revenir dans la ville de départ.

    A priori, le problème paraît simple lorsque le nombre des villes est peu élevé. Mais plus le nombre de villes croit, plus le nombre de solutions augmente de manière exponentielle. Par exemple pour 4 villes données, il n’existe que 3 solutions possibles. Mais pour 6 villes, le nombre de solutions s’élève à 360. Vu qu’il n’existe pas d’algorithme permettant de trouver une solution exacte rapidement dans tous les cas, une équipe de chercheurs japonais de l’université de Keio à Tokyo s’est servie d’une amibe afin de chercher à trouver des solutions au problème. En principe, les amibes sont des organismes unicellulaires qui ne ressemblent en rien à un système nerveux central, ce qui les rend moins aptes à résoudre un casse-tête aussi complexe. Cependant, l’expérience des chercheurs japonais a permis de démontrer que cet organisme est un candidat idéal pour calculer des solutions presque optimales au problème du voyageur de commerce dans huit villes au maximum.

    Il faut préciser que cet organisme unicellulaire du nom de Physarum polycephalum est capable de déformer son corps amorphe afin de pouvoir atteindre un point donné. Les chercheurs ont donc placé l’amibe dans une puce de 64 canaux. Et le tout a été positionné dans un environnement riche en nutriments afin d’amener l’organisme à s’étendre pour aller chercher de la nourriture. Par analogie au problème du voyageur de commerce, les canaux représentent les différentes villes à parcourir avant de revenir à la ville initiale. Les canaux ont été codifiés de A à H désignant chaque ville. Et pour définir l’ordre et le nombre de villes, un numéro de 1 à 8 est également attribué à chaque lettre pour déterminer les différentes étapes que l’amibe a suivies pour chercher et trouver la nourriture. Ainsi, si l’amibe étendait ses branches dans les canaux A3, B2, C4 et D1, la solution correcte au problème du voyageur de commerce serait D, B, A et C, car D1 indique que D est la première ville a avoir été parcourue, B2 indique que B est la deuxième ville, A3 indique que A devrait être la troisième ville et C4 indique que C est la quatrième avoir été parcourue.

    Il faut souligner en outre que l’amibe est assez réticente au métal et attirée par les sources de nourritures, ce qui fait qu’elle reste sur la puce. Par ailleurs, elle a également montré une aversion pour les stimuli lumineux, ce qui fait qu’elle se rétractera lorsqu’une voie sera éclairée et sera prompte à s’étendre lorsqu’une piste ne le sera pas. Pour ne pas influencer volontairement l’organisme dans sa progression, tous les stimuli lumineux ont été mis à jour de manière synchrone sur la base d’un réseau de neurones.


    Après avoir mené l’expérience avec ces 64 canaux, les chercheurs ont remarqué que le temps nécessaire au micro-organisme pour trouver une solution de qualité raisonnablement élevée au problème du commis voyageur (dans notre cas étendre son corps pour trouver le circuit de canaux le plus court afin d’atteindre les nutriments et revenir au point de départ) augmente de façon linéaire lorsque la taille du problème passe de quatre à huit villes. Et le fait le plus intéressant pour les chercheurs est que la qualité de la solution trouvée par le plasmodium ne s’est pas dégradée, même lorsque la taille du problème est devenue plus grande. Selon les chercheurs, ces résultats suggèrent que le plasmodium a la capacité de rechercher une solution de qualité raisonnablement élevée à un faible coût d’exploration.

    Le souhait des chercheurs serait d’extrapoler l’expérience en construisant un modèle beaucoup plus grand représentant un nombre de villes beaucoup plus élevé afin de voir si les mêmes conclusions se confirment et trouver des applications informatiques à ce procédé.

    Source : Royal Society

    Et vous ?

    Que vous suggère cette expérience ?

    Pensez-vous que la prochaine révolution informatique pourrait se trouver dans les dispositifs informatiques basés sur la biologie ?

    Voir aussi

    À 18 ans, il montre qu'un algorithme classique peut être aussi performant qu'un algorithme quantique et relance le débat sur la suprématie quantique
    Des chercheurs de Harvard ont créé un nouvel algorithme d'optimisation qui augmente de manière exponentielle la vitesse de calcul des ordinateurs
    OpenAI conçoit un algorithme basé sur l'IA qui permet à un robot d'imiter des tâches réalisées par des humains dans un environnement virtuel
    Des chercheurs trouvent un algorithme qui pourrait expliquer l'intelligence humaine et avancer le domaine de l'intelligence artificielle
    Des chercheurs du MIT créent un algorithme permettant d'avoir « du visible dans l'invisible », le code disponible en open source
    Contribuez au club : Corrections, suggestions, critiques, ... : Contactez le service news et Rédigez des actualités

  2. #2
    Membre extrêmement actif Avatar de Sodium
    Homme Profil pro
    Développeur Web
    Inscrit en
    avril 2014
    Messages
    997
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : avril 2014
    Messages : 997
    Points : 1 355
    Points
    1 355

    Par défaut

    Curieux qu'il n'y ait aucune mention du blob sur lequel des recherches similaires ont été menées.
    http://sweetrandomscience.blogspot.c...outes-des.html

  3. #3
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 137
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 137
    Points : 157 420
    Points
    157 420

    Par défaut

    Quelle est la qualité de leur solution (écart par rapport à l'optimum) ? Je doute qu'ils arrivent à une quelconque preuve formelle, vu le contexte, mais ça reste une analyse intéressante de leur approche.

    Pour la complexité, on ne peut pas extrapoler grand-chose de résultats sur quatre et huit villes, c'est trop petit… N'empêche, si leur temps est effectivement linéaire, ça serait un progrès remarquable (je ne connais pas d'heuristique qui ait une meilleure complexité que O(n log n) pour n villes).

    À titre de comparaison, on a pu trouver, dans les années nonante, la solution optimale à des problèmes d'une quinzaine de villes en quelques centièmes de seconde (http://www.math.uwaterloo.ca/tsp/con...s/bench99.html), pas beaucoup plus pour une vingtaine de villes… Pourtant, la complexité est exponentielle, mais on ne le remarque qu'avec des dizaines ou centaines de milliers de villes.

    Sinon, quid d'autres problèmes, intéressants, eux ? Genre, tournée de véhicules, beaucoup plus difficiles à optimiser (malgré sa classe de complexité, le TSP est assez simple à résoudre en pratique, sauf cas pathologique).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  4. #4
    Membre éclairé
    Profil pro
    Inscrit en
    décembre 2007
    Messages
    366
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2007
    Messages : 366
    Points : 848
    Points
    848

    Par défaut

    Citation Envoyé par Sodium Voir le message
    Curieux qu'il n'y ait aucune mention du blob sur lequel des recherches similaires ont été menées.
    http://sweetrandomscience.blogspot.c...outes-des.html
    J'allais dire la même chose.

  5. #5
    Membre confirmé Avatar de Vulcania
    Homme Profil pro
    Developpeur C++
    Inscrit en
    juillet 2011
    Messages
    84
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Developpeur C++
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juillet 2011
    Messages : 84
    Points : 647
    Points
    647

    Par défaut

    Si cette amibe est nourrie avec du café, pourrait-on la considérer comme un/une développeur(se) ?

  6. #6
    Membre éclairé
    Homme Profil pro
    Enseignant
    Inscrit en
    décembre 2007
    Messages
    206
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Suisse

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2007
    Messages : 206
    Points : 837
    Points
    837

    Par défaut

    Citation Envoyé par Sodium Voir le message
    Curieux qu'il n'y ait aucune mention du blob sur lequel des recherches similaires ont été menées.
    http://sweetrandomscience.blogspot.c...outes-des.html
    L'article de 2010 est cité dans celui de 2018 et dans les deux cas il s'agit de Physarum polycephalum.

  7. #7
    Membre actif
    Inscrit en
    février 2006
    Messages
    311
    Détails du profil
    Informations forums :
    Inscription : février 2006
    Messages : 311
    Points : 236
    Points
    236

    Par défaut

    L'un des problèmes qui m'a donné des cauchemars à la fac

  8. #8
    Nouveau membre du Club
    Homme Profil pro
    Retraité
    Inscrit en
    décembre 2009
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 68
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : décembre 2009
    Messages : 13
    Points : 26
    Points
    26

    Par défaut Faux problème

    Je suis impressionné du temps passé sur ce type de réflexion !
    Quelle est l'application pratique ? Les livraisons d' Amazon ?
    La belle affaire ! Vous croyez que c'est optimisé d'avoir 50 sociétés de livraison pour le dernier kilomètre en déplaçant une camionnette et un livreur pour transporter un colis de 300 g, qui plus est pas pressé mais qu'on veut avoir dans les 24 heures ?

    On n'est pas sûr d'avoir la solution optimale pour livrer 20 clients dans la journée et on repasse deux fois chez le tiers des clients ; belle optimisation ! Il suffit de décrocher son téléphone plutôt que de faire de savants calculs.
    Ou peut-être d'avoir un seul service de livraison finale mais efficace : ça s'appelle le facteur... ; malheureusement, il n'ont pas toujours fait leur boulot correctement et on a créé de nombreux services parallèles.

  9. #9
    Membre extrêmement actif Avatar de Sodium
    Homme Profil pro
    Développeur Web
    Inscrit en
    avril 2014
    Messages
    997
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : avril 2014
    Messages : 997
    Points : 1 355
    Points
    1 355

    Par défaut

    La curiosité scientifique tout simplement. Toutes les recherches scientifiques n'ont pas pour but d'aboutir à une application pratique, d'autant plus qu'en sciences on trouve souvent des applications pratiques par accident. Le fait qu'un organisme unicellulaire sans cerveau parvienne à résoudre des problèmes mathématiques est déjà suffisamment passionnant.

  10. #10
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 137
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 137
    Points : 157 420
    Points
    157 420

    Par défaut

    Tu prends l'exemple des livraisons Amazon, mais justement ce type de problème apparaît pour déterminer des tournées optimales. C'est un problème de recherche (tant académique qu'industrielle) très actif, comme maintenant. Même la Poste s'y met (au moins en Belgique, avec bpost), avec leur système Géoroute.

    Les tournées, c'est un problème bien plus complexe que le voyageur de commerce. Cependant, pas mal de techniques de résolution se basent sur de la génération de colonnes, des relâchements, des heuristiques diverses et variées, dans l'objectif d'utiliser un problème plus simple à résoudre (comme un voyageur de commerce, potentiellement avec l'une ou l'autre contrainte supplémentaire) pour apporter de l'information sur le problème d'origine. Tu as une petite liste d'applications sur le site de Guy Desaulniers, par exemple : https://www.gerad.ca/~guyd/pub.html.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  11. #11
    Futur Membre du Club
    Homme Profil pro
    jardinier
    Inscrit en
    avril 2018
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : jardinier

    Informations forums :
    Inscription : avril 2018
    Messages : 4
    Points : 6
    Points
    6

    Par défaut la sagesse des anciens

    Pour trouver un augure de qualité autant le récupérer dans les plus archaïques, le résultat n'en sera que plus mystérieux: l'alignement des étoiles est-il pris en compte? L'influence de Jupiter? Les scientifiques étaient certes auréolés d'une sainteté climatique mais prenons garde à ne pas les confondre avec les oracles des temps modernes (sans doute mieux que les politiques)...

  12. #12
    Membre habitué
    Profil pro
    Inscrit en
    juin 2007
    Messages
    321
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2007
    Messages : 321
    Points : 159
    Points
    159

    Par défaut

    Le problème du voyageur du commerce est présent un peu partout dans les mathématiques, dès qu'il est question d'optimisation

    Par exemple, je le retrouve quand je dois optimiser les points de départ des passes dans un programme d'usinage

    J'utilise les algorithmes génétiques pour y parvenir

    A bientôt

Discussions similaires

  1. Réponses: 5
    Dernier message: 18/01/2017, 15h21
  2. Des chercheurs utilisent nos tweets pour mesurer notre santé mentale
    Par Amine Horseman dans le forum Actualités
    Réponses: 6
    Dernier message: 02/01/2015, 14h48
  3. Réponses: 20
    Dernier message: 25/01/2011, 13h12
  4. Réponses: 2
    Dernier message: 16/12/2010, 15h31
  5. Comment utiliser Developpez.com pour résoudre votre problème
    Par Anomaly dans le forum Mode d'emploi & aide aux nouveaux
    Réponses: 0
    Dernier message: 08/01/2005, 12h11

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo