Cours de complexité

La complexité

” Si les gens ne croient pas que les mathématiques sont simples, c’est uniquement parce qu’ils ne réalisent pas à quel point la vie est compliquée ” – John Von Neumann

Larousse : (du latin complexus, de complecti : embrasser)

Complexe : se dit de ce qui contient plusieurs parties ou plusieurs éléments combinés d’une manière qui n’est pas immédiatement claire pour l’esprit.

I. Introduction

I.1. Première approche : celle du groupe

Pour le groupe ensemble, on dresse la carte mentale du mot complexité.

La différence entre complexe et compliqué :

Première approche : pour mieux aborder la différence entre les deux notions (si tant est qu’il en existe une), on dresse également la carte mentale du groupe sur le mot compliqué.

Seconde approche : étude bibliographique sur les définitions des deux termes.

I.2. Présentation de la complexité selon quelques auteurs fameux

La complexité qui est actuellement mangée à toutes les sauces ne peut avoir de définition simple et unique, on en trouvera plusieurs selon les points de vue : c’est normal, nous comprendrons pourquoi dans la suite de cette présentation.

Premier point de vue : celui de Jean Petitot

On a deux classes de situation :

- la complexité qui engendre la complexité au sein d’un même niveau de réalité : c’est par exemple l’évolution.

- la complexité qui engendre la simplicité en changeant de niveau : c’est l’émergence.

Le premier axe est celui du temps ; le second axe révèle qu’une individualité peut être plus que la somme de ses parties : on l’observe souvent dans les réseaux de neurone (chapitre àà : apprentissage de la marche par un robot hexapode), on verra également un exemple dans l’organisation des tas de sable ! C’est bien parce qu’il y a émergence d’un état plus simple en changeant de niveau qu’un tas de sable paraît si trivial: nous verrons que ce n’est pas forcément le cas.

La complexité est un phénomène naturel et on peut y discerner 4 aspects typiques :

- la singularité : les systèmes complexes sont tous uniques,

- l’historicité : ils sont irréversibles et dépendent de leur histoire,

- l’adaptation : ils résultent de processus adaptatifs

- la régulation : ils possèdent des boucles de rétroaction qui les maintiennent dans une zone de “bon fonctionnement”.

Second point de vue : celui de Murray Gell-Mann

Murray Gell-Mann [1] distingue les systèmes adaptatifs complexes, comme les être vivants, qui peuvent apprendre et s’organiser face à une perturbation, des systèmes complexes en évolution, c’est à dire des systèmes dont la dynamique est en cours de déploiement : par exemple les galaxies.

Il tente également de donner des définitions de la complexité : la définition calculatoire, la définition selon la longueur nécessaire de symboles pour décrire un système.

Depuis la définition de l’ordinateur universel de Von Neumann, dont on sait qu’il peut réaliser toute fonction, les informaticiens ont pris l’habitude de mesurer la complexité sous la forme d’une complexité calculatoire, c’est à dire la complexité du programme qui réaliserait la fonction choisie. La complexité calculatoire est alors le temps le plus court possible mis par un ordinateur pour résoudre le problème. Evidemment, nous verrons que ce temps dépend de plusieurs facteurs et ne donne pas une définition complètement satisfaisante de la complexité. En particulier cette définition ne traduit pas la notion d’organisation qui sous tend souvent le mot “complexe”.

Cette dernière vision de la complexité : liée à l’aspect compliqué de l’organisation pourrait être quantifiée par la longueur du message nécessaire à la présentation de l’organisation en question, ou à la description du système considéré. Ceci est vrai, par exemple, pour les systèmes écologiques. Par exemple, en sciences de l’écologie on a débattu pour savoir si les éco-systèmes les plus simples étaient plus stables que les écosystèmes les plus complexes : ainsi, la forêt équatoriale est elle plus résistante à des perturbations extérieures qu’une forêt alpine (a priori plus simple). Dans ce cas, la mesure de la complexité par la longueur du message nécessaire à la description du système paraît admissible car il y a un nombre bien plus grand d’espèces animales et végétales dans la forêt tropicale que dans un e forêt de haute montagne. Ceci est encore accentué si on ne se contente pas de décrire les espèces en présence mais si en plus on décrit les interactions entre ces espèces (proie prédateurs, pollinisateurs, …).

Cette définition est celle que Gell-Mann appelle la complexité brute, il la différentie de la complexité effective qui est la description des régularités du système. Nous en discuterons dans le chapitre II.2.1.

I.3. Les tenants de la complexité

Le problème du changement de niveau d’intégration

Il se pose des questions dont nous ne savons pas si une réponse existe : par exemple lorsque l’on s’intéresse au cerveau, on peut étudier en détail les fonctionnements des cellules et de ses constituants biochimiques, mais un abîme sépare ces considérations des considérations de mémoire ou des considérations psychologiques, et encore plus encore les sépare de la conscience. Changeux a écrit que la conscience, comme les souvenirs, ne sont que des états du système neuronal [6] composé de l’état des neurones individuels, mais cette considération est très matérialiste et contestée par des approches plus religieuses. Il est clair que lorsque l’on change de niveau de description, ou d’intégration, ou de grain comme dit Gell-Mann, il se produit des phénomènes de réorganisation, de simplification qui ne sont pas toujours bien compris : c’est une caractéristique de la complexité.

Le problème de l’indétermination : quantique ou fortuite ?

Henry Poincarré en 1908 écrivait dans son livre : “Science et méthodes” :

“Si nous connaissions exactement les lois de la nature et la situation de l’univers à l’instant initial, nous pourrions prédire exactement la situation de ce même univers à un instant ultérieur. Mais, lors même que les lois naturelles n’auraient plus de secret pour nous, nous ne pourrions connaître la situation initiale qu’approximativement. Si cela nous permet de prévoir la situation ultérieure avec la même approximation, c’est tout ce qu’il nous faut, nous disons que le phénomène a été prévu, qu’il est régit par des lois ; mais il n’en est pas toujours ainsi, il peut arriver que de petites différences dans les conditions initiales en engendrent de très grandes dans les phénomènes finaux ; une petite erreur sur les premières produirait une erreur énorme sur les derniers. La prédiction devaient impossible et nous avons le phénomène fortuit.”

Henri Poincarré vient ici de présenter le phénomène du “chaos déterministe” : du fait d’une très grande sensibilité aux conditions initiales, il est impossible de déterminer le futur d’un système car les conditions initiales ne sont jamais connues avec une précision suffisante.

Le chaos déterministe nécessite la présence de plusieurs ingrédients :

- une non-linéarité,

- un retour de la sortie sur l’entrée.

Lorsque ces ingrédients sont réunis, et que la non-linéarité est assez forte, on peut voir apparaître des phénomènes de chaos. On l’appelle chaos déterministe car si l’on refait l’expérience avec exactement les mêmes conditions initiales, on observe le même comportement. Néanmoins dans la nature, ou dans la réalité il est impossible de refaire une expérience identique, de même qu’il est impossible de connaître toutes les entrées d’un système et toutes les conditions initiales avec une précision infinie.

Ce phénomène intervient dans les systèmes physiques bien décrits formellement, on en trouvera des exemples aux chapitres ààà … Le terme “chaos déterministe” est apparu la première fois à propos de la dynamique des systèmes non-linéaires. Il est à la mode et un peu galvaudé en ce moment.

Par exemple, c’est ce phénomène qui est décrit sous une forme de suspense et en faisant intervenir des paramètres que l’on peut mal mesurer : les paramètre humains dans “Jurassic Park”. Le parc qui est très bien conçu pour protéger les visiteurs des monstres qu’il enferme vient d’un seul coup à sa perte à cause d’un petit grain de sable.

…

Le chaos déterministe, c’est aussi “l’effet papillon” : effet fameux, mais pas toujours identifié du battement d’aile d’un papillon qui déclenche des catastrophes à l’autre bout du monde. C’est aussi actuellement l’effet du courant marin “el niño ” dont on suppose qu’il cause les dysfonctionnements climatiques observés actuellement.

