Résolution de problèmes par émergence








télécharger 0.83 Mb.
titreRésolution de problèmes par émergence
page8/31
date de publication01.07.2017
taille0.83 Mb.
typeSolution
ar.21-bal.com > documents > Solution
1   ...   4   5   6   7   8   9   10   11   ...   31

Techniques diverses


L'utilisation du concept d'émergence et de mécanismes permettant l'auto-organisation dans un système, afin que celui-ci effectue de la résolution de problèmes au sens large, pose effectivement un cadre spécifique qui oblige le concepteur à (et lui permet de) se conformer à des règles, même si celles-ci, nous l'avons vu, peuvent s'avérer relativement floues. Mais en aucune manière cette utilisation n'impose une technique particulière pour y arriver. La partie 1.2 montre que les systèmes multi-agents sont particulièrement adaptés pour cette approche et sont à mon sens très naturellement utilisables par leur nature intrinsèquement identifiable à la manière dont nous imaginons les processus d'auto-organisation. Pour autant, l'approche SMA n'est pas la seule et certainement pas la première technique utilisée. A l'image de la nature, la diversité est reine et de nombreuses autres techniques ont vu le jour, certaines donnant naissance à des domaines complets de la recherche.

Je vais commencer cette partie par une réflexion sur la résolution de problèmes qui amène à considérer toute recherche de solutions comme une recherche plus ou moins efficace dans un espace d'états. A partir de là, l'exploration de toutes les manières possibles et imaginables pour effectuer cette recherche est valable. L'approche SMA est celle qui nous intéresse le plus mais je ferai une présentation et une analyse rapide de trois domaines ou techniques très différentes des SMA : le calcul évolutionnaire (comprenant notamment les algorithmes génétiques), les réseaux neuronaux (et plus précisément les RN "dynamiques") et les algorithmes de colonies de fourmis. Les AG et les RN sont des domaines historiques forts et regroupent toujours de très nombreuses recherches, ce qui incite naturellement à les étudier pour en extraire des leçons ou des inspirations, même s'ils sont très éloignés des SMA. L'approche par colonies de fourmis par contre montre de nombreuses similitudes avec les SMA et mérite donc elle aussi une analyse.

Les très nombreuses techniques imaginées par la communauté scientifique pour résoudre des problèmes de façon automatisée ne peuvent toutes être traitées et j'ai procédé à des choix en fonction des leurs caractéristiques pour montrer celles qui nous paraissent les plus représentatives. J'en cite cependant quelques unes de plus, dans le dernier point, qui pourraient être des sources d'inspiration supplémentaires. Je montrerai également pour chaque technique qu'il est tout aussi délicat que pour les SMA de mettre en place une utilisation effective de l'émergence et je discuterai de leurs caractéristiques principales qui nous font préférer les SMA pour la programmation émergente.
      1. Introduction : la recherche dans les espaces d'états


Considérons intuitivement ce qu'est la résolution de problèmes au sens large, et donc en premier lieu ce que sont un problème et une solution. Être confronté à un problème signifie en substance que l'état actuel dans lequel nous nous trouvons ne nous convient pas : ses caractéristiques sont indésirables, nous ne possédons pas l'information voulue, les comportements observés ou productibles ne nous conviennent pas, … Une solution à ce problème est alors simplement un autre état qui satisfasse des contraintes précises : ses caractéristiques nous conviennent, nous possédons les bonnes informations, les comportements sont ceux attendus. Par conséquent, la résolution d'un problème constitue le processus et l'ensemble des techniques mises en œuvre pour atteindre cet état solution.
        1. Un exemple minimaliste


Approchons un peu plus formellement un exemple minimaliste : le problème de trouver le "bon" nombre entre 1 et 6. Le "bon" nombre signifie par exemple celui choisi ou tiré au dé par une tierce personne et que nous devons deviner. Il s'agit donc ici de trouver un état particulier parmi 6 états possibles, un état étant simplement le choix d'un nombre. On peut noter qu'il y a exactement 6 états, chacun numéroté sans ambiguïté (espace discret dénombrable fini). L'ensemble de ces états possibles constitue l'espace d'états ou espace de recherche. Proposer une solution à ce problème revient à fournir une façon particulière de procéder afin d'aboutir au bon nombre et constitue donc une stratégie donnée de parcours de l'espace de recherche. Les caractéristiques de la stratégie sont bien sûr de première importance en conditionnant notamment la façon de passer d'un état à un autre (les opérateurs) et les informations nécessaires (et donc comment sont représentés la solution et l'espace d'états).

