Résolution de problèmes par émergence








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

Calcul évolutionnaire et algorithmes génétiques


Le pan de recherche appelé calcul évolutionnaire (evolutionary algorithms) est l'exemple même de l'approche informatique inspirée de la nature. Partant du constat fascinant de l'incroyable capacité d'adaptation du vivant à son environnement qui produit une variété phénoménale avec pourtant deux caractéristiques fondamentales : la viabilité et l'efficacité. Ce sont deux caractéristiques également indispensables lorsqu'il s'agit de créer des systèmes artificiels : viabilité dans le sens où ces systèmes doivent effectivement exhiber les comportements attendus par l'utilisateur (adéquation fonctionnelle) et cela de façon efficace (optimisation).

Le calcul évolutionnaire repose en premier sur les théories Darwiniennes de l'évolution des espèces par des mécanismes d'héritage génétique et de sélection naturelle. Il repose sur un ensemble de méthodes de résolution et d'optimisation stochastique qui représentent un modèle simplifié des principes biologiques associés et peut alors être considéré comme du "Darwinisme Artificiel".

Les algorithmes génétiques constituent la version la plus étudiée (et une des plus anciennes) de ces techniques qui se différencient dans leurs façons d'aborder les représentations du problème, les mécanismes génétiques et la sélection naturelle concrètement, mais ces versions sont toutes basées sur les mêmes principes de base.
        1. Principe de fonctionnement


Le principe fondamental est la manipulation de populations d'individus qui représentent des points de l'espace de recherche pour un problème donné. Il s'agit alors d'appliquer stochastiquement un ensemble d'opérations sur chacun des individus tout en les catégorisant par générations du processus artificiel d'évolution. Ces opérations sont de deux types distincts : la sélection, basée sur le jugement de la "performance" d'un individu au regard du problème posé (fonction de fitness, i.e. de coût, performance, évaluation), et les mécanismes génétiques, généralement les croisements (crossover) et les mutations, qui produisent de nouveaux individus.

