Résolution de problèmes par émergence








télécharger 0.83 Mb.
titreRésolution de problèmes par émergence
page1/31
date de publication31.03.2017
taille0.83 Mb.
typeSolution
b.21-bal.com > documents > Solution
  1   2   3   4   5   6   7   8   9   ...   31
UNIVERSITé TOULOUSE III - PAUL SABATIER

U.F.R. Mathématiques, Informatique et Gestion.

THESE

Pour obtenir le grade de
Docteur de l’université Toulouse III

Discipline : Informatique

Présentée et soutenue par

Jean-Pierre Georgé

Le 6 juillet 2004

Résolution de problèmes par émergence

Étude d'un Environnement de Programmation Émergente

JUry

Claudette Cayrol, Professeur, Université Paul Sabatier Présidente du jury,

François Charpillet, Directeur de recherche INRIA, Rapporteur,

Philippe Mathieu, Professeur, Université de Lille 1 Rapporteur,

Pierre Glize, Ingénieur CNRS Habilité, Directeur de thèse,

Marie-Pierre Gleizes, Maître de conférence, Université Paul Sabatier Co-encadrante,

Jean-Pierre Georgé

Résolution de problèmes par émergence

Étude d'un Environnement de Programmation Émergente

Directeur de thèse :

Pierre Glize, Ingénieur de recherche CNRS, HDR,
IRIT

- Résumé -

Nous proposons la réalisation d'un Environnement de Programmation Emergente, permettant de concevoir des systèmes complexes adaptatifs afin de répondre au problème de complexité croissante de la programmation, au problème du dynamisme du système et de l'environnement, ainsi qu'à la méconnaissance du problème et de la solution. Pour cela, nous utilisons comme bases le concept de l'émergence et la technologie des systèmes multi-agents dont le fonctionnement repose sur des mécanismes d'Auto-organisation coopératifs conformes à la théorie AMAS (Adaptive Multi-Agent Systems).

L'objectif général est alors de réaliser un langage complet de programmation dans lequel chaque instruction est un agent autonome cherchant à être coopératif avec les autres agents du système, ainsi qu'avec l'environnement du système. En dotant ces agents-instructions de mécanismes d'Auto-organisation, nous obtenons un système capable de s'adapter continuellement à la tâche requise par le programmeur (i.e. de s'auto-programmer suivant les besoins). Le travail présenté dans ce document montre la faisabilité d'un tel concept en spécifiant, puis en soumettant à expérimentation, un noyau consacré à un sous-ensemble du calcul mathématique.

Parallèlement, cette approche par Emergence est généralisée à tout type de résolution de problèmes. Nous proposons une réflexion sur les caractéristiques particulières du problème de la programmation émergente en particulier et des problèmes traitables par auto-organisation en général. Nous définissons alors un cadre strict pour l'utilisation des mécanismes de réorganisation afin que ceux-ci permettent l'apparition de ce phénomène si particulier, l'émergence.

Mots Clés : Systèmes Multi-Agents, adaptation, émergence, systèmes complexes, auto-organisation, programmation, résolution de problèmes.
IRIT,
Université Paul Sabatier, 118 route de Narbonne, 31062 Toulouse Cedex 4.

Mes remerciements …


à Pierre Glize, Ingénieur CNRS Habilité rattaché à l'IRIT, mon directeur de thèse. Il n'y avait malheureusement que la place pour mon nom au milieu de la première page de ce document, mais je considère ce travail comme le fruit d'une réelle coopération et il t'appartient autant qu'à moi (c'est-à-dire pas du tout puisqu'il appartient désormais à la Science…). Dire que ce travail n'aurait pu aboutir sans toi ne décrit pas à sa juste valeur tout le temps que tu as consacré à ce travail, que tu m'as consacré. Tes conseils, tes idées et nos discussions (ainsi que ton humour) ont été un guide tout au long de ces années.

à Marie-Pierre Gleizes, Maître de Conférence à l'Université Paul Sabatier, ma co-encadrante. Parmi les souvenirs les plus fort au cours de ma thèse se trouvent indéniablement les nombreuses réunions à trois où l'intense échange d'idées nous faisait explorer des voies auxquelles nous n'aurions pu penser séparément, à l'image du monde de la recherche. Et c'est ce que tu as été pour moi pendant ces années à partager ton bureau : l'image de l'enseignant-chercheur, concrètement, au-delà de mon imaginaire d'étudiant. Plus que toute autre personne, tu m'as appris ce métier si particulier.