Pour cet exemple, nous pouvons imaginer deux solutions simples :

  • Le parcours aveugle ou la stratégie aléatoire : tirage au sort d'un nombre entre 1 et 6. C'est une stratégie très générale car elle ne demande aucune information particulière, ni sur chaque état tiré (à part indiquer le succès ou l'échec), ni sur comment parcourir l'espace d'états, ni sur cet espace en lui-même (si ce n'est que le nombre tiré est un entier compris entre 1 et 6). L'atteinte de l'état solution est ici certaine mais au bout d'un temps qui peut être infini, ce qui n'est pas très efficace, il faut en convenir.

  • Par dichotomie : le premier nombre proposé est le "milieu" de l'espace de recherche et on partitionne cet espace entre états "plus petits" et "plus grands" que ce "milieu". Cela fonctionne évidemment uniquement si l'espace d'état présente un ordre total, ce qui est le cas ici. Cette stratégie très efficace (ln(6) états parcourus dans le pire des cas) nécessite cependant une connaissance très poussée du problème : l'ordre total des états, des opérateurs pour atteindre ces états, des opérateurs de partitionnement, et le plus important, l'information pour un état donné sous la forme supérieur/inférieur.


        1. Généralisation


Nous pouvons généraliser la recherche d'une solution dans un espace d'états par :

  • L'état initial : le point de départ dans le processus de recherche. Suivant la stratégie utilisée, cet état initial peut avoir une importance cruciale pour le parcours.

  • L'ensemble des opérateurs (ou actions) qui permettent les transitions d'un état à un autre.

  • L'état solution : l'état sur lequel le parcours doit aboutir le plus efficacement possible.

  • L'espace d'états : l'ensemble des états atteignables par le problème considéré.

  • La stratégie de parcours : comment et en fonction de quelles informations utiliser les opérateurs pour se déplacer au sein de l'espace d'états.

On peut noter qu'il peut y avoir plusieurs états solutions (ou buts), comme il peut y avoir plusieurs états initiaux, ou simplement que l'état initial est quelconque (aléatoire par exemple). Une autre notion importante est celle de "chemin" : la suite des états parcourus ou des opérateurs exécutés pour ce parcours. La solution du problème peut d'ailleurs ne pas être uniquement l'atteinte de l'état solution mais également le chemin ou parcours effectué. De plus, il peut là aussi exister plusieurs chemins et il est alors souvent nécessaire de pouvoir évaluer ces chemins pour trouver le "plus court".

L'espace d'états est en fait une abstraction du monde du problème (par exemple une abstraction du monde réel limité à certains paramètres importants pour le problème si celui-ci est un problème du monde réel). Et il est toujours possible d'effectuer cette abstraction bien qu'elle produise des espaces d'états très différents en fonction du problème et potentiellement difficilement représentables. La notion de recherche dans un espace d'états et donc une notion très générique et, de façon plus ou moins abstraite, la résolution de problème revient alors toujours à trouver une stratégie de parcours dans un espace d'états pour converger vers un état ou ensemble d'états solutions.

A partir de ce constat, toute forme de parcours est envisageable, d'où l'existence d'approches très variées pour la résolution de problèmes. Il peut ainsi exister des techniques très génériques de parcours qui ne se soucient que peu de la nature de l'espace de recherche, comme des techniques très spécifiques et dépendant fortement de cette nature et d'informations associées.
1   ...   4   5   6   7   8   9   10   11   ...   31

similaire:

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

Résolution de problèmes par émergence iconRésolution des problèmes techniques liés au chantier

Résolution de problèmes par émergence iconInstallation logiciels et résolution des problèmes
«Exception e convert error dans le module sismolog exe à 00008 e 19/12/1990 n’est pas une date correcte»

Résolution de problèmes par émergence iconBibliographie La pédagogie par situations-problèmes est aujourd'hui...

Résolution de problèmes par émergence iconDe beaubourg à la république, en passant par le temple; L’Émergence de "la sociale"

Résolution de problèmes par émergence iconPar delà les industries culturelles, l’émergence du capitalisme culturel

Résolution de problèmes par émergence iconMéthodologie de mise en œuvre et problèmes posés par la première application de la réforme 2005

Résolution de problèmes par émergence iconI. presentation de l'homme
«d'avoir des problèmes sur le chantier», ce qui peut se résumer par le tableau suivant

Résolution de problèmes par émergence iconRésumé Le vote par Internet est aujourd’hui une réalité en cours...

Résolution de problèmes par émergence iconEssai sur L’Esprit de l’Azerbaïdjan
«dépassés» par les océans et ceux-ci par l’espace interplanétaire et bientôt intersidéral a donné lieu à l’émergence d’une civilisation...








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