Auteurs :
Cet article est repris du site Binaire avec l’autorisation de l’INRIA.
Tous les ans les étudiantes et étudiants des classes préparatoires aux écoles d’ingénieur-e-s font un travail d’initiative personnelle encadré (TIPE) qui permet de les évaluer, au delà de compétences plus scolaires, sur leur capacités à proposer un projet de recherche en équipe et le mener à bien.
Ce travail pourrait défavoriser les candidat-e-s éloignés des ressources humaines et documentaires utiles, mais la mission de médiation scientifique Inria se met au service de toutes et tous à ce propos, avec Interstices (sélection des ressources) et Pixees (accompagnement et ressources), en lien avec ePrep.
Cette année le thème est Optimalité : choix, contraintes, hasard, c’est un sujet scientifique passionnant : laissons à la parole [1] Guy Cohen, Pierre Bernhard et ses collègues pour nous l’expliquer. Thierry Viéville .
Optimiser pour résoudre un problème ? Une idée d’ingénieur-e !
Faire “le mieux possible” est somme toute une attitude naturelle dans la vie courante. Pour un ingénieur également, c’est un objectif permanent lorsqu’il est par exemple en charge la conception d’un équipement ou le dimensionnement d’une installation.
Mais, l’expression doit être relativisée. Tout dépend des contraintes, par exemple de budget ou de sécurité, tandis que le choix du critère à optimiser a fait l’objet de décisions préalables et souvent extérieures au travail à réaliser.
L’arbitraire du choix du critère et des contraintes ne fait donc pas partie du formalisme. Cet arbitraire est la marge de manœuvre qui permet à l’utilisateur ou au client d’exprimer ses désirs plus ou moins précis, voir même contradictoires.
Une fois ces spécifications arrêtées, il faut expliciter une solution (ou une décision) qui soit “meilleure” que toutes les autres. Il s’agit alors de modéliser le problème : caractériser cette solution pour la reconnaître (conditions d’optimalité) car la définition informelle de l’optimalité n’est pas utilisable de façon opérationnelle. On peut ensuite voir comment la faire calculer.
Soit. Mais une compréhension de la méthode mathématique et informatique qui vient ensuite permettre de guider ces choix est très utile, y compris aux « utilisateurs finaux », évitant par exemple des formulations difficiles à résoudre, fournissant des retours sur la nature du problème posé, quantifier dans une certaine mesure les choix a priori les uns par rapport aux autres.
Regardons alors cet aspect.
Optimiser pour résoudre un problème ? Une idée d’informathématicien-ne !
Cette façon de poser le problème place la théorie de l’optimisation dans une famille plus large dite des “problèmes variationnels” qui contient notamment tous les problèmes d’équilibre rencontrés dans de nombreuses branches de la Physique, des problèmes de transport, de théorie des jeux, les algorithmes d’apprentissage automatique, etc. Inversement, certains états d’équilibre de la Nature peuvent se réinterpréter comme les solutions de problèmes d’optimisation, ce qui donne souvent des moyens efficaces pour en étudier leurs propriétés. Ainsi considère-t-on, en général que les espèces au cours de leurs évolutions se sont adaptées au mieux à l’environnement. Et si ingénieurs et mathématinformaticiens ont l’habitude de poser les problèmes d’optimisation en termes de minimisation (d’un coût), les économistes aussi utilisent ce paradigme mais eux maximisent (un profit).
On se convaincra que c’est (au signe près : maximiser une fonction est bien équivalent à minimiser son opposé) la même théorie qui s’applique.
Quel est le levier pour résoudre un tel problème ? Une “cuisine” algorithmique. Une fois que le mathématicien a su caractériser une solution, et se prononcer sur son existence, voire son unicité, l’ingénieur voudrait bien pouvoir calculer cette solution. Il est hors de question de passer en revue tout ce qui est imaginable ou autorisé ; il s’agit d’aller au plus vite vers la solution en améliorant par touches successives une ébauche de celle-ci.
Il y a une première idée très simple : partir d’une proposition initiale raisonnable voir même choisie au hasard. Ensuite, regarder dans son voisinage si une autre proposition ne serait pas encore meilleure. Oui ? Prenons là alors ! C’est déjà ça de gagné. Et recommençons avec cette nouvelle proposition, regardant de proche en proche comment améliorer. Rien de meilleur dans le voisinage ? Dans ce cas, cela signifie que la proposition est localement optimale. Facile, non ?
Racontons l’histoire avec un langage mathématique. Brrr il fait froid ici ! Trouvons un endroit, une position p, idéale où il fasse bien chaud. Comme c’est des maths, j’écris T(p) = 30 pour dire : « je veux une position p où la température T est de 30 degrés ». C’est la solution à mon problème. Mais … comment deviner quelle est la bonne position : le bon p ? Essayons avec ma position actuelle, je la nomme p0. Je calcule T(p0) = 10. Dix degrés : Ouf ! Ça caille. Allez, bougeons un peu, vers la droite j’arrive à une position p1, avec T(p1) = 5. Mauvaise pioche. Et vers la gauche ? Là j’arrive à une position p2, avec T(p2) = 15. C’est déjà mieux. Je vais alors tester le voisinage et aller vers un endroit encore plus chaud. Exactement comme lorsque nous étions enfants et nous jouions à deviner une cachette en guidant le joueur à force de « tu te réchauffes » ou « tu refroidis » jusqu’au « tu brûles » qui … bon. Tout le monde a compris.
Au lieu de trouver la bonne solution à un problème, on utilise un algorithme qui va améliorer d’itération en itération la solution initiale pour trouver la meilleure solution . Ici, le mieux est l’ami du bien.
De belles mathématiques pour que l’idée fonctionne.
Que faut-il pour que cette idée fonctionne bien ? Les mathématiques nous fournissent deux grandes idées : la première est la continuité . Dans cet exemple, il faut que la température varie continument pour que ma recherche ait un sens. Si, à contrario, tout change dans tous les sens dans le voisinage je vais vite errer de manière chaotique à la merci de valeurs difficiles à relier entre elles.
Une deuxième grande idée est la convexité . Finalement, avec mon mécanisme, je ne fait que trouver un optimum local . Qui me dit que si je n’explore pas plus loin, quitte à passer par une zone fort froide, je ne vais pas trouver finalement un bon coin de feu, tout à fait réchauffant ? Garantir qu’il n’y a qu’un seul optimum global , sans concavité (autrement dit sans minimum local qui empêcherait de rechercher plus loin une meilleure solution) a été étudié en détail, c’est cette notion de convexité.
On redit la même chose avec des équations ? Regardez cette figure [ici insérer probleme-optimisation.jpg (en fin de ce texte) avec les formules de Pierre]. Ce qu’elle contient peut attirer, rebuter, mais c’est en tout cas très joli !
Et quand l’informatique vient au secours des mathématiques.
Dans beaucoup de problèmes d’ingénierie (ou d’économie), on sait calculer la fonction objectif, mais au prix d’un programme complexe. Dans certains cas on sait aussi calculer les variations de cette fonction pour aller vers l’optimum, mais encore au prix d’un programme compliqué (parfois déduit automatiquement du précédent). Dans des cas plus graves, on ne sait même pas calculer les variations exactes. Et puis il y a beaucoup de situations où il n’existe pas “un” optimum global mais plusieurs optima locaux qui ne s’obtiennent pas avec une formule mathématique, il faut alors ajouter des mécanismes d’exploration.
Il existe ainsi un grand nombres d’algorithmes d’optimisation. Par exemple des algorithmes génétiques, qui s’inspirent de ce que l’on comprend de l’évolution génétique des systèmes biologiques pour coupler optimisation locale d’une solution, avec un mécanisme de mutation vers de nouvelles solutions inédites. En pratique, c’est le dernier recours quand rien de plus efficace n’est possible !
L’étude des algorithmes d’optimisation, plus ou moins sophstiqués, est donc un sujet de la plus haute importance. Certains auteurs ont voulu opposer une mathématique “traditionnelle”, préoccupée de théorèmes, à une informatique “contemporaine”, préoccupée d’algorithmes. Mais que serait un algorithme sans un théorème disant qu’il calcule effectivement ce qu’on veut ? La création et l’étude des algorithmes est un objet essentiel, aussi ancien que les mathématiques elles-mêmes qui requiert des théorèmes de convergence, de cohérence (“consistency”, c’est à dire que si l’algorithme converge, c’est bien vers le résultat recherché) et qui mobilise tout l’arsenal des mathématiques “traditionnelles”.
Des humains aux cellules … Dame Nature ferait-elle de l’optimisation ?
Regardons deux exemples d’applications un peu inattendues.
Embouteillages.
Dans une ville encombrée, les automobilistes ont le choix entre plusieurs routes possibles pour se rendre d’un point à un autre. Tous souhaitent éviter les encombrements, et, disons, effectuer leur déplacement dans le temps le plus court possible. Pour fluidifier la circulation, les pouvoirs publics peuvent (en dépensant beaucoup d’argent !) ouvrir de nouvelles voies ou améliorer considérablement la vitesse de parcours de certaines. Mais il est arrivé (Stuttgart 1969) que cela fasse tellement empirer la situation de tout le monde qu’il faille fermer une voie récemment ouverte. (Paradoxe de Braess). On a pu observer ce paradoxe à New York lors de la fermeture de la 42ème rue.
Bref il faut parfois “bloquer des voies” pour … limiter les embouteillages.
L’étude de cette question, notamment par John Glenn Wardrop (1952), et Dietrich Braess (1968) rejoint des questions de théorie des jeux, et pose de nombreuses questions annexes : l’occurence d’un paradoxe de Braess est-elle fréquente ou exceptionnelle ? Pourrait-on améliorer le trafic en étant plus directif, et de combien ?, etc.
Une chercheuse Inria, Paola Goattin, étudie ce type de problème et … sauve des vies humaines en montrant que lors de l’évacuation d’une foule (par exemple dans un cinéma en feu) il faut mettre des poteaux qui freinent les gens (en fait évitent les phénomènes de bousculade) pour optimiser les chances que tout le monde sorte vivant. Ce qui est remarquable c’est que le modèle est celui d’un fluide dont les humains seraient les particules et dont on éviterait les turbulences.
Évolution des espèces .
On admet que l’évolution des espèces biologiques a sélectionné les comportements les plus efficaces. Pourquoi, donc, observe-t-on des comportements différents au sein d’une même espèce ?
Un peu de dynamique des populations (comment évoluent les effectifs des populations) permet de répondre. L’exemple type est celui dit “des faucons et des colombes” par référence non pas à deux espèces animales (on parle bien de variablité intra-spécifique : au sein d’une même espèce) mais à la terminologie désignant au congrès des USA les députés belliqueux ou pacifistes. « Être agressif ou ne pas l’être » ? that is the question, here :) La coexistence de plusieurs comportements au sein d’une même espèce vivante est prédite par le fait qu’il y a plusieurs optima possibles quand on optimise son comportement.
Plus généralement, la théorie de l’évolution introduit aussi une source d’optimalité par le hasard. La reproduction de notre ADN via les ribosomes et l’ARN messager produit des erreurs de recopie. Ces erreurs donnent naissance à des individus “mutés”. La plupart d’entre eux sont non ou peu viables. Mais si une mutation aléatoire donne naissance à un animal mieux adapté (disons avec une meilleure efficacité reproductive) il peut être à l’origine d’un nouveau groupe d’animaux (une nouvelle espèce) qui va petit à petit envahir toute la “niche écologique”. La reproduction et ses mutations aléatoires se comporte donc comme un algorithme de recherche de la meilleure efficacité reproductive.
Récemment un des plus grands chercheurs en neuroscience (Karl Friston 2006) a pris le risque de proposer une explication “unifiée” du comportement d’un système biologique : assurer sa survie, en s’assurant que ses variables vitales restent dans des intervalles de valeurs “acceptables”. Mais comme un tel système ignore le fonctionnement de son environnement et ce qu’il peut y arriver, le système va alors se doter d’un modèle interne de son environnement et de lui-même. Il va activement inférer les paramètres de ce modèle, de façon à pouvoir optimiser ses perceptions et ses actions. Cette théorie prédit que minimiser la surprise par rapport à ce qui pourrait lui arriver (y compris en explorant pour mieux connaître cet environnement donc éviter les surprises futures) est le comportement optimal, compte-tenu de ce qui est observable. Depuis près de dix ans, cette théorie explique pas à pas les fonctionnalités de notre cerveau et notre survie.
Si Dieu, qu’Elle ou Il soit, nous prête vie :).