Couplage d’algorithmes d’optimisation par un système multi-agents pour l’exploration distribuée de simulateurs complexes

Couplage d’algorithmes d’optimisation par un système multi-agents pour l’exploration distribuée de simulateurs complexes

Systèmes complexes 

Nous sommes obligés d’admettre qu’il existe beaucoup de systèmes constitués d’un grand nombre d’éléments, organisés, faisant émerger des phénomènes inattendus qui ne sont pas la somme des caractéristiques et des dynamiques individuelles. On qualifie ces systèmes de «complexes». Les systèmes complexes se distinguent des «systèmes non complexes » par leur caractère naturellement non prédictible. Compte tenu du nombre d’interactions intrinsèques conduisant à l’émergence d’un comportement, seul le modèle et l’analyse de ce modèle (par le calcul mathématique ou la simulation) permettent d’élaborer des prédictions aidant à la décision. Les systèmes non complexes peuvent quand à eux être analysés sans nécessité l’utilisation d’un modèle. Il peut être utile de distinguer un système complexe d’un système compliqué avant de proposer une définition concise de la complexité. Pour cela, prenons l’exemple d’un avion de ligne et d’une colonie de fourmis, tous les deux sont des systèmes qui comportent des éléments. — Un avion est un système compliqué car un entraînement approfondi permet de faire voler un avion et de prédire toutes les conséquences d’un problème. — Une colonie de fourmis est quant-à elle un système complexe parce qu’il est impossible de prédire précisément ce qui se passe à l’intérieur d’une colonie. Les fourmis qui communiquent via des phéromones afin de se repérer et de transporter de la nourriture vers la fourmilière. Dans ce contexte seuls les modèles (tels qu’ils sont proposés dans les plates-formes comme Netlogo [Wil99] ou Gama [GTG+13]) et l’exécution de ces derniers (souvent par simulation) permettent de comprendre la dynamique du phénomène étudié et de l’anticiper. Il n’existe ni de définition concise d’un système complexe, ni de définition établie sur laquelle tous les scientifiques s’accordent. Les productions des réseaux pluridisciplinaires nationaux et internationaux tel que le RNSC (Réseau National des Systèmes Complexes) et le SCS (Society of complex system), les propositions de quelques chercheurs dans [Sim62, MdW04, Rou07, CBP+09] établissent une définition basée sur leur axe de recherche, tout en faisant un effort sur la généricité. Au début, les sciences de la complexité, [Sim62] et [MdW04] se sont principalement concentrées sur le caractère décomposable de la complexité pour la modélisation d’un système complexe. Plus tard, [Rou07] donne une définition dans le domaine du médical et la sécurité, domaines où la compétitivité industrielle est l’objectif principal tandis que [CBP+09] a mis son attention sur les disciplines scientifiques. Il donne une vision large de la complexité en abordant les thèmes de la physique théorique, des systèmes microbiens, des sciences de la vie, de l’écologie, de l’économie, de la sociologie et du management. [Rou07] considère dans son rapport avec l’Académie nationale de l’Ingénierie aux États-Unis que l’on a besoin d’une éducation plus large et plus flexible qui permet de comprendre la complexité des systèmes comme les services médicaux, l’infrastructure, l’environnement, la sécurité ou l’économie au sein desquels leurs technologies sont déployées. La capacité de comprendre et de traiter des systèmes complexes nécessite une considération de nombreux phénomènes qui ne sont pas intrinsèquement considérés comme des phénomènes d’ingénierie. Les communautés des sciences traditionnelles d’ingénierie trouvent qu’il est très difficile à adapter à ces nouveaux besoins éducatifs. Il donne la définition dans ce contexte : «A system whose perceived complicated behaviors can be attributed to one or more of the following characteristics : large numbers of elements, large numbers of relationships among elements, nonlinear and discontinuous relationships, and uncertain characteristics of elements and relationships. Complexity is perceived because apparent complexity can decrease with learning. » [Rou07]. C’est-à-dire Un système complexe est un système dont les comportements complexes perçues peuvent être attribués à une ou plusieurs des caractéristiques suivantes : un grand nombre d’éléments, un grand nombre de relations entre les éléments des relations non linéaires et discontinues, et les caractéristiques incertaines des éléments et des relations. La complexité est perçue à cause de la complexité apparente qui peut diminuer avec l’apprentissage. Dans le cadre de cette thèse, nous nous intéresserons principalement à la définition proposée par le RNSC dans le «French Complex Systems Roadmap» [CBP+09] : «A complex system is in general any system comprised of a great number of heterogeneous entities, among which local interactions create multiple levels of collective structure and organization ». C’est-à-dire les systèmes complexes sont composés d’un grand nombre d’entités hétérogènes interagissant localement et faisant émerger des niveaux multiples de structure et d’organisation. Cette définition indique qu’un grand nombre d’éléments constitutifs d’un système complexe en interaction empêchent l’observateur de prévoir son comportement ou son évolution et s’accorde sur le fait que la complexité d’un système ne se découpe pas, s’apprécie dans sa globalité. Plusieurs caractéristiques permettant de discerner les systèmes complexes ont été identifiées dans [Par11] : — Un système complexe comporte plusieurs composantes interdépendantes. Il est possible que les entités constitutives soient homogènes mais le plus souvent, elles sont hétérogènes avec une structure interne qui ne peut être négligée. — Il se caractérise par la nature des interactions. Ces interactions sont catégorisées en deux types : (1) les interactions entre les éléments constitutifs (le système) ; et les interactions entre le système et le reste du monde (l’environnement / l’extérieur). — Les dynamiques d’un système complexe appartiennent à l’ensemble du système entier sans appartenir à aucun des constituants. Les propriétés ou les comportements globaux d’un système ne peuvent pas être anticipées à partir des propriétés ou comportements des différentes parties. Il faut comprendre le système pour étudier les «phénomènes collectifs» ou de «propriétés émergentes». Ces caractéristiques donnent lieu à des phénomènes propres aux systèmes complexes. — Émergence multi-niveaux : une propriété émergente d’un système complexe est observée à une échelle différente de celles des éléments qui la construisent. Plus exactement, un phénomène émergent est observé à une échelle supérieure et ne peut pas être visualisé au niveau individuel [CGB+12]. Ces propriétés émergentes se produisent quand nous observons des phénomènes émergents globaux lors d’expérimentations ou de simulations informatiques à base d’agents. Dans le modèle de Schelling [Sch69] présenté dans [DL06], la ségrégation spatiale dans les zones résidentielles, lorsque les agents ne sont pas satisfaits avec leur position actuelle (ou voisinages), ils choisissent aléatoirement un nouveau lieu de résidence. De toute évidence, les véritables raisons d’un déménagement sont loin d’être aléatoire (proximité au travail, qualité de vie du quartier, etc). Pour contrôler la discrimination au niveau micro du modèle, on utilise le paramètre de pourcentage de la similarité souhaitée. On simule jusqu’à ce que tous les agents soient satisfaits et ensuite, on évalue le pourcentage de similarité. Par exemple, dans le modèle de ségrégation, les liens dynamiques entre le niveau micro et macro ne sont pas pris en compte. L’action d’un individu au comportement intégrateur dépend de l’action d’un autre individu de même comportement. La ségrégation observable à un niveau agréé est le résultat de processus interdépendants au niveau micro. — Multi-échelle et évolution : Il existe au moins de deux nivaux descriptifs : une locale et une globale. Cependant, des descriptions intermédiaires peuvent s’avérer nécessaires. Il faut considérer différentes échelles d’organisation que peuvent présenter les systèmes. Ce sont à la fois l’évolution des éléments au sein de chaque niveau, mais également les rapports qu’entretiennent les différents niveaux entre eux. L’émergence du système évolue à travers des niveaux et au cours du temps. Dans ces niveaux, les entités interagissent à l’échelle locale de temps et d’espace. Mais le point de vue va changer quand on observe le système entier au niveau global. Par exemple quand on veut modéliser un système complexe biologique, on peut considérer plusieurs niveaux d’échelle pour présenter le système, si on souhaite modéliser une cellule, il y a par exemple trois niveaux : le niveau des atomes, le niveau des molécules (ADN, protéines) et le niveau des organites. Dans ce cas, une question intéressante est posée : comment les molécules opèrent au sein du niveau cellule ou comment les cellules et les tissus échangent les informations ? — Sensibilité aux conditions initiales et dynamiques non-linéaires : On considère que dans un système complexe, de très petites différences dans les conditions initiales produisent des différences significatives aux niveaux des sorties quantitatives et qualitatives. L’émergence est conséquence de la dynamique non linéaire des interactions si bien que : (i) la sortie d’un système complexe n’est pas proportionnelle à son entrée ; (ii) et donc la dynamique observée n’est pas la simple somme des comportements locaux. Dans les systèmes complexes, la sensibilité aux conditions initiales ainsi que la dynamique non linéaire signifie qu’une petite perturbation peut provoquer un effet important. Par exemple dans le modèle de fourragement, les fourmis laissent des phéromones sur un trajectoire lorsqu’elles rapportent de la nourriture à la fourmilière pour aider les autres à trouver le chemin à la source de nourriture. Nombre de paramètres contrôlent le modèle tels que : vitesse des fourmis, taux d’évaporation des phéromones, taux de diffusion des phéromones. Un phénomène émergent visualisable est le comportement fourragement : une recherche aléatoire de nourriture ou une recherche via des files de fourmis. Les travaux de Calvez [CH06] montrent la sensibilité aux conditions initiales et dynamiques non-linéaires. Si le taux d’évaporation est trop fort, cela amène qu’il n’y a pas de phéromones laissées, les fourmis effectuent une recherche aléatoire. Si le taux d’évaporation est faible (proche de zero), les phéromones saturent tout l’environnement, on observe alors une recherche aléatoire des fourmis. C’est seulement quand l’évaporation est moyenne que des files de fourmis sont observables. Quand l’évaporation est moyenne, on peut s’intéresser plus précisément à l’influence du changement des valeurs de deux paramètres de la diffusion et de l’évaporation sur la dynamique des lignes de fourmis. Il y a trois modèles avec de petites modifications pour les deux paramètres : le nombre de files de fourmis change entre 1 file avec [diffusion :60, évaporation :20], 2 files avec [diffusion :50, évaporation :15] et 3 files avec [diffusion :40, évaporation :15]. Ces petites variations peuvent conduire à des dynamiques différentes dans l”exploitation des sources alimentaires. Nous avons présenté quelques définitions de systèmes complexes ainsi que certaines caractéristiques émergentes pour l’étude des systèmes complexes. Nos citations ne couvrent pas toutes les caractéristiques possibles d’un système complexe mais portent uniquement sur les critères qui nous intéressent. Dans la partie suivante, nous vous présentons les études dans le domaine de systèmes complexes. 

 Modélisation et simulation de systèmes complexes

 L’avènement des TIC connu ces 20 dernières années favorise aujourd’hui la conception, le développement et l’exécution de modèles et de méthodes statistiques et heuristiques d’exploration. Leur objectif est de reproduire, par simulation, un phénomène en vue de le comprendre et de prendre une décision dans les études prospectives. L’étude des systèmes complexes, avec les modèles de systèmes complexes et les moyens analytiques et numériques [TDZ08], vise précisément à comprendre et à prédire les comportements (niveau «macroscopique») sur plusieurs échelles d’espace et de temps, à partir des caractéristiques des éléments constitutifs (niveau «microscopique»). Modèles de systèmes complexes Dans le domaine des sciences sociales, l’étude des systèmes complexes requiert premièrement une source à représenter dont on souhaite reproduire une dynamique, des connaissances sur le système et un modèle qui reproduit la dynamique du système complexe. Un tel modèle, selon [Min65], «est une abstraction simplifiée, systémique et dynamique du domaine d’objet formalisée à l’aide d’un langage non ambigu, qui sert un but précis : un modèle existe pour fournir un outil pour répondre à certains buts, questions ou aspects particuliers du système que l’on cherche à étudier par l’observation et la manipulation du modèle ». Nous allons utiliser la notion de «modèle » pour simplifier la notion «modèle informatique dynamique » dans la suite du mémoire. Cela veut dire que dans ce mémoire de thèse, on n’aborde pas le modèle statique qui représente uniquement le système à un moment donné. D’autre part, ce mémoire n’aborde pas les modèles non-informatiques qui ne sont pas exécutables par simulation. Choix de la complexité d’un modèle La complexité n’est pas une qualité intrinsèque d’un système mais plutôt est une propriété attribuée au système via des modèles. Dans plusieurs cas, la complexité ne peut pas être prévue mais doit être analysée au cours des simulations. Elle se distingue donc de la complexité de l’algorithme qui correspond à une évaluation du nombre d’opérations effectuées par le calcul pour aboutir à un résultat et se distingue également d’autres types de complexité abordés dans la vision de (complexité mathématique, complexité de Von Neumann) [DBC+15]. Dans le cadre de cette thèse, visant à proposer des méthodes et outils adaptés pour explorer des modèles de systèmes complexes, nous adoptons un point de vue extérieur au modèle. Un modèle est une boîte noire que nous explorons. Dans ce contexte, la complexité peut être catégorisée en deux types [Mon08] : — La complexité des processus : Cette complexité permet de décrire et d’expliquer les évolutions du système. Celle-ci assure qu’on ne simplifie pas les caractéristiques qui peuvent être la clé d’une certaine propriété que l’on ne veut pas rater. Il faut prendre en compte différentes dynamiques : biologiques, écologiques, sociales, économiques. Cette complexité laisse à l’explorateur des contraintes d’analyse : nombres des paramètres qui sont difficiles à tracer. — La complexité des organisations : Cette complexité se situe au niveau de la représentation. La plupart des problèmes environnementaux et épidémiologiques veulent être proches de la réalité doivent être spatialisés (différentes échelles d’espace et de temps), multi-niveaux (différents intervenants, hybrides), différents points de vue (en vue individuelle ou collective des constituants). Cette complexité laisse à l’explorateur des contraintes de simulation : temps d’exécution et mémoire. Le choix de la complexité d’un modèle est important pour approcher virtuellement un phénomène réel et caractériser sa dynamique. En effet la définition du niveau d’abstraction et du niveau de détail est intimement lié à la question posée et aux enjeux scientifiques. Le niveau de la complexité d’un modèle du système dépend de la question posée. Mais elle est nécessaire pour éviter toute réticence, comparer les résultats avec les données de terrain et améliorer la confiance vis à vis des conclusions. Néanmoins, les modèles peuvent être compliqués, c’est-à-dire longs et difficiles à construire et leurs comportements aussi complexes que les phénomènes qu’ils sont censés représenter. [Aum07]. Cette partie vise à étudier les définitions d’un modèle de systèmes complexes. Il se caractérise par un système cible avec une question sur ce système. La réponse à cette question nécessite la construction d’un modèle (abstraction) de ce système. On essaie de construire la description abstraite, un modèle réduit à certains aspects, d’un système que l’on décrit pour rendre ce modèle plus facile à manipuler que le système source. Néanmoins, un modèle est relatif à un but précis dès le départ et est toujours imparfait, c’est pourquoi il faut explorer le modèle pour que : le modèle implémenté corresponde aux spécifications, corresponde aux attentes des utilisateurs et/ou aux propriétés attendues. L’exploration des modèles complexes est présentée dans la partie suivante. 

 Explorer des modèles par simulation 

