Sites Inria

English version

Mathématiques appliquées, calcul et simulation

7/05/2007

A(rt)lgorithme, design sous influence mathématique

Le Centre Pompidou à Paris offre en ce moment au regard de l’amateur comme à celui du curieux une nouvelle présentation de la collection du musée d’art moderne. Ce voyage artistique inclut une ouverture sur la jeune génération internationale d’architectes et de designers, parmi lesquels s’expose l’agence EZCT Architecture & Design Research et ses créations de chaises, fabriquées à partir d’algorithmes évolutionnaires conçus par des chercheurs d'Inria.

La rencontre de deux univers

À l’origine de cette convergence inédite de l'art et des mathématiques, l’initiative de l’agence EZCT de questionner la relation entre calcul et architecture. Dans sa recherche architecturale EZCT aborde l’imbrication actuelle des sciences et des technologies, grâce à l’association de théoriciens et universitaires provenant de divers champs disciplinaires. Intéressé de longue date par l’optimisation de structure, cette proposition innovante a séduit Marc Schoenauer, directeur de recherche Inria et responsable de l'équipe-projet Tao. Leur collaboration a reposé sur l’idée originale de confronter algorithmes évolutionnaires et problèmes architecturaux, à partir d’un cas typique de problématique en architecture : la conception d’une chaise. Marc Schoenauer et un de ses anciens doctorants Hatem Hamda se sont ainsi attachés à faire évoluer des chaises : minimiser leurs poids sous des contraintes de résistance à une ou plusieurs charge (un humain assis dessus, etc.). Derrière cette expérimentation, se trouvent les algorithmes évolutionnaires.

Des algorithmes (r)évolutionnaires

Selon Charles Darwin (1809 -1882), l'évolution des espèces naturelles est gouvernée par la conjonction de deux mécanismes principaux : les variations dites « aveugles » qui se produisent dans les caractéristiques génétiques lors de la transmission des parents aux enfants, et la sélection naturelle, qui tend à préserver les individus qui, du fait de variations chanceuses, sont les plus adaptés à leur environnement. C'est ce mécanisme très simplifié que tentent d'implanter sur ordinateur les algorithmes évolutionnaires, dont les plus connus sont les algorithmes génétiques.
Pour résoudre un problème donné, on fait évoluer artificiellement une population d'individus en modifiant leurs caractéristiques aléatoirement d'une génération à l'autre, et en sélectionnant ceux qui répondent le mieux à la question posée. Ainsi, pour concevoir des formes de chaises (qui résistent lorsque l'on s'assied dessus !), on va créer au sein de l'ordinateur une population de chaises, que l'on va croiser et faire muter au hasard, en gardant préférentiellement les chaises les plus résistantes à une manière de s'asseoir donnée.
Les deux questions importantes sont alors :

  • Comment juger de la qualité d'une chaise , ou, plus simplement, comment comparer deux structures à vocation de chaises pour savoir laquelle a le plus de chance de donner naissance à de beaux rejetons, qui, eux, seront peut-être de vraies chaises.
  • Comment représenter en machine des structures , de telle sorte que d'une part la représentation choisie permette de représenter de vraies chaises, et que, d'autre part, la manipulation aléatoire de ces représentations par croisements et mutations permette d'explorer le plus efficacement possible un ensemble de structures le plus vaste possible afin d'y dénicher les plus intéressantes d'un point de vue architectural.

Critères de sélection de chaises

La première question a reçu ici une réponse basée d'une part sur le poids de la chaise (la plus légère possible), mais dans les limites de la résistance à des charges de personnes assises - cette résistance étant calculée sur ordinateur par la méthode dite des éléments finis, très utilisés dans l'industrie (aéronautiques, automobiles...). Le concepteur imagine des situations dans lesquelles quelqu'un est assis sur la chaise, appuyant en divers endroits de la structure avec diverses forces, ainsi que les déformations de la chaises maximales autorisées. L'adaptation d'une structure est alors donnée par le poids de la chaise, auquel on ajoute des pénalités en cas de dépassement des limites de déformation autorisées.
À noter que dans les expériences présentées ici, les chargements appliqués sont tous statiques, c'est à dire qu'on ne considère pas le cas d'une personne s'asseyant violemment sur la chaise, mais uniquement le moment où elle est de fait assise. Pour plus de réalisme, il faudrait faire un calcul en dynamique - ce qui ne présente pas de difficulté conceptuelle, en revanche cela augmente considérablement les temps de calcul.