Si ce principe est appliqué correctement, il produit alors une recherche stochastique dynamique dans l'espace de recherche qui converge vers un état d'optimum global pour le problème traité. Une bonne partie du travail théorique autour du calcul évolutionnaire se concentre d'ailleurs sur le problème de la convergence et de l'influence des paramètres sur cette convergence (notamment sa vitesse). Car en dépit de l'apparente simplicité du principe, l'implémentation pour un problème réel peut s'avérer extrêmement compliquée à cause d'une grande sensibilité du processus à de nombreux paramètres (comme le nombre d'individus et les poids des choix stochastiques).

Le traitement d'un problème donné commence par le choix d'une représentation sous forme de génome de chaque état de l'espace de recherche (un génome est un ensemble de gènes qui codent une solution potentielle au problème) et par le choix d'une population d'individus (chaque individu contient un génome et la plupart du temps n'est constitué que de ce génome) théoriquement quelconque (mais l'influence de la population initiale sur le processus peut être primordiale pour certains problèmes). Le processus est alors intégré à une boucle principale au sein de laquelle chaque itération représente une génération et ses individus sont appelés les parents de la prochaine génération. Une itération contient approximativement (de nombreuses variations sont possibles), et dans l'ordre, les étapes suivantes :

  • Sélection : cette étape sélectionne les parents qui vont être utilisés pour la reproduction en fonction d'une évaluation de la performance ou valeur d'un individu. Cette évaluation est effectuée par la fonction de performance (fitness) qui est censée croître au cours du processus.

  • Reproduction : les parents sélectionnés sont accouplés au hasard et donnent habituellement deux enfants à partir du génome des parents avec une certaine probabilité d'un croisement (crossover), le point de croisement étant également choisi au hasard. Ensuite chaque enfant, résultant d'un croisement ou non (simple recopie d'un des parents) subit, à nouveau avec une certaine probabilité, une mutation qui peut remplacer certaines parties du génome (création de nouveauté).

  • Évaluation : les enfants sont alors également évalués par la fonction de performance.

  • Remplacement : cette étape crée la nouvelle génération d'individus en choisissant les plus aptes parmi le pool des parents et des enfants afin de garder un nombre stable d'individus.

  • Cas d'arrêt : Le processus s'arrête lorsqu'un certain critère a été atteint, généralement un certain nombre de générations ou un seuil défini pour la fonction de performance.


        1. Références


Le domaine du calcul évolutionnaire trouve ses débuts dans les années soixante avec les travaux de John Holland, L.J. Fogel et Ingo Rechenberg, chacun donnant un nom spécifique à ses travaux, et qui constituent encore aujourd'hui des sous-classes du concept global : algorithmes génétiques pour Holland [Holland 75] [Goldberg 89] [Dejong 75], programmation évolutionnaire (evolutionary programming) pour Fogel [Fogel 66], et stratégies évolutionnaires (evolution strategies) pour Rechenberg [Rechenberg 73] [Schwefel 77]. On peut considérer que Holland était plus intéressé par les processus d'adaptation dans les systèmes naturels alors que Rechenberg et Fogel y voyaient un moyen de résoudre des problèmes d'optimisation. De ce fait, il existe des différences algorithmiques mais les principes restent les mêmes que ceux décrits précédemment.

Cependant, s'il ne fallait citer qu'une seule personne, ce serait John R. Koza avec notamment la série de livres sur la programmation génétique (genetic programming) [Koza 92] [Koza 94] [Koza 99] [Koza 03], problème très proche de la programmation émergente. Ces travaux illustrent bien l'approche par un compte rendu détaillé et une description minutieuse de travaux expérimentaux sur un vaste domaine d'exemples. Bien qu'axés essentiellement sur les Algorithmes Génétiques, ils fournissent de nombreuses données pour la compréhension et la réflexion sur la calcul évolutionnaire en général. Les travaux de Karl Sims poussent également à la réflexion quand on considère les résultats fascinants et surprenants sur les tentatives de déplacement de créatures virtuelles [Sims 94].

Dans la communauté française, on peut par exemple noter les travaux d'Evelyne Lutton [Lutton 03] avec entre autre l'utilisation de fractales pour la compréhension des fonctionnements du calcul évolutionnaire, ou de Michele Sebag [Ratle 03] qui s'est également penchée sur les problèmes de programmation génétique. De façon générale, de nombreux noms de la communauté française se retrouvent lors des régulières Journées Evolutionnaires Trimestrielles (JET) de l'AFIA qui liste également le groupe de travail "Evolution Artificielle" associé.
        1. La question de l'émergence et de la convergence


Pour pouvoir utiliser le calcul évolutionnaire concrètement pour la résolution de problèmes, le principe décrit précédemment doit être implémenté de façon à ce que le processus converge effectivement vers une solution, et cela le plus rapidement possible. Comme pour la discussion sur l'utilisation de l'auto-organisation (cf. 1.2.2), tout l'enjeu repose sur notre capacité à mettre en place des mécanismes qui permettent au système de progresser vers la solution sans pour autant avoir à lui indiquer explicitement comment y arriver, i.e. lui indiquer le chemin en quelque sorte dans l'espace de recherche.

Une grande partie des mécanismes repose sur une base stochastique : choix des couples de parents, choix des croisements, choix du locus pour le croisement, choix de la mutation, etc… Ces mécanismes ne servent donc en eux-mêmes qu'à explorer rapidement, avec une priorité vers la nouveauté et en évitant le systématique, l'espace des possibilités de solutions. Le seul élément qui indique une "direction" d'exploration est en fait la fonction de performance. Cette fonction, par l'évaluation des individus qui sert ensuite pour leur sélection, va contraindre les opérations stochastiques à parcourir l'espace de recherche d'une manière précise dépendant de cette fonction de performance. En effet on n'effectue ces opérations que sur les individus jugés les plus performants pour espérer obtenir des enfants héritant de la performance des parents. Et ces enfants sont eux-mêmes introduits dans la nouvelle génération seulement s'ils sont jugés performants à leur tour. La fonction de performance est donc le seul attracteur du calcul évolutionnaire.

Or l'histoire du calcul évolutionnaire et les nombreux exemples traités ont montré qu'il peut s'avérer très délicat de trouver la bonne fonction de performance pour un problème donné. Si cette fonction sélectionne de façon erronée les individus, le processus représente alors un simple parcours au hasard de l'espace de recherche. D'autre part, un individu peut dans certains types de problèmes posséder un génome présentant peu de similitudes avec une solution quelconque et pourtant afficher une bonne performance avec certains jugements simplistes de la performance. Ceci n'est pas un problème en soi si l'erreur produite par l'utilisation de cet individu peut être résorbée par le reste du processus.

Mais la tentation est alors grande de ne pas regarder simplement les résultats produits par les individus mais directement leurs génomes. Si un jugement est effectué sur la structure du génome, alors nous introduisons une indication du comment atteindre la bonne solution. Par exemple, s'il s'agit d'individus censés parcourir un labyrinthe, nous pouvons noter que se tourner quatre fois vers la droite successivement ramène à la position initiale et est donc inutile. Le processus peut alors éliminer les parties du génome codant ces quatre opérations au sein des individus présentant de tels génomes. De telles opérations peuvent être utiles quand elles sont réalisables parce qu'elles épurent le génome, mais plus le problème est complexe, moins ce genre d'opérations semble réaliste. Il faut alors noter que ces opérations produisent des effets sur l'évolution des individus qui n'ont absolument rien d'émergent. Rien de surprenant dans le fait que les individus de l'exemple (certes simpliste) ne tournent pas sur eux-mêmes.
        1. Spécificité caractéristique et le problème de la programmation émergente


Comme indiqué dans les références, un pan du calcul évolutionnaire, la programmation génétique, s'intéresse effectivement à produire des programmes, généralement par assemblage d'instructions d'un langage fonctionnel ou équivalent (cf. également l'exemple présenté dans le Chapitre III., point 1.1.2.2.). Plusieurs caractéristiques du calcul évolutionnaire ont cependant fait porter notre choix sur les SMA à auto-organisation, en particulier intégrant la notion de coopération.

Tout d'abord, la fonction de performance comme seul attracteur pour la convergence ainsi que la difficulté à trouver une fonction efficace poussent vers la recherche d'autres techniques dans l'espoir de ne pas rencontrer les mêmes difficultés. L'utilisation de la coopération lors des opérations d'auto-organisation en est une des idées clés et se place en opposition des opérations stochastiques du calcul évolutionnaire : la coopération constitue un ensemble d'attracteurs à l'intérieur du système.

Ensuite, le principe même de l'évolution implique l'utilisation d'une population d'individus. En pratique, cette population doit être relativement large et le nombre de générations est élevé. Comme de plus il faut juger tous les individus de la population avec la fonction de performance, la puissance de calcul nécessaire est énorme. Mais le problème vient surtout du fait qu'un individu en lui-même n'a rien d'adaptatif : c'est l'espèce (l'ensemble des individus au cours des générations) qui est adaptative. Le calcul évolutionnaire produit en fait un individu, ou un ensemble d'individus au bout d'un certain nombre de générations, puis est censé s'arrêter. On récupère ensuite cet individu pour l'utiliser concrètement. Comment appliquer ceci dans un robot adaptatif plongé dans un environnement dynamique ? On peut imaginer des fonctionnements qui contournent le problème en injectant à chaque génération l'individu le plus performant pour être le contrôle réel du robot, mais les autres individus doivent aussi être évalués par rapport à leurs performances dans l'environnement. Seule la simulation du monde en interne permet le jugement massivement parallèle nécessaire, ce parallélisme que permet la nature mais ne convient pas aux systèmes artificiels que nous voulons concevoir.
      1. Réseaux neuronaux "dynamiques"


