D@mien Olivier

Des Fêtes de la science partout en France

Ce titre vaut ce qu'il vaut, mais je ne suis pas sur que dans le contexte actuel où tout doit être utilitariste nous empruntions la bonne voie ! La novlangue accompagne ce mouvement, il n'est question que d'excellence, de pépite .... Une vision très consommatrice de la science comme notre société peut l'être avec les ressources et une volonté de toujours plus. Mes états d'âme n'ont pas d'importance, oublions les que la fête commence !

Source : [1]

C'est la 23e édition elle se déroulera du 8 au 12 octobre 2014 sur l'ensemble de la France et le LITIS tiendra un stand dans le hall de l’hôtel de ville du Havre.

On fait quoi à la teuf

Le thème développé est la Mobilité, science en mouvement... au premier ou second degré, de la théorie à la pratique. Nous y proposerons des expériences simples, qui vous permettront de découvrir les applications de la recherche en informatique et en mathématiques. Des chercheurs présenteront leurs travaux ainsi que des réalisations faites dans le Fablab ABC de l'université du Havre et de l'ESADHAR. Ce sera l'occasion de découvrir ce qui se cache derrière ce mot étrange et le do it yourself ! Vous pourrez également découvrir un ordinateur à bulle capable de résoudre un problème de plus court chemin. Le voyageur de commerce ou le touriste américain verra également son problème de parcours d'un ensemble de villes résolu par des fourmis qui sont un peu spéciales, elles sont numériques.

Bullons un peu

Nous avons tous joué avec des bulles de savon et peut être regardons nous avec envie les enfants qui y jouent. La recherche du plus court chemin reliant quatre villes nous donne un prétexte pour continuer et nous emmène vers des surfaces minimisant leurs aires sous l'effet de contrainte. On peut également l'appliquer à l'échelle de la Normandie. Derrière cela se pose des jolis problèmes de mathématique et d'informatique, mais aussi de méthodologie scientifique.

• Le poster

Voyage voyage

Tout d'abord un peu de publicité pour une collègue. Elizabeth Durot-Boucé Jeudi 9 octobre de 14h à 14h45 à l’hôtel de ville vous emmènera en voyage dans la littérature du XVIIIe siècle où le thème est très présent. Réel ou imaginaire, le voyage est un prétexte à l'accomplissement de soi. C'est une oratrice hors pair elle vous fera rencontrer au détour d'une œuvre Candide, Rica et Usbek à moins que cela soit Donatien, la mise en perspective avec notre quotidien est parfois cruelle.

Si la littérature nous offre des voyages souvent immobiles, l'informatique s'interroge sur les chemins les plus courts pour aller d'un point à un autre. Cette question appartient à notre quotidien dans le cadre de nos mobilités et d'une simple lecture de carte (graphe) nous sommes passés à l'utilisation d'algorithmes avancés avec nos "GPS". Certain de ces algorithmes trouvent leurs racines dans les comportements naturels observés chez les insectes sociaux et en particulier les fourmis.

Considérons le problème dit du voyageur de commerce : étant donné n villes et les distances séparant chaque ville, trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque ville et revienne à la ville de départ. Avant d'aller plus avant dans la présentation d'une résolution informatique du problème, intéressons nous au comportement des fourmis dans le cadre du fouragement.

Les fourmis lorsqu'elles cherchent de la nourriture commencent à explorer aléatoirement l'environnement autour du nid. Lorsqu'une ou plusieurs trouvent de la nourriture elles rentrent au nid en déposant chemin faisant des phéromones qui sont des molécules chimiques volatiles. Ces dernières sont attractives, elles attirent les fourmis ne transportant pas de nourriture, les autres reviennent vers le nid et déposent des phéromones renforçant la ou les pistes. Lorsque plusieurs chemins sont possibles, le plus court étant le plus rapide, les fourmis l'empruntant le renforcent d'abord et il devient plus attractif, par renforcement. Les phéromones étant volatiles, elles s'évaporent et de ce fait font disparaître le marquage éventuel des plus longs chemins. Il faut noter que bien que les fourmis tendent simplement à suivre les pistes de phéromone, elles peuvent quitter un chemin marqué et en découvrir un nouveau. Ce type de fluctuation permet de s'adapter à des changements au niveau de l'environnement comme l'apparition d'un obstacle.

