Soutenance mémoire
Les automates cellulaires
Contrairement aux équations différentielles, les automates cellulaires modélisent le domaine étudié de manière discrète. Ils sont ainsi définis par une grille régulière contenant des cellules, chacune possédant un état distinct synthétisant l’état de cette portion d’espace. Ce dernier appartient à un ensemble fini d’états prédéterminés lors de l’élaboration du modèle. Cependant, il en existe des variantes continues, équivalentes à des systèmes différentiels discrétisés dans le temps et dans l’espace [Lenuzza, 2009]. L’évolution de l’état de chacune des cellules au cours du temps est déterminée par un ensemble de règles prédéfinies le liant à l’état des cellules voisines. La simulation d’un automate cellulaire consiste à appliquer ces règles d’évolution de manière répétée sur l’ensemble de ses cellules. Un pas de simulation est terminé lorsque ces règles ont été appliquées successivement à chacune des cellules. Classiquement, les états de toutes les cases sont modifiés simultanément : la totalité de la grille est mise à jour de manière synchrone. Néanmoins, certains travaux proposent des automates cellulaires asynchrones où les cellules évoluent tour à tour plutôt que simultanément [Schönfisch et de Roos, 1999]. L’invention des automates cellulaires est accordée à John von Neumann (ainsi qu’à Arthur Walter Burks qui compléta son travail) qui étudiait les systèmes capables de s’auto-répliquer [Von Neumann et Burks, 1966]. Il mit ainsi au point un automate cellulaire possédant 29 états et une règle de transition prenant la forme d’une machine à états finis. Cette règle permettait à une cellule de changer d’état en fonction d’un voisinage de von Neumann, c’est-à-dire de son état actuel et de celui de ses quatre voisines (verticalement et horizontalement). Il montra finalement qu’une certaine configuration de son automate parvenait à se répliquer. L’exemple le plus célèbre d’automate cellulaire est celui du « jeu de la vie » développé par John Conway dont une explication détaillée est proposée dans [Gardner, 1970]. Il consiste en une grille en deux dimensions composée de cellules à deux états (vivante et morte). L’évolution de l’état d’une cellule est déterminée en fonction de son voisinage de Moore, c’est-à-dire par son état propre ainsi que celui de ses huit autres voisines. Les règles pilotant cette évolution sont au nombre de deux et contrôlent la naissance (une cellule morte naît si elle possède trois voisines vivantes) ou la mort d’une cellule (une cellule vivante meurt si elle ne possède ni deux ni trois voisines vivantes). Malgré des règles extrêmement simples uniquement basées sur le nombre de cellules vivantes adjacentes, le « jeu de la vie » est capable de faire apparaître des comportements complexes. La complexité de ces comportements est responsable de son succès au travers de différentes communautés scientifiques. Cet exemple est principalement utilisé à des fins pédagogiques afin de montrer qu’une certaine auto-organisation peut « émerger » d’un système autonome muni de règles extrêmement basiques. Une illustration de cet automate cellulaire est présentée sur la figure 1.1. Le « jeu de la vie » est le parent de différentes simulations à base d’automates cellulaires en biologie. Par exemple, les travaux présentés dans [Kaufman et al., 1985] proposent d’appliquer un automate booléen à l’immunologie, alors que dans [Alarcón et al., 2003], un automate cellulaire est utilisé pour modéliser la croissance d’une tumeur. Le lecteur intéressé peut trouver de nombreux autres exemples d’applications biologiques dans [Ermentrout et Edelstein-Keshet, 1993].
Les systèmes multi-agents
Les systèmes multi-agents sont composés d’individus autonomes (les agents) évoluant au sein d’un environnement qu’ils perçoivent localement. Comme le mentionne Michael Wooldridge dans [Wooldridge, 2009], il n’existe pas de définition universelle des systèmes multi-agents. L’élaboration de cette définition est même particulièrement sujette à débat et controverse en raison de l’origine interdisciplinaire des systèmes multi-agents. En effet, ces derniers sont le résultat de recherches réalisées dans des domaines variés tels que l’intelligence artificielle (autonomie des individus), les systèmes distribués (concurrence entre les individus) ou encore les sciences humaines (sociétés d’individus). Or, ces communautés scientifiques ne définissent pas les systèmes multi-agents de manière identique. Malgré cela, les différents acteurs de ces communautés s’accordent sur l’importance de l’autonomie des agents au sein du système [Tisseau, 2001]. Michael Wooldridge propose ainsi de définir un agent de la manière suivante : « Un agent est un programme informatique situé dans un environnement et capable d’effectuer des actions de manière autonome au sein de cet environnement afin d’atteindre les objectifs pour lesquels il a été conçu . » Nous adhérons à cette définition et définissons les modélisations multi-agents par l’intermédiaire des caractéristiques suivantes :
• l’autonomie : chaque agent est indépendant et capable de prendre des décisions en fonction des éléments (agents voisins ou environnement) qu’il perçoit ;
• la perception locale : un agent ne perçoit qu’une portion de l’environnement et des agents qui l’entourent ;
• la décentralisation : aucun mécanisme ne contrôle la simulation à l’échelle globale.
La simulation de tels systèmes est obtenue en faisant « vivre » ces agents, c’est-à-dire en exécutant le programme informatique définissant leur comportement, tour à tour à chaque cycle de simulation. À l’instar des méthodes à base d’équations différentielles et des automates cellulaires, les systèmes multi-agents comptent de nombreuses applications liées à la biologie [Merelli et al., 2007; An et al., 2009]. Nous retrouvons des exemples récurrents tels que l’étude de la cinétique biochimique [Andrews et al., 2009] ou encore celle de la croissance de tumeurs [Byrne et Drasdo, 2009]. À cela s’ajoutent des travaux appliqués au domaine de la biologie animale comme par exemple l’étude du phytoplancton dans les océans [Hellweger et Bucci, 2009] ou l’étude classique de la collecte de nourriture au sein d’une colonie de fourmis [Nugala et al., 1998]. Habituellement, un agent représente un individu de la population modélisée. Cependant, certains travaux tels que [Querrec, 2005] et [Desmeulles, 2006] proposent un modèle de système multi-agents particulier et original en réifiant les interactions des systèmes biologiques. Cela signifie que les auteurs individualisent les interactions liant les individus de la population, plutôt que les individus eux-mêmes. Ainsi, contrairement à une système multiagents classique dont la simulation est obtenue en faisant « vivre » tour à tour chacun des individus de la population, ces travaux proposent de faire « vivre » les interactions. Nous notons que la littérature fait état de deux types d’agent : les agents cognitifs (ou intelligents), c’est-à-dire dotés de capacités de raisonnement, et les agents réactifs, c’est-à-dire obéissant à un schéma réflexe stimulus → réponse [Wooldridge, 2009]. Lors de la simulation de systèmes biologiques, la majorité des agents utilisés sont réactifs. En effet, hormis dans certaines situations (notamment l’étude d’animaux dotés de facultés cognitives) la plupart des entités biologiques (cellules, molécules, animaux primitifs) sont dépourvues de capacités cognitives évoluées et se contentent d’effectuer une action lorsqu’une situation particulière survient (interaction avec un autre agent, variation de l’état de l’environnement. . .). En outre, face aux différentes connotations qui peuvent être données aux termes « agent » et « système multi-agents » en fonction des domaines étudiés, nous privilégions l’utilisation des termes « individu » et « système individu-centré » dans le contexte de ce mémoire.
Bilan des approches individu-centrées
En proposant des modélisations à un niveau de détail nettement plus élevé que leurs homologues population-centrés, les approches individu-centrées permettent de tenir compte efficacement de l’hétérogénéité des populations. Cela est dû au fait que le comportement de chaque individu appartenant à la population étudiée est modélisé individuellement. Néanmoins, en raison de cette capacité intrinsèque à modéliser chaque élément du système biologique individuellement, les approches individu centrées peuvent être extrêmement coûteuses en temps de calcul. En effet, pour obtenir des résultats significatifs, il est souvent nécessaire de simuler un nombre considérable d’individus (de quelques milliers à plusieurs millions) et parfois, sur une très longue durée. En outre, malgré leur simplicité apparente, lorsque les comportements des individus sont évolués, les modèles individu-centrés peuvent très rapidement devenir compliqués et beaucoup plus difficiles à maintenir qu’un modèle à base d’équations différentielles.Dans cet état de l’art des approches individu-centrées, nous ne considérons volontairement pas l’approche dite de microsimulation, dont la paternité est généralement accordée à [Orcutt, 1957], qui, bien qu’étant une approche individu-centrée très utilisée (notamment dans les domaines des sciences sociales et de l’économie), est inadéquate pour modéliser la biologie. En effet, la microsimulation consiste à prédire l’évolution d’individus en fonction de larges bases de données et de règles statistiques définissant les préférences et affinités des individus et ne permet clairement pas de modéliser les interactions liant ces individus au sein des systèmes biologiques. L’étude des approches population et individu-centrées que nous avons proposée nous permet de mettre en évidence leurs principaux avantages et inconvénients lors de la modélisation et simulation de systèmes biologiques. Afin d’obtenir des simulations qui partagent les atouts et s’affranchissent des défauts de ces deux types d’approche, un troisième a vu le jour : il s’agit des approches que nous qualifions de mixtes.
Exemples basés sur une approche population-centrée
Les travaux [dos Santos et al., 2004] présentent un modèle déterministe mêlant EDPs et EDOs pour étudier l’activité électrique au sein des tissus cardiaques. En raison de la charge de calcul qu’entraîne la résolution des équations composant le modèle, les auteurs proposent de distribuer les différents traitements grâce à un cluster de 16 nœuds munis chacun d’un processeur mono-cœur afin d’optimiser les performances de leur simulation. La communication entre les nœuds composant le cluster est assurée grâce au standard MPI présenté brièvement précédemment. Leur implémentation consiste à découper l’ensemble du domaine étudié et à le répartir entre les processeurs. Les auteurs proposent des algorithmes de résolution numérique spécifiques afin de minimiser les communications superflues entre chacun des nœuds du cluster. Ils observent que plus le ratio entre temps de calcul et temps de communication est élevé, plus l’approche distribuée apporte un gain de performance important. Pour réduire significativement les temps de communication, les auteurs envisagent d’utiliser un réseau plus rapide. D’autres travaux utilisent des modèles stochastiques à base d’EDOs probabilistes afin de modéliser les réactions chimiques intervenant lors de la transcription de gènes [Burrage et al., 2003]. Les simulations basées sur des modélisations stochastiques nécessitent, de par leur caractère aléatoire, d’être répétées un très grand nombre de fois afin de pouvoir calculer des données statistiques (moyenne, variance. . .) sur les solutions obtenues. Pour cela, les auteurs de ces travaux utilisent une architecture distribuée afin de répartir toutes ces répétitions indépendantes entre différentes machines appartenant à une grille de calcul. Les simulations sont attribuées aux machines clientes par l’intermédiaire d’un serveur centralisant les résultats. Grâce à l’indépendance des répétitions, les performances offertes par cette application distribuée sont très intéressantes. Le peu d’échanges entre les unités de calcul permet de maximiser le ratio entre temps de calcul et temps de communication.
|
Table des matières
Introduction
1 Simulation parallélisée des systèmes biologiques
1.1 Modélisation et simulation des systèmes biologiques
1.1.1 Approches population-centrées
1.1.2 Approches individu-centrées
1.1.3 Approches mixtes
1.2 Solutions de parallélisation et de distribution
1.2.1 Architectures multicœur et multiprocesseur
1.2.2 Architectures graphiques
1.2.3 Architectures distribuées
1.3 Bilan de notre étude
1.3.1 Intérêt d’une approche mixte
1.3.2 Intérêt de la parallélisation face à la distribution
1.3.3 Parallélisation d’approches mixtes
2 Modélisation et parallélisation mixtes
2.1 Modèle individu-centré asynchrone
2.1.1 Description de nos entités autonomes
2.1.2 Schéma d’ordonnancement
2.1.3 Ordonnancement parallèle
2.1.4 Bilan de notre modèle individu-centré
2.2 Modèles population-centrés synchrones
2.2.1 Maillage de l’espace
2.2.2 Méthodes de parallélisation
2.2.3 Bilan de nos modèles population-centrés
2.3 Couplage de modèles population et individu-centrés
2.3.1 Déroulement d’une simulation
2.3.2 Interaction entre les modèles
2.4 Bilan de notre proposition
3 Exemples d’application à la coagulation du sang
3.1 Cinétique biochimique à l’échelle microscopique
3.1.1 La cinétique biochimique
3.1.2 Modélisation individu-centrée de la cinétique biochimique
3.1.3 Validation et résultats
3.1.4 Discussion et perspectives
3.2 Vaisseau sanguin virtuel
3.2.1 Notions élémentaires d’hématologie
3.2.2 Modélisation mixte d’un vaisseau sanguin
3.2.3 Évaluation des performances
3.2.4 Potentiel applicatif
3.2.5 Discussion et perspectives
3.3 Bilan de nos exemples d’application
Conclusion
Télécharger le rapport complet