De la même manière que l'évolution des espèces a inspiré le Calcul Evolutionnaire, le fonctionnement du cerveau, du moins tel que nous le concevons, a inspiré le domaine des réseaux neuronaux (RN). Dès que les mécanismes de base ont été découverts (neurone, dendrite, axone, propagation de signal, seuil d'activation, …), la fascination n'a cessé de croître pour ces mécanismes pourtant simples qui supportent un vaste panel de fonctions supérieures, de comportements réflexes chez des animaux simples jusqu'à l'intelligence, la conscience et tous les processus cognitifs de haut niveau inhérents à l'être humain. La tentation de reproduire artificiellement ces mécanismes paraît alors toute naturelle.

Un RN est un modèle formel simplifié de l'activité des neurones biologiques, d'autant plus simplifié que la recherche sur le cerveau n'a cessé de progresser et que nous nous rendons compte que les mécanismes de base ne sont en fait qu'une petite partie d'un ensemble beaucoup plus complexe (rôle important de l'activité chimique, complexité de la morphogenèse du cerveau, plasticité continue sur le cerveau adulte, …). Mais ce modèle produit déjà des résultats avancés, ou plutôt ces modèles car de nombreuses variations existent là aussi, se distinguant par des variations techniques ou des évolutions des mêmes principes de base. A strictement parler, nous devrions utiliser l'appellation RNA (pour RN Artificiel) car les fonctionnements techniques finaux sont loin de la complexité de réseaux de neurones biologiques.
        1. Principe de fonctionnement des réseaux neuronaux


Un RN est un réseau composé généralement d'un grand nombre d'unités de calcul très simples (les neurones formels) avec chacun une mémoire limitée. Ces neurones formels sont connectés par des canaux de communications unidirectionnels qui propagent des valeurs numériques traitées telles quelles (pas de communication symbolique). Le fonctionnement des neurones formels est local et ne prend en compte que ses propres données et celles disponibles sur ses connections d'entrée. La plupart des RN ont une règle d'apprentissage qui modifie les poids des connexions en fonction des stimuli présentés en entrée au RN et une certaine classe de RN modifie ces poids également par rétro-propagation d'un feedback. Pour simplifier, les RN "apprennent" par l'exemple comme un enfant apprend à reconnaître une "table" quelle qu'en soit la forme (et donc le concept de "table") uniquement en voyant des exemples de tables.