Certains auteurs (Todd Brun) estiment qu’il y a un lien entre le chaos au niveau macroscopique, et l’indétermination quantique ; la première étant en quelques sortes l’amplification de la seconde.

L’irréversibilité

Les systèmes complexes sont irréversibles et dépendent de leur passé. De ce fait ils rompent avec la tradition des systèmes physiques classiques pour lesquels les équations sont symétriques par rapport au temps (mécanique Newtonienne, …). Depuis l’antiquité, le dilemme auquel conduit le déterminisme de la physique a été montré du doigt : Ilya Prigogine cite Epicure lorsqu’il écrivait déjà qu’il préférait le libre arbitre humain plutôt que le déroulement mécanique des lois de la physique [3].

“Quant au destin, que certains regardent comme le maître de tout, le sage en rit. En effet, mieux vaut encore accepter le mythe sur les dieux que s’asservir au destin des physiciens. Car le mythe nous laisse l’espoir de nous concilier les Dieux par les honneurs que nous leur rendons, tandis que le destin a un caractère de nécessité inexorable.”

En effet, où se trouve le libre arbitre si tout le comportement du monde est décrit par un système d’équations différentielles et des conditions initiales ?

Au XIX ème siècle le débat a été fort : comment expliquer la diversité du vivant avec les lois de la physique si déterministes ? Les scientifiques ont oscillé entre deux attitudes opposées.

La première considère que la diversité vient d’un épiphénomène se rajoutant aux phénomènes physiques bien expliqués, la seconde considère que ces phénomènes sont bien réel, mais provienne d’un supplément ontologique

Aujourd’hui, on considère les phénomènes complexes à part entière.

Théorie des catastrophes.

Les simulations informatiques

Pourquoi la complexité fait-elle actuellement une OPA sur tous les domaines scientifiques, des sciences molles aux sciences dures , alors que certains de ses aspects étaient déjà soulevés par Poincarré ?

C’est parce que la capacité de calcul des ordinateurs a augmenté considérablement et rend accessibles ces problèmes à tous les scientifiques et ingénieurs et même aux adolescents curieux.

Grâce aux simulations informatiques, on peut désormais “expliquer de manière scientifique (matérielle et causale), modéliser mathématiquement et simuler les structures et le devenir des systèmes organisés complexes” [2].

Il est cependant nécessaire d’avoir quelques notions de codage de l’information et de théorie de l’information pour aborder le problème de la simulation numérique sans redécouvrir tous les problèmes déjà rencontrés. Sait-on par exemple que le nombre 0.3 est rarement identique d’un type d’ordinateur à un autre, alors que 0.25 l’est toujours ? Sait-on exactement ce qu’est une suite de nombres aléatoires calculée par un ordinateur, et comment ces derniers sont calculés ? Ces éléments sont nécessaires à connaître dès lors que l’on veut aborder le problème de la complexité en simulant l’imprécision des conditions initiales par l’introduction de nombre aléatoires. Nous en parlerons au chapitre ààà.

Mais place à notre expérimentation de la complexité …

I.4. Une expérience “vécue”

Premier exercice

Les participants au cours se groupent par trois ou quatre dans des salles différentes et rédigent durant 30mn une fin à l’histoire suivante.

II. Les définitions de la complexité

II.1. Le simple et le complexe

La suite suivante :

0000 0000 0000 0000 0000 0000 0000

est de toute évidences assez simple ; en revanche la suite suivante :

45268 1572 5634 1579 5216 7854 2348

paraît plus compliquée.

Prenons un autre exemple :

2653 5897 9323 8462 6433 8327 9502 8841 9716

Cette dernière suite paraît tout autant compliquée et difficile à décrire que la précédente, or ce n’est pas le cas car il s’agit de la suite des décimales de P à partir de la sixième décimale.

Prenons encore un autre exemple : considérons un ensemble d’individus pouvant discuter entre eux ; on imagine que plus ils pourront discuter entre eux, plus les échanges seront complexes, et de même, moins ils pourront discuter, moins les échanges seront complexes.

Plusieurs schémas peuvent être envisagés, qui, si l’hypothèse précédente est bonne seront du moins complexe au plus complexe : plus on peut discuter, plus les échanges sont complexes.

Situation 1. Les échanges sont hiérarchisés : seuls les échanges professeur — élèves sont autorisés.

Situation 2 – Les échanges sont en partie hiérarchisés : certains peuvent discuter entre eux, mais pas à tout le monde. Il s’agit par exemple du schéma des communications de travail dans une entreprise : les cadres d’un service ne peuvent demander un service à une personne d’un autre service sans passer par la hiérarchie.

Situation 3 – Les échanges ne sont pas hiérarchisés : tout le monde discute avec tout le monde.

Or, il apparaît assez rapidement que la situation 3 n’est pas si complexe que cela : elle possède des symétries et un ordre qui permet de l’appréhender facilement. Ceci n’est pas le cas de la seconde situation pour laquelle il faut dresser les communications autorisées une par une.

Il apparaît donc que l’on peut distinguer deux types de complexité :

La complexité “aléatoire” qui signifierait :

sans ordre, sans régularité, aléatoire,

la complexité organisée qui comprendrait :

organisée, structurée, riche en information.

Voyons comment ces deux aspects de la complexité peuvent être définis et mesurés.

II.2. La complexité aléatoire

II.2.1. Présentation

La complexité aléatoire est celle que Gell-Mann a appelé “complexité brute”. Si l’on voulait décrire la suite de nombres aléatoires telle que celle présentée précédemment, il faut malheureusement se contenter de citer tous les chiffres les uns après les autres, alors que pour la suite des décimales de P, on pourrait se contenter de donner la définition de P (si tant est qu’elle existe).

On propose donc, dans un premier temps, que la mesure de cette complexité aléatoire, liée à l’imprévisible et au non ordonné, serait la longueur de la description du système.

Considérons alors le cas suivant : une institutrice demande à des enfants de décrire un évènement grave de leur vie en 200 mots. Toto, toujours mauvais élève, raconte l’histoire suivante :

“Je suis passé à coté du chien du voisin, et il m’a mordu. J’ai crié au secours, au secours, ….au secours, …” et ainsi de suite jusqu’à ce que les 200 mots soient écrits.

Toto aurait pu raconter la même histoire en écrivant :

“Je suis passé à coté du chien du voisin, et il m’a mordu. j’ai crié “au secours” quatre vingt neuf fois”.

Il est clair que les deux histoires sont identiques, mais ont une longueur assez différente. L’information contenue dans les histoires est la même, ainsi que leur complexité. Il paraît donc intéressant pour mesurer la complexité de chercher l’information.

II.2.2. Théorie de l’information

L’information au sens de Shannon

Qu’est-ce que l’information ? C’est une quantité intuitive qu’il est difficile de définir. On peut imaginer que la quantité d’information d’un message est liée à son volume et sa rareté. Par exemple on apprend une information plus importante en connaissant à l’avance les numéros gagnants du loto qu’en connaissant à l’avance le résultat du tirage d’une pièce (pile ou face). De même, on a plus d’information, pour un temps donné, en connaissant une image haute définition qu’en connaissant un signal musical.

La quantité de l’information en donc liée au volume et la probabilité.

On sait qu’il est possible de représenter un signal analogique sous forme d’un signal numérique sans perdre d’information grâce au théorème de Shannon. Nous allons donc d’abord nous intéresser aux signaux numériques.

Un système de transmission de l’information comprend trois éléments :

• la source qui émet le signal (que l’on considèrera discret),

• un canal de transmission, c’est à dire le système qui assure le transport de l’information (ligne téléphonique, liaison hertzienne,…),

• le récepteur qui interprète le signal reçu.

La source

Dans ce chapitre nous allons essayer de définir de manière intuitive une “mesure” de l’information délivrée par une source.

On peut penser de manière intuitive que plus la source peut délivrer de symboles différents, plus elle peut délivrer une quantité d’information importante (image en noir et blanc ou en couleur).

Source délivrant des messages équiprobables

Considérons une source susceptible de fournir un message parmi n possibles. Du point de vue des probabilités nous considérons que tous ces messages sont équiprobables.