à Claudette Cayrol, Professeur à l'Université Paul Sabatier, présidente du jury. Je vous remercie d'avoir accepté spontanément de faire partie de mon jury, de l'avoir présidé consciencieusement et surtout d'avoir montré autant d'intérêt pour mon document de thèse.

à François Charpillet et Philippe Mathieu, respectivement Directeur de recherche INRIA à Nancy et Professeur à l'Université de Lille 1, rapporteurs. Quand l'Homme est jugé, il ne peut qu'espérer en l'honnêteté, l'intégrité et la compétence de ses juges. Je pense sincèrement n'avoir eu aucun souci à me faire quant aux miens et je vous en suis très reconnaissant. De plus, le réel intérêt scientifique que vous avez porté à mon travail, et ce malgré les délais contraignants que vous avez bien voulu accepter, a contribué à rasséréner cette période difficile pour tout doctorant.

à Jean-Luc Soubie, Ingénieur de recherche INRIA Habilité, rattaché à l'IRIT, mon ex-directeur de thèse pour raisons administratives. Plus que le fait d'avoir bien voulu être mon directeur sur le papier au début de ma thèse, c'est le regard sur la recherche au-delà de l'équipe que je voudrais évoquer ici. Tu m'as permis de mieux appréhender le dédale du monde de la recherche et ses coulisses (le "panier à crabes" ?) grâce à ton honnêteté et ta franchise.

à l'équipe SMAC et en particulier Gauthier Picard, Davy Capera, Jean Pierre Mano, Carole Bernon, Valérie Camps, Christine Régis et André Machonin. Vous m'avez offert des conditions de travail et un environnement de tous les jours si appréciables. C'est cet ensemble de multiple petites choses que l'on remarque ou non, ces conseils et ces discussions, scientifiques et autres, qui ont fait que même en de périodes difficiles, mon lieu de travail est toujours resté agréable.

à mes amis David Fauthoux, David Chemouil, Ulrich Roissard, Vincent Labatut, Gauthier Picard et Davy Capera (pour ces deux dernier, oui, on peut être dans deux catégories à la fois, mélangeons donc le plaisir et le travail). On ne peut espérer atteindre une plénitude professionnelle sans l'équilibrer avec un épanouissement personnel. Et vous avez su, sciemment ou inconsciemment, constamment agir sur la balance, que ce soit d'un côté ou de l'autre (vous la relierez deux fois, celle-là…).

à ma famille, Gitti, Nico et Saskia, Oma und Opa. Ich weis dass ihr immer an meinem erfolg geklaubt habt und ihr habt mir die Möglichkeit geschenkt mein Traum zu realisieren. Eine bessere Familie hätte ich mir nicht wünschen können. Danke für alles.

à Émilie. Ce document te doit une bonne part de sa clarté et de sa qualité d'écriture. Les lecteurs apprécieront. Moi j'ai apprécié la façon dont tu as su te faire une place dans ma vie de doctorant surchargé d'activités pour finir par te rendre indispensable.