Dès que l'on crée un RN, au moins les quatre points suivants sont à traiter :

  • Les caractéristiques des neurones formels : il faut définir comment le neurone formel somme ses entrées, comment il les transforme en fonction d'activation, comment fonctionne son seuil d'activation, comment ce seuil d'activation se modifie au cours du temps, et comment l'activation est modifiée pour être propagée sur son axone (ses sorties).

  • La connectivité : il faut spécifier les connexions des neurones formels (quel neurone est connecté avec quel autre, avec la distinction entrée/sortie). Il s'agit en fait de définir le graphe à arcs directionnels représentant le réseau. Une des caractéristiques principales de ce graphe est l'association de "poids" sur les arcs. Ces poids qui varient au cours du temps servent au calcul de la propagation des signaux et représentent en quelque sorte la "connaissance" acquise par le RN. On choisit alors généralement de représenter le RN par une matrice qui liste l'ensemble des poids pour chaque connexion entre deux neurones formels, un poids nul signifiant l'absence de connexion. Il faut noter qu'il existe deux catégories de neurones formels particulières, distinguables par le fait qu'ils possèdent au moins une connexion à autre chose qu'à un neurone formel. La couche d'entrée regroupe les neurones dont une entrée au moins est connectée à l'extérieur du RN, i.e. à son environnement (par exemple un capteur quelconque pour un robot). Symétriquement, la couche de sortie regroupe les neurones formels dont une sortie au moins est connectée à l'environnement du RN (par exemple un affichage, ou un effecteur pour un robot) et représente le résultat produit par le RN.

  • La répartition des poids dans la matrice donne également une information sur le type de RN représenté en fonction de la répartition des connexions. On peut par exemple reconnaître l'existence ou non de boucles au sein du RN, ces boucles étant importantes pour la caractéristique de non-linéarité. Il existe également des RN à connexité totale (tout neurone est relié à tout autre dans les deux directions).

  • La règle de propagation : il faut spécifier comment un signal d'activation se propage en sortie d'un neurone formel jusqu'aux entrées des neurones avec lesquels il est connecté. Généralement, une version très simple est utilisée qui se contente de propager à tous les neurones de sortie en un temps unitaire le stimuli d'activation produit en sortie. Mais des versions prenant en compte un temps de propagation ou une atténuation du signal existent.

  • La règle d'apprentissage : il s'agit de spécifier comment les poids sur les liens reliant les neurones se modifient au cours du temps. Une des règles les plus simples consiste par exemple à considérer que le poids d'un lien entre deux neurones augmente quand l'activation de l'un entraîne de façon répétée et persistante l'activation de l'autre. Il existe de nombreuses variations de ce principe mais elles sont toutes limitées par le fait de ne produire qu'une augmentation des poids. D'autres mécanismes sont alors rajoutés pour pouvoir diminuer également les poids.


        1. Réseaux neuronaux "dynamiques"


La partie la plus importante de l'apprentissage chez l'Homme se faisant pendant la petite enfance alors que la morphogenèse du cerveau est très importante, et se poursuivant encore chez l'adulte, il semble naturel d'affirmer que ce processus est primordial. Pourtant, la plupart des approches des RN imposent une topologie relativement statique du réseau. Des travaux plus récents commencent à s'intéresser aux mécanismes permettant de conférer aux RN la plasticité de leurs pendants biologiques. Il s'agit alors de permettre la création de neurones au sein du réseau ainsi que l'apparition de liens entre neurones n'en possédant pas initialement.

La capacité d'auto-organisation du RN se trouve alors décuplée et l'apparition de comportements réellement nouveaux produirait un potentiel d'adaptation et d'apprentissage certainement plus proche de son modèle biologique. On parle alors de RN "dynamiques" mais il faut noter que cette appellation n'est pas généralisée, le terme de "dynamique" étant par ailleurs également utilisé pour certains ajustements de poids au sein de RN plus classiques.

Cette approche n'en est concrètement encore qu'à ses débuts comme le montre le travail bibliographique de Emile Fiesler [Fiesler 94] sur ce sujet et la visibilité réduite de ce champ depuis. Elle nous semble pourtant indispensable pour profiter pleinement du principe d'auto-organisation.
        1. Références