On note I(n) la quantité d’information que peut fournir cette source. D’après ce que l’on a intuité, I(n) est une fonction croissante de n.

Supposons que l’émission du message n précédent soit décomposable en deux ensembles de messages n1 et n2 indépendants (au sens probabilistique).

En admettant que la quantité d’information est une grandeur additive, la quantité d’information contenue dans le message n est donc : I(n) = I(n1) + I(n2).

Par exemple, la source émet un mot de 5 chiffres décimaux qui sont décomposables en deux sous-ensembles de 2 chiffres et de 3 chiffres. On a au total 105 messages possibles : n ; et deux sous-ensembles n1 de 102 messages et n2 de 103 messages.

On voit donc que l’on a : n = n1.n2.

Ceci nous conduit donc à écrire :

I(n1.n2) = I(n1) + I(n2).

La fonction croissante la plus simple satisfaisant cette équation est le fonction logarithme.

En fonction de la base de log choisie l’unité d’expression de l’information varie :

base 2 : l’unité est le bit,

base naturelle (népériens) : l’unité est le nat (comme naturel),

base décimale : le décit ou Hartley.

Attention, on appelle en général bit un symbole d’écriture en binaire. Or, nous verrons que si la probabilité qu’a la source de délivrer un “1″ ou un “0″ sont différentes, la quantité d’information délivrée par un symbole ne vaut plus un bit. C’est pourquoi les puristes appellent ces symboles “digits” et non pas “bits”.

La quantité d’information délivrée par une source de n messages équiprobables est donc :

I(n) : log(n).

Source délivrant des messages inégalement probables.

Nous allons essayer de formuler une expression vraisemblable de la quantité de l’information incluant la considération intuitive suivante : plus la probabilité du message est faible, plus l’information contenue est grande.

Considérons :

- n1 résultats constituant le groupe G1,

- n2 résultats constituant le groupe G2,

Tels que n1 + n2 = n, le nombre d’évènements total.

La quantité d’information apportée par un évènement parmi les n est :

I = log(n),

Considérons que cette information peut être apportée en deux fois :

I = Ia + Ib, où :

Ia est la connaissance du groupe,

et Ib est la connaissance du numéro de l’évènement dans le groupe.

La probabilité de tirer un évènement appartenant à G1 est :

P1 = nombre d’évènement de G1/Nombre d’évènement total

P1 = n1/(n1 + n2) = n1/n.

De la même manière P2 = n2/(n1 + n2).

On voit que P1 et P2 sont différentes.

Lorsqu’un message du groupe 1 est émis, on peut réécrire l’équation I = Ia + Ib :

log(n) = Ia + log(n1), c’est à dire :

log(n/n1) = Ia.

On obtient donc : Ia = -log(P1),

La quantité d’information contenue dans un message de probabilité p est égale à -log(p).

On peut retrouver le résultat précédent dans le cas équiprobable : la probabilité de tirer un message sur n équiprobables est 1/n, on a donc

I(n) = -log(1/n) = log(n).

Entropie d’une source

Une source peut émettre des messages correspondant à une quantité d’information très variable. On la caractérise donc plutôt par la quantité d’information moyenne qu’elle transmet (la probabilité pi introduit le terme de normalisation):

I = Si pi.Ii.

ou bien :

I = -Si pi.log(pi).

En effectuant une analogie avec l’expression de l’entropie en thermodynamique statistique, on peut appeler cette grandeur : entropie de la source.

L’entropie d’une source est donc la valeur moyenne de la quantité d’information qu’elle délivre. Pour une source délivrant n messages de probabilité respectives pi, son expression est : H = -Si pi.log(pi).

On peut démontrer que l’entropie d’une source est maximale lorsque tous les messages sont équiprobables.

Exemples :

a. Soit une source dont les messages sont les lettres de l’alphabet, si les lettres sont toutes équiprobables, on peut calculer :

H = -Si pi.log(pi) = -Si (1/26).log(1/26) = log(26) = 4,7004… bits/lettre

(log à base 2)

En réalité, les lettres ne sont pas toutes équiprobables, par exemple pour la langue française on trouve

H = 3,98 bits/lettres.

b. Soit une source binaire délivrant des 0 et des 1 avec une probabilité égale, son entropie est :

H = -(0,5.log(0,5) + 0,5.log(0,5)) = log2 = 1bit/digit.

Un peu de thermodynamique

Le premier principe de la thermodynamique dit que l’énergie d’un système isolé reste constante. Le second principe de la thermodynamique, plus subtil, nous indique que l’entropie d’un système isolé ne peut qu’être constante, ou augmenter. On ironise sur ces principes en disant que le premier principe interdit de gagner au jeu tandis que le second principe interdit même de récupérer sa mise…

Le second principe indique que le désordre d’un système isolé ne peut qu’augmenter, ce que l’on voit à l’œuvre tous les jours (même si localement notre monde n’est pas isolé) : on trouve toujours du beurre dans le pot de confiture après le goûter des enfants ; et si par malheur on fait tomber le tiroir qui contient les résistances en TP d’électronique, il faut un sacré apport d’énergie pour arriver à tout re-trier.

On explique ceci tout simplement parce que l’état ordonné d’un système est, soit unique, soit assez peu probable, tandis que l’état désordonné est très probable car possible dans beaucoup plus de combinaisons.

Reprenons notre exemple du tiroir de résistances (expérience vécue…) supposons que l’on ait 20 sortes de résistances avec 1 représentant par catégorie (dans la réalité c’est plutôt 20 ou 50) : il n’y a qu’une manière de ranger ces 20 résistances par ordre croissant dans 20 petits casiers. En revanche, il y a (20!-1) manières de ranger les résistances n’importe comment. Si tous les états “microscopiques” sont équiprobables, on a donc beaucoup plus de chances que le désordre augmente plutôt que les résistances, lors de la chute du tiroir, se retrouvent chacune dans la bonne case. L’entropie a donc augmenté.

Que signifie l’entropie en terme d’information ?

Nous avons vu que la quantité d’information est liée à sa rareté : I = -log(p) ; plus la probabilité est faible, plus l’information est grande.

L’entropie, elle, est également liée à la probabilité : plus un état macroscopique est probable (les résistances mélangées) plus son entropie est forte. Ainsi en termes d’information, l’entropie est une mesure de l’ignorance : plus elle est grande, plus le désordre est grand et moins on connaît d’information précise. Plus elle est faible, plus on est dans un état rare et plus il est riche d’information.

II.2.3. Les machines qui calculent

Comment arriver à mesurer la complexité si ce n’est par une machine bien connue et invariante qui fera un calcul automatique et objectif ? C’est pourquoi les théoriciens de l’informatique ont été les premiers à se poser ce type de question : comment mesurer l’information ? Comment mesurer la complexité d’une tâche à réaliser, d’un algorithme, d’un programme après compilation ? Ce sont autant de questions intéressantes à parcourir pour appréhender les définitions de la complexité.

La machine de Von Neumann

C’est le modèle de l’ordinateur le plus utilisé actuellement : les données sont stockées dans une mémoire, une unité de calcul synchronisée par une horloge rythme l’accès de l’unité arithmétique et logique à un “ordre” stocké dans la mémoire et ensuite exécute cet ordre. Les informations “ordre” (“instruction”) ou données sont stockées indifféremment dans la même mémoire ou dans des mémoires séparées.

John Von Neumann à coté de l’ENIAC.L’ENIAC est un des premiers ordinateurs (1940). Il était construit à partir de 18 000 tubes à vide, et avait une mémoire inférieure à 4Koctets.

Ce qui est important dans ce modèle, outre son application généralisée, est qu’il peut exécuter tout algorithme possible : il s’agit réellement de la machine universelle qui peut tout simuler.

Ce n’est pas le seul modèle de calculateur qui existe, nous verrons qu’il existe également des ordinateurs cellulaires ou hautement parallèles, comme la “connection machine” [8]. Mais ces derniers peuvent toujours être simulés par la machine de Von Neumann moyennant un temps plus important.