Sommaire (vue d'ensemble)

Mes remerciements … 5

5

Sommaire (vue d'ensemble) 9

Sommaire (vue détaillée) 11

Introduction : Problématique et Programmation Émergente 15

1.1. Problématique 15

1.2. Description de l'idée de "programmation émergente" 18

1.3. Généralisation : la résolution de problèmes par émergence 20

1.4. Structure et contenu du document 22

Chapitre I. Le phénomène d'émergence et son utilisation 27

1. Émergence 27

1.2. Auto-organisation et systèmes multi-agents 42

1.3. Techniques diverses 53

Chapitre II. Théorie AMAS Technologie AMAS 73

1. Introduction aux travaux de l'équipe 73

1.2. La théorie AMAS 76

1.3. La Technologie AMAS 81

1.4. Vers une distribution industrielle : la méthodologie ADELFE 86

1.5. L'apport de mes travaux dans l'approche AMAS 89

1.6. Étude et discussion de quelques applications AMAS 92

Chapitre III. EPE :
Environnement de Programmation Émergente 105


1. La programmation émergente : introduction et description détaillée 105

1.2. Le "Toy Problem" de la Factorielle : un sous-problème représentatif 122

1.3. Résultats expérimentaux et analyse des organisations 151

1.4. Comportements d'auto-organisation coopératifs informés dans un système élémentaire 170

Chapitre IV. PE : implémentation 189

1. Introduction 189

1.2. Architecture 194

1.3. Le logiciel EPE 206

Conclusion : Enseignements et Perspectives 211

1. De l'Expérience aux Enseignements 211

1.2. Perspectives 216

1.3. Ma conclusion 222

Glossaire 227

Bibliographie 231

1. Problématique 231

1.1. Emergence 232

1.2. Auto-organisation et systèmes multi-agents 234

1.3. Techniques diverses 237

1.4. Théorie AMAS – Technologie AMAS 240

1.5. EPE et la Programmation Émergente 242

Sommaire (vue détaillée)

Mes remerciements … 5

5

Sommaire (vue d'ensemble) 9

Sommaire (vue détaillée) 11

Introduction : Problématique et Programmation Émergente 15

1.1. Problématique 15

1.1.1. Les besoins futurs en informatique 15

1.1.2. Des sources d’inspiration 17

1.1.3. Synthèse 17

1.2. Description de l'idée de "programmation émergente" 18

1.2.1. Un système multi-agent pour la programmation émergente 19

1.2.2. Un environnement de néo-programmation 19

1.2.3. Le néo-système produit 20

1.2.4. Ma contribution à la programmation émergente 20

1.3. Généralisation : la résolution de problèmes par émergence 20

1.3.1. La programmation émergente : un outil universel 21

1.3.2. La résolution par émergence 21

1.3.3. Ma contribution à la résolution de problèmes par émergence 22

1.4. Structure et contenu du document 22

Chapitre I. Le phénomène d'émergence et son utilisation 27

1. Émergence 27

1.1.1. Historique et définition de l'émergence 28

1.1.2. L’émergence en informatique 32

1.1.3. Les domaines scientifiques connexes 33

1.1.4. Nécessité/utilité du concept d'émergence 34

1.1.5. Exemples de systèmes émergents 36

1.2. Auto-organisation et systèmes multi-agents 42

1.2.1. Auto-organisation : définition et contexte 42

1.2.2. Auto-organisation, émergence et règles de comportement locales 45

1.2.3. Auto-organisation dans les systèmes multi-agents 47

1.3. Techniques diverses 53

1.3.1. Introduction : la recherche dans les espaces d'états 53

1.3.2. Calcul évolutionnaire et algorithmes génétiques 55

1.3.3. Réseaux neuronaux "dynamiques" 60

1.3.4. Algorithmes de colonies de fourmis et optimisation par essaims particulaires 65

1.3.5. Autres techniques 69

Chapitre II. Théorie AMAS Technologie AMAS 73

1. Introduction aux travaux de l'équipe 73

1.1.1. Au sujet des systèmes multi-agents 74

1.1.2. L'approche émergente comme fondement 74

1.2. La théorie AMAS 76

1.2.1. Théorème de l’adéquation fonctionnelle 76

1.2.2. Adapter le système par ses parties 79

1.3. La Technologie AMAS 81

1.3.1. Les composantes d'un agent AMAS 81

1.3.2. Les Situations Non Coopératives (SNC) 82

1.3.3. L'algorithme de coopération 83

1.4. Vers une distribution industrielle : la méthodologie ADELFE 86

1.4.1. Contenu 86

1.4.2. Visibilité internationale 86

1.4.3. Distribution industrielle 87

1.4.4. Living Design 87

1.5. L'apport de mes travaux dans l'approche AMAS 89

1.5.1. L'approche expérimentale indispensable 89

1.5.2. L'approche expérimentale dans l'équipe 90

1.5.3. Un pas plus loin : le problème de la programmation émergente 91

1.6. Étude et discussion de quelques applications AMAS 92

1.6.1. Eléments pour la classification de problèmes 92

1.6.2. Quelques problèmes traités par la théorie AMAS 97

1.6.3. Éléments caractéristiques de la programmation émergente 102

Chapitre III. EPE :
Environnement de Programmation Émergente 105


1. La programmation émergente : introduction et description détaillée 105

1.1.1. L'idée de programmation émergente 106

1.1.2. Travaux connexes 107

1.1.3. EPE : Description 110

1.1.4. Les difficultés 120

1.2. Le "Toy Problem" de la Factorielle : un sous-problème représentatif 122

1.2.1. Présentation 122

1.2.2. Justification et avantages 122

1.2.3. Description du sous-ensemble d’agents 125

1.2.4. Fonctionnement 128

1.3. Résultats expérimentaux et analyse des organisations 151

1.3.1. Résultats expérimentaux et difficultés 151

1.3.2. Analyse statistique des organisations 157

1.3.3. Conclusion 167

1.4. Comportements d'auto-organisation coopératifs informés dans un système élémentaire 170

1.4.1. Utilité d'un système élémentaire 170

1.4.2. Description du système élémentaire choisi 172

1.4.3. Description de la stratégie d'auto-organisation informée 174

1.4.4. Résultats expérimentaux 183

1.4.5. Un premier pas de "Scaling up" 185

1.4.6. Conclusion 186

Chapitre IV. PE : implémentation 189

1. Introduction 189

1.1.1. Quelques informations générales 189

1.1.2. Le manque de plates-formes SMA réellement génériques 190

1.1.3. La question de l'autonomie et de la simulation 191

1.1.4. Des agents "simples" mais des comportements complexes 193

1.2. Architecture 194

1.2.1. Architecture générale 194

1.2.2. Les types d'agents 195

1.2.3. L'environnement du système 196

1.2.4. La gestion d'accointances 197

1.2.5. La communication 198

1.2.6. La réorganisation 202

1.2.7. L'interface graphique 205

1.2.8. Les outils d'observation 205

1.3. Le logiciel EPE 206

Conclusion : Enseignements et Perspectives 211

1. De l'Expérience aux Enseignements 211

1.1.1. Des difficultés imprévues 211

1.1.2. Une classe particulière de problèmes 212

1.1.3. La difficulté d'implémentation 213

1.1.4. Les mécanismes d'auto-organisation, la coopération et les SNC 214

1.1.5. Auto-organisation et émergence 215

1.2. Perspectives 216

1.2.1. Vers une généralisation à un langage complet 217

1.2.2. Vers un environnement complet 220

1.2.3. Des exemples réels 221

1.3. Ma conclusion 222

Glossaire 227

Bibliographie 231

1. Problématique 231

1.1. Emergence 232

1.2. Auto-organisation et systèmes multi-agents 234

1.3. Techniques diverses 237

1.4. Théorie AMAS – Technologie AMAS 240

1.5. EPE et la Programmation Émergente 242
  1   2   3   4   5   6   7   8   9   ...   31

similaire:

Résolution de problèmes par émergence iconCours ppa-6015
«L’approche par problèmes est une approche pédagogique qui consiste à confronter l’élève à des problèmes signifiants et motivants,...

Résolution de problèmes par émergence icon1. MÉThode de travail 1 MÉthode scientifique et résolution de problèmes

Résolution de problèmes par émergence iconUn scénario d’activité pédagogique
«00uq : Appliquer les méthodes de l’algèbre linéaire et de la géométrie vectorielle à la résolution de problèmes». Pour en arriver...

Résolution de problèmes par émergence iconJ. Ardoino Les postures (ou impostures) respectives du chercheur, de l’expert et du consultant
«establishment» du savoir, au cours de l'émergence difficile des sciences de l'homme, plus naturellement ouvertes, par leur ancrage...

Résolution de problèmes par émergence iconPetit détour par les neurosciences pour mieux comprendre les problèmes dentaires

Résolution de problèmes par émergence iconRésolution a été

Résolution de problèmes par émergence iconRapport de la Mission conduite par
«jeunes pousses» et l’émergence des «Business Angels». Comme tout phénomène brutal une telle croissance ne pouvait se produire "à-coups"...

Résolution de problèmes par émergence iconSurpris par ce retour alors que cela faisait bien quinze ans que...
«innéistes» pour traiter de divers problèmes psychologiques, politiques ou sociaux

Résolution de problèmes par émergence icon"Emergences des Maladies Parasitaires et Infectieuses/Emergence of...

Résolution de problèmes par émergence iconContenus scientifiques (problèmes, plan élève, activités, mots clés)
La dérive des continents. Les fixistes nient tout déplacement continental, en s'appuyant sur les connaissances en physique de l'époque....








Tous droits réservés. Copyright © 2016
contacts
b.21-bal.com