L'origine des RN est relativement ancienne puisque qu'elle date des années quarante, bien avant que l'on puisse réellement simuler sur ordinateur les fonctionnements théoriques développés alors. Mais l'évolution de la discipline ne s'est pas faite en continue jusqu'à nos jours. En effet, les fluctuations des courants de pensée dans l'I.A. en général avec notamment la forte poussée du symbolisme ont fait varier l'intérêt (comme les financements) de la discipline. Il est alors intéressant de présenter les références du domaine dans un historique classé par périodes comme cela a été fait dans plusieurs historiques :

  • Les premier essais : McCulloch et Pitts [McCulloch 43] ont été les premiers à proposer un modèle inspiré des connaissances en neurologie de l'époque à l'aide de logique formelle. Les premiers essais par simulation sur des ordinateurs ont étés réalisés par Farley et Clark en 1954 [Farley 54] puis l'on retrouve Rochester et Holland [Rochester 56] également parmi les premiers à s'intéresser au RN. On peut noter dès les débuts une étroite collaboration avec les neurologues qui se poursuit encore de nos jours.

  • Une nouvelle technologie prometteuse : en plus de l'influence des neurologues, les RN ont alors reçu des apports variés de psychologues, pour des aspects d'apprentissage et de cognition, ainsi que de mathématiciens et d'ingénieurs pour les aspects techniques. Rosenblat [Rosenblat 58] développe alors le célèbre principe du Perceptron avec sa couche d'entrée, de sortie et couche cachée (dite d'association), qui permet l'apprentissage d'association entre des entrées données et des sorties spécifiques. Widrow et Hoff [Widrow 60] développent de leur coté le système ADALINE (ADAptive LInear Element) qui se distingue surtout du Perceptron par une règle d'apprentissage différente, ce qui lance alors l'intérêt pour explorer des pistes très diverses de fonctionnement pour les RN.

  • Frustration et discrédit : en 1969, Minsky et Papert [Minsky 69] publient un livre dans lequel ils généralisent les limitations des Perceptrons simple couche à des systèmes multicouches en qualifiant amèrement cette voie de "stérile". Les financements pour les RN ainsi que l'intérêt général s'en trouvent pour le moins diminués.

  • Période d'innovation : malgré un intérêt général réduit, quelques chercheurs continuent leurs travaux et pendant cette période, plusieurs paradigmes ont été produits, développés encore actuellement. Citons les travaux de Steve Grossberg [Grossberg 88] avec l'ART (Adaptive Resonance Theory), de A. H. Klopf [Klopf 72] sur l'apprentissage par hétérostase, de Paul Werbos [Werbos 74] sur la rétro-propagation très utilisée dans les travaux actuels, ou de F. Kunihiko [Fukushima 75] sur le Cognitron à base de RN multi-couche capable de reconnaître l'écriture manuscrite.

  • Renaissance : ces avancés ont alors contribué à relancer l'intérêt pour les RN et permis à une importante communauté de se créer, et qui produit de nos jours une quantité significative de travaux.

On peut trouver des informations très complètes sur les détails des fonctionnements des différents types de RN dans les livres d'Anderson [Anderson 95] et de Hertz, Krogh et Palmer [Hertz 91]. Le récent livre "Understanding Intelligence" de Rolf Pfeifer et Christian Scheier [Pfeifer 01] présente également une discussion très intéressante sur les limitations des RN actuels face au "Symbol-Grounding Problem" (le problème de la capacité d'un système artificiel à associer un objet ou une action du monde réel à une représentation symbolique de celui-ci).

Par ailleurs, on peut constater que des travaux sur les RN et sur les Agents se rejoignent, mais il s'agit pour la grande majorité d'intégrer simplement un RN au sein de l'agent pour lui donner des capacités d'apprentissage. Ces travaux ne s'intéressent aucunement à intégrer les mécanismes des RN au sein de SMA pour contribuer à la capacité d'auto-organisation de ceux-ci.
        1. L'apprentissage et la question de l'émergence


Dans leur principe de base, les RN reposent entièrement sur les concepts d'auto-organisation et d'émergence : des règles locales de base d'interaction entre de nombreuses entités qui produisent au niveau global des comportements de plus haut niveau qui ne sont pas décrits au sein des règles. Si on leur rajoute en respectant toujours ces principes des capacités de création de neurones formels et d'apparition de nouveaux liens, ils présentent une technique intéressante pour la résolution de problèmes par émergence.

Mais encore une fois, le principe peut être biaisé par l'application technique. Le point délicat pour les RN réside dans l'apprentissage imposé au réseau. Sous certaines formes, cet apprentissage peut en effet introduire artificiellement au sein du réseau en devenir les caractéristiques observées en sortie censées être émergentes. Les pages 167 à 177 du livre cité dans le point précédent, "Understanding Intelligence" [Pfeifer 01], contiennent une discussion détaillée de ce problème avec notamment les présentations des différences entre apprentissage supervisé, par renforcement, ou non supervisé, et leurs conséquences, ainsi qu'un exemple d'application pour illustrer les propriétés émergentes ou non. Il s'agit de l'application NETTalk qui a pour but de prononcer correctement du texte anglais donné en entrée. Les auteurs montrent qu'une partie du comportement appris est effectivement émergent (l'association réussie des lettres en fonction de leur contexte avec les bons phonèmes), mais que la distinction entre consonnes et voyelles au sein même de la couche cachée qu'un observateur pourrait juger émergent, est en fait induite par le fait que cette distinction se trouve déjà dans les exemples fournis au système (les phonèmes ne sont pas les mêmes pour les voyelles et les consonnes).