Revenons à la complexité : serait il possible de mesurer le complexité grâce à cet ordinateur qui, en théorie, peut tout simuler ? Comment le ferait-on ? Même si le terme complexité n’était pas utilisé dans les années 50 ou avant la guerre de 40, les scientifiques et mathématiciens de très haut niveau ont réfléchi à ces problèmes : la machine de Turing apporte des éléments de réponse.

La machine de Turing

La machine de Turing n’est pas une machine réelle, au contraire de celle de Von Neumann, elle sert aux théoriciens de l’informatique et du calcul automatisé à raisonner.

En adaptant la description de Turing à la technologie moderne, imaginons qu’il existe une machine bâtie selon l’architecture de Von Neumann, et qui disposerait d’un espace mémoire pour stocker les données et les instructions qui soit extensible autant que nécessaire. Cet espace n’est pas infini a priori, mais il peut être augmenté sans limites en fonction des besoins.

En revanche, les états internes de la machine sont finis, c’est à dire le nombre d’états précédents nécessaires à conserver pour achever le calcul en cours.

Une machine de Turing doit exécuter un algorithme de dimension finie et doit donner son résultat en un temps fini : elle permet donc de faire la différence entre ce qui est calculable (la machine s’arrête) et ce qui ne l’est pas (la machine ne termine pas).

En raisonnant sur la machine, Turing a montré qu’il n’y avait pas de machine de Turing universelle qui pourrait décider d’un résultat mathématique, quel qu’il soit. C’est à dire qu’un algorithme ne peut pas toujours donner une solution à un problème mathématique. Ce résultat est important par rapport au problème de la calculabilité des problèmes.

En effet, un des problèmes de la mesure de la complexité est de savoir si les systèmes physiques ou biologiques sont tous calculables ou pas ?

Autrement posée cette question s’applique à un des systèmes les plus complexes que l’on connaisse, le cerveau, en ces termes : l’intelligence est-elle algorithmique ? On pourra se reporter à ce propos à l’ouvrage de Roger Penrose [5].

Le test de Turing

Imaginons que l’on arrive un jour à concevoir un système artificiel intelligent, à tel point qu’il pourrait atteindre les capacités de raisonnement d’un être humain. Le fabricant du dispositif affirme que son système pense réellement, il éprouve même des sentiments. Il est doué de conscience. Il peut même, comme dans le film “Blade Runner” avoir en plus une apparence humaine.

Comment faire la différence entre un être humain et ce cerveau artificiel ? C’est une question posée par les partisants de l’IA forte qui prétendent que l’intelligence est algorithmique, et qu’il est donc possible de réaliser un tel système. Ces partisants pensent que l’égalité des deux systèmes peut s’évaluer au travers des entrées et des sorties : si aux mêmes entrées, on a les mêmes sorties : alors les deux systèmes sont égaux.

Turing répond à cette question dans un article paru en 1950 : “Computing Machninery and Intelligence” dans la revue “Mind“. Il propose que le système soit comparé à un être humain : les deux êtres à comparer sont soumis en parallèle à des questions et répondent de manière impersonnelle (clavier, voix artificielle), une examinatrice évalue les réponses aux questions et délivre à l’issue de l’interrogatoire son jugement : l’un des deux est l’humain. Si l’interrogatrice se trompe ou n’arrive pas à imaginer de manière certaine l’humain, le fabricant est déclaré gagnant.

On peut remarquer au passage que le test n’est pas égal vis à vis de l’ordinateur : il suffirait d’un question pour distinguer n’importe quel ordinateur d’un être humain par rapport à ses capacités de calcul. Par exemple : que vaut la division de 5687541134,2578544 par 27965485,5574 ? Le temps de réponse suffit à séparer l’humain de la machine !…

Dans le film “Blade Runner”, il s’agit de détecter des robots humanoïdes qui ont décidé de détruire l’humanité afin de sortir de l’esclavage dans lequel ils sont maintenus. on voit se dérouler le test tel que l’a préconisé Alan Turing, on ne dira pas la fin…

II.2.4. Le Contenu d’Information Algorithmique

Le Contenu d’information algorithmique a été introduit dans les années 60 par 3 personnes :

- Andrei N. Kolmogorov,

- Gregory Chaitain (alors agé de 15 ans),

- Ray Solomonoff.

Le CIA est la longueur du programme informatique le plus court qui produit le message dont on veut mesurer la complexité.

Pour établir la longueur de ce programme, on a de nombreuses sources d’arbitraire : le type de machine, le type de codage, … mais il ne faut pas s’arrêter à ces différences, il est plutôt intéressant de regarder le comportement des algorithmes quand la dimension du problème augmente. Les sources d’arbitraire interviennent comme des facteurs d’échelle, mais le comportement asymptotique permet de différencier les messages.

Greg Chaitain a démontré que le CIA est incalculable.

Lorsque l’on observe une suite de bit il est très difficile de savoir si ces derniers sont aléatoires ou non. Dans le cas où ils sont aléatoire le programme le plus court qui permet de produire cette chaîne est alors l’instruction “print” suivie de la chaîne de caractères à produire. Dans le cas contraire Chaitain a prouvé qu’on ne peut pas démontré que le programme minimum a été trouvé : le problème est incalculable.

Gödel : étant donné un ensemble d’axiomes mathématiques, il existera toujours des propositions qui seront indécidables sur la base de ces axiomes. On ne peut démontrer ni qu’elles sont vraies, ni qu’elles sont fausses.

Exemple de propriété qu’on n’a pas encore prouvée : la conjecture de Goldbach.

“tout nombre pair supérieur à 2 est la somme de deux nombres premiers”. On peut le vérifier pour quelques nombres, des ordinateurs l’ont faits jusqu’à de très grandes valeurs, mais on n’a jamais prouvé que c’était vrai, ni faux.

Le CIA est très intéressant mais il est limité : en effet il est clair que le CIA ets le plus grand pour les chaînes aléatoires.

On peut donc dire que le CIA n’est pas vraiment une mesure de la complexité, mais une mesure de l’aléatoire. En ce sens il est limité.

II.2.5. Simulations informatiques

Codage des nombres non entiers

Codage en virgule fixe

On représente les nombres non entiers par un entiers multiplié par un facteur d’échelle;

N = p.K où K est le facteur d’échelle, et p la partie entière.

-> rapidité,

-> simplicité,

mais

-> connaissance a priori du facteur d’échelle,

-> impossibilité d’adopter ce codage pour des nombres d’ordre de grandeur très différents.

Codage en virgule flottante

Le principe

Le facteur d’échelle est donné de manière explicite avec le chiffre de manière à pouvoir le modifier; on a :

x = m.B^e, avec :

• m qui est la mantisse,

• B qui est la base de représentation, de m,

• e qui est l’exposant;

Les réalisations

Il n’y a pas unicité de la représentation en virgule flottante :

• le signe peut être représenté en complément à B, à 1 ou par un bit de signe,

• on peut choisir différentes bases B,

Première règle pour représenter les nombres avec le maximum de précision. On choisira m tel que :

¾ m <1

c’est à dire tel que la mantisse soit <1 et ne comporte pas de 0 comme premier digit après la virgule.

Ainsi, le nombre 12,53 en décimal sera représenté 0,1253.102 et non pas par 1253,0.10-2 ou 0,0012.104 .

Standart IEEE simple précision

Les réels sont écrits sur 32 bits, comprenant

• 1 bit de signe,

• 23 bits de mantisse,

• 8 bits d’exposant.

La base de numération est 2, le chiffre est représenté sous la forme 1,m où m est la mantisse. Le premier 1 est implicite : comme il est présent par définition, on évite de le mémoriser.

L’exposant est représenté en mode “décalage” ou biaisé c’est à dire qu’il représente la vraie valeur de l’exposant à laquelle est ajoutée (décalée de) la moitié du plus grand nombre qu’il peut coder. Par exemple pour un exposant sur 8 bits (qui permet de compter de 0 à 255), le code d’un exposant sera sa valeur à laquelle on a ajouté 127. Ainsi, le code binaire ne comprenant que des “0″ sera le nombre le plus négatif (-127), tandis que le code binaire de l’exposant ne comprenant que des “1″ sera le plus positif (+128).