Comment représenter des (futures) chaises ?

Il s'agit de trouver une manière de représenter dans l'ordinateur d'une manière la plus générale possible, et avec l'idée de les faire évoluer "génétiquement", des structures matérielles, constituées ici, pour simplifier, d'un matériau unique. Nous allons supposer également que ces structures doivent rester confinées dans un domaine prédéfini. Plutôt que tenter de représenter chacun des petits éléments de l'espace qui seront utilisés pour calculer l'adaptation des structures-chaises, il est plus efficace d'utiliser une représentation de plus haut niveau, basée ici sur la notion de diagrammes de Voronoï.
Imaginez un ensemble de ballons de baudruche, dont le centre est fixé, et qui vont le gonfler jusqu'à rencontrer soit d'autres ballons, soit la limite du domaine autorisé : cela donne un découpage dudit domaine en polygones convexes (voir figure 1-gauche). Si maintenant certains des ballons sont remplis de matière, et que les autres restent vides, l'ensemble de la matière constitue une structure incluse dans le domaine autorisé, c'est-à-dire une chaise possible.
D'une manière plus mathématique, un diagramme de Voronoï est un ensemble de points du domaine de définition, appelés sites de Voronoï. À chaque site est attachée une cellule de Voronoï, ensemble des points du domaine dont le site le plus proche est celui-ci. L'ensemble des cellules constitue une partition du domaine en polygones convexes. Au niveau informatique, maintenant, le génome de chaque individu-chaise est constitué uniquement de l'ensemble des sites de Voronoï avec, pour chaque site, le fait de savoir si la cellule correspondante est vide ou pleine. Il est alors facile d'imaginer des opérateurs de variation darwiniens pour ces individus :

  • deux structures parents vont se recombiner en échangeant des sites (figures). Après séparation en deux parties du domaine de définition, les sites situés d'un côté de la séparation sont échangés entre les deux structures, et bien sûr chaque structure est ensuite reconstituée à partir du nouvel ensemble des sites. L'idée sous-jacente est bien de recombiner des bonnes parties de structure, par exemple le dossier de l'une, qui avait été sélectionné justement parce que son dossier lui donnait un avantage sur ses congénères, avec le siège de l'autre, dont le siège constituait l'atout le plus avantageux. L'idée de base étant d'avoir une probabilité non nulle d'obtenir une chaise-enfant plus performante que chacune de ses deux chaises-parents.

  • chaque structure subit également, avec une petite probabilité, des mutations, qui consistent soit en une modification des positions des sites de Voronoï existants (voir figure 3), soit en un ajout de nouveaux sites tirés au hasard, ou une suppression de sites existants. Ces mutations sont la plupart du temps très légères, mais peuvent de temps en temps modifier largement la structure (par exemple les distances de déplacements des sites sont tirées suivant une loi Gaussienne)

Mais où est passé l'architecte ?

La méthode proposée ne se veut pas (encore ?) une alternative à la chaîne de conception complète de structures, mais plutôt un outil à visée exploratoire permettant au concepteur de mettre au point des idées de conceptions nouvelles qu'il n'aurait sans doute pas imaginées ex abrupto pour remplir les conditions du cahier des charges initial. Le caractère aléatoire de l'algorithme permet d'ailleurs de trouver de nombreuses solutions différentes à un même problème, accentuant le caractère créatif du processus.
Mais au final, le résultat dépendra uniquement des savoir-faire de l'ingénieur informaticien et de l'architecte (qui, idéalement, sont une seule et même personne !), dans leurs choix de conception de l'algorithme, depuis la représentation et les opérateurs de variation jusqu'à la définition de ce qui sera l'adaptation des structures, via les simulations appropriées (choix du domaine, des parties fixes sur lesquelles seront appliquées les forces, puis des forces elles-mêmes). Les résultats de ces algorithmes peuvent alors constituer une source d'inspiration exceptionnelle pour le concepteur, lui fournissant un ensemble de points de départ possibles pour ses propres recherches.

Mots-clés : Saclay - Île-de-France Marc Schoenauer Algorithmes Design

Haut de page

Suivez Inria