Il est délicat d'argumenter sur l'apprentissage dans les RN sans exemple détaillé et je préfère renvoyer à la lecture de ce passage plutôt que de m'y attarder ici, d'autant plus que les RN ont d'autres caractéristiques inappropriées pour le problème de la programmation émergente comme je le détaille au point suivant.
        1. Spécificité caractéristique et le problème de la programmation émergente


Tout d'abord, dans leur grande majorité, les RN présentent des neurones formels homogènes, i.e. aux mécanismes identiques. Quand les RN incluent des types de neurones formels différents, il s'agit en fait seulement de faire varier la sommation des entrées, le seuil d'activation ou autre ajustement du même principe fondamental inspiré des neurones biologiques. Or la programmation émergente, de par son lien avec les langages de programmation, implique forcément des entités aux fonctionnements très variés. En fait, les instructions d'un langage sont justement choisies afin de fournir une expressivité maximale au langage et il en existe donc un grand nombre aux fonctionnements très spécifiques répondant à des besoins ne rentrant pas dans une seule catégorie avec variation.

Ensuite, une fois l'apprentissage effectué, tout le fonctionnement du RN repose sur les poids des liens (dont la matrice représentative représente en fait la fonction apprise) et les variations possibles des poids donnent les différentes fonctions du RN. Or le principe de la programmation émergente repose sur l'association d'une structure d'organisation donnée à la fonction produite. Pour changer de fonction, la structure de l'organisation doit changer. En fait, lors du calcul à proprement parler, un système reposant sur des instructions doit simplement déclencher les instructions dans l'ordre, l'intensité du signal de déclenchement importe peu : une donnée qui circule est forcément activante pour l'instruction qui la reçoit.

Ces distinctions reposent en fait sur la nature très différente des fonctionnements des RN et de la programmation émergente. Les RN reposent sur un parcours continu de l'espace de recherche dû aux modifications continues du réseau (changements des poids) afin de produire une fonction généralement continue (changements continus en fonction des changements continus des entrées). La programmation émergente nécessite, elle, des mécanismes discontinus (modification de l'organisation) qui produisent une fonction en général discontinue (un programme peut réagir très différemment suivant ses entrées). Une discussion sur ces distinctions se trouve au , partie 1.6.

Si par contre on pousse plus loin le principe des RN dynamiques avec l'apparition de neurones et de liens qui permettent alors des changements structurels poussés, et si on rajoute des neurones aux fonctionnements variés calqués sur des instructions, ainsi que des stratégies locales d'interaction et d'auto-organisation entre les neurones formels ainsi définis, la programmation paraît alors abordable. Mais ne sommes nous pas par ces modifications en train de transformer les neurones formels en agents et les RN en SMA ?
      1. Algorithmes de colonies de fourmis et optimisation par essaims particulaires


Les algorithmes de colonies de fourmis (ACF) et les techniques d'optimisation par essaim particulaires (PSO pour particle swarm optimisation) sont deux techniques beaucoup plus récentes s'inspirant de comportements observés dans la nature. Ces deux techniques sont en quelque sorte plus précises et spécifiques que le calcul évolutionnaire ou les réseaux neuronaux artificiels, dans le sens où elles s'inspirent de comportements très précis. Pour les ACF, les mécanismes miment ceux donnés par les éthologues quant aux comportements de fourragement des fourmis, et pour les PSO, ceux attribués aux comportements d'essaim observés dans les bancs de poissons ou les vols d'oiseaux.

J'ai regroupé ces deux techniques ici à cause des similitudes entre elles, mais surtout de par leur proximité conceptuelle avec le principe d'auto-organisation. J'en conclus de ce fait, et grâce aux propriétés génériques des SMA, qu'il peut être envisageable de les redéfinir sous forme de SMA, ou tout du moins de réutiliser leurs principes lors de la définition des mécanismes d'auto-organisation pour les SMA.
        1. Algorithmes de colonies de fourmis


Cette approche trouve son origine dans la description du fourragement des fourmis, et en particulier de leur capacité à trouver le plus court chemin du nid vers la nourriture, en termes de mécanismes simples reposant principalement sur le dépôt de phéromone et l'orientation en fonction des traces de phéromones présentes dans l'environnement. Les premiers travaux sont dus à Colorni, Dorigo et Maniezzo [Colorni 92] et proposent une modélisation algorithmique qui représente des mécanismes collectifs de résolution de problèmes par stigmergie. La stigmergie est le principe décrit initialement en biologie selon lequel des communications indirectes au travers de la modification de l'environnement produisent des comportements spécifiques sur le collectif.