On remarque que l’on a une dissymétrie entre le nombre d’exposants négatifs et le nombre d’exposants positifs ; ceci est inévitable si l’on veut coder la valeur “0″ qui n’est ni positive ni négative, compte tenu que 8 bits permettent de coder 256 valeurs.

Par exemple :

La mantisse vaut : environ 0,758, c’est à dire 1,758 avec le “1 implicite”..

l’exposant est biaisé ; le biais vaut : 2**(8-1) -1 = 127.

L’exposant exprimé en décimal vaut donc : 2**7+2**3+2**1-2**7+ 1 = 11.

On a donc : N = 1,758.2**11 = 1,758.2048 = 3600,384.

On comprend pourquoi les calculs effectués sur des flottants sont plus longs à réaliser.

Quelques exemples empruntés de la mémoire d’un IMAC :

0,5 (décimal) est codé 3F000000 (hexadécimal)

0,25 (décimal) est codé 3E800000 (hexadécimal)

0,125 (décimal) est codé 3E000000 (hexadécimal)

2 (décimal) est codé 400000000 (hexadécimal)

-2 (décimal) est codé C0000000 (hexadécimal)

Il s’agit pour l’instant de puissances de 2 qui sont assez simples à coder. Qu’en est-il de nombres plus difficiles comme 0,3 :

Lorsqu’on l’on fait une affectation comme par exemple :

float f=0,3;

En mémoire l’ordinateur code 3E999999, et il affiche en décimal : 0,30000001 ! Il y a donc une erreur dans le codage.

De très nombreuses valeurs ne sont pas codables en binaire sur une chaîne finie ; autre exemple :9,4 est codé 9,399996.

Lorsque l’on code des valeurs monétaires : on utilise un code différent du fait de ces arrondis : 10 octets sont utilisés, et les chiffres sont codés comme des caractères, mais avec un code spécifique (1/2 octet). Dans le cas des finances, il apparaît que l’imprécision a de la valeur !

Dépassements de capacité et de précision

En flottant, le dépassement de capacité correspond au cas où l’on demande un calcul pour lequel l’exposant qui devrait être calculé dépasse la valeur possible (+ de 8 bits dans ce cas ci).

Le message classiquement renvoyé par les ordinateurs est alors “overflow” ou “underflow”.

Le dépassement de précision se produit lorsqu’il n’est pas possible de coder toute la mantisse avec l’espace disponible (ici 23 bits). En général aucun message n’est alors affiché et l’utilisateur ne sait pas qu’une erreur est en train de se produire. Ce type d’erreur peut être sensible lorsque l’on effectue un calcul avec une boucle : les erreurs peuvent alors se cumuler.

Un code particulier est utilisé pour représenter 0.

Petits exercices d’assimilation

La génération de nombres aléatoires

Dans de nombreux problèmes complexes, c’est à dire possédant les propriétés annoncées dans l’introduction, il est nécessaire de recourir aux simulations informatiques afin de savoir comment le phénomène va se comporter.

Il s’agit donc soit d’établir un modèle numérique du phénomène, soit d’étudier le comportement d’un modèle déjà proposé. Pour cela on veut appliquer des entrées au système qui représentent autant que possible la réalité et on est amenés à alimenter le modèle avec des données bruitées, ces dernières représentant soit le bruit de la mesure, soit les fluctuations inhérentes au système (cf. imprécision sur les conditions initiales).

De ce fait on va chercher à obtenir des séries de nombres aléatoires.

Deux options sont possibles :

• On mesure le bruit d’un système physique qui génère du bruit naturellement (par exemple le bruit thermique d’une résistance électrique), puis on échantillonne et on numérise. Le bruit est alors réellement aléatoire.
• On calcule directement sur un ordinateur une série de nombres aléatoires, on a alors en fait une série “pseudo-aléatoire”.

C’est au deuxième procédé que nous nous intéressons ici.

Premier exemple de génération : la suite de Halton

Pour obtenir une série de nombres aléatoires {…,i,…}, on procède ainsi :

-1- on code le nombre i sur une base b (nombre premier), par exemple, pour b = 3, le nombre 17 se code 122,

-2- on inverse l’ordre des digits : 122 devient 221, et on met une virgule devant, on obtient 0,221 en base 3

-3- 0,221 est le nombre aléatoire obtenu.

On peut remarquer que cette suite atteint des valeurs de plus en plus fines, quand le nombre de tirages augmente. il est tout de même nécessaire d’aller assez loin.

On peut aussi trouver une génération de générateurs de nombres aléatoires qui se fondent sur des multiplications et des additions avec des nombres bien choisis de manière à créer des overflow. Dans le cas d’un dépassement de capacité, les bits les plus significatifs sont perdus, tandis que les bits les moins significatifs restent. Ce sont ces derniers bits qui donnent la suite de nombres aléatoires.

Exemple : la fonction RAND du C délivre un nombre aléatoire selon ce principe. Il est nécessaire de démarre le processus avec un premier nombre qu e l’on appelle la graine ou la racine. L’initialisation de cette racine (seed en anglais) peut être réalisée avec la fonction SRAND. Si l’on n’utilise pas SRAND, RAND s’auto-initialise avec la valeur d’horloge du système.

Exemples de tirages aléatoires réalisés avec la fonction RAND :

1) à chaque tirage on réinitialise rand avec SRAND (transparents).

2) le bon usage : à chaque tirage, on appelle RAND sans le réinitialiser.

Ceci démontre qu’il est nécessaire, avant toute simulation, et en particulier pour un processus complexe de vérifier les bonnes qualités du générateur de nombres pseudo-aléatoires.

II.3. La complexité organisée

“Deux moutons ne sont pas deux fois plus complexes qu’un mouton”.

La complexité de deux moutons est sensiblement la même que celle d’un seul mouton. La complexité organisée n’est donc pas additive.

Le CIA ou la longueur d’une description ne correspondent pas à la définition que l’on entend spontanément dans le mot complexe. Au contraire, ce qui est complexe est la description des règles ou des régularités qui sont dues, bien souvent, à des causes identifiées. On est donc dans ce domaine loin de l’aléatoire complet.

L’approche de la complexité organisée que prend Gell-Mann [@] est liée à la description des régularités d’un système par un système adaptatif complexe qui l’observe.

Prenons l’exemple des corps célestes : galaxies, planètes, étoiles et autres corps. Ils paraissent extrêmement complexes. Néanmoins l’homme, système complexe adaptatif, a réussi à dégager la loi qui permet d’expliquer cette diversité des formes. La relativité générale, et la loi de la pesanteur peuvent paraître difficiles pour certains, mais il ne reste pas moins vrai qu’elles sont remarquablement simples relativement à la complexité apparente des systèmes qu’elle permettent de décrire.

Dans la complexité organisée, on peut distinguer les systèmes tels les corps célestes, les montagnes, tas de sable, et autres qui sont longs à décrire, mais dont on a pu extraire la loi sous-jacente. Ces systèmes sont en évolution sous l’effet d’une dynamique assez lente et ne restent donc pas figés dans un état d’immobilité.

On doit les distinguer des systèmes adaptatifs complexes qui eux sont capables d’apprendre quelque chose sous la pression de l’environnement.

Considérons par exemple les processus suivants :

- l’évolution biologique,

- le fonctionnement du système immunitaire,

-l’apprentissage et la pensée chez les animaux,

- le comportement des investisseurs sur les marchés financiers,

- l’utilisation de prédicteurs , …

Le point commun entre ces processus est ce qui permet de décrire de manière générale ce qu’est un système adaptatif complexe.

Tous ces systèmes acquièrent de l’information en relation avec leur environnement ; ils identifient les régularité” de cet environnement ; résument ces régularités sous forme d’un schéma, appelé aussi modèle, et agissent ensuite sur l’environnement à partir de ce schéma.

On peut dire que la capacité d’apprentissage peut revêtir plusieurs formes : elle est très claire pour l’être humain qui va apprendre à parler, ou à faire un gâteau, mais elle est présente aussi chez les animaux par le biais de l’évolution biologique. En effet il est plus parlant chez les animaux que ces derniers ont des connaissances déjà acquises à leur naissance grâce à l’évolution. En ce sens, l’évolution est aussi un système adaptatif complexe.