La modélisation des systèmes complexes est souvent indissociable de l’exploration des modèles [AP06]. Il faut explorer des modèles pour (1) comprendre le système modélisé (élaboration d’hypothèses, simulation prospective, formalisation/vérification de théories sociologiques) ; et pour (2) décider (simulation prédictive pour l’aide à la décision, test de scénarios par la simulation et artefacts pour l’aide à la négociation ou gestion coordonnée). Traditionnellement, on utilise l’étude analytique des systèmes d’équations différentielles. Néanmoins, il n’y a pas toujours les compétences ou les outils mathématiques pour faire une exploration mathématique (analytique) à cause du (1) non-existence ou de la complexité des solutions analytiques (grande dimension des systèmes, non-existence de formulation analytique, le manque d’exactitude des règles de décision pour un modèle en réalité, la difficulté de résoudre analytiquement les équations associées), (2) la stochasticité des modèles et (3) l’inflexibilité au changement de variable d’état pour les propriétés émergentes. L’exploration analytique devient impossible. Explorer des modèles par simulation informatique est alors une solution raisonnable. La simulation informatique représente le système via les structures des entités et dépend de l’interconnexion entre eux en utilisant la théorie évolutionniste des jeux [LACJ03], la simulation cellular automata, la simulation Monte-Carlo, la simulation à base d’agents [Mat]. La technique s’intéresse plus à l’aptitude à apprendre et à créer un réseau complexe en interaction des acteurs constituant un système plutôt qu’à la complexité relative des systèmes et de leurs éléments. Explorer des modèles par simulation est très nouveau mais plus utilisé depuis peu de temps pour l’étude de systèmes complexes dans la science sociologique (socio-environnementale, socio-écologique, sécurité environnementale) où nombreux agents très hétérogènes interagissent, s’auto-organisent, et génèrent des propriétés émergentes du système dans un environnement physique. En outre, l’environnement physique (le territoire) des modèles géographiques dynamiques est un acteur très influencé dans un modèle. Cette méthode permet récemment de considérer l’environnement physique comme un système complexe [Moi06] et de l’intégrer dans le modèle à partir des données de terrain comme un système informatique géographique (SIG). Cependant, cette technique a ses limites : (i) sur la réalisation : il est très difficile, voire impossible, de résoudre un système analytiquement (spécialement avec un système multi-agent) et (ii) sur l’utilisation : la demande de ressources de calcul coûteuse, la limite de multi-utilisation et la demande de validité avec les données réelles. Dans ce cas, on considère le modèle comme une boîte noire, il faut avoir une approche raisonnée pour explorer des systèmes complexes par simulation : approche non exhaustive, approche statistique, théorie des plans d’expériences ou méthode indépendante au modèle. Vers un cycle de modélisation par simulation des systèmes complexes La simulation informatique interactive, surtout la simulation à base d’agents, est l’une des techniques des plus évoluées pour étudier des systèmes complexes et pour calculer les résultats face à des changements dans les paramètres [Joh08]. Un premier courant distingue l’étude de systèmes complexes par deux processus différents pour l’étude d’un système complexe : la « modélisation » et la « simulation. Tandis que la modélisation est un processus visant à concevoir des modèles par l’usage de méta-modèles, la simulation est un processus visant à animer ces modèles par l’usage d’un programme informatique, d’un simulateur ou d’une plate-forme telle que GAMA, Netlogo, Repast. Il s’agit, alors de manipuler le modèle via ses paramètres pour comprendre le comportement du système, appréhender ses caractéristiques dynamiques ou évaluer différentes décisions [Hil93]. Mais, selon [Fis95], la modélisation et la simulation sont indissociables dans un cycle de modélisation par simulation (figure 1.1). La figure 1.2 est une analyse des processus de modélisation par simulation de la littérature afin de mettre avant le processus d’exploration pour le clarifier. Fishwick s’appuie sur trois étapes : l’élaboration de la simulation, l’exécution du modèle sur ordinateur et l’analyse des résultats obtenus. Cette méthode générique a été source d’inspiration pour de nombreux travaux dont [DVM03], [TCM+06], [Aum07] ou [Mor09]. Celles-ci sont d’accord que la modélisation par simulation de systèmes complexes est un processus cyclique : le modèle est progressivement amélioré en introduisant des nouvelles connaissances et en corrigeant les effets indésirables. Toutes ces approches établissent un déroulé du processus adapté à leur domaine d’application. Elles respectent néanmoins l’idée originelle de [Fis95] : Figure 1.1 – Le processus de modélisation de [Fis95] — Élaboration de la simulation : Cette première étape vise à élaborer et à créer une première abstraction du problème à partir des connaissances de la littérature, d’expertises, de données observées du système et des questions posées. L’objectif de cette étape est d’appliquer des méthodes et outils de modélisation pour caractériser à la fois la structure du système complexe et sa dynamique. Ainsi que la programmation est réalisée. Le résultat de cette étape est un modèle A et des scénarios d’utilisation B. Le modèle A repose sur des algorithmes qui réalisent le calcul de la simulation avec les données de l’état courant d’une simulation pendant que le scénario d’utilisation de B est déterminé par les paramètres qui indiquent l’état initial de la simulation. [Rio09]. — Exécution de la simulation : Cette deuxième étape vise à réaliser des simulations en tenant compte des scénarios précédemment choisis pour reproduire la dynamique du système réel. Pour cela, on a besoin de l’outil exécutable appelé simulateur. Le simulateur est une transformation de la spécification du modèle en une suite d’instructions exécutables par un ordinateur. Il correspond donc à l’implémentation du modèle [TDZ08]. C’est un code de calcul constitué (figure 1.3) de : (1) modèles élaborés ; (2) des variables d’entrée descriptives de l’état du système simulé selon un scénario ; et (3) les observables. Les variables d’entrée définissent : (i) les conditions initiales du système (paramètres caractérisants) ; (ii) certaines lois ou relations utilisées (contraintes) ; et (iii) tout ce qui influe sur le comportement du modèle. Les observables sont : les variables, les attributs souhaités au cours de la simulation ou des variables agrégées, les indicateurs, construits à partir de la simulation [DBQ12] désirés dans la modélisation. Ainsi, le simulateur peut être vu comme une boîte noire en prennant des paramètres en entrée et délivrant en sortie les réponses sur les variables d’état du système en fonction du temps. Alors, une simulation consiste à fixer un ou plusieurs jeux de variables d’entrée, réaliser les calcul, puis à analyser les réponses fournies par le simulateur [Ngu13]. La simulation permet une exploration des comportements possibles du système au travers des scénarios qui permettent de tester l’influence de configurations initiales multiples et cela dans un temps limité. — Analyse des données de la simulation : cette troisième étape vise à analyser les données obtenues. Cette étape est constituée par la vérification, la validation et la critique [Aum07]. Plusieurs méthodes dans les sciences expérimentales sont utilisées pour réaliser cette phase telles que l’analyse analytique, statistique ou heuristique. Dans ce domaine, une expérience de simulation est définie comme une simulation dans la deuxième étape. Dans cette étude, les observations réalisées au cours de l’expérimentation sont alors rapprochées des hypothèses conceptuelles ou comparées à des données empiriques collectées sur le phénomène.