C
oncrètement, les fourmis naturelles déposent des substances volatiles appelées phéromones qui servent de moyen de communication. Elles sont en effet très sensibles à cette phéromone et ont une tendance à suivre les dépôts qui sont de véritables pistes ou chemins pour la colonie. Un certain nombre des décisions des fourmis restent cependant stochastiques, ou c'est du moins comme cela que nous pouvons les considérer, et permettent l'exploration de zones non encore explorées, tout comme le choix aléatoire pondéré entre deux pistes de phéromones. Mais la donnée principale réside dans le suivi prioritaire de plus grandes quantités de phéromones. La capacité à trouver le chemin le plus court se comprend alors en fonction de cette préférence : le plus court chemin accumule plus rapidement des phéromones car les fourmis mettent moins de temps à effectuer les déplacements entre le nid et la nourriture, et les fourmis "préfèrent" alors progressivement ce chemin parce qu'il présente une concentration plus élevée de phéromone (cf. Error: Reference source not found). L'évaporation naturelle de la phéromone renforce encore plus cette tendance par l'affaiblissement des chemins plus longs.

Il existe alors différentes variations du même algorithme de base qui se contente d'accumuler suivant une formule donnée la phéromone virtuelle sur les chemins possibles d'un problème donné, de définir une règle de déplacement appelée "règle aléatoire de transition proportionnelle" [Bonabeau 99] et de calculer l'évaporation de la phéromone (règle de mise à jour des chemins). Les problèmes du type "voyageur de commerce" se prêtent particulièrement bien à cette approche.
        1. Optimisation par essaims particulaires


L'analogie est ici faite avec les déplacements collectifs observés chez certains animaux et basée uniquement sur l'observation locale du comportement des voisins. L'approche par PSO (Particle Swarm Optimisation) a été principalement définie par Kennedy et Eberhart [Kennedy 95] [Eberhart 01] et repose sur l'apparition de dynamiques collectives particulières ne dépendant que des comportements locaux des individus en fonction de paramètres tels que la position et la vitesse des voisins proches. L'exemple classique est le comportement d'évitement d'un banc de poissons confronté à un prédateur. On suppose que les poissons n'ont que des comportements définis sous forme de "rester proche des voisins", "ne pas entrer en collision", "se déplacer à la même vitesse", ajouté à l'évitement individuel d'un prédateur ou d'un obstacle quand celui-ci est suffisamment proche pour être détecté.

Il est alors aisé d'imaginer l'implication de l'approche d'un prédateur pour les déplacements du banc entier : les poissons percevant le prédateur effectuent des trajectoires pour l'éviter et les autres poissons se contentent de calquer leurs mouvements de proche en proche. L'ensemble du banc de poisson effectue alors un déplacement d'évitement alors qu'il n'a été initié que par quelques poissons. La plupart des poissons ont pu d'ailleurs ne pas se rendre compte de la présence du prédateur, si ce n'est par l'accélération des déplacements.

L'algorithme formel repose sur la définition de particules possédant un vecteur de déplacement ainsi que des "voisins". Ce voisinage peut prendre des formes variées et n'est pas forcément spatial. L'évolution du vecteur de déplacement est alors calculée en fonction des déplacements précédents couplés avec les déplacements des particules voisines. Si l'on rajoute une évaluation de la position des individus, et que cette évaluation influe pour la prise en compte de l'importance des différents voisins d'une particule donnée, le principe de la PSO permet alors d'explorer l'espace de recherche pour atteindre de meilleures positions, pour un individu donné ou pour le collectif.

Les références précédentes présentent exhaustivement le domaine et une synthèse en français peut se trouver dans [Clerc 02].
        1. L'auto-organisation évidente et la question de l'émergence


Les deux approches précédentes ainsi que diverses autres reposant sur le même genre d'inspiration sont généralement regroupées sous les termes d'"Intelligence Collective". Il s'agit en fait d'inspirations directes de phénomènes naturels cités comme exemples de phénomènes d'auto-organisation. Il s'agit à chaque fois de reposer la résolution du problème sur les conséquences de l'interaction d'un certain nombre d'individus agissant selon un comportement défini uniquement par des règles locales aux individus. De plus, dans les principes exposés, ces règles ne sont pas informées du but global et de comment l'atteindre.

La forme du parcours de l'espace de recherche est alors bien un phénomène émergent dans le sens où aucune information n'explicite ce parcours. Mais il est bien entendu facile d'introduire au sein de l'algorithme générique des informations constituant un biais pour la recherche de la solution. Nous ne pouvons qu'insister sur le fait que dans les problèmes réels difficiles, ceci est irréaliste.
        1. Retour aux SMA


Les approches par Intelligence Collective semblent particulièrement intéressantes pour une approche de la résolution de problèmes par émergence. Elles possèdent cependant des caractéristiques particulières qui nous semblent restrictives. En effet, chacune est très proche de son pendant biologique et en prend donc les formes particulières, spécifiques à chacun des modèles. Il est alors souvent difficile de les réutiliser pour des problèmes présentant des topologies ou contraintes différentes. Une forte traduction et adaptation sont alors nécessaires. De plus, elles reposent en général chacune sur un mécanisme d'auto-organisation particulier et se restreignent à n'utiliser que celui-là : phéromones pour les ACF, déplacement des voisins pour les PSO, par exemple.