On peut noter aussi que le modèle élaboré par le système complexe adaptatif est un modèle compressé des informations : le système a extrait les régularités observées afin d’établir le modèle.

C’est vrai lorsque l’homme (SCA) trouve les lois de la pesanteur, c’est aussi vrai lorsque l’évolution code le comportement des animaux dans leurs gênes.

Comme le disait Isaac Asimov, l’étudiant en physique connaît les lois de la pesanteur, mais le chien qui ramasse au vol une balle les connaît aussi.

Un système adaptatif complexe pourrait donc être représenté par le schéma suivant :

La définition que donne Gell-Mann de la complexité effective d’une entité , en relation avec un SAC qui l’observe et construit un modèle : “la longueur d’une description précise des régularités de l’entité, identifiées par le modèle”.

III. Les éléments fondateurs de la complexité

III.1. Les régulations ou bouclages

Les systèmes asservis : rétroactions explicites

On considère par exemple le remplissage d’un bac. Pour obtenir le niveau désiré il est nécessaire d’effectuer un contrôle du niveau effectif et d’ajuster le débit de liquide en fonction de ce dernier. On obtient alors ce type de schéma avec une boucle de retour (cf schéma du réservoir).

Le contrôle donne la mesure de la valeur de sortie. La commande est le signal appliqué en entrée du système pour l’amener à cette valeur désirée.

Lorsque le système considéré est linéaire comme c’est le cas dans le bac considéré; l’ensemble bouclé est encore linéaire ; on peut donc effectuer des calculs sur la stabilité, la dynamique … Mais lorsque le système n’est pas linéaire tous les comportements possibles sont envisageables.

Systèmes dynamiques avec des rétroactions non explicites

Parfois les bouclages interviennent de manière indirecte, et n’apparaissent pas dans le système lui même : c’est le cas lorsque la sortie d’un système influence des variables diverses qui, à leur tour, influencent l’entrée. C’est le cas de tous les systèmes écologiques, mais aussi de nombreux systèmes sociaux ou humains : la bourse.

L’analyse d’un système comportant des boucles est souvent rendue difficile par la mise en présence de plusieurs entrées et de nombreuses perturbations ou entrées secondaires.

Par exemple, par rapport à l’accident de l’ERIKA et de la marée noire qui en a résulté, il est difficile de prédire dès à présent quel en sera l’impact sur la société Total : les ventes de pétrole vont sûrement diminuer, mais d’autres produits sont aussi vendus en parallèle : produits de nettoyage. Si le producteur est reconnu innocent, il peut en outre valoriser les efforts qu’il a réalisés pour dépolluer…

III.2. L’irreversibilité

L’irréversibilité des systèmes physiques prend sa justification dans le second principe de la thermodynamique : l’entropie ne peut que rester stable ou augmenter. Ainsi, si l’entropie augmente, le système ne pourra jamais, s’il reste isolé, revenir à son état initial.

Considérons par exemple l’univers, il est actuellement en expansion. Si l’on adhère à l’hypothèse qu’il sera un jour dans une nouvelle contraction, il est clair que cette contraction ne sera pas l’image inversée de l’expansion qui a précédé du fait de l’irréversibilité. Les particules qui ont laissé leur trace dans les papiers photosensibles ne vont pas effacer leurs traces, les êtres vivants ne vont pas vomir ce qu’ils ont mangé au fur et à mesure qu’ils vont rajeunir. Le dernier souffle que le Christ à expulsé à l’instant de sa mort et dont on dit qu’il est à ce jour si bien mélangé à toute l’atmosphère que l’on en respire au moins une molécule à chaque respiration, ne sera pas reconstitué, molécule par molécule pour re-rentrer dans ses poumons.

Bref, la flèche du temps ne va pas s’inverser, alors que nombre des modèles de la physique sont symétriques par rapport au temps. Ces modèles sont en général linéaires alors que les systèmes complexes ne le sont pas.

Les systèmes complexes ne sont pas réversibles, et en particulier les systèmes biologiques. Le “démon de maxwell” n’a pas d’efficacité sur eux.

III.3. Le changement de niveau d’intégration

Le changement de niveau d’intégration n’est pas un changement d’échelle comme on l’entend en physique. Il ne s’agit pas de considérer ce qui se passe lorsque l’on décuple les doses observées, mais lorsque l’on observe le système sous un autre ordre de grandeur. Par exemple, l’observation des états de la matière, de l’infiniment petit vers l’infiniment grand, nous fait apercevoir de nombreuses émergences simplificatrices : pour savoir comment va évoluer une étoile il ne faut pas étudier les combinaison de chacun des quarks qui constituent chacun des noyaux de ses atomes, il suffit, en gros, de connaître se masse totale. Ainsi, selon que l’on considère une échelle atomique ou cellulaire, ou planétaire, … des lois nouvelles émergent qui permettent de ne pas tenir compte des éléments individuels du système de l’échelle immédiatement inférieure.

III.3.1. Les tas de sable

Liquide ou solide ?

Le sable est considéré comme a mi-chemin entre l’état liquide et l’état solide :

• si l’on retourne un pâté sur une table vigoureusement, le contenu se déverse en un coup, mais le tas formé reste ensuite immobile ; en revanche si on le retourne plus doucement, il s’effondre et s’écoule en vagues de surfaces successives.
• lorsque l’on applique une contrainte de cisaillement, le sable cède à partir d’un certain seuil qui dépend de la profondeur sur laquelle est appliquée la contrainte dans le tas : le tas est donc de plus en plus solide.

Les écoulements dans le sable : par exemple dans un sablier ne sont pas uniformes : il arrive qu’une sorte de voûte se construise et fasse obstacle à la progression des grains vers le sous-tirage. Ce phénomène fait que les ouvriers des silos à grains continuent à taper allègrement sur les parois pour détruire ces édifices naturels. Une poignée de grains bloque ainsi la sortie à une tonne de leurs semblables.

Le poids d’un silo à grains

Si l’on s’intéresse à mesurer le poids d’un silo à grains en mesurant le poids sur le fond : si le remplissage se fait avec un entonnoir, on remarque que le poids augmente eu début comme le veut la quantité de sable, mais lorsque la hauteur atteint environ le diamètre du silo, le poids mesurer n’augmente pas comme il le faudrait. En effet, les micro voûtes dont nous parlions précédemment reportent les forces et les pressions vers les parois du silo qui supporte ainsi une bonne partie du poids des grains.

On a pu noter [@], que lorsque l’on remplit le silo avec un entonnoir ce phénomène se produit et que l’on a alors une pressions minimale au centre du tas de grain : là où la hauteur est maximale : en revanche, lorsque l’on rempli le silo par couches successives horizontales : ce phénomène ne se produit pas.

La complexité du tas de sable

Un tas de sable est formé de nombreux grains reposant les uns sur les autres ; c’est à dire en interactions. On est donc bien dans la configuration d’un de plusieurs autres en interactions. Ces interactions ne sont pas en général linéaires, dues aux frottements sur des grains de forme quelconques. On est donc bien dans la configuration d’un système complexe, et certains scientifiques étudient ces systèmes en effectuant des simulations numériques. Ils ont noté deux caractéristiques :

de nombreuses voûtes de forment spontanément qui diminuent le poids apparent du sable en dessous d’elles mêmes,

Ces voûtes sont en perpétuel réarrangement : il suffit qu’un grain glisse pour que la voûte se réarrange d’une autre manière.

III.3.2. Les réseaux de neurones

Définition générale

Voir poly AJ.

• Le neurone formel
• Les architectures de réseau
• Le principe de l’apprentissage : règle de gradient

Robot hexapode

Dans le but de réaliser un robot capable d’évoluer en site naturel, nous avons développé au LGI2P un robot capable d’apprentissage.

La nécessité de l’introduction d’un apprentissage vient, selon notre analyse, de l’impossibilité de connaître avec une totale précision le milieu naturel qui entoure le robot. Si complexe que soit l’analyse de l’environnement que pourra faire le programmeur du robot, elle sera toujours mise en défaut tôt ou tard par une configuration inattendue. La position que nous avons choisie pour pallier cet inconvénient est alors de réaliser un robot qui serait capable d’apprendre seul ses comportements en fonction d’un objectif que nous lui fixons.

Trois comportements ont été testés :

• l’apprentissage de la marche,
• l’évitement d’obstacle,
• la marche en mode dégradé.

Apprentissage par renforcement

L’apprentissage par renforcement prend sa source dans l’observation de l’apprentissage chez les animaux. Lorsque l’animal (ou le robot) réalise une bonne action, il reçoit une récompense ; tandis que lorsqu’il se trompe il reçoit une punition.

L’apprentissage par renforcement pour le contrôle d’un agent nécessite la configuration minimale suivante :

• Un agent qui :

• reçoit les entrées venant de l’environnement (position, vitesse, …), ainsi qu’un éventuel retours concernant son propre état, et le signal de renforcement.
• propose ses actions.

• Mesure ou une modélisation des interactions entre les actions proposées et par l’agent et l’environnement. :

• ses entrées sont les actions proposées par l’agent,
• ses sorties sont les actions effectivement réalisées par l’agent ; les actions proposées et les actions réalisées ne sont pas nécessairement les mêmes du fait des imperfections dans la modélisation (hypothèse de départ). Par exemple, le robot peut glisser sur un sole lisse ou planter ses pattes dans du sable, …

• Une fonction heuristique qui prend ses informations à partir de capteurs et évalue les effets des actions en relation avec le comportement désiré (objectif).La fonction heuristique est appelée le “critique”, elle délivre le signal de renforcement qui informe l’agent de la qualité de ses actions.

On retrouve dans ce schéma celui que Gell-Mann a proposé pour le système adaptatif complexe (cf. chapitre II.3.).

L’algorithme de pénalité récompense appliqué à un réseau de neurones à une couche.

Présenté en premier lieu par Barto et Anandan [&], l’algorithme “Associative Reward Penality” (Arp) prend son inspiration de deux sources : tout d’abord des algorithmes d’apprentissage d’automates où le comportement d’un automate est fonction du retour probabiliste de l’environnement, et en second lieu des algorithmes d’apprentissage supervisé où une fonction de coût est minimisée au travers d’une descente de gradient classique.

L’application de l’algorithme Arp aux réseaux de neurones est suggérée par les auteurs ; elle se réalise facilement. Elle a également été formulée pour l’apprentissage de la marche hexapode sans contraintes quant à l’architecture choisie [&]. Partant du principe que plus le réseau de neurones est simple, mieux il est compris, nous avons utilisé dans une première étape le réseau le plus simple possible : un réseau à une couche de neurones binaires. L’expérience a montré, a posteriori, que ce choix était le bon.

Le réseau est composé de six neurones (un par patte) arrangés en une seule couche de type perceptron. Les sorties des neurones codent le mouvement, tandis que les entrées codent la position des pattes (Fig.1).

La sortie si = +1 correspond au mouvement “lever et avancer la patte” ; la sortie si = -1 correspond au mouvement “baisser et reculer la patte”.

Figure 1 : Réseau de neurones à une couche

Les neurones sont figurés par des cercles et les entrées par les carrés ; chaque neurone est connecté à toutes les entrées par un coefficient (flèche). Chaque neurone est indépendant des autres neurones, par exemple les connexions d’un neurone sont représentées en noir tandis que celles des autres neurones sont figurées en gris.

Les itérations du réseau sont parallèles. Chaque itération comprend les opérations suivantes :

• Pour chaque neurone, calculer la somme pondérée des entrées :

vi : Sj=1,6 cij.Ij.

Les paramètres cij sont les coefficients synaptiques, Ij est l’entrée représentant la position de la patte j, et vi est appelé le potentiel du neurone i.

• Pour chaque neurone, la sortie est calculée en appliquant un seuil bruité.

On a : si = sign(vi + bi),

Où sign est la fonction signe et bi est le bruit. Le bruit est choisi de manière à obtenir une sortie binaire (si) dépendant du bruit de la manière suivante :

• si = 1 avec la probabilité : P(+1) = ,
• et si = -1 avec : P(-1) =

ß est un paramètre qui doit être fixé préalablement à l’apprentissage.

I.2. Apprentissage

Au début de l’apprentissage, les coefficients sont initialisés aléatoirement de manière à ce que, en moyenne, chaque patte (chaque neurone) ait la même probabilité de réaliser un mouvement ou un autre (P=0,5).

A chaque itération, une fonction appelée le “critique” évalue les performances du mouvement qui a été réalisé, et envoie au réseau une information de pénalité ou de récompense notée r. Cette information est prise en compte pour effectuer la modification des coefficients synaptiques de manière à accroître la probabilité de mouvements “satisfaisants”. En ce sens, on peut dire que l’apprentissage est “supervisé” par l’environnement. Lorsque l’apprentissage se réalise bien, à la fin de la procédure, le comportement est déterministe. Il est à noter que si une modification importante se produit dans l’environnement du robot, certains des mouvements précédemment récompensés deviendront pénalisés. Ainsi, l’apprentissage redeviendra actif afin de modifier les coefficients synaptiques pour s’adapter à ces modifications. Lors de l’apprentissage, afin de comparer le mouvement désiré au mouvement produit, sans être influencé par le bruit ajouté au potentiel, Barto et Anandan introduisent la moyenne des mouvements qu’aurait fait le robot dans la même situation. Cette moyenne est calculée par l’espérance mathématique des mouvements réalisés par un grand nombre de robots identiques soumis au même type de bruit et recevant la même entrée. On la calcule ainsi :

E(si|cij, Ij) = (+1).P(+1)+(-1).P(-1) = th(ß.vi).

La règle d’apprentissage peut alors être écrite :

Si r = +1 (récompense), Dcij= µ+(r.si – E(si|cij, Ij))Ij.

Si r = -1 (pénalité), Dcij= µ-(r.si – E(si|cij, Ij))Ij.

µ+ et µ- sont deux paramètres du type “pas de gradient”, ils sont différents afin de compenser le fait qu’il existe beaucoup plus de situations pénalisantes que de situations récompensantes.

Ainsi, il apparaît que cet algorithme d’apprentissage peut être utilisé pour réaliser l’apprentissage de plusieurs tâches, celles ci étant décrites par une fonction appelé le ” critique”. Nous allons voir par la suite comment deux comportements peuvent être appris grâce à deux “critiques” différents.

Apprentissage de la marche

Position du problème et simulations

Le réseau utilisé pour réaliser l’apprentissage de la marche est celui décrit précédemment. Du fait des itérations parallèles, les mouvements sont synchrones. Nous avons choisi de coder le mouvement des pattes et non leur position afin de diminuer la dimension de l’espace des états de sortie et ainsi de diminuer le temps de convergence.

Le critique choisi pour l’apprentissage de la marche est le suivant : “avancer sans tomber”.

La règle d’apprentissage peut être rappelée ainsi : après un mouvement, si le robot chute ou reste immobile, le critique considère qu’il y a un échec, et le mouvement fait précédemment est pénalisé ; si le robot avance sans tomber, il y a réussite, et le mouvement est encouragé.

Les simulations ont montré que, lorsque les paramètres (µ+, µ-, ß) sont correctement ajustés, l’apprentissage converge rapidement (en moins de 100 itérations dans 70% des cas) vers une marche stable [&]. Il est relativement aisé de déterminer si l’apprentissage a trouvé une solution puisque les marches obtenues sont périodiques à deux états.

Marches trouvées par l’apprentissage

La patte noire représente une jambe posée au sol (poussant vers l’arrière) et la patte blanche une patte levée (ramenée vers l’avant).

Les deux marches sont périodiques à deux états.

Apprentissage de la marche et de l’évitement d’obstacle

Architecture du réseau global.