Les fourmis trouvent collectivement la solution, on parle alors d'intelligence en essaim ou d'intelligence collective.

Les fourmis font preuves d'auto-organisation. Quatre caractéristiques se dégagent [2] :

1. Des interactions nombreuses et multiples ;
2. Des fluctuations ;
3. Un mécanisme de rétroaction positive créant un phénomène d'amplification. Une piste déjà très marquée attire d'autre fourmi qui vont la renforcer.
4. Un mécanisme de rétroaction négative qui permet une régulation. Dans le cas des phéromones il s'agit de l'évaporation.

Ces comportements ont donné lieu à différent modèles et des simulations comme celle proposée en NetLogo [3].

On constate que la source de nourriture est d'abord exploitée puis les suivantes.

Dans le cas précédent l'environnement est ouvert Jean-Louis Deneubourg et al se sont interrogés sur un fonctionnement plus contraint, en définissant des chemins. Pour cela ils ont réalisé l'expérience du pont binaire [4-5] (binary bridge). Elle est constituée d'un double pont entre un nid et unse source de nourriture. Plusieurs chemins sont alors possibles dont certains plus longs que les autres. Les fourmis vont alors emprunter le chemin le plus court comme le montre la photo ci-dessous.

Le modèle [6]

On considère un graphe modélisé par des sommets et des arcs reliant ces derniers. Des fourmis numériques parcourent ce graphe et déposent dans l'environnement des phéromones sous la forme de valeurs numériques sur les arcs. Les fourmis se déplacent dans ce graphe suivant ces valeurs qui définissent des probabilités. Supposons qu'une fourmi soit sur un nœud `A` et que de ce nœud elle puisse atteindre les nœuds `B` `C` et `D` et que sur chacun des arcs il y ait respectivement 10, 30 et 20 unités de phéromone. L'arc `A-B` a une probabilité d'être emprunté de 1/6, `A-C` de 1/2 et `A-D` de 2/3. Les fourmis construisent le chemin à l'aller entre le nœud de départ et d'arrivée et au retour marque le chemin en augmentant les phéromones sur les arcs traversés. Cela constitue la mise en œuvre du mécanisme de rétroaction positive.

La rétroaction négative consiste à faire décroître les valeurs de quantité de phéromone sur les arcs à chaque pas de temps. La fluctuation est assurée par l'aléatoire, la modification d'un chemin est alors possible et le meilleur chemin peut à nouveau être découvert, comme le montre la figure ci-dessous.

Maintenant que nous avons vu les différents principes nous pouvons revenir à notre problème de voyageur de commerce.

Le voyageur de commerce

Les villes sont donc les sommets du graphe et tous les trajets sont possibles, autrement dit ils sont tous connectés. L’algorithme est simple :

• On considère un ensemble de fourmis réparties sur les sommets du graphe.
• À chaque pas de temps, chaque fourmi choisit son prochain sommet. Le choix dépend de la distance entre le sommet sur lequel elle se situe et le suivant mais aussi de la quantité de phéromone sur l'arc qu'elle va éventuellement parcourir.
• Les sommets déjà visités ne peuvent être revisités, ils sont donc supprimés des sommets accessibles par la fourmi.
• Lorsque toutes les fourmis ont terminé leur parcours, les phéromones sont mises à jour. L'évaporation joue à chaque itération.

Sur la figure ci-dessous on voit la résolution avec 46 villes et 60 foumis. Au départ le parcours est de 1521 unités et on obtient au final un parcours de 413 unités.

Pourquoi j'aime la science et vous ?