Considérons maintenant le paradigme des SMA. Au final, il présente surtout une structure générale, une "vue" de haut niveau des systèmes sous forme d'entités en interaction. Manipuler n'importe quel programme ou considérer n'importe quel phénomène comme un SMA revient simplement à le structurer sous forme d'agents et à définir leurs comportements. Or justement, rien ne spécifie ces comportements dans les définitions des SMA, si ce n'est de donner toutes les possibilités relatives à cette vision systémique sous forme d'accointances, de croyances, etc… Les SMA apparaissent alors comme une technique extrêmement générique au sein de laquelle toute forme de fonctionnement est définissable. Ceci explique d'ailleurs l'utilisation de plus en plus répandue des SMA ou simplement des agents dans des domaines et pour des utilisations très variés.

En ce qui concerne l'auto-organisation dans les SMA, il suffit en fait d'expliciter les mécanismes régissant les comportements des agents en accord avec les caractéristiques particulières du principe d'auto-organisation. Dès lors, rien ne nous empêche de redéfinir les algorithmes des approches par Intelligence Collective en terme de SMA : il suffit d'introduire les mêmes mécanismes au sein des agents. Dès lors, nous pouvons également combiner les diverses inspirations biologiques en donnant plus de possibilités aux agents. De plus, le fonctionnement concret des SMA est certainement plus proche des modèles biologiques (simulation des interactions plus réalistes).

Approcher la résolution de problèmes par des SMA basés sur des mécanismes d'auto-organisation signifie alors explorer la variété de mécanismes possibles dans un cadre générique les supportant. Nous avons ainsi une grande liberté qui permet à la fois de se reposer sur une combinaison d'inspirations issues de toutes les techniques présentées précédemment, comme d'explorer de nouvelles voies.
      1. Autres techniques


Il existe de très nombreuses techniques de résolution de problèmes que l'on retrouve souvent sous l'appellation de "méthodes d'optimisation". Elles vont de techniques très pointues seulement applicables à une poignée de problèmes (car utilisant des connaissances précises sur la nature de l'espace de recherche et des solutions) à des approches très génériques, certaines se contentant de donner une idée générale de comment procéder.

Nous pouvons ainsi citer la méthode du Recuit Simulé inspirée de phénomènes physiques tels que l'agencement ordonné des spins magnétiques dans un morceau de métal au fur et à mesure que la température décroît, qui est un exemple classique d'émergence (des travaux sur les SMA s'en sont d'ailleurs inspirés comme ceux de Khaled Ghédira et T. Daouas [Daouas 94]). Cette méthode repose sur une gestion du désordre et de l'ordre en fonction d'un paramètre général (la température) décroissant lentement. La modification progressive des déplacements de molécules donnant les cellules de Bénard est une autre façon de considérer les mécanismes de cette technique. Nous pouvons également citer la recherche avec Tabous qui est une technique plutôt générale mais limitée dans ses applications. Il s'agit simplement de stratégiser les déplacements dans l'espace de recherche en choisissant les "meilleurs" états possibles (même s'ils sont moins bons que le précédent) et en gérant une mémoire qui évite de retomber trop directement dans l'état précédent (pour éviter les minima locaux).

L'excellent livre "Métaheuristiques pour l'optimisation difficile" de Dréo, Pétrowski, Siarry et Taillard [Dréo 03] présente de façon claire et précise un grand nombre de ces techniques, avec entres autres, en plus des techniques précédentes :

  • des variantes du recuit simulé (diffusion simulée, recuit microcanonique, méthodes du seuil, du "grand déluge", du "voyage de record en record");

  • la méthode du bruitage;

  • la méthode de recherche distribuée;

  • la méthode Aliénor;

  • les algorithmes à estimation de distribution;

  • la méthode GRASP;

  • la méthode "Cross-Entropy";

  • les systèmes immunitaires artificiels;

  • l'évolution différentielle;

  • d'autres algorithmes inspirés des insectes sociaux.

Il faut noter que la plupart présentent des caractéristiques très spécifiques qui contraignent fortement leur utilisation. L'idée principale que je voudrais faire ressortir de ce premier chapitre est l'utilisation de cette grande variété comme source inépuisable d'inspirations diverses afin de définir des mécanismes d'auto-organisation puissants et génériques pour des SMA. La capacité à exhiber des phénomènes émergents me paraît être primordiale pour les problèmes que nous voulons traiter, en particulier celui de la programmation émergente. C'est pourquoi j'ai présenté tout au long de ce chapitre des discussions sur les conséquences des règles et mécanismes d'auto-organisation qui veulent montrer qu'il est délicat de rester dans un cadre strict d'auto-organisation et conduisant ainsi à des phénomènes émergents.
1   ...   5   6   7   8   9   10   11   12   ...   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