Pour réaliser les deux fonctions de marche et d’évitement d’obstacle, au moins deux solutions sont envisageables : la première consiste en un seul réseau dédié aux deux tâches, la seconde en deux réseaux, chacun réalisant une des tâches. La seconde solution nous paraît la meilleure d’une part parce que les deux comportements peuvent être appris séparément et donc de manière plus simple, et d’autre part parce qu’il n’y a aucune raison pour que les deux comportements nécessitent des paramètres d’apprentissage identiques. Le fonctionnement choisi est donc le suivant : tant que le robot ne rencontre pas d’obstacle, il est piloté par le réseau d’apprentissage de la marche. Lorsque le robot rencontre un obstacle, le réseau “marche” est inhibé, le réseau “évitement d’obstacle” entre en action et conduit le robot à éviter l’obstacle. Lorsque l’obstacle est sorti du champ de sensibilité du robot, le réseau de marche entre à nouveau en action. Le réseau global proposé, résultant des deux sous-réseaux, est représenté ci dessous.

Evitement d’obstacle

Dans un premier temps, nous avons constaté que le robot évitait toujours les obstacles (de type convexe). Afin de vérifier qu’il avait effectivement acquis ce comportement, nous avons présenté plusieurs fois le même obstacle au robot ayant déjà appris à marcher, avec les mêmes conditions initiales. Le critique retenu est le suivant : ne pas tomber, ne pas rester immobile, ne pas reculer droit, ne pas rencontrer d’obstacles en reculant. On considère que l’évitement est accompli quand le robot a avancé de dix pas successifs sans rencontrer l’obstacle.

Les nombreuses simulations effectuées montrent que les coefficients synaptiques convergent toujours. Les variations brusques des coefficients qui sont observées en cours de convergence dans certains cas correspondent à des changements importants de direction.

Nous présentons ci-dessous deux exemples des déplacements successifs du robot obtenus après la convergence d’après un travail de deux élèves en Initiation à la Recherche [MM Canal et Lang].

Exemples d’évolutions du robot contournant un obstacle.

Le robot est figuré par un segment ; il démarre en bas au centre de la figure et se dirige droit vers l’obstacle situé en haut (carré noir). Chacun des segments représente l’orientation du robot après un pas ; à chaque pas, si le robot détecte un obstacle, il doit reculer en tournant. On peut noter que le bruit inhérent à l’algorithme conduit à des trajectoires qui peuvent être très différentes.

Apprentissage d’une marche, ou continuelle marche au hasard ?

Il est intéressant de savoir si le robot apprend un moyen d’éviter un obstacle ou s’il est constamment entrain de tirer ses mouvements au hasard. Pour cela des élèves en initiation à la recherche [MM Fleury et Ruiz] ont réalisé de nombreuses tentatives d’évitement d’obstacle en gardant tous les paramètres constants hormis le tirage aléatoire permettant d’introduire du bruit. A chaque nouvelle tentative d’évitement les coefficients précédemment appris sont conservés. Ils ont pu mettre en évidence plusieurs type de convergence.

Un autre point intéressant a été observé lorsque le processus précédent a été répété un très grand nombre de fois : plus de 500 évitements avec une seule initialisation des coefficients au début du processus. La figure ci-dessous trace l’écart quadratique moyen (Mc) entre le jeu de coefficients à l’issue de l’évitement à l’évitement d’obstacle oa, et celui issu de l’évitement oa+1.

on peut remarquer sur la figure qu’un genre de dispersion apparaît lorsque l’apprentissage se poursuit très longtemps. Ce type de comportement évoque le chaos déterministe : des points de bifurcation apparaissent.

L’apparition de ce comportement chaotique n’est pas très étonnante du fait du caractère non-linéaire et bouclé du système étudié.

Comportement chaotique

Après plusieurs répétitions de l’apprentissage, le critère de convergence (Mc) converge puis se sépare en plusieurs états dégénérés, symptomatiques d’un attracteur étrange.

III.3.3. Les automates cellulaires

III.4. l’indétermination

III.4.1. La mécanique quantique

III.4.2. Le chaos déterministe

En 1961, le mathématicien et météorologue Edward Lorentz simule déjà sur un ordinateur à tubes un phénomène intervenant en météo : la convection thermique.

Il fait tourner son programme et observe les résultats : les prévisions de vitesse de vent, de température, de pluviométrie… Il est intéressant de constater que les résultats ne sont jamais les mêmes, lorsque l’on laisse le système itérer, les résultats n’atteignent jamais un fonctionnement périodique.

Un jour, pour essayer de mettre à nouveau en évidence un résultat obtenu, il réinitialise son système avec des valeurs qu’il avait notées auparavant : vitesse du vent… et là oh surprise, il se rend compte que les résultats au bout d’un certain temps diffèrent complètement de ce qu’il avait précédemment obtenu…

Il en conclu que le système est très fortement sensible aux conditions initiales et qu’il a introduit les valeurs avec une trop grande imprécision.

Lorentz se penche donc sur les équations qui décrivent son phénomène : elles sont non linéaires et le phénomène est récurrent.

Les équations de Lorentz :

On peut remarquer que ces équations sont non-linéaires et récurrentes.

En fonction des valeurs initiales des paramètres météo a, b, c, on peut obtenir plusieurs types de comportements dans l’espace des phases (http://www.ensicaen.ismra.fr/~rognier/lorentz/lancelo.html).

Quelques exemples : les courbes représentent une projection sur un plan du cheminement des valeurs d’état x, y, z, du système.

A gauche : a=2, b=1, c=0,001, on a une convergence vers un attracteur simple.

Au centre : a=2, b=-1, c=-0.001, divergence en forme de tire-bouchon.

A droite : a=3, b=28, c=3.3, convergence en forme de spirale logarithmique.

La figure la plus connue :

Le papillon de Lorentz (a=10, b=28, c=3.3).

Cet attracteur possède des propriétés particulières : les trajectoires autours des attracteurs ne sont jamais exactement les mêmes. Ce type d’attracteur est appelé “attracteur étrange” il est caractéristique du chaos.

Il est clair à la lueur des travaux de Lorentz que la prévision des phénomènes météos (qui font obligatoirement intervenir les phénomènes de convection) ne pourront jamais être totalement prédis ; tout ce que l’on peut faire est améliorer la prévision en augmentant la précision des valeurs initiales et en diminuant le maillage des mesures.

Autre aspect des phénomènes chaotique : les points de bifurcation

Lorsque le système s’éloigne de son point d’équilibre (s’il en a un), les fluctuations et perturbations ont une importance assez grande. Elles conduisent le système soit dans un type d’état, soit dans un autre (ou plusieurs autres). Ainsi au fur et à mesure que le temps s’écoule, le système dynamique non-linéaire évolue et choisi successivement plusieurs options qui sont autant de bifurcations et que l’on peut imaginer comme étant des chemins différents que prendrait un piéton.

Image tirée de : http://www-ensimag.imag.fr/eleves/Guillaume.Molleda/tipe2.htm

IV. Conclusion

L’avenir appartient aux systèmes complexes, mais nous sommes pour l’instant balbutiants, il n’y a que récemment, que l’ordinateur nous a permis de les approcher de plus près.

” Le maintien de l’organisation dans la nature n’est pas – et ne peut pas être – réalisé par une gestion centralisée, l’ordre ne peut être maintenu que par une auto-organisation. Les systèmes auto-organisateurs permettent l’adaptation aux circonstances environnementales ; par exemple ils réagissent à des modifications de l’environnement grâce à une réponse thermodynamique qui les rend extraordinairement flexibles et robustes par rapport aux perturbations externes. Nous voulons souligner la supériorité des systèmes auto-organisateurs par rapport à la technologie humaine habituelle qui évite soigneusement la complexité et gère de manière centralisée la grande majorité des systèmes techniques. Par exemple, en chimie synthétique les différentes étapes réactionnelles sont généralement soigneusement séparées les unes des autres et les contributions liées à la diffusion des réactifs sont éliminées par brassage. Une technologie entièrement nouvelle devra être développée pour exploiter le grand potentiel d’idées et de règles des système auto-organisateurs en matière de processus technologiques. La supériorité des systèmes auto-organisés est illustrée par les systèmes biologiques où des produits complexes sont formés avec une précision, une efficacité, une vitesse sans pareille”.

D’après un rapport à la Communauté Européenne, C.K. Briebracher, G. Nicolis et P. Schuster.