REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE UNIVERSITE MOHAMED BOUDIAF - M’SILA FACULTE DE MATHEMATIQUES ET D ’INFORMATIQUE DEPARTEMENT D’INFORMATIQUE MEMOIRE de fin d’études Présenté pour l’obtention du diplôme de MASTER Domaine : Mathématiques et Informatique Filière : Informatique Spécialité : Informatique Décisionnelle et Optimisation Par : Mlle KADRI Yassamine THEME Soutenu publiquement le : ……………… devant le jury composé de : Pr. AKHROUF Samir UMB M’sila Président Pr. HERAGUEMI Kamel-Eddine UMB M’sila Examinateur Dr. HEMMAK Allaoua UMB M’sila Rapporteur Promotion : 2021/2022 Modélisation de l’évolution urbaine par automate cellulaire Cas d’application : ville de M’sila I Remerciements Je présente mes sincères remerciements pour mon encadreur, Mr HEMMAK Allaoua pour son aide et ses conseils tout au long de ma mémoire. De façon plus générale, je remercie toutes les personnes qui ont contribué de près ou de loin dans ce modeste travaille. Dedicace Je dédie ce travail à Mes parents , A mes frères et mes sœurs , A mes amies. A tous mes professeurs, À moi, de moi. Enfin! II Tables des matières Introduction générale…………………………………………………………01 Chapitre I : Evolution Urbaine 1. Introduction …………………………………………….........................05 2. Evolution urbaine………………………………………………………..05 3. Mode d’urbanisation…….....………………………………………...….07 4. Géo simulation urbaine………...…………………..……………………08 5. Urbanisation et développement durable…………….…………………...09 6. Urbanisation dans le monde…………………………………………..…09 7. Modélisation du système urbain…………………………………………10 8. Conclusion………………………………………………….……………11 Chapitre II : Automates cellulaires 1. Introduction…………………………………………………..………….12 2. Les Automates cellulaires………………………....………………….…13 3. Définition…………………………………………………………..……17 4. Définition 1……………………………………………………..……….20 5. Définition 2……………………………………………………...………20 6. Origines et développement……………………………………..……….21 7. Caractéristiques…………………………………………………………22 8. Propriétés…………………………………………………………….…26 9. Terminologie……………………………………………………………29 10. Le jeu de la vie…………………………………………………….……30 11. Classification de WOLFRAME…………………………………..….…34 12. Les Automates cellulaires……………………………………………….36 13. Domaine d’application……………………………………………..……38 14. Conclusion…………………………………………………………....…40 Chapitre III : La modélisation par automates cellulaires 1. Introduction………………………………………………………….…40 2. Etat de l’art :............................................................................................40 3. La modalisation…………………………………………………………45 4. Modalisation par Automates cellulaires………………………………46 5. Utilisations des Automates cellulaires en modalisation………………48 6. Création des automates cellulaires…………………………...……….…48 III 7. Différentes variantes d’automates cellulaires…………………………50 8. Structure de l’automates……………………………………………….53 9. Conclusion…………………………………………………………..…57 Chapitre IV : Simulation urbaine de la ville M’sila par l’AC 1. Introduction……………………………………………………….……57 2. Problématique………………………………………………………….58 3. Contexte………………………………………………………….…….58 4. Présentation de la ville du M’sila………………………………………59 5. Analyse de l’évolution de l’espace de la ville M’sila…………………60 6. Secteurs de la ville de M'sila……………………………………………64 7. Résultats du l’analyse de la ville M’sila…………………………..……66 8. Conduit à tenir……………………………………………………….….66 9. Conclusion………………………………………………………………68 Chapitre IIV : Implémentation et résultats 1. Introduction……………………………………………………………69 2. Langage de programmation et environnement de développement..…69 3. Description de logiciel……………………………………………….…71 4. Conclusion……………………………………………………..………73 conclusion générale……………………………………………….…………75 Résumé IV Liste des Figures Figure I.1 : Modélisation du système urbain………………………….09 Figure II.1 : Voisinages de Moore (a) et de Von Neumann (b) …......16 Figure II.2 : Règle de mise à jour d’ AC………………………………19 Figure II.3 : Composants d’un automate cellulaire………………….. 19 Figure II.4 : voisinage de Von Neuman et de Moore………………….22 Figure II.5 : voisinage de Moore etendu et de Margolus……………. 22 Figure II.6 : variation de voisinage de Von Neuman…………………. 23 Figure II.7 : voisinage des cellules de bord………………...……….. 23 Figure II.8 : propriété de reproduction……………………………….. 26 Figure II.9 : l’automate déplacement Est………………………………27 Figure II.10: automate de type jeu de la vie…………………………...27 Figure II.11 : règle de survie dans jeu de la vie………………………..28 Figure II.12 : règle de mort dans jeu de la vie……………………...….29 Figure II.13 : règle de naissance dans jeu de la vie……………………29 Figure II.14 : jeu de vie………………………………………………..30 Figure II.15 : exemple de jeu de la vie…………………………………32 Figure II.16 : exemple de jeu de la vie…………………………...…….32 Figure II.17 : les 256 automates de Wolframe …………………….…..34 Figure II.18 : automate cellulaire……………………………………....36 Figure III.1 : Schéma méthodologique général de modélisation et de simulation [Schmidt et Pavé, 2002…………………………………...…45 Figure III.2 : Différentes dimensions d'un automate cellulaire……..…50 Figure III.3 : Tessellations du cas bidimensionnel : (A) grille carrée; (B) grille triangulaire et (C) grille hexagonale……………………….……..50 Figure III.4 : Tessellation tridimensionnelle cubique…………………50 Figure III.5: (A) Voisinages de Von Neumann; (B) de Moore; (C) de Von Neumann étendu et (D) de Moore étendu……………………..…..51 Figure III.6 : Voisinage pour une tessellation hexagonale........……….51 Figure III.7: Composantes typologiques des automates cellulaires……52 Figure IV.1 : Localisation de la région d'étude Carte d'occupation des sols de la wilaya de M'sila……………………………………………...59 Figure IV.2: Les quartiers et places publiques de la ville de M’sila pendant la période coloniale (1950)…………………………………...60 Figure IV.3 : La première installation urbaine coloniale aux abords du quartier d’El Argoub aux alentours de 1895………………………..…..60 Figure IV.4: Évolution spatiale de la ville de M’sila…………………61 Figure IV.5: Étalement urbain de la ville de M'sila…………………..62 Figure IV.6: Évolution de la population, urbanisation et ratio des espaces verts urbains de la ville de M'sila……………………………………….63 Figure IV.7: Evolution spatiale de la ville de M’sila………………….64 Figure V.1: Interface Principal…………………………………………71 V Figure V.2. Apporter le fichier texte………………………..……..…71 Figure V.3.Affichage de la matrice sur text area…………….………...71 Figure V.4.Présentation de l’Automates Cellulaires………….………..72 Figure V.5. L’Apprentissage…………………………………….……..72 Figure V.6 : Exemple de Apporter le ficher texte……………………73 Figure V.7 :Affichage de la matrice d’état de la ville M’sila en 2013…73 Figure V.8: l’Automate Cellulaire qui représente l’état de l’année 2013………………………………………………………………………74 Figure V.9 : Apprentissage de l’état d’automates cellulaires d’année 2013…………………………………………………………………….…74 Figure V.10 : Résultat de la Prédiction………………………………….75 Introduction générale INTRODUCTION GENERALE 1 Introduction générale De notre temps, sans l’avancement théorique, méthodologique et technique une bonne compréhension du monde et de ses changements ne peut avoir lieu qui décode les dynamiques complexes des systèmes humains et environnementaux. Ces systèmes peuvent être représentés en tant que processus évoluant dans l’espace et dans le temps. Pour une meilleure représentation de ces processus, il est nécessaire de considérer leurs caractéristiques spécifiques telles que la dimension du phénomène, son étendue spatiale, sa continuité, sa dynamique, sa fréquence dans le temps et ses différentes échelles spatiales et temporelles. La prise en compte de tous ces critères exige des outils appropriés permettant d’abord de mieux comprendre le comportement de tels processus et ensuite de simuler les différents scénarios possibles et d’en anticiper les conséquences, afin d’aider les gestionnaires à prendre des décisions éclairées. C’est ainsi que la représentation, la de modélisation et la simulation des processus spatiotemporels constituent des outils d’aide à la décision dans un sens de gestion du territoire, de protection de l’environnement et de développement durable. Cette étude joue en outre à la fois le rôle de trait d'union entre les disciplines scientifiques, techniques et sociales et aussi d’élaboration de modèles opérationnels. Notre sujet est Modélisation Evolution Urbaine par Automate Cellulaire en Prendre la ville de M'sila comme cas d'étude Modéliser l’évolution urbaine veut dire aussi « fabrique » de la ville au travers de l’expérimentation virtuelle. Cependant Nous avons montrer qu’il est possible de développer un modèle qui n'est pas basé sur des équations mathématiques, mais sur des règles qualitatives d’évolution de l’espace, traduites assez directement du langage naturel et facile. Ces règles s’appliquent en chaque lieu (les cellules de l’automate) et permettent de faire évoluer l’occupation du sol par la mise en concurrence entre les contraintes internes de développement de chaque cellule et des contraintes externes venues des cellules environnantes. Entre force de vie qui tente de faire perdurer l’état actuel et forces environnementales qui tentent de le changer. Le système complexe – ville, ainsi modélisé, En tant que tel, dans un jeu permanent d’actions et de rétroactions. L’objectif de cette recherche consiste à proposer un modèle spatial se rapprochant encore plus de la réalité du terrain susceptible d’être employé dans un système de évolution urbaine et permettant d’améliorer le raisonnement spatial appliqué sur les données et les résultats des modèles réguliers traditionnels ,Tout cela dans l'intérêt d'une réalité plus belle pour la ville de M’sila et pour l'amélioration de l'urbanisation en anticipant l'état de la ville INTRODUCTION GENERALE 2 dans le futur .Ces simulations facilitent la planification future .Dans le but de planifier une stratégie rationnelle qui garantit tous les besoins de la population tout en maintenant les conditions en vigueur. Organisation du mémoire Ce mémoire est structuré en cinq chapitres, incluant le présent chapitre d’introduction. Le première chapitre présente de façon détaillée évolution urbain de tout le monde et les différentes modes de l’urbanisation et ces développements car elle est phénomène global qui puise ses racines dans l’histoire des populations humaines. Le second chapitre et spécialement pour la notion du les Automates cellulaire et ces origines ce sont des modèles dynamiques permettant d'effectuer des simulations de grande envergure sur la base de règles simples. Le troisième chapitre expose la modélisation conceptuelle nous verrons comment on va faire la modélisation avec les automates cellulaires et comment créât et utilisé ces automates et aussi avec l’état de l’art. Le quatrième chapitre est sur la ville de M’sila avec simulation détaillé on arrive à une visualisation d'un résultat approximatif pour l'avenir de la ville par l’analyse de la ville et aussi récolter diverses photos classées par ordre chronologique de la ville de M'sila et diverses informations sur le passé de la ville, pour arriver à un résultat qui permet de modéliser ce développement. Enfin, le cinquième chapitre décrit le partie programmation de cette modélisation par automate cellulaire on utilisent le logiciel netbeans avec langage Java , Tandis que nous présentons les concepts particuliers développés , en particulier un langage simple qui permet à l’utilisateur de définir son propre modèle et les nouvelles fonctionnalités qui ont permis de construire un nouveau modèle que nous présentons . Nous terminons par la présentation du travail réalisé , la fabrication des données sources, la constitution de la base de règles du modèle d’évolution et quelques indications sur sa validation. Chapitre I : Evolution Urbaine Chapitre I : EVOLUTION URBAINE 5 1.Introduction : Dans ce chapitre on va parler sur l’évolution urbaine dans une manière générale et sur une perspective de long terme .Alors, l’urbanisation est un phénomène global qui puise ses racines dans l’histoire des populations humaines, qui s’accélère au fil des siècles et semble promis à une inexorable progression dans l’avenir. Il se manifeste par une augmentation continue de la population des zones urbaines, et corollairement par l’extension physique des agglomérations. 2. L'informatique urbaine : L'informatique urbaine est une approche interdisciplinaire pour comprendre, gérer, et concevoir la ville en utilisant des théories et des méthodes systématiques basées sur de nouvelles informations. technologies de mations, et fondé sur les développements contemporains des ordinateurs et communications. Il intègre les sciences urbaines, la géomatique et l'informatique : urbanisme la science propose des études d'activités, de lieux et de flux dans l'espace urbain ; géomatique fournit la science et les technologies de mesure spatio-temporelle et dynamique objets urbains dans le monde réel et la gestion des données obtenues à partir de la mesurement ; l'informatique fournit la science et les technologies du traitement de l'information, les systèmes d'information, l'informatique et les statistiques qui soutiennent la quête de développer des applications aux villes. Le domaine couvre de nombreux secteurs qui définissent les systèmes de la ville. Ces secteurs sont souvent étudiés en tant que tels, tels que le transport, le logement, l'activité de vente au détail, infrastructure impliquant la distribution des déchets, de l'eau, de l'électricité et d'autres sources de l'énergie, ainsi que la structure démographique, la situation économique, le développement urbain, et une foule de perspectives connexes qui se rapportent aux villes et aux systèmes urbains. Ce qui rend une informatique urbaine différente et complémentaire de ces approches disciplinaires est le fait que le calcul est au cœur de la manière dont les méthodes et les modèles sont utilisés pour générer une compréhension plus profonde : de nombreux problèmes qui impliquent de déterminer comment fonctionnement des villes, comment elles génèrent des formes différentes, comment leur dynamique reflète manières dont ils grandissent et déclinent, et comment ils se mélangent, se séparent et se polarisent populations et activités différentes. Ce qui fait de l'informatique urbaine un moyen particulièrement opportun de rassembler et fusionnant de nombreuses perspectives interdisciplinaires qui impliquent le calcul est que au cours des vingt dernières années, les ordinateurs se sont réduits au point de Chapitre I : EVOLUTION URBAINE 6 pouvoir être utilisé comme capteurs et intégré dans une variété d'infrastructures physiques ainsi comme étant utilisé dans un contexte mobile par l'ensemble de la population. Cela a signifié que tout à coup, nous sommes maintenant dotés de flux de données sur le fonctionnement d'une ville en temps réel, ce qui n'était généralement pas disponible jusqu'alors lorsque la plupart de nos les méthodes de collecte de données n'étaient pas automatisées au moyen de capteurs. Cela a conduit à ce que s'appelle le big data, c'est-à-dire des données générées en temps réel, avec une grande variété, et donc volume presque illimité. Ces données peuvent être le produit de capteurs qui fonctionnent continuellement et fournir des mises à jour immédiates au système qui nous concerne. Pour ces données, nous avons besoin de nouvelles méthodes et de nouveaux modèles pour nous aider à comprendre et à interpréter les anciennes des modèles toujours pertinents. Cela a jeté la ville 24 heures sur 24 à l'ordre du jour. Le temps se reflète maintenant profondément dans nos modèles, alors que dans le passé l'accent était davantage mis sur la variété spatiale. Le domaine de l'informatique urbaine continue de se développer rapidement dans son étreinte de nouveaux technologies de détection, nouveaux types de science des données spatiales, nouvelles méthodes d'analyse qui allant des méthodes statistiques traditionnelles comme dans l'économétrie spatiale, jusqu'à les nouveaux développements de l'apprentissage automatique et l'analyse multivariée qui permettent aux analystes explorer les méga données d'une manière qui n'a pas été possible jusqu'à présent. [4] 2.1. Comment l’évaluer Le niveau d’urbanisation d’un territoire (région, pays, continent…) s’évalue par : • le rapport entre le nombre des résidents urbains et celui des ruraux, • la densité de peuplement des différentes zones, • l’expansion territoriale des agglomérations, • la transformation des modes de vie. À noter que le terme d’urbanisation est à distinguer de celui d’urbanisme, qui désigne la façon dont les villes et espaces périurbains sont construits, transformés, aménagés et organisés.[3] 3.Mode d’urbanisation La morphologie urbaine permet d'étudier les différentes formes d'urbanisation. Les villes peuvent se développer grâce à la ERP de façon verticale ou horizontale, voire les deux à la fois. Le développement horizontal est tantôt concentrique, dendritique, ou linéaire (fréquent https://fr.wikipedia.org/wiki/Morphologie_urbaine https://fr.wikipedia.org/wiki/Progiciel_de_gestion_int%C3%A9gr%C3%A9 Chapitre I : EVOLUTION URBAINE 7 dans les vallées, ou sur le bord d'axes importants), ceci en fonction du contexte biogéographique, politique ou historique (incluant l'évolution des conditions historiques de propriété). L'urbanisme s'appuie généralement sur l'existant, sur le réseau de transport et sur un ou plusieurs centres ou pôles (développement multipolaire). De nombreuses villes nouvelles ont été créées dans les années 1960 en France à la suite de la politique des villes nouvelles (comme Lille-Est, Évry ou Cergy-Pontoise par exemple). Hormis dans le cas de villes champignons liées à la découverte de filons d'or, de ressources rapidement épuisées, ou dans le cas de cités touchées par les retombées de Tchernobyl, depuis les années 1700, il est rare que les villes se stabilisent, disparaissent ou décroissent. Même Hiroshima et Nagasaki, ou les villes rasées durant la Première Guerre mondiale ou durant la Seconde Guerre mondiale, ou lors d'autres conflits ont rapidement été reconstruites et se sont développées. Ce n'est pourtant que dans les années 1970 avec les villes nouvelles, et dans les années 1990 que les urbanistes ont commencé à réfléchir aux conditions de soutenabilité du développement urbain. Et il faut attendre les années 2000 pour voir apparaître les premiers quartiers HQE (Bedzed par exemple à Londres) et 2006 pour le premier projet de ville HQE (en Chine).[6] 4.Géosimulation urbaine La géosimulation est l’une des approches les plus utilisées pour la simulation urbaine. Les premiers balbutiements des simulations spatiales pour l’exploration de dynamiques urbaines sont quasi-conjoints à l’apparition de l’ordinateur, les analystes des problèmes urbains ayant rapidement décelé le potentiel de l’informatique pour décrire ou modéliser la ville [Ingram et al. 1972]. Ce type de modélisation urbaine à très grande échelle est par contre rapidement critiqué en raison notamment de la quantité astronomique de données requise, de leur résolution inadéquate, de leur manque de transparence et de la non- reproductibilité de leurs résultats [D. Lee 1973; D. Lee 1994; Torrens 2000b]. Depuis ce temps, des centaines de modèles de simulation urbaine ont été proposés, mais il a fallu attendre 1979 avec la simulation de croissance urbaine de Tobler [Tobler 1979] pour voir le couplage entre les automates cellulaires et espace urbain, et les années 1990 pour que cette association entre dans les mœurs, popularisée par certaines applications en géographie urbaine [Batty et al. 1997]. La notion de géosimulation urbaine est donc récente et représente une nouvelle tendance de simulation urbaine : la modélisation de systèmes à l’échelle des individus et des infrastructures [Waddell & Alberti 1998]. Le concept s’est imposé rapidement; à preuve que les applications à base de géosimulation ont été la principale forme de modélisation urbaine au cours des deux https://fr.wikipedia.org/wiki/Urbanisme https://fr.wikipedia.org/wiki/Ville_nouvelle https://fr.wikipedia.org/wiki/Ville_nouvelle https://fr.wikipedia.org/wiki/Politique_des_villes_nouvelles_fran%C3%A7aises https://fr.wikipedia.org/wiki/Politique_des_villes_nouvelles_fran%C3%A7aises https://fr.wikipedia.org/wiki/Hiroshima https://fr.wikipedia.org/wiki/Nagasaki https://fr.wikipedia.org/wiki/Ville_nouvelle https://fr.wikipedia.org/wiki/Ville_nouvelle https://fr.wikipedia.org/wiki/Durabilit%C3%A9 https://fr.wikipedia.org/wiki/Haute_qualit%C3%A9_environnementale https://fr.wikipedia.org/wiki/Bedzed https://fr.wikipedia.org/wiki/Haute_qualit%C3%A9_environnementale Chapitre I : EVOLUTION URBAINE 8 dernières décennies [Stevens & Dragicevic 2007]. Les exemples abondent dans la littérature; ces applications touchent des domaines aussi variés que la simulation de piétons ou de foule [Batty 2001; Moulin et al. 2003; Kukla et al. 2003], la ségrégation [Nara & Torrens 2005; Omer & Benenson 2002], l’utilisation du sol et l’étalement urbain [Sanders et al. 1997; White et al. 1997; Batty et al. 1999; White & Engelen 2000; Shi & Pang 2000] et la simulation du trafic routier [Torrens 2000b; Nagel et al. 1999; Claramunt & Jiang 2001]. Ces dernières années, l’utilisation de la géosimulation pour résoudre les problèmes urbains a connu une expansion fulgurante, principalement en raison de l’essor des systèmes d’information géographique (SIG) et des bases de données spatiales [Benenson & Torrens 2004] ainsi qu’à la disponibilité de données géographiques de haute résolution en grande quantité et, généralement, accessibles à tous [Benenson & Torrens 2005]. On considère tout de même que les modèles de géosimulation n’en sont qu’à leurs débuts dans le domaine de la modélisation urbaine [Torrens 2001] en raison de toutes les possibilités qu’ils procurent, mais aussi du fait des nombreux défis qui les attendent.[5] 5.Urbanisation et développement durable Pour un quadruplement de la population globale, celle des villes a augmenté d’un facteur 20. Les statistiques de l’ONU laissent augurer d’un nouveau doublement d’ici un siècle. Le processus d’urbanisation, par ailleurs, ne s’opère pas partout selon les mêmes modalités. Dans les pays riches et/ou très structurés, il est relativement encadré via des politiques d’aménagement du territoire. Au Sud, les migrations des populations rurales vers les villes échappent souvent à tout contrôle. S’ensuivent des situations très hétérodoxes selon les cas : Pour le positif : développement des industries, des services, des transports… Pour le négatif : pollutions diverses, augmentation des émissions de GES et du réchauffement climatique, dégradation des milieux, ghettoïsation et déculturation de populations fragilisées… Autant de problématiques qui questionnent les stratégies de développement durable et de résilience à l’échelle locale et à celle de la planète. Toutefois, il faut noter que si l’urbanisation pose de nombreuses questions en termes de durabilité, elle peut également représenter une opportunité pour nos sociétés d’être plus durables. En effet, on constate que globalement, dans les pays développés, les populations vivant en ville sont plus « durables » que celles qui vivent à la campagne : elles ont une empreinte carbone moins élevée, une empreinte sur le territoire moins forte. Les populations urbaine utilisent généralement moins Chapitre I : EVOLUTION URBAINE 9 leur voiture, ils consomment moins d’énergie car ils possèdent des surfaces habitables plus faibles, sans compter les économies d’échelles que permettent de constituer des villes denses en termes d’empreinte au sol, d’économie circulaire… C’est pourquoi de plus en plus de chercheurs estiment que pour faire la transition vers des sociétés durables, respectant l’écosystème, il faut généraliser des villes denses, basées sur les énergies renouvelables et les principes de l’urbanisme durable.[3] 6.Urbanisation dans le monde Dans le monde, on observe un peu partout des phénomènes d’urbanisation. Généralement, l’urbanisation va de pair avec le développement économique industriel d’une région ou d’un pays. En quête d’un développement économique plus propice, de nombreuses populations se déplacent vers les villes. Actuellement, plus de 70% de la population mondiale vit dans les villes, contre seulement 15% en 1900 ou 50% en 2007.[3] 7.Modélisation du système urbain Figure I.1 : Modélisation du système urbain Modélisation du système urbain La ville est un système ouvert. Il faut donc étudier la relation que la ville entretient avec son environnement. Par exemple, les relations entre la ville et la campagne sont très importantes et permettent à la ville d'assurer sa survie. Une ville développe des interactions entre les hommes, les activités et les biens, mais si l'intensité d'occupation du sol résultant des activités de la ville, des habitats, des infrastructures... - produit de la richesse et des équipements, elle produit aussi de la vulnérabilité et donc du risque. En considérant la ville comme un système, nous avons mis en évidence les Chapitre I : EVOLUTION URBAINE 10 interrelations entre les différentes composantes urbaines. Il est donc intéressant d'étudier ces interrelations après une perturbation, en commençant par le modèle urbain productif. Ainsi, en étudiant différentes composantes urbaines et leur vulnérabilité au risque, il est possible de modéliser l'environnement urbain en temps de crise. Il apparaît ainsi que, compte tenu des contraintes de localisation et de structures, les réseaux constituent non seulement une « porte » des risques en milieu urbain, mais aussi une « porte » des risques du fait des effets domino que ces réseaux peuvent provoquer. [7] 8.Conclusion Les modèles de simulation de développement urbain peuvent être des outils importants pour Aide à la décision car ces modèles permettent de mieux comprendre les processus morphologiques au travail, leurs principaux déterminants et leurs résultats. Elle peut également être intégrée à l'aménagement du territoire dans la mesure où elle permet de tester différents scénarios d'aménagement urbain. Dans un contexte où l'on cherche à réduire les investissements publics dans les infrastructures de transport et sous la pression de considérations environnementales de plus en plus importantes, l'impact de la restriction de certaines formes de mobilité sur la performance urbaine peut alimenter une réflexion plus approfondie sur la relation entre mobilité, formes bâties et évolution des systèmes urbains . Chapitre II : les automates cellulaires Chapitre II : LES AUTOMATES CELLULAIRES 12 1.Introduction "... One might have thought that if a program was simple it should only do simple things. But amazingly enough, that isn't even close to correct. And in fact what I've discovered is that some of the very simplest imaginable computer programs can do things as complex as anything in our whole universe. It's this point that seems to be the secret that's used all over nature to produce the complex and intricate things we see..." [... On aurait pu croire que si un programme était simple il ne devrait faire que des choses simples. Mais assez étonnamment, ce n'est même pas près de vrai. Et en fait ce que j'ai découvert que certains des très simples programmes d'ordinateurs imaginables peuvent faire des choses aussi complexes que quoi que ce soit dans l'ensemble de notre univers. C'est ce point qui semble être le secret qui est utilisé dans la nature pour produire la complexité et les choses complexes que nous voyons...] [Ma TRD]. C'était un extrait d'une discussion avec Stephen Wolfram, à propos du sujet de son livre " A new kind of science " , des règles extrêmement simples pouvaient alors émerger des structures beaucoup plus complexes. Dans ce chapitre, nous venons introduire la notion d’automate cellulaire, par présentation un aperçu historique sur l’évolution de ce domaine de simulation utilisé aujourd’hui dans vaste filières de la physique, biologie, chimie, informatique. Un automate cellulaire consiste en une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini et qui peut évoluer au cours du temps. L'état d'une cellule au temps t+1 est fonction de l'état au temps t d'un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération précédente. Étudiés en mathématiques et en informatique théorique, les automates cellulaires sont à la fois un modèle de système dynamique discret et un modèle de calcul. Le modèle des automates cellulaires est remarquable par l'écart entre la simplicité de sa définition et la complexité que peuvent atteindre certains comportements macroscopiques : l'évolution dans le temps de l'ensemble des cellules ne se réduit pas à la règle locale qui définit le système. À ce titre il constitue un des modèles standards dans l'étude des systèmes complexes. 2.Les Automates cellulaires Les automates cellulaires sont des modèles dynamiques permettant d'effectuer des simulations de grande envergure sur la base de règles simples [Carvalho et al. 2006b; Langlois https://www.techno-science.net/glossaire-definition/Ensemble-fini.html https://www.techno-science.net/glossaire-definition/Temps.html https://www.techno-science.net/glossaire-definition/Nombre.html https://www.techno-science.net/glossaire-definition/Mathematiques.html https://www.techno-science.net/glossaire-definition/Informatique-theorique.html https://www.techno-science.net/glossaire-definition/Systeme-dynamique.html https://www.techno-science.net/definition/6402.html https://www.techno-science.net/glossaire-definition/Complexite.html https://www.techno-science.net/glossaire-definition/Ensemble.html Chapitre II : LES AUTOMATES CELLULAIRES 13 & Phipps 1997]. En effet, malgré le fait qu’ils forment l’un des modèles spatiaux les plus simples, ils sont particulièrement adaptés pour la modélisation de systèmes complexes en raison de leur facilité à reproduire des comportements globaux complexes à partir des interactions locales de cellules individuelles [White & Engelen 2000; Wolfram 1984]. Pour cette raison, ils sont de plus en plus utilisés dans la simulation de systèmes naturels et humains complexes, et plus particulièrement en géosimulation, dont ils constituent l’un des fondements. La popularité des automates cellulaires en géosimulation est due aux nombreux avantages que leur utilisation confère à ce type de simulation, notamment une grande simplicité à la fois dans la représentation visuelle et pour les traitements, une approche dynamique et flexible, la représentation explicite du temps et de l’espace [Moreno & Marceau 2007], une excellente compatibilité avec les systèmes d’information géographique (SIG) et les données raster (très disponibles) [White & Engelen 2000] ainsi qu’avec le paradigme de la programmation orientée objet et enfin un certain réalisme dans la simulation. Ceci fait de l’automate cellulaire un des modèles de simulation spatiale les plus établis, particulièrement pour les simulations urbaines. Dans sa définition la plus basique, un automate cellulaire correspond à une grille composée de cellules identiques [O'Sullivan & Torrens 2000]. Au temps t de la simulation, chacune des cellules est dans un état E faisant partie d’un ensemble prédéterminé d’états. L’état d’une cellule est modifié du temps t au temps t + 1 par l’application d’un ensemble de règles internes tenant compte de l’état de la cellule et des cellules voisines. L’application répétitive de ces règles aux cellules de façon synchrone permet d’en changer les états de façon itérative et de le faire évoluer. Si on le décortique, l’automate cellulaire traditionnel comporte donc cinq composantes: • une grille de cellules carrées; • un ensemble fini d’états permettant de définir les cellules; • un voisinage uniforme pour chacune des cellules; • un ensemble de règles de transition permettant de modifier les états des cellules; • une dimension temporelle, chaque itération permettant de modifier les cellules simultanément. Ce formalisme décrit l’automate cellulaire classique tel que défini à l’origine par Von Neumann [Von Neumann & Burks 1966] et qui demeure toujours d’actualité : cellules Chapitre II : LES AUTOMATES CELLULAIRES 14 régulières identiques, voisinage et règles de transition homogènes, mise à jour synchrone des cellules. Or, l’uniformité omniprésente dans la définition de base de l’automate en fait une approche difficile à appliquer dans le cadre de simulations de dynamiques urbaines réelles. En réalité, et tel qu’appliqué à la modélisation de systèmes urbains comportant des dimensions sociales, économiques et spatiales, la définition d’un automate cellulaire est beaucoup plus complexe [Torrens 2000a]. De nombreux assouplissements ont été proposés au fil de l’évolution de la géosimulation pour adapter les automates cellulaires à celle-ci. La pionnière en ce domaine demeure Couclelis [Couclelis 1985], qui fut la première à remettre en cause l’uniformité des automates cellulaires et plus particulièrement de deux de leurs composantes, soit le voisinage et les règles de transition. Depuis, plusieurs modifications ont été apportées aux automates cellulaires de façon à adapter ceux- ci au contexte de la géosimulation. La question de savoir si on doit s’éloigner du formalisme strict des automates cellulaires pour la géosimulation urbaine fait d’ailleurs encore l’objet de plusieurs débats [Torrens & O’Sullivan 2000]. Les sections ci-dessous détaillent les différentes composantes des automates cellulaires, la place qu’elles occupent dans un système de géosimulation ainsi que les assouplissements apportés au fil du temps pour tailler une place à cette approche en simulation urbaine et en géosimulation. 2.1.Grille Dans un automate cellulaire, la surface représentant l’environnement virtuel est divisée en une partition de cellules de forme régulière, le plus souvent une grille en deux dimensions de cellules carrées, mais parfois aussi hexagonales [Sanders et al. 1997]. Plus rarement, les cellules peuvent être de forme irrégulière. On appelle tessellation spatiale ce morcellement de l’espace. Par définition, la tessellation d’une surface correspond au recouvrement de cette surface à l’aide d’un arrangement de polygones qui ne se chevauchent pas [Y. C. Lee et al. 2000]. Le recouvrement de la surface doit être complet, c’est-à-dire qu’il ne doit pas y avoir de vide entre les cellules. L’expression « tessellation régulière » fait référence à une structure dont les polygones sont identiques et réguliers (figure dont tous les côtés sont de même longueur et tous les angles sont égaux); dans le cas contraire, il s’agit d’une tessellation dite « irrégulière » [Worboys & Duckham 2004]. Dans un système de géosimulation urbaine, la grille de cellules est considérée comme étant la structure spatiale de la simulation. Elle représente le territoire, l’environnement; bref, la structure physique de la ville modélisée [Torrens 2001]. Les cellules sont les éléments fondamentaux de la simulation; ce sont des automates individuels mais elles demeurent Chapitre II : LES AUTOMATES CELLULAIRES 15 fixes ;elles ne se déplacent pas. La plupart du temps, les cellules sont identiques, malgré l’irrégularité marquée de la plupart des villes. Des cellules de tailles et de formes homogènes sont ainsi employées pour représenter des objets géographiques urbains aux formes irrégulières, telles que des parcelles cadastrales ou des zones d’utilisation du sol. Récemment, quelques rares systèmes de géosimulation à base d’automates cellulaires irréguliers [Stevens & Dragicevic 2007; Hammam 2004; Moreno, Ménard et al. 2008] ont fait leur apparition. 2.2.Etat À chaque itération de la simulation, un état (discret) provenant d’un ensemble fini d’états est attribué à chacune des cellules. Cet état correspond à un attribut approprié selon le phénomène modélisé. Dans un contexte de simulation urbaine, l’état peut représenter par exemple le type d’occupation du sol (industriel, commercial ou résidentiel), l’occupation (occupé ou libre), la densité (haute, moyenne ou basse) ou le stade de développement (vacant ou construit). Depuis peu, l’état est parfois remplacé par un ensemble de caractéristiques, permettant ainsi de mieux représenter le contexte étudié. Des états non discrets peuvent également être employés [X. Li & Yeh 2000], reflétant mieux la diversité des valeurs que peuvent prendre certaines caractéristiques urbaines telles que le taux de croissance de la population. 2.3.Voisinage Le voisinage d’une cellule représente l’ensemble des régions qui ont une influence sur cette cellule [Shiyuan & Deren 2004; O'Sullivan 2001b]. Le concept de voisinage est basé sur la notion d’adjacence. Le voisinage de l’automate cellulaire traditionnel est composé des 4 cellules adjacentes aux cotés de la cellule (voisinage de Von Neumann) ou des 8 cellules adjacentes à la cellule (voisinage de Moore), que l’on peut observer sur la Figure 1 ci- dessous. (a) (b) Figure II.1 : Voisinages de Moore (a) et de Von Neumann (b) Chapitre II : LES AUTOMATES CELLULAIRES 16 Dans un contexte urbain, les zones d’influence ne sont pas uniquement topologiques et font parfois référence à des notions de distance [Torrens 2000a]. De plus, dans le cas de systèmes comportant une dimension humaine, la notion de voisinage peut être très large, puisqu’une personne est consciente de son environnement dans un contexte beaucoup plus vaste que ce qu’implique la notion classique de voisinage [White & Engelen 2000]. Pour cette raison, certaines recherches ont défini des voisinages alternatifs, basés sur la distance ou la proximité [Stevens & Dragicevic 2007] ou encore sur la nature des objets [White & Engelen 2000]. 2.4.Règles de transition Les règles de transition forment le cœur, ou moteur, de la simulation; elles déterminent le comportement du modèle et l’évolution de la simulation [Dawson et al. 2006]. L’ensemble de règles synchrones gère la transition des états des cellules entre chacune des itérations. Les règles se présentent sous la forme d’énoncés conditionnels qui déterminent l’état futur de chacune des cellules en tenant compte à la fois de l’état de la cellule et des valeurs des cellules voisines, soit celles faisant partie du voisinage de la cellule [Vliet et al. 2009]. Dans un contexte de géosimulation urbaine, une règle de transition peut représenter n’importe quel processus affectant une région urbaine. Par exemple, dans un système de géosimulation suivant l’accroissement urbain, une cellule peut devenir candidate pour une conversion de l’état « Vacant » à l’état « Développé » seulement si toutes les cellules de son voisinage ont un état correspondant à « Très haute valeur foncière ». Dans le cas contraire, l’état de la cellule demeure « Vacant » [Torrens 2009]. Des principes novateurs ont récemment été introduits dans la description des règles de transition; citons notamment la logique floue [Carvalho et al. 2006b] ainsi que les systèmes stochastiques ou probabilistes. 2.5.Temps Dans un automate cellulaire, le temps est discret et procède par évolution itérative, passant du temps t au temps t + 1, puis au temps t + 2, etc. La granularité de l’échelle de temps change selon le contexte : un intervalle de temps peut représenter aussi peu qu’une seconde ou une minute (modèles de simulation de trafic) mais aussi de plus grosses périodes de temps, par exemple un mois ou un an, dans les modèles d’étalement urbain. Cependant, l’échelle de temps doit demeurer réaliste, c’est-à-dire que l’on tiendra compte du temps dévolu à une itération pour déterminer ce qui évolue pendant celle-ci. À chaque itération, les règles de transition sont appliquées à l’ensemble des cellules de façon à faire évoluer leurs états. Chapitre II : LES AUTOMATES CELLULAIRES 17 C’est de cette façon que progresse la simulation.[5] 3.Définitions de base Un AC se définit à l‘aide de deux types de caractéristiques : structurelles et fonctionnelles . Les premières concernent l’aspect topologique du réseau cellulaire, les secondes concernent l’aspect dynamique de l‘évolution du réseau au cours du temps. En règle générale, le réseau des cellules peut prendre corps dans des espaces à D dimensions, D étant une, deux ou trois dimensions ou encore plus. Théoriquement, il n'y a pas de limite à la dimension d'un automate, si ce n'est la puissance de calcul des machines sensées le reproduire. Par exemple, dans le cas d'une matrice à 2D, la structure du réseau cellulaire peut-être de deux types : 3.1.La structure en île : Les cellules du réseau sont virtuellement entourées par des cellules mortes. 3.2. La structure en tore : Les cellules du bord haut de la matrice peuvent contacter celles du bord bas, et de même pour les cellules des bords gauche et droit. Le réseau cellulaire peut également être variable comme, par exemple, le réseau orthogonal ou hexagonal. Dans un AC une cellule n'a conscience que d'un sous-ensemble de cellules dites voisines ayant une influence sur elle. On dit qu'un voisinage d'une cellule est aveugle si chacune des cellules le constituant joue un rôle identique, la cellule concernée n'aura donc connaissance que des différents états des cellules voisines sans savoir quel état correspond à quelle cellule. Ce type de voisinage est le plus souvent utilisé par la plupart des AC sans le préciser. Le fonctionnement de chaque cellule du réseau peut être caractérisé par l‘automate fini (V, vo, f). • V est l‘ensemble des états cellulaires. • vo un état particulier appelé état de repos. • f est la fonction de transition qui à chaque voisinage qui est n-tuple d‘éléments de V associe un élément de V. V étant l'ensemble des états que peut prendre une cellule. Le plus souvent limité à 2, mais il n'y a aucune limite à ce nombre, c'est le cas par exemple pour l'automate de Von Neumann qui était à 29 états. Dans la pratique, les états cellulaires sont souvent représentés par des couleurs ce qui permet de suivre l'évolution de l'automate. Comment l'évolution de tel automate aura lieu ? Chapitre II : LES AUTOMATES CELLULAIRES 18 Si (t + 1) = f ({ Sj (t) } ) où j Є Vi Λ Vi désigne le voisinage de la cellule i La fonction de transition f est un ensemble de règles qui permettent de déterminer le nouvel état d'une cellule en fonction de son état précédent et de l'état précédent de son voisinage. Généralement, ces règles ne sont pas explicitées, mais résumées sous la forme de métarègles de type « si...alors ». L'automate évolue discrètement par génération où le temps s'écoule par à-coups. Ceci signifie qu'à la génération t, chaque cellule décide d'après sa fonction de transition que devient son état au futur c'est-à-dire au temps t+1. Une fois chaque cellule a déterminé son prochain état, et seulement à ce moment là, elle passe au nouvel état calculé d'une façon à ce que le réseau cellulaire sera entièrement remis à jour de manière synchrone. On parle alors d'une simulation d'un traitement parallèle. Formellement, on peut exprimer l'évolution de l'automate par la formule . Figure II.2 : Règle de mise à jour d’ AC Un AC pouvait donc être défini par un aspect topologique décrivant la façon par laquelle les cellules sont arrangées sur le réseau cellulaire et un autre fonctionnel caractérisé par le voisinage, l'ensemble d'états et la fonction de transition qui décrit son évolution.[9] Figure II.3 : Composants d’un automate cellulaire Chapitre II : LES AUTOMATES CELLULAIRES 19 4.Définition 1 Un automate cellulaire est un tuple A = (d, Q, V, δ) ou : • d ϵN∗ est la dimension de l'automate cellulaire, et indique que le réseau sous- jacent est Zd. • Ꝗ est un ensemble fini d’états. • Ѵ ⸦ Zd est un sous-ensemble f i ni ordonné (appelé voisinage) du réseau sous-jacent Zd. • δ : QV → Q est la fonction de transition locale de l'automate. La plupart des automates cellulaires traités dans cette thèse auront pour fonction de reconnaître des langages. Pour cette raison, on définit un alphabet d'entrée dans lequel seront exprimés les langages caractérisés par un automate cellulaire.[11] 5.Définition 2 D’un point de vue formel ,un automate cellulaire géographique est défini par le quadruplet (U, V, E, F) avec : • U = {U₁, U₂,…Uᵢ,… Uₙ}, un ensemble fini d’unités spatiales, réparties le plus souvent selon un arrangement régulier (grille) ; • V = {V₁, V₂,…Vᵢ,… Vₙ}, l’ensemble des voisinages de ces unités spatiales, définis selon un critère topologique (contigüité et/ou connexité) ou métrique (distances entre centroïdes). Chaque voisinage Vᵢ est une liste d’unités spatiales Vᵢ = {Uⱼ, Uₖ,…, Uₘ} considérées comme voisines de l’unité i, selon le critère retenu ; • E, l’ensemble des états possibles des cellules, sous forme de variables qualitatives ou quantitatives, discrètes ou continues ; • F, l’ensemble des fonctions de transition locales ƒ, déterministes ou probabilistes, permettant de faire évoluer à chaque pas de temps t l’état des cellules en fonction de l’état de la cellule concernée et des états des cellules voisines, telles que Eᵢ ͭ⁺¹ = ƒ(Eᵢ ͭ ;Evᵢ ͭ ).[11] Chapitre II : LES AUTOMATES CELLULAIRES 20 6.Origines et développement Dans les années quarante, le chercheur Von Neumann, père des architectures des ordinateurs actuels, a étudié les automates autoreproducteurs, le but fut de savoir s‘il était possible de concevoir une machine capable de s‘auto reproduire, c'est à dire produire une copie d'elle même. En effet, ce mécanisme correspond à l'interprétation actuelle du fonctionnement de la molécule d'ADN découverte plus tard. Etant donné que l'ADN n'était pas encore découvert au cours de cette période, Von Neumann souhaite alors mieux comprendre la logique qui sous-tend de tels phénomènes. Von Neumann trouva son chemin pour résoudre le problème posé grâce aux travaux du mathématicien Stanislas Ulam, son collègue au laboratoire de Los Alamos. Ce dernier a étudié la génération des structures graphiques définies de façon récursive. La source étant des règles simples permettant d'engendrer des figures complexes et esthétiques pouvant par fois se répliquer. Il a utilisé un espace à deux dimensions divisé en « cellules ». Chacune d'entre elles pouvait avoir deux états : allumé ou éteint. Partant d'une configuration donnée, la génération suivante était déterminée en fonction des règles de voisinage. Il suggéra alors à Von Neumann d‘utiliser ce qu'il appelait les « espaces cellulaires » pour pallier les difficultés pratiques qui se posaient lors de la construction de l‘automate autoreproducteur. Von Neumann a, tout de suite, construit son automate autoreproducteur, c‘était un automate bidimensionnel à 29 états avec un voisinage de 5 cellules (cellule cible + 4 cellules voisines contiguës). Il a également décrit comment un constructeur universel pouvait être construit, c'est à dire une structure capable de générer n'importe quelle configuration stockée dans une structure de stockage. Ce n‘est qu‘en 1966 que le terme automate cellulaire est créé par Arthur Burks en coïncidence avec la publication du premier grand ouvrage consacré au problème de l‘autoreproduction : Theory of self-reproducing automata. Rappelons que dans les années soixante, quelques-uns des problèmes mathématiques ont été résolus par des AC comme celui de « la synchronisation des fusiliers » par exemple. L'application des AC n'est élargie qu'après l'apparition du désormais fameux Jeu de la Vie (Life) de John Horton Conway en 1970. Nous n'allons pas l'aborder ici car il le sera par la suite. Beaucoup de chercheurs se sont intéressés à son fonctionnement plus tard afin de maîtriser les énigmes qui sont nées de son étude. Parallèlement aux recherches qui se déroulaient sur Life, d'autres chercheurs étudiaient d‘autres AC ayant des règles simples et qui conduisaient aussi à des comportements imprévisibles. Plus tard, dans les années 80, les chercheurs se sont également dirigés vers la physique où les AC ont été utilisés comme modèles de simulation des comportements des molécules et d‘autres phénomènes physiques. Chapitre II : LES AUTOMATES CELLULAIRES 21 Depuis le début des années 90, l‘utilisation des AC s‘est généralisée en touchant à de nombreux domaines, notamment la cryptographie, l'imagerie, l‘étude du développement de systèmes urbains ... etc.[9] 7.Caractéristiques 7.1.Caractéristiques techniques d’un automate cellulaire 7.1.1.La cellule L'élément de base d'un automate cellulaire (en abrégé AC) est la cellule. Une cellule est une sorte de mémoire qui permet de stocker un état. Dans le cas le plus simple, l'état d'une cellule est constitué d'un bit, chaque cellule pouvant donc se trouver soit dans l'état 1, soit dans l'état 0. Cependant, l'état d'une cellule peut être plus complexe et comporter plusieurs attributs, mais le nombre d'états possibles pour la cellule reste fini. L'automate auto-répliquant de Von Neumann admettait 29 états. 7.1.2.Le réseau Les cellules sont disposées sur un réseau dont la géométrie est celle d'un réseau régulier de dimension n. Cependant, dans la plupart des cas, on choisit un réseau carré avec n=1 ou 2. On peut construire des réseaux avec n=3, mais ceux-ci sont plus difficiles à visualiser. Les réseaux unidimensionnels sont plus faciles à étudier et permettent d'obtenir des résultats théoriques. La terminologie de site du réseau s'employé aussi pour désigner une cellule du réseau. Le terme site présuppose une appartenance et une localisation sur un réseau. 7.1.3.Le voisinage La dynamique d'un automate cellulaire nécessite la définition de la notion de voisinage d'une cellule: c'est l'ensemble des cellules susceptibles d'interagir avec elle à un temps donné. Le voisinage contient toute l'information nécessaire pour la mise à jour de l'état de la cellule à chaque pas de temps. Il détermine donc l'évolution temporelle de la cellule. Précisons qu'une cellule appartient à son propre voisinage. Les voisinages les plus répandus sur un réseau bidimensionnel carré sont: • Le voisinage de von Neumann (ci-dessous figure (a)) d'une cellule contient les quatre cellules nord, sud, est, ouest. • Le voisinage de Moore (ci-dessous figure (b)) étend le voisinage de von Neumann en y adjoignant les cellules sur les diagonales. Chapitre II : LES AUTOMATES CELLULAIRES 22 Figure II.4 : voisinage de Von Neuman et de Moore • Le voisinage de Moore étendu (ci-dessous figure (a)) est similaire au voisinage de Moore, mais on y incorpore aussi la deuxième couche de cellules. • Le voisinage de Margolus (ci-dessous figure (b)) nécessite un partitionnement du réseau en blocs adjacents de 2 x 2 cellules. La règle d'évolution dépend de la position de la cellule au sein d'un bloc, soit supérieur-droit, supérieur-gauche, inférieur-droit, inférieur- gauche. Le partitionnement du réseau change, lorsque la règle est itérée, en alternant entre une partition paire et une partition impaire. Figure II.5 : voisinage de Moore etendu et de Margolus • On peut établir de plusieurs manières une correspondance entre un réseau hexagonal et un réseau carré. Le voisinage hexagonal est alors envoyé sur un sous-ensemble de six cellules du voisinage de Moore. On énumère les possibilités en considérant le voisinage de von Neumann auquel on adjoint: soit une diagonale (ci-dessous figure (a)), soit les deux voisins nord-est et nord-ouest, nord-est et sud-est, sud-ouest et nord-ouest (ci-dessous figure (b)), ou bien sud-est et sud-ouest. Chapitre II : LES AUTOMATES CELLULAIRES 23 Figure II.6 : variation de voisinage de Von Neuman 7.1.4.conditions aux bords En pratique, le nombre de cellules du réseau est bien évidemment fini. Il faut alors préciser la notion de voisinage pour les cellules aux bords du domaine. L'information concernant la localisation d'une cellule est codée dans la cellule même. Une règle d'évolution différente devrait être appliquée aux cellules de bord. En réalité, plutôt que de définir une règle différente sur les bords, on étend le voisinage des cellules de bord. On définit alors plusieurs conditions aux bords (figure ci-dessous): Périodiques: En dimension deux, cela signifie que les bords gauche et droite, ainsi que supérieur et inférieur sont connectés. Le domaine peut alors être vu comme un tore. Fixes: Le voisinage est complété avec des cellules dont l'état est fixe. Adiabatiques: Le voisinage est complété en dupliquant la cellule. Symétriques: Le voisinage est complété en dupliquant la cellule du voisinage dans la direction opposée. C'est souvent la nature du système étudié qui dicte le choix de la condition aux bords. Figure II.7 : voisinage des cellules de bord. 7.3.La règle d'évolution La dynamique est décrite à l'aide d'une règle d'évolution. La principale source de variété dans l'univers des automates cellulaires est le grand nombre de règles potentielles. La règle d'évolution permet de déterminer l'état d'une cellule au pas de temps suivant comme une fonction de l'état des cellules de son voisinage. En fait, si K est le nombre d'états possibles de Chapitre II : LES AUTOMATES CELLULAIRES 24 chaque cellule et m le nombre de cellules de son voisinage, il existe règles possibles. Pour un automate binaire avec le voisinage de von Neumann (où m=5 ), il existe donc plus de règles possibles. Avec le voisinage de Moore (où m=9 ) , il en existe environ . Une règle est donc une fonction f : { 1,..,k } ͫ → {1, .. ,k} Les règles possibles pour définir un automate cellulaire sont très nombreuses, même avec un petit nombre d'états et un petit voisinage : 2 états 3 états 4 états 5 états 2 Voisins 8 19 683 4 294 967 296 3 Voisins 256 7 625 597 484 987 4 Voisins 65 536 5 Voisins 4 294 967 296 6 Voisins nombre de règles possibles selon nombre de voisin et nombre d’états 7.2.Caractéristiques fonctionnelles d'un automate cellulaire On peut tirer de ce qui précède 5 notions essentielles à la compréhension du fonctionnement d'un automate cellulaire: 7.2.1.Le voisinage A chaque génération, le nouvel état de chaque cellule est déterminé à partir de sa position spatiale dans l'univers de l'automate. C'est en fonction des états (allumé/éteint ou vivant/mort) des cellules voisines à t+n que le nouvel état n d'une cellule est défini. Les transitions d'un état à l'autre de l'automate se font localement pour chaque cellule 7.2.2.Le parallélisme Toutes les cellules constituant l'univers de l'automate sont mises à jour de manière simultanée et synchrone, leur transition de l'état t+(n-1) à l'état t+n se produisant en même temps. 7.2.3.Le déterminisme Pour une cellule, la donnée des états des cellules voisines détermine à elle seule le nouvel état. Certains automates cellulaires dits stochastiques introduisent un facteur probabilité dans la transition : une même configuration de voisinage pourra conduire à différentes nouvelles configurations. Chapitre II : LES AUTOMATES CELLULAIRES 25 7.2.4.L'homogénéité Toutes les cellules de l'automate utilisent les mêmes règles de transition pour déterminer leur état suivant. 7.2.5.La discrétisation Un automate cellulaire se déroule dans le temps de manière discrète, c'est à dire en opposition avec la plupart des phénomènes physiques se déroulant de façon continue. Le temps de l'univers d'un automate avance par saut (t+0, t+1,...,t+n) génération après génération.[12] 8.propriétés 8.1.L'autoreproduction La notion d'autoreproduction à la description de la dynamique d'un système social et vivant, est introduit par la recherche de VON NEUMANN– qu’aboutit à la formulation d'un premier AC qui était animée précisément par le désir de concevoir une « machine autoreproductrice »: le «kinématon » avec 29 états. VON NEUMANN découvrit d'autre part que tout système autoreproducteur, pour sortir d'une impasse logique, devait nécessairement consister en un constructeur-copieur universel, capable non seulement de construire un quelconque objet – y inclus soi-même –, en partant d'une description et mettant à son usage les objets de son monde, mais également de distinguer entre une phase d'interprétation de sa propre description et une deuxième phase de copie de cette description même; une distinction aucun triviale pour un automate mathématique abstrait. Notons que, étonnamment, le principe du constructeur-copieur universel correspond à celui du processus biologique de la méiose, découvert deux ans plus tard. C'est en 1966 que von Neumann réussit à démontrer la possibilité de construire un tel constructeur copieur universel au sein d’un automate cellulaire. Des recherches ultérieures sont démontré que l'ordre de grandeur d'un système autoreproducteur concret, réalisant une telle « machine » au sein d'un AC du type du Jeu de la Vie serait de l'ordre de 10cellules organisées d'une façon complexe et précise. Cet ordre de grandeur fut alors désigné comme « seuil de complexité » en deçà duquel l’autoreproduction n'est point possible. Chapitre II : LES AUTOMATES CELLULAIRES 26 Figure II.8 : propriété de reproduction 8.2.L'auto-organisation L'auto-organisation apparaît lorsqu'on partant d'un état initial aléatoire où chaque cellule a une chance égale d'être dans l'état vivant ou mort. Au bout de quelques pas de temps, ou pour reprendre la terminologie consacrée, au bout de quelques générations, les simulations montrent que l'état du système a perdu son aspect aléatoire. Il comporte des zones totalement mortes, des îlots stables de cellules vivantes, alors que d'autres restent en évolution . 8.3.L'invisibilité On appelle automate inverse l’automate qui permet de revenir aux états précédents. Un exemple simple d’automate inverse est celui de l’automate déplacement Est. Chaque case peut avoir deux états, 0 et 1 (vide ou plein). L’automate regarde l’état de la case voisine Ouest, s’en souvient et agit en le prenant pour nouvel état de la case. Un réseau d’automates Déplacement Est sur un plan a pour effet, d’une génération à l’autre, de déplacer d’une case vers l’Est le motif initial. Son inverse est l’automate Déplacement Ouest. Figure II.9 : l’automate déplacement Est Cet automate possède deux états : 0 et 1, représentés l'un par une case blanche, l'autre par une case noire. D'une génération à l'autre, chaque automate du réseau regarde l'état de son voisin Ouest et le prend pour lui-même. Le résultat est que le dessin se déplace vers l'Est. Chapitre II : LES AUTOMATES CELLULAIRES 27 On a démontré que tous les automates n’ont pas nécessairement un inverse. Pour démontrer qu’un automate n’a pas d’inverse il suffit de trouver deux configurations différentes qui aboutissent à la même configuration. Figure II.10 : automate de type jeu de la vie Cet automate, utilisant les règles du jeu de la vie, commence par un pentamino et évolue en 11 étapes. Au bout de la onzième l'étape 12 est la même que la dixième. On a donc deux configurations différentes qui donnent la même : l'automate de Conway (qui est celui du jeu de la vie) n'est pas inversible. La question qui se pose alors est, lorsqu’on a construit un automate, de savoir si celui- ci est inversible. Et bien cette question est un problème indécidable. 8.4.L'indécidabilité L’une des caractéristiques importantes des automates cellulaires est le caractère d’indécidabilité qui touche nombre de leurs propriétés Ainsi, déterminer si un automate cellulaire possède un inverse est indécidable : il ne sera jamais possible d’écrire un programme prenant en paramètres un automate quelconque et pouvant décider si oui ou non cet automate possède un inverse. De la même façon, l’« avenir » d’un automate est indécidable. On n’a pas de méthode générale permettant de déterminer si un automate ne va pas s’éteindre au bout d’un certain nombre de générations ou s’il va se stabiliser. 8.5.Emergence Exprime l’apparition des propriétés nouvelles qui apparaissent du fait de l’agrégation d’élément au sein d’un ensemble, en opposition total avec les théories.[12] Chapitre II : LES AUTOMATES CELLULAIRES 28 9.Terminologie Nous avons choisi quelques concepts de base que la plupart des AC se partagent : • Voisinage : Pour chaque cellule le passage d'un état à un autre est déterminé en examinant les états des cellules voisines. Seules les interactions locales sont permises entre les cellules. • Parallélisme : Toutes les cellules constituant le réseau cellulaire de l'automate sont mises à jour de manière simultanée et synchrone. • Déterminisme : Un AC est dit déterministe si sa fonction de transition est une fonction classique c'est-à-dire une même entrée donne lieu toujours à la même sortie, donc la donnée des états des cellules voisines détermine à elle seule le nouvel état d'une cellule. Certains AC dits stochastiques introduisent un facteur de probabilité dans leurs fonctions de transitions en faisant intervenir des variables aléatoires, donc une même entrée peut donner lieu à plusieurs sorties différentes, en d'autre terme l'évolution d'une configuration par une même fonction de transition n‘est pas toujours la même. • Homogénéité : On dit qu'un AC est homogène s'il satisfait les conditions suivantes : • La topologie du réseau cellulaire est régulière. • La fonction qui calcule le voisinage doit être uniforme pour toutes les cellules. • L'évolution de l'automate se définit par une seule règle de transition qui s'applique à toutes les cellules. • Discrétisation : Un AC s'évolue dans le temps de manière discrète, c'est-à-dire génération après génération, ce qui s'oppose avec nombreux phénomènes physiques continus.[9] • 10.Le jeu de la vie Il faut préciser que le jeu de la vie n'est pas vraiment un jeu au sens ludique, puisqu'il ne nécessite aucun joueur ; il s'agit d'un automate cellulaire, un modèle où chaque état conduit mécaniquement à l'état suivant à partir de règles préétablies. Le « jeu de la vie » est un automate cellulaire bidimensionnel où chaque cellule peut prendre deux valeurs (« 0 » ou « 1 », mais on parle plutôt de « vivante » ou « morte ») et où son état futur est déterminé par son état actuel et par le nombre de cellules vivantes parmi les huit qui l'entourent : • Si la cellule est vivante et entourée par deux ou trois cellules vivantes, elle reste en vie à la génération suivante, sinon elle meurt. • Si la cellule est morte et entourée par exactement trois cellules vivantes, elle naît à la Chapitre II : LES AUTOMATES CELLULAIRES 29 génération suivante. En apparence simples, ces règles font émerger une forte complexité. On peut sur le même principe imaginer un grand nombre de règles en faisant varier les seuils de naissance ou de survie, ou en ajoutant des états supplémentaires, etc. Parmi ces variations, on peut citer : - Day & Night. - HighLife. - Immigration. - QuadLife. Certains ne prennent en compte pour déterminer les changements d'état d'une cellule que les voisins immédiats de la case considérée, mais d'autres prennent également en compte l'état des cellules voisines dans un rayon de deux cases, voire plus. D'autres attribuent aussi un poids plus important à certaines cases du voisinages qu'à d'autres (WeightedLife).[9] 10.1.Survie Toute cellule ayant exactement deux ou trois cellules voisines survit à la génération suivante. Figure II.11 : règle de survie dans jeu de la vie 10.2.Mort Toute cellule ayant quatre cellules voisines ou plus meurt par étouffement à la génération suivante. Une cellule isolée ou n’ayant qu’une seule cellule voisine meurt d’isolement à la génération suivante. Figure II.12 : règle de mort dans jeu de la vie https://www.techno-science.net/glossaire-definition/Immigration.html https://www.techno-science.net/glossaire-definition/Poids.html Chapitre II : LES AUTOMATES CELLULAIRES 30 10.3.Naissance Sur une case vide comportant exactement trois cellules voisines, il naît une cellule à la génération suivante . Figure II.13 : règle de naissance dans jeu de la vie 10.4.Règles de jeu de vie Le jeu se déroule sur une grille à deux dimensions, théoriquement infinie (mais de longueur et de largeur finies et plus ou moins grandes dans la pratique), dont les cases qu'on appelle des « cellules », par analogie avec les cellules vivantes peuvent prendre deux états distincts :« vivantes » ou « mortes ». Ici, nous travaillerons sur un tore : il n'y aura pas de bords. Sur notre grille, la première colonne sera voisine de la dernière et la première ligne sera voisine de la dernière.[13] Figure II.14 : jeu de vie À chaque étape, l'évolution d'une cellule (la case bleue ci-dessous) est entièrement déterminée par l'état de ses huit voisines de la façon suivante (les cellules vivantes sont les cases noires) : Chapitre II : LES AUTOMATES CELLULAIRES 31 Si une cellule (morte ou vivante) a exactement deux voisines vivantes, elle restera dans son état actuel à l'étape suivante. Si une cellule morte a exactement trois cellules vivantes comme voisines, elle renaîtra à l'étape suivante. Si une cellule a plus de trois voisines vivantes, elle mourra à l'étape suivante. Si une cellule a moins de deux voisines vivantes, elle mourra à l'étape suivante. 10.5.Exemple de jeu de la vie montre l'évolution de quelques configurations simples. Le lecteur pourra s'amuser à suivre à la main sur du papier quadrillé, ou à programmer, l'évolution d'autres configurations. En général, la plupart des configurations évoluent assez rapidement vers un ensemble de configurations attractrices simples: carrés, nids d'abeille, feux clignotants. La configuration du planeur est assez remarquable: on la retrouve identique à elle- même, à une translation près, après quatre itérations. C'est l'un des ingrédients de base pour la construction d'un véritable "ordinateur cellulaire". Avant d'indiquer les principes de base de cette construction, donnons-en les motivations. Une manière d'étalonner la richesse des comportements dynamiques d'un système consiste à démontrer son équivalence formelle avec une machine de Turing, ou calculateur universel, dont les performances sont bien établies. Pour construire une machine de Turing il suffit de savoir construire deux fonctions logiques, dont la négation. Notre ordinateur cellulaire est donc basé sur les éléments suivants: • Les planeurs, jouant le rôle d'un signal binaire se propageant à vitesse constante le long de diagonales du réseau. La présence d'un planeur s'interprète comme un signal 1, son absence comme un 0. • La configuration "canon" expulse des planeurs à intervalles réguliers (toutes les trente itérations). Grâce à elle nous disposons d'un signal à l'état 1. • La collision de deux planeurs les détruit tous les deux. Chapitre II : LES AUTOMATES CELLULAIRES 32 Figure II.15 : exemple de jeu de la vie Evolution de quatre configurations. Le temps varie de gauche à droite. Les deux premières configurations évoluent vers des points fixes, la troisième vers un attracteur de période deux; la quatrième est un planeur, qui se reproduit identique à lui-même à une translation d'un carreau près (vers le bas et vers la droite), après quatre itérations.[13] La figure montre l'évolution d’une exécution du jeu de la vie sur une configuration torique 50 x 50 Figure II.16 : exemple de jeu de la vie 11.Classification de WOLFRAME Il s'agit d'une des premières et sans doute de la plus connue des classifications d'automates cellulaires. Elle est basée sur des expériences, c'est à dire en fait sur l'observation d'extraits de diagrammes espace-temps d'automates à partir de segments initiaux tirés aléatoirement. À partir de là, Wolfram a explicité ([Wol84]) une division en quatre classes disjointes : • Les automates évoluent vers une même configuration uniforme. • Différentes structures, mais stables ou périodiques émergent toujours. • Le comportement est plus compliqué, semble aléatoire, mais avec des motifs qui se répètent. • Apparition de motifs simples mais ayant des interactions, et donc un comportement global complexe. Chapitre II : LES AUTOMATES CELLULAIRES 33 Cette classification a des limites évidentes, en premier lieu l'absence d'un formalisme qui permette de se poser réellement pour un automate donné la question de son appartenance. Cette absence fait aussi que même pour les automates les plus petits, bien connus, la classe n'est pas toujours évidente. Des tentatives ont bien été faites pour formaliser ces classes, en particulier [CY88], mais toutes présentes des limites. Cependant, cette classification a d'abord le mérite de chercher à distinguer différents types de comportements en fonctions de l'évolution à relativement long terme des AC. Et surtout, elle se base sur l'observation du comportement des automates à partir de configurations aléatoires. On est ici à l'opposé de la construction à priori de structure. On cherche à identifier de la structure qui apparaisse de manière visible, c'est à dire fréquemment, dans des diagrammes espace-temps partiels des automates. [12] Enfin elle a motivée toute une série de propositions de classifications qui ont été développées par la suite. Chapitre II : LES AUTOMATES CELLULAIRES 34 Figure II.17 : les 256 automates de Wolframe 11.1.Classe I évolution vers un état fixe et homogène (par exemple la grille complètement vierge ou encore complètement couverte de pions) (dynamiques locales ordonnées de façon homogène).Les automates (0, 4, 16, 32, 36, 48, 54, 60 et 62) sont des exemples de ce type de classe. Chapitre II : LES AUTOMATES CELLULAIRES 35 11.2.Classe II (régulier) évolution vers des structures stables ou périodiques (il peut y avoir des structures locales qui oscillent entre deux états différents, insérées dans ne structure globalement stable) (dynamiques locales ordonnées de façon cyclique).Les automates (8, 24, 40, 56 et 58). Sont des exemples de ce type de classe. 11.3.Classe III (chaotiques) L'évolution conduit à des configurations chaotiques. Tous les états possibles initiaux conduits à apériodiques ("chaotique") modèles. Après un nombre suffisamment grand pas de temps, les propriétés statistiques de ces modèles sont généralement les mêmes pour presque tous les états initiaux. En particulier, la densité des sites non nuls tend généralement à une valeur fixe non nulle. Les automates (2, 10, 12, 14, 18, 22, 26, 28, 30, 34, 38, 42, 44, 46 and 50) sont des exemples de ce type de classe. 11.4.Classe IV évolution vers un système complexe ou des structures émergent (comme dans le jeu de la vie ou on trouve par exemple des planeurs et des possibilités de simuler une machine de Turing) (dynamiques complexes à mi-chemin entre les dynamiques ordonnées et désordonnées) .Les automates (52 et 110)Sont des exemples de ce type de classe. 12.Les automates cellulaires L'automate cellulaire non-trivial le plus simple que l'on puisse concevoir consiste en une grille unidimensionnelle de cellules ne pouvant prendre que deux états (« 0 » ou « 1 »), avec un voisinage constitué, pour chaque cellule, d'elle-même et des deux cellules qui lui sont adjacentes. Chacune des cellules pouvant prendre deux états, il existe 23=8 configurations (ou motifs) possibles d'un tel voisinage. Pour que l'automate cellulaire fonctionne, il faut définir quel doit être l'état, à la génération suivante, d'une cellule pour chacun de ces motifs. Il y a 28=256 façons différentes de s'y prendre, soit donc 256 automates cellulaires différents de ce type. https://www.techno-science.net/definition/6693.html https://www.techno-science.net/definition/5293.html Chapitre II : LES AUTOMATES CELLULAIRES 36 Les automates de cette famille sont dit "élémentaires". On les désigne souvent par un entier entre 0 et 255 dont la représentation binaire est la suite des états pris par l'automate sur les motifs successifs 111, 110, 101, etc. À titre d'exemple, considérons l'automate cellulaire défini par la table suivante, qui donne la règle d'évolution : Motif initial 111 110 101 100 011 010 001 000 Valeur suivante de la cellule centrale 0 0 0 1 1 1 1 0 (cela signifie que si par exemple, à un temps t donné, une cellule est à l'état « 1 », sa voisine de gauche à l'état « 1 » et sa voisine de droite à l'état « 0 », au temps t+1 elle sera à l'état « 0 ».) Si l'on part d'une grille initiale où toutes les cellules sont à l'état « 0 » sauf une, on aboutit à : Figure II.18 : automate cellulaire où chaque ligne est le résultat de la ligne précédente. Par convention cette règle est nommée « règle 30 », car 30 s'écrit 00011110 en binaire et 00011110 est la deuxième ligne du tableau ci-dessus, décrivant la règle d'évolution.[9] 13.Domaine d’application L’idée principale est d’effectuer un modèle discret de l’Univers, plus facile à gérer qu’un modèle continu. Une représentation simpliste en celle des éléments finis, avec un découpage vraiment élémentaire . Voici un panorama des motivations qui expliquent le succès du modèle automate cellulaire : 13.1.en physique : dans un automate cellulaire, tous les calculs résultent de l’application de règles locales – ceci correspond tout à fait aux présupposés usuels de la physique : invariance des lois de la physique par déplacements spatiaux, et invariance des lois de la physique par https://www.techno-science.net/definition/5229.html Chapitre II : LES AUTOMATES CELLULAIRES 37 déphasage temporels, (le troisième principe de la physique étant l’isotropie : l’invariance par rotation !). Dans un automate cellulaire, le fait que toutes les transformations soient locales, induit qu’aucune information ne peut se déplacer dans un automate cellulaire plus vite que la loi d’évolution locale ne le permet. Autrement dit, dans un automate cellulaire, la notion de localité induit une notion de vitesse de la lumière. Cette caractéristique rend le modèle automate cellulaire séduisant aux yeux d’une partie des physiciens (il s’agit là cependant d’un sujet de controverse). En effet, l’évolution récente de la physique fonde une partie de ses théories sur des principes de localité, en mettant en avant l’existence de particules messagères (d). Et pourtant, d’un point de vue théorique, nous ne sommes pas encore prêts à passer à un modèle entièrement discret. 13.2.en biologie : les automates cellulaires sont adaptés à la simulation d’organismes biologiques. Leur structure cellulaire peut servir à reflêter l’organisation des systèmes vivants. En biologie, on est souvent confronté à des phénomènes qui agissent à plusieurs échelles et dont la réactivité dépend d’autres réactions. Les modèles simplistes d’automates cellulaires sont insuffisants pour rendre compte correctement de la diversité des astuces mises en jeu par le vivant (a). 13.3.en sociologie : en économie ; les automates cellulaires sont encore fréquemment employés pour modéliser des phénomènes sociologiques. Là encore, il se trouve que le modèle d’automates cellulaires est trop souvent simpliste et inadapté : la seule grande idée qu’imposent les automates cellulaires, à savoir l’existence d’un état global du système qui se représente à travers l’espace et pour lequel la loi d’évolution est pareille en tout point, ne suffit pas à rendre compte de tout ce que l’on observe. Au niveau des modèles proposés, ce sont le plus souvent, soit des automates cellulaires très complexes, soit des modèles intrinsèquement plus puissants que les automates cellulaires classiques. 13.4.en informatique : ici, ce sont la limite de leur puissance de calcul ainsi que les méthodes de programmation relatives qui captivent les chercheurs. Comment peut-on amener un automate cellulaire à calculer comme on le souhaite ? Un automate cellulaire est une architecture de calcul massivement parallèle. Chapitre II : LES AUTOMATES CELLULAIRES 38 13.5.En cryptographie : il est possible de décoder des messages en les parcourant à l’aide d’un automate qui va par exemple repérer l’occurence de certains motifs. On peut alors raffiner le système de reconnaissance en y ajoutant des probabilités de présence de certains motifs dont peut être coutumier le producteur du code.[12] 14.Conclusion Les automates sont un développement relativement récent de la science moderne. Extrêmement vaste et complexe à étudier, bien que facilement modélisable sur ordinateur, cette discipline est promise à un grand avenir car elle permet de modéliser de façon pratique et simple de nombreux phénomènes physiques. De plus, les « curiosités »mathématiques et philosophiques qu’elles soulèvent font d’elle un domaine passionnant pour les chercheurs. Comme cela a été développé, il s’agit d’autre part d’une nouvelle technique de modélisation qui rompt avec la tradition continue. La mécanique quantique ayant mis en avant, parallèlement à nos connaissances de l’atome un monde appréhendable de façon discrète, il est tentant de se laisser aller à rêver d’un univers, gigantesque automate cellulaire dont la nature calculerait à chaque instant l’évolution. Chapitre III : La modélisation par automates cellulaires Chapitre III :LA MODELISATION PAR AUTOMATES CELLULAIRES 40 1.Introduction Comme le rappelle Y. Guermond, (Guermond, 2005) « l’objectif de la modélisation pour un chercheur est de reproduire au mieux le fonctionnement d’un phénomène géographique, afin d’essayer d’utiliser ensuite le modèle pour tester des hypothèses. L’objectif n’est pas de tester « un » modèle unique, ni de faire fonctionner un système qui s’invente lui-même, en produisant ses règles de manière endogène. Au contraire, le modèle devrait plutôt être envisagé comme un outil de recherche sans ambition normative, que le chercheur construit pas à pas. Les automates cellulaires conviennent bien à cette « modélisation incrémentale », qui permet par des simulations successives de constituer ce « laboratoire virtuel » évoqué par Michael Batty (Batty, 2001) indispensable pour la recherche en sciences humaines et sociales, pour lesquelles c’est la seule voie d’expérimentation ». Dans ce chapitre, nous allons vous montrer comment on va faire la modalisation avec automates cellulaires . Ou Nous pouvons considérer le modèle des automates cellulaires comme le pendant distinct des EDP. Ainsi, chaque fois qu'un phénomène physique est décrit par des équations aux dérivées partielles, on peut proposer des estimations sous la forme d'un humain cellulaire. Il reste à déterminer dans quelle mesure le modèle cellulaire est adapté pour expliquer et prédire le phénomène étudié. Rien n'est garanti dans le cas général et la description de la dynamique globale d'un modèle cellulaire selon sa définition locale peut être au moins aussi difficile que de résoudre un système d'équations aux dérivées partielles. D'autre part, l'humain cellulaire peut être facilement simulé par ordinateur. Ainsi, en analyse numérique, de nombreuses méthodes consistent à estimer certaines quantités (espace, temps et valeur) pour effectuer des simulations numériques (voir Méthode des éléments finis, volumes finis ou différences finies). 2.Etat de l’art : Modalisation de la morphologie et de lamorphogénèse urbaine Si on écarte d’emblée les approches historiques et urbanistiques de la morphologie urbaine (les plans types), et si on s’intéresse davantage à la morphologie urbaine d’un point de vue dynamique, dans sa dynamique de croissance et de développement par exemple, plusieurs modèles morphogéniques ont été développés et explorés récemment : les modèles de croissance cellulaire par percolation en sont les plus anciens représentants et ont ouvert la voie à des modèles plus récents, basés sur des approches par automates cellulaires. Les premiers modèles de croissance de la forme urbaine se sont souvent inspirés de la physique ou de la biologie. Le modèle d’agrégation limitée par diffusion (DLA, pour Chapitre III :LA MODELISATION PAR AUTOMATES CELLULAIRES 41 Diffusion-Limited Agregation) proposé en 1981 par les physiciens T. Witten et L.Sander, issu de travaux menés en cristallogenèse, a été utilisé dans de nombreuses applications en géographie dans les années 1990 (Batty, 1991 ; Batty, Longley, 1994 ; Le Bras, 1996 ; Schweitzer, Steinbrink, 1997 ; Bailly, 1999). Le modèle DLA permet de simuler la croissance de surfaces ou de volumes par arrivées successives et agrégation de particules décrivant une marche aléatoire. La forme résultante de ce processus peut être assimilée à un agrégat fractal. Elle est contrainte par le processus de diffusion des particules et reflète essentiellement le processus de croissance retenu (Pelcé, 2000). Or, rien n’indique que ces processus correspondent à des processus géographiques agissant sur la croissance des formes urbaines, même pour ses composantes les plus volatiles telles que les quartiers d’habitats spontanés (Barros, Sobreira, 2002). La représentation de l’espace par des cellules fut employée dans les modèles d’utilisation du sol de F. Chapin et S. Weiss (1968) et de G. Lathtrop et J. Hamburg (1965). Toutefois dans ces modèles, la dynamique d’une cellule n’était pas dépendante de ses voisines et donc les propriétés topologiques de l’espace géographique n’étaient pas prises en compte. Waldo Tobler (1979) proposa pour la première fois l’utilisation d’automates cellulaires pour la simulation du changement de l’utilisation du sol. Dans le type de modèle proposé, celui des modèles géographiques dynamiques, l’état d’une cellule est fonction de l’état précédent du voisinage, qui inclut la cellule même. Le voisinage définit la zone d’influence géographique d’une cellule. Pour Tobler le voisinage d’une cellule le plus simple est celui qui est défini par un rectangle dont la cellule est le centre, ou celui des cellules adjacentes (Nord, Sud, Est et Ouest) de la cellule. La solution adoptée dans la description du modèle de Tobler est celle de la stationnarité des voisinages des cellules, c’est-à-dire que tous les voisinages possèdent la même forme et la même taille. W. Tobler admet dans son article précurseur que cette définition des voisinages est arbitraire et très éloignée de la réalité: “This model contrasts very nicely with reality in which, for example, an urban resident may have a geographical contact field that differs in size and shape from that of a rural resident, or of a suburbanite” . Mais les difficultés topologiques rencontrées pour définir des voisinages irréguliers constituent pour lui des raisons suffisantes pour adopter dans un premier temps de telles simplifications. L’idée d’une Géographie Cellulaire, basée sur l’influence de chaque unité spatiale de terrain sur ses voisins immédiats fut exploitée plus amplement par d’autres auteurs comme Codd (1968), Albin (1975), Nakajima (1977) et Couclelis (1985, 1988, 1989), Itami (1988), Phipps (1989), Cecchini et Viola (1990) et Takeyama (1996). Chapitre III :LA MODELISATION PAR AUTOMATES CELLULAIRES 42 Ces développements théoriques ont servi de base à l’application des automates cellulaires au milieu urbain dans les années 1990. Les travaux de White et Engelen (1993), Batty et Xie (1994, 1997), Xie (1996), Clarke et al. (1997), Phipps et Langlois (1997) ; Papini et al. (1998) sont quelques exemples de l’application d’automates cellulaires à la modélisation du changement de l’utilisation du sol en milieu urbain. Le modèle de R. White et G. Engelen (1993) est emblématique de ces travaux. Il s’agit d’un modèle stochastique qui utilise un potentiel de transition du type : P = (1 + ∑ ω)*ε Ce potentiel P décrit l’influence exercée sur une cellule par les cellules voisines caractérisées par une certaine catégorie d’utilisation du sol. Le poids ω exercé par une cellule est décroissant avec la distance. Le facteur ε introduit la stochasticité dans le modèle. L’évolution du nombre de cellules devant posséder un certain type d’utilisation du sol est déterminé de manière externe à l’automate, puis les cellules ayant le plus grand potentiel de transition changent d’état pour satisfaire la demande. L’application de ce modèle à la ville de Cincinnati a montré qu’il permet une bonne prédiction de l’évolution urbaine : les variations introduites par le paramètre stochastique n’augmentent pas inconsidérément la variabilité des trajectoires temporelles du modèle. Les zones pour lesquelles des différences entre le comportement du modèle et la réalité de l’évolution de la ville sont significatives peuvent être identifiées et des singularités locales mises en évidence. Cet exemple illustre la manière dont les modèles géographiques fondés sur des automates cellulaires permettent d’analyser le système urbain dans sa dynamique spatio-temporelle. R. White et al. (1997) ont introduit l’effet du réseau de transport et des éléments d’infrastructure comme des contraintes dans leur modèle, dans ce qu’ils ont appelé un “automate cellulaire contraint” (“constrained cellular automata”). Cette notion a été employée par la suite dans les modèles subséquents afin d’intégrer le rôle de l’accessibilité dans les fonctions de transition et tenir compte du facteur de site et des stratégies d’aménagement dans la dynamique des modèles. De nombreux modèles ont été développés dans lesquels le rôle des structures de voisinage est complété par l’inclusion de facteurs de nature spatiale dans les fonctions de transition (Xie, 1996 ; Batty, Xie, 1997 ; Phipps, Langlois, 1997 ; Engelen et al., 2002 ; Barredo et al., 2003 ; Dubos-Paillard et al., 2003). Bien que ces modèles aient intégré l’impact des infrastructures de transport sur l’évolution urbaine, l’effet des réseaux et des modes de transport est difficile à définir dans Chapitre III :LA MODELISATION PAR AUTOMATES CELLULAIRES 43 des structures cellulaires. Même si l’intégration de contraintes spatiales a permis d’introduire une certaine hétérogénéité spatiale dans les modèles, l’approche reste fondamentalement contrainte par des hypothèses spatiales d’isotropie et de stationnarité. Or, ces hypothèses ne permettent pas de rendre compte des relations spatiales complexes en milieu urbain. Certains géographes ont affirmé que ces hypothèses, qui ne sont pas pertinentes pour décrire des structures complexes de l’espace géographique, devraient être abandonnées, au moins en partie. D. O’Sullivan (2001a) a ainsi montré qu’il est nécessaire de redéfinir le formalisme des automates cellulaires à cause de la grande sensibilité des processus spatiaux à des faibles modifications de la structure de l’espace dans lequel ils ont lieu. H. Couclelis (1997) a également ouvert la discussion sur la relation entre l’espace proximal, les automates cellulaires et le formalisme de ce type de modèles à travers une Géo- algèbre (Couclelis, 1997 ; Takeyama, 1996 ; Takeyama, Couclelis, 1997). Son analyse constitue un effort pour résoudre le problème de la relation entre structure et processus dans les modèles géographiques à base d’automates cellulaires. À l’issue de sa réflexion une formalisation d’une théorie géo-computationnelle a été avancée. Les relations spatiales dans les automates cellulaires peuvent être définies de manière explicite à travers une approche basée sur des graphes mathématiques. Le formalisme des graphes peut être employé pour décrire la complexité des relations de proximité et peut être intégré dans les automates cellulaires pour la simulation urbaine (O’Sullivan, 2000, 2001a, 2001b). Le cadre théorique des graphes offre un grand éventail de méthodes et d’outils qui rend aisée l’exploration des relations entre forme et fonctionnement dans la ville. D’un point de vue formel (Takeyama, Couclelis, 1997) un automate cellulaire géographique peut être défini comme un quadruplet (U, V, E, F), avec: • U = {U₁ , U₂,...,Uᵢ ,..., Uₙ}, ensemble fini de n unités spatiales ou cellules. Ces unités sont le plus souvent agencées dans une grille régulière. • V = {V₁ , V₂,...,Vᵢ,..., Vₙ}, ensemble de voisinages définis par un critère topologique (contigüité) ou géométrique (distance entre unités spatiales).Chaque voisinage Vᵢ correspond à la liste des m unités spatiales qui sont voisines de la cellule i selon le critère choisi : Vᵢ= {Uⱼ, Uₓ,..., Uₘ}. • E, ensemble des états possibles des cellules, définies par des variables qualitatives ou quantitatives, généralement discrètes. • F, fonction de transition, probabiliste or déterministe, qui détermine le changement d’état de chaque cellule à chaque pas de temps, selon l’état de la cellule et les états des cellules environnantes : = f ( Eᶠᵢ ; ) Chapitre III :LA MODELISATION PAR AUTOMATES CELLULAIRES 44 On peut donc distinguer dans cette architecture une composante structurelle {U,V} et une composante dynamique {E,F} dans la formalisation mathématique d’un automate cellulaire (AC) : AC = ( { U , V } , { E , F } ) La première composante permet de définir la manière de formaliser les structures spatiales qui conditionnent la dynamique de l’automate. Les automates géographiques ont toutefois le plus souvent été développés en référence à un cadre formel extérieur, selon lequel « les automates cellulaires sont des automates répartis sur les nœuds d’un réseau périodique, c’est-à-dire une structure géométrique discrète, conservée par certaines opérations de translation et de rotation » (Weisbuch, 1989, p. 1). La plupart des références (Nakajima, 1977 ; Xie, 1996 ; Batty, Xie, 1997 ; White, Engelen, 1997 ; Langlois, Phipps, 1997 ; Phipps, Langlois, 1997 ; Engelen et al., 2002 ; Barredo et al, 2003 ; Langlois, 2010) s’inscrivent dans une telle perspective. Afin de prendre en compte d’autres relations spatiales entre unités, D. O’Sullivan proposa l’utilisation d’automates cellulaires à base de graphes (2000, 2001a, 2001b).Ces modèles vont au-delà de la stationnarité en redéfinissant la composante structurelle de l’automate qui manque de réalisme dans un environnement urbain. Un tel automate permet d’analyser l’impact de la morphologie sur le comportement et l’évolution des systèmes urbains, à l’image du modèle Raumulus, conçu dans l’objectif d’analyser l’influence de différents types de proximités sur la croissance d’une surface bâtie autour d’une ou plusieurs centralités urbaines.[15] 3.La modalisation Selon Schmidt et Pavé [2002], la modélisation est la méthode qui permet de représenter un objet ou un phénomène du monde réel par une formule d’un système formel choisi. La simulation quant à elle, ou plus souvent encore la simulation numérique, est la méthode qui permet de mettre en œuvre un modèle et notamment d’obtenir des valeurs calculées pouvant être confrontées à des valeurs observées. Le but de la modélisation et de la simulation est essentiellement de comprendre les phénomènes observés, de tester les hypothèses et les théories ainsi que de prédire le comportement spatiotemporel des systèmes dans divers scenarios et conditions, et de découvrir le fonctionnement des phénomènes géospatiaux grâce, entre autres, aux expériences faites sur ordinateur. les différentes étapes des processus de modélisation et de simulation Chapitre III :LA MODELISATION PAR AUTOMATES CELLULAIRES 45 montrant le passage du monde réel vers l’utilisation des résultats en passant par la modélisation conceptuelle et formelle, l’étude logique et analytique et la validation. Il est toujours difficile de classifier les méthodes de modélisation car celles-ci dépendent en grande partie non seulement des processus qu’on étudie mais aussi des objets pris en compte. On assiste alors assez souvent au développement de méthodes qui ne se fondent que sur l’utilisation d’un outil mathématique qui sert de base de modèle : modèles dynamiques construits sur des équations différentielles; modèles logistiques pour expliquer des processus comportementaux désagrégés, systèmes multi-agent pour analyser des phénomènes de diffusion et de colonisation d’espaces, etc. Ces différents outils donnent naissance, en fonction de leur utilisation, à différentes grandes familles de modèles [Durand Dastès, 1992] : agrégés ou désagrégés, dynamiques ou statiques, explicatifs ou descriptifs, déterministes ou probabilistes. Figure III.1 : Schéma méthodologique général de modélisation et de simulation [Schmidt et Pavé, 2002] Si on désire classifier les méthodes et approches de modélisation en se basant sur la littérature, on peut annoncer que deux grandes catégories de modèles peuvent être citées. D’abord, les modèles empiriques qui sont fondés sur l'analyse statistique des données observées et ne sont généralement applicables que dans les conditions où les observations ont été faites. Puis, les modèles basés sur des processus, qui sont fondés sur la compréhension des processus physiques, chimiques, géologiques, biologiques ou socio-économiques, ainsi que Chapitre III :LA MODELISATION PAR AUTOMATES CELLULAIRES 46 leur description mathématique. Les modèles des systèmes complexes ont souvent recours à la combinaison d’approches empiriques et d’approches basées sur les processus [Mitasova,1998]. Ceci dit, les processus réels sont complexes et incluent souvent des comportements non-linéaires, des composants stochastiques et des boucles de rétroaction sur des échelles spatiales et temporelles différentes. Ainsi, les modèles peuvent représenter les processus uniquement avec un certain niveau de simplification.[1] 4.Modalisation par automate cellulaire Comme la majorité des automates cellulaires, ce modèle repose sur un mécanisme stochastique de transition des cellules qui changent d’état en fonction d’un potentiel de transition qui leur est propre. A l’initialisation du modèle, chaque cellule du modèle possède un état qui correspond à un mode d’occupation du sol parmi les sept classes définies plus haut. Par ailleurs, le modélisateur caractérise chaque état en fonction du mécanisme de transition des cellules qu’il précise de la façon qui suit : • L’état « immuable » gèle les cellules dans leur état initial pour toute la durée de la simulation. • L’état « vacant » permet aux cellules de changer d’état sans restriction. • L’état « fonctionnel » permet aux cellules de changer d’état dans une certaine proportion définie en début de simulation. Dans notre modèle, seules les cellules urbaines et agricoles sont déclarées fonctionnelles et donnent lieu à la définition d’objectifs à atteindre en fin de simulation en terme de surface globale. Pour ces cellules, la transition d’état est fonction d’un potentiel de transition (T) qui dépend des six facteurs suivants : • L’effet de voisinage (P) • L’occupation du sol actuelle (comprise dans P) • Le zonage géographique (Z) • L’aptitude physique (S) • L’accessibilité (A) • Une perturbation aléatoire (random) Pour ces cellules urbaines et agricoles, le potentiel de transition « T » vaut : T = (1+(-log(random)^0.35)*(P+10*S+100*Z+50*A) Les cellules de forêt, de végétation mixte et de sol à nu ont été quant elles déclarées « vacantes », ce qui signifie qu’elles peuvent s’étendre ou au contraire se raréfier sans aucune restriction. Pour ces dernières, le potentiel de transition « T » ne dépend que de l’addition de Chapitre III :LA MODELISATION PAR AUTOMATES CELLULAIRES 47 l’effet de voisinage et de l’aptitude physique (T=P+S). Enfin, les cellules qui constituent la frange littorale et les pentes supérieures à 30% sont déclarées « immuables » : non concernées par la transition d’état, elles ont donc un potentiel de transition nul. Comme on le voit,