C'est une question qu'il m'arrive de me poser, encore faut-il avouer que je l'évacue rapidement. Bizarrement cette interrogation surgit plutôt quand les ennuis dépassent les plaisirs dans un quotidien souvent encombré de contraintes. Voila une entrée en matière ! Il aurait peut-être été plus simple de commencer en disant que j'ai été poussé dedans quand j'étais petit, mais voila c'est à la fois vrai et faux. Vrai car cela appartenait à la culture familiale et que j'étais attiré par elle, faux car l'école ne m'amenait pas à la science, mais de la science souvent sans ses processus et j'étais dépassée par elle, cela s'est construit. C'est une mémoire rétive qui a terminé le travail et qui m'a fait tomber dedans, apprenant mal il m'a fallu comprendre pour savoir.

Toute science se définit par un objet et une méthode. Les mathématiques on fait le choix de la démonstration et la majorité des autres de la méthode expérimentale. Claude Bernard disait "le fait suggère l'idée, l'idée dirige l'expérience, l'expérience vérifie l'idée". L'informatique est atypique en ce sens qu'elle est à la fois éthérée comme les mathématiques et relève des deux méthodologies. Mais c'est dans la deuxième que je me reconnais le mieux, je suis avant tout bricolicien. Le fait suggère le modèle, le modèle engendre le programme, le programme dirige la simulation et la simulation vérifie le modèle. On part donc du problème, dont on extrait un modèle "calculable" (computable) et avec les outils mis à disposition par l'informatique, on plonge le modèle dans le temps pour le confronter au problème initial. Imaginer, voir, toucher et parfois comprendre ces trajectoires créent du plaisir.

J'aime la science, la recherche en science on pourrait lire, pour les problèmes qu'elle pose, nous poussant à comprendre (saisir par l'intelligence), mais aussi parce que la compréhension (prendre ensemble) se fait collectivement et le temps n'a que peu d'emprise. Je comprends des problèmes grâce à ceux qui nous ont laissé souvent des éclairs de génie, parfois plusieurs siècles en arrière, et modestement avec vous, avec d'autres, nous cherchons à avancer. Peut-être cela servira t-il à d'autres encore, maintenant, plus tard, ou jamais ? Comprendre et transmettre, c'est collectif et c'est une aventure humaine commencée avec le premier homme, c'est même une grande partie de ce qui fait l'humanité. Cela échappe au mercantile, même si de nombreuses dérives actuelles nous y poussent dans nos sociétés toujours plus technologiques, voulant croire qu'un avenir se construit sur des fonctions que l'on optimise.

J'aime la science pour ses racines communes dans cet amour du savoir avec la philosophie, mais également pour la beauté qu'elle génère au détour de l'élégance d'une démonstration, ou de la résolution d'un pavage du plan. Elle ne remplacera jamais l'art, mais elle peut en être une muse.

J'aime la science parce que je ne comprend pas que l'on puisse pas l'aimer !

Partagez votre point de vue en laissant un commentaire.

Références

[1] T. Latty, K. Ramsch, K. Ito, T. Nakagaki, D. J. T. Sumpter, M. Middendorf, et M. Beekman. Structure and Formation of Ant Transportation Networks. Journal of The Royal Society Interface 8, no 62, pages 1298‑1306, 7 septembre 2011.
[2] E. Bonabeau, M. Dorigo M, G. Théraulaz, Swarm Intelligence. From Natural to Artificial Systems, Oxford University Press, pages 8-14, 1999.
[3] U. Wilensky, NetLogo Ants model. http://ccl.northwestern.edu/netlogo/models/Ants. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL 1997.
[4] S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, Self-organized shortcuts in the Argentine ant, Naturwissenschaften, volume 76, pages 579-581, 1989.
[5] J.-L. Deneubourg, S. Aron, S. Goss et J.-M. Pasteels, The self-organizing exploratory pattern of the Argentine ant, Journal of Insect Behavior, volume 3, page 159, 1990.
[6] A. Dutot, F. Guinand, et D. Olivier. General principles of combinatorial problems solving by ant colony. In Artificial Ants - From Collective Intelligence to Real-life Optimization and Beyond, édité par Nicolas Monmarché, Frédéric Guinand, et Patrick Siarry, pages 19‑70, 2010.