Les fourmis, les micro-icônes de l’assiduité et de l’organisation, apparemment peuvent nous apprendre quelque chose sur la façon dont fonctionnent les réseaux informatiques et comment ils peuvent être améliorés. Une équipe du Computer Science and Artificial Intelligence Laboratory du MIT a étudié les fourmis pour créer un modèle d’analyse des réseaux sociaux, de prise de décision collective des essaims de robots, et de communication dans les réseaux décentralisés, ad hoc sans fil.
L’étude du MIT confirme une hypothèse de longue date dans la communauté scientifique, à savoir que les fourmis estiment leur densité de population en fonction de la fréquence à laquelle elles se cognent à d’autres fourmis tout en explorant au hasard leurs environs. Cette capacité semble être la clé de plusieurs activités, y compris de décider où la colonie établit un nouveau nid.
« C’est intuitif que si un tas de gens se promènent au hasard autour d’une zone, le nombre de fois qu’elles se cognent l’un à l’autre sera un substitut de la densité de la population», assure Cameron Musco, co-auteur d’un article sur la recherche. « Ce que nous faisons est d’effectuer une analyse rigoureuse derrière cette intuition, et dire aussi que l’estimation est une très bonne estimation, plutôt qu’une estimation grossière. »
Les chercheurs font un parallèle entre l’environnement d’une fourmi et une grille. Une fourmi exploratrice commence à partir d’une certaine cellule de la grille et se déplace probablement vers l’une des cellules adjacentes. Il est également probable qu’elle se déplace ensuite vers une autre cellule adjacente à celle qu’elle a quittée, et ainsi de suite. En langage statistique technique, on appelle cela «une marche aléatoire». La fourmi exploratrice compte le nombre d’autres fourmis dans toutes les cellules qu’elle visite.
Marche aléatoire versus échantillonnage aléatoire
L’étude compare la marche aléatoire à l’échantillonnage aléatoire, qui est lorsque les cellules sont choisies dans la grille au hasard et le nombre de fourmis comptées dans chaque cellule. Dans les deux cas, la précision s’améliore avec chaque échantillon supplémentaire, mais le facteur surprenant ici est que la marche aléatoire peut révéler la vraie densité de population presque aussi vite que la méthode d’échantillonnage aléatoire essayée et testée, le fait.
Les chercheurs disent que cela est pertinent parce que, dans de nombreux cas pratiques d’échantillonnage aléatoires, ce n’est pas une option. Par exemple, dans les réseaux ad hoc, un dispositif donné ne connaît que les emplacements des appareils dans son voisinage immédiat. Un algorithme qui utilise des trajets aléatoires pour regrouper des informations provenant de plusieurs appareils serait beaucoup plus facile à mettre en œuvre que celui qui doit caractériser le réseau dans son ensemble.
L’étude reçoit devient alors intéressante pour ses constatations les plus contre-intuitives.
Il serait logique de supposer que la fourmi exploratrice est susceptible de revenir vers une cellule, qu’elle a déjà visitée, donc une cellule donnée serait plus probablement échantillonnée que dans le cas des échantillonnages aléatoires. Mais quand les chercheurs sont devenus nerveux à propos des données échantillonnées et qu’ils ont essayé de les filtrer, ils ont constaté que, au lieu d’améliorer leur algorithme, c’était pire. Ils ont une explication théorique pour cela.
« Si vous marchez au hasard autour d’une grille, vous n’allez pas vous cogner dans tout le monde, parce que vous n’allez pas traverser toute la grille», explique Cameron Musco. « Donc, il y a quelqu’un de l’autre côté de la grille dont j’ai à peu près aucune chance de cogner. Mais si je cogne moins dans ces gars-là moins, je cogne plus de personnes en local. Je dois compter sur toute mon interaction avec les personnes en local pour compenser le fait qu’il y a ces personnes au lointain que je ne vais jamais cogner. C’est une sorte d’équilibre en quelque sorte parfaitement « .
La structure de données de graphes
Pour modéliser l’environnement des fourmis, les chercheurs ont utilisé une structure de données de graphe comprenant des nœuds (cercles) et des bords, qui sont des segments de droite reliant les nœuds. Dans la grille, chaque cellule est un nœud, et il partage des bords uniquement avec les cellules immédiatement adjacentes.
Si le graphique n’est pas très bien connecté, avec juste une chaîne de nœuds, chacun est connecté uniquement aux deux nœuds adjacents, mais le suréchantillonnage pourrait devenir un problème, avec l’exploratrice coincée dans le même ensemble de nœuds. Mais des graphiques décrivant des réseaux de communication comportent souvent deux marches aléatoires à partir du même nœud, puis bifurquent dans des directions différentes. Ceci étant le cas, les marches aléatoires peuvent offrir presque le même degré de précision que l’échantillonnage aléatoire.
Plus le nombre d’exploratrices est grand, plus une analyse produirait une estimation précise. « Si elles étaient des robots à la place des fourmis, elles pourraient obtenir des gains en parlant les uns aux autres et en disant:« Oh, ceci est mon estimation » ajoute Cameron Musco.
Les chercheurs présenteront leur communication lors Association for Computing Machinery’s Symposium on Principles of Distributed Computing conference, qui aura lieu à Chicago du 25-29 Juillet.
http://news.mit.edu/2016/ant-colony-behavior-better-algorithms-network-communication-0713
http://www.podc.org/podc2016/program/
