Informatique naturelle

L'informatique naturelle^[1]^,^[2], également appelée calcul naturel (ou natural computing d'après le terme anglais) est une notion introduite pour englober trois classes de méthodes : celles qui s'inspirent de la nature pour le développement de nouvelles techniques de résolution de problèmes; celles qui reposent sur l'utilisation d'ordinateurs pour synthétiser des phénomènes naturels; et enfin celles qui utilisent des matériaux naturels (par exemple, des molécules) pour effectuer des calculs.

Description

Les principaux domaines de recherche qui composent ces trois branches sont notamment les réseaux de neurones artificiels, les algorithmes évolutionnistes, l'intelligence distribuée, les systèmes immunitaires artificiels, la géométrie fractale, la vie artificielle, l'ordinateur à ADN et l'informatique quantique.

Les paradigmes informatiques étudiés par l'informatique naturelle sont des abstractions de phénomènes naturels aussi divers que l'autoréplication, le fonctionnement du cerveau, l'évolution darwinienne, la dynamique de groupe, le système immunitaire, les propriétés déterminantes des formes de vie, les membranes cellulaires ou la morphogenèse. Outre les outils électroniques traditionnels, ces paradigmes de calcul peuvent être mis en œuvre sur des supports physiques autres tels que des biomolécules (ADN, ARN) ou des dispositifs informatiques quantiques à ions piégés.

De manière duale, on peut concevoir les processus se déroulant dans la nature comme une sorte de traitement d'information. Ces processus comprennent l'auto-assemblage, les processus de développement, les réseaux de régulation de l'expression des gènes, l'interaction protéine-protéine les réseaux de transport biologique (transport actif ou passif) et l'assemblage de gènes dans les organismes unicellulaires. Les efforts pour comprendre les systèmes biologiques comprennent également l'ingénierie des organismes semi-synthétiques et la compréhension de l'univers lui-même du point de vue du traitement de l'information.

La thèse dite de Zuse-Fredkin, datant des années 1960, affirme que l'univers tout entier est un énorme automate cellulaire qui met continuellement à jour ses règles^[3]^,^[4]. Récemment, il a été suggéré que l'univers entier est un ordinateur quantique qui calcule son propre comportement^[5]. L'univers et la nature en tant que mécanisme de calcul est abordé par H. Zenil^[6] explorant la nature avec l'aide des idées de calculabilité, et par Dodig-Crnkovic et Giovagnoli^[7] qui étudient les processus naturels en tant que calculs de traitement de l'information.

Modèles de calcul inspirés de processus naturels

Les modèles de calcul inspirés de la nature les plus établis sont les automates cellulaires, le calcul neuronal et le calcul évolutif. Des systèmes de calcul plus récents inspirés de processus naturels comprennent l'intelligence en essaim, les systèmes immunitaires artificiels, le calcul membranaire et le calcul amorphe. Des descriptions détaillées sont données par exemple dans les livres de Olarius et Zomaya^[8] ou de de Castro^[9].

Automates cellulaires

Article détaillé : Automate cellulaire.

Un automate cellulaire est un système dynamique constitué d'un tableau de cellules. L'espace et le temps sont discrets et chacune des cellules peut être dans un nombre fini d' états . L'automate cellulaire met à jour les états de ses cellules de manière synchrone selon les règles de transition données a priori. L'état suivant d'une cellule est calculé par une règle de transition et il ne dépend que de son état actuel et des états de ses voisins.

Le jeu de la vie de John Horton Conway est l'un des exemples les plus connus d'automates cellulaires, et il a été démontré qu'il est le Turing-complet, donc un modèle de calcul universel. Les automates cellulaires ont été appliqués à la modélisation de processus variés tels que la communication, la croissance, la reproduction, la compétition, l'évolution et autres processus physiques et biologiques.

Calcul neuronal

Article détaillé : Réseau de neurones artificiels].

Le calcul neuronal est le domaine de recherche qui a émergé de la comparaison entre les ordinateurs et le système nerveux humain^[10]. Ce domaine vise à la fois à comprendre le fonctionnement du cerveau des organismes vivants (les neurosciences computationnelles ), et à concevoir des algorithmes efficaces basés sur la façon dont le cerveau humain traite l'information (artificial neural networks, ou ANN^[11]).

Un réseau de neurones artificiels est un réseau de neurones formels^[12]. Un neurone formel A est équipé d'une fonction $f_{A}$ , qui reçoit n nombres réels $x_{1},x_{2},\ldots ,x_{n}$ en entrée avec des poids respectifs $w_{1},w_{2},\ldots ,w_{n}$ , et qui produit en sortie la valeur réelle $f_{A}(w_{1}x_{1}+w_{2}x_{2}+\ldots +w_{n}x_{n})$ . Certains neurones sont distinguées comme neurones de sortie, et la fonction de réseau est la fonction vectorielle qui associe, aux n valeurs d'entrée, les sorties des m neurones de sortie sélectionnés. Des choix différents au niveau des poids peuvent produire des fonctions de réseau différentes pour les mêmes entrées. La rétropropagation est une méthode d'apprentissage supervisé par laquelle les poids des connexions dans le réseau sont ajustés à plusieurs reprises de manière à minimiser la différence entre le vecteur de sorties réelles et celui des sorties souhaitées. Des algorithmes d'apprentissage basés sur la rétropropagation du gradient peuvent être utilisés pour trouver des poids optimaux pour une topologie de réseau et des paires d'entrée-sortie données.

Calcul évolutif

Le calcul évolutif est un paradigme de calcul inspiré de l'évolution darwinienne^[13]^,^[14].

Trois questions principales se posent dans le calcul évolutionniste : comment tirer profit de la modification des paramètres pendant l'exécution d'un algorithme ; comment les algorithmes évolutionnistes font face à des environnements dynamiques changeants ou stochastiques ; et comment la diversité de la population influence les performances. Trois classes d'algorithmes sont l'objet de travaux théoriques : les algorithmes d'estimation de la distribution, les systèmes immunitaires artificiels et la programmation génétique.

Intelligence distribuée

Article détaillé : Intelligence distribuée.

L'intelligence distribuée, appelée aussi intelligence en essaim, désigne l'apparition de phénomènes cohérents à l'échelle d'une population dont les individus agissent selon des règles simples. L'interaction ou la synergie entre actions individuelles simples peut de façons variées permettre l'émergence de formes, organisations, ou comportements collectifs, complexes ou cohérents, tandis que les individus eux se comportent à leur échelle indépendamment de toute règle globale. C'est le comportement qui émerge de l'interaction entre les agents individuels (par exemple bactéries, fourmis, termites, abeilles, araignées, poissons, oiseaux) qui communiquent avec d'autres agents en agissant sur leur environnement local.

Matériel inspiré de la nature

Toutes les techniques de calcul mentionnées ci-dessus, bien qu'inspirées par la nature, ont été mises en œuvre jusqu'à présent principalement sur du matériel électronique traditionnel. En revanche, deux paradigmes qui sont l'ordinateur à ADN et l'informatique quantique, utilisent des types de matériel différents.

Ordinateur moléculaire

Article détaillé : Ordinateur à ADN.

L'ordinateur à ADN ou ordinateur moléculaire est un paradigme informatique dans lequel les données sont codées sous forme de biomolécules telles que brins d'ADN, et les outils de biologie moléculaire agissent sur les données pour effectuer diverses opérations, comme des opérations arithmétique ou opérations logiques).

La première réalisation expérimentale d'un ordinateur moléculaire spécialisé a été l'expérience de 1994 de Leonard Adleman qui a résolu un exemple du problème du chemin hamiltonien dans un graphe à 7 sommets par la manipulation de brins d'ADN dans des tubes à essai^[15]. Les calculs d'ADN partent d'une entrée initiale codée comme une séquence d'ADN (essentiellement une séquence au-dessus de l'alphabet à quatre lettres {A, C, G, T}), et procèdent par une succession de bio-opérations telles que le cut-and-paste (par enzymes de restriction et ligases), extraction des brins contenant une certaine sous-séquence (en utilisant la complémentarité Watson-Crick), copie (en utilisant la réaction de la polymérase^[16] . Des recherches expérimentales ont réussi à résoudre des cas plus complexes de problèmes NP-complets, comme un cas à 20 variables de 3-SAT, et des implémentations d'ADN humide de machines à états finis.

Informatique quantique

Article détaillé : Informatique quantique.

La nature en tant que traitement de l'information

Une des visée de l'informatique naturelle est de comprendre les phénomènes naturels comme un traitement de l'information. Dès les années 1960, Zuse et Fredkin ont émis l'idée que l'univers entier est un mécanisme de calcul, modélisé comme un automate cellulaire qui met continuellement à jour ses règles^[3]^,^[4]. Une approche récente de la mécanique quantique de Lloyd suggère de voir l'univers comme un ordinateur quantique qui calcule son propre comportement^[5] tandis que Vedral^[17] suggère que l'information est l'élément le plus fondamental de la réalité.

Les principaux axes de recherche dans ce domaine sont la biologie des systèmes, la biologie synthétique et le calcul cellulaire.

Bibliographie

Ouvrages récents

Benjamin Doerr et Frank Neumann (éditeurs), Theory of Evolutionary Computation : Recent Developments in Discrete Optimization, Springer Science & Business Media, 2020, xii + 506 (ISBN 978-3-030-29414-4 et 3-030-29414-5)

Articles historiques

[Kari Rozenberg 2008] Lila Kari, Grzegorz Rozenberg, « The Many Facets of Natural Computing », Communications of the ACM, vol. 51, n^o 10,‎ octobre 2008, p. 72–83 (DOI 10.1145/1400181.1400200)
[de Castro 2007] Leandro Nunes de Castro, « Fundamentals of Natural Computing: An Overview », Physics of Life Reviews, vol. 4, n^o 1,‎ mars 2007, p. 1–36 (DOI 10.1016/j.plrev.2006.10.002)

Périodiques spécialisés

International Journal of Natural Computing Research,
Natural Computing et la collection Natural Computing book series,
Theoretical Computer Science, Series C: Theory of Natural Computing

Conférences

Conference on the Theory and Practice of Natural Computing ; la 9^e conférence a lieu à Taoyuan, au Taïwan.
International Conference on Unconventional Computation and Natural Computation (UCNC) ; la 19^e conférence a lieu (à distance) à l'université Aalto, au campus d'Otaniemi à Espoo, en Finlande du 18 au 22 october 2021.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Natural Computing » (voir la liste des auteurs).

↑ Grzegorz Rozenberg, Thomas Bäck et Joost N. Kok (éditeurs), Handbook of Natural Computing, Springer Verlag, 2012, lii+052 (ISBN 978-3-540-92909-3).
↑ Anthony Brabazon, Michael O’Neill, Seán McGarraghy, Natural Computing Algorithms, Springer Verlag, 2015, xx + 554 (ISBN 9783662436301 et 978-3-662-43631-8, présentation en ligne).
↑ ^{a et b} F. Fredkin, « Digital mechanics: An informational process based on reversible universal CA », Physica D, vol. 45,‎ 1990, p. 254-270.
↑ ^{a et b} K. Zuse, « Rechnender Raum », Elektronische Datenverarbeitung, vol. 8,‎ 1967, p. 336-344.
↑ ^{a et b} Seth Lloyd, Programming the Universe: A Quantum Computer Scientist Takes on the Cosmos, Knopf, 2006.
↑ Hector Zenil (éditeur), A Computable Universe: Understanding and Exploring Nature as Computation, World Scientific Publishing Company, 2012, 810 p. (ISBN 9789814374293).
↑ Gordana Dodig-Crnkovic et Raffaela Giovagnoli, Computing Nature, Springer Science & Business Media, 2013, 269 p..
↑ Olarius S., Zomaya A. Y., Handbook of Bioinspired Algorithms and Applications, Chapman & Hall/CRC, 2005.
↑ Leandro Nunes de Castro, Fundamentals of Natural Computing: Basic Concepts, Algorithms, and Applications, CRC Press, 2006.
↑ John von Neumann, The Computer and the Brain, Yale University Press, 1958 (3^e édition 2012), 136 p. (ISBN 9780300181111, présentation en ligne) — The Computer and the Brain (en).
↑ Michael A. Arbib (éditeur), The Handbook of Brain Theory and Neural Networks, MIT Press, 2003, 1134 p. (ISBN 9780262011488, présentation en ligne).
↑ Raul Rojas, Neural Networks : A Systematic Introduction, Springer-Verlag, 1996, xx+502 (ISBN 978-3-540-60505-8).
↑ Bäck, T., Fogel, D. et Michalewicz, Z. (éditeurs), Handbook of Evolutionary Computation, IOP Publishing, 1997.
↑ Benjamin Doerr et Frank Neumann (éditeurs), Theory of Evolutionary Computation : Recent Developments in Discrete Optimization, Springer Science & Business Media, 2020, xii + 506 (ISBN 978-3-030-29414-4 et 3-030-29414-5).
↑ (en) Leonard M. Adelman, « Molecular computation of solutions to combinatorial problems », Science, vol. 266, n^o 5187,‎ 1994, p. 1021-1024 (DOI 10.1126/science.7973651, résumé) — Le premier article sur l'ordinateur à ADN. Décrit une solution pour le problème du chemin hamiltonien. Aussi disponible ici: [1]
↑ Kari, L. DNA computing - the arrival of biological mathematics). The Mathematical Intelligencer 19, 2 (1997) 9-22
↑ Vedral, V. Decoding Reality : The Universe as Quantum Information. Oxford University Press, 2010

Article liés

[handbook_NC-1] Grzegorz Rozenberg, Thomas Bäck et Joost N. Kok (éditeurs), Handbook of Natural Computing, Springer Verlag, 2012, lii+052 (ISBN 978-3-540-92909-3).

[NCA_book-2] Anthony Brabazon, Michael O’Neill, Seán McGarraghy, Natural Computing Algorithms, Springer Verlag, 2015, xx + 554 (ISBN 9783662436301 et 978-3-662-43631-8, présentation en ligne).

[Fredkin90-3] {a et b} F. Fredkin, « Digital mechanics: An informational process based on reversible universal CA », Physica D, vol. 45,‎ 1990, p. 254-270.

[Zuse67-4] {a et b} K. Zuse, « Rechnender Raum », Elektronische Datenverarbeitung, vol. 8,‎ 1967, p. 336-344.

[Lloyd06-5] {a et b} Seth Lloyd, Programming the Universe: A Quantum Computer Scientist Takes on the Cosmos, Knopf, 2006.

[Zenil12-6] Hector Zenil (éditeur), A Computable Universe: Understanding and Exploring Nature as Computation, World Scientific Publishing Company, 2012, 810 p. (ISBN 9789814374293).

[Dodig-Crnkovic13-7] Gordana Dodig-Crnkovic et Raffaela Giovagnoli, Computing Nature, Springer Science & Business Media, 2013, 269 p..

[Olarius-8] Olarius S., Zomaya A. Y., Handbook of Bioinspired Algorithms and Applications, Chapman & Hall/CRC, 2005.

[de_Castro-9] Leandro Nunes de Castro, Fundamentals of Natural Computing: Basic Concepts, Algorithms, and Applications, CRC Press, 2006.

[Neumann58-10] John von Neumann, The Computer and the Brain, Yale University Press, 1958 (3^e édition 2012), 136 p. (ISBN 9780300181111, présentation en ligne) — The Computer and the Brain (en).

[Arbib03-11] Michael A. Arbib (éditeur), The Handbook of Brain Theory and Neural Networks, MIT Press, 2003, 1134 p. (ISBN 9780262011488, présentation en ligne).

[Rojas96-12] Raul Rojas, Neural Networks : A Systematic Introduction, Springer-Verlag, 1996, xx+502 (ISBN 978-3-540-60505-8).

[13] Bäck, T., Fogel, D. et Michalewicz, Z. (éditeurs), Handbook of Evolutionary Computation, IOP Publishing, 1997.

[14] Benjamin Doerr et Frank Neumann (éditeurs), Theory of Evolutionary Computation : Recent Developments in Discrete Optimization, Springer Science & Business Media, 2020, xii + 506 (ISBN 978-3-030-29414-4 et 3-030-29414-5).

[Adleman94-15] (en) Leonard M. Adelman, « Molecular computation of solutions to combinatorial problems », Science, vol. 266, n^o 5187,‎ 1994, p. 1021-1024 (DOI 10.1126/science.7973651, résumé) — Le premier article sur l'ordinateur à ADN. Décrit une solution pour le problème du chemin hamiltonien. Aussi disponible ici: [1]

[Kari97-16] Kari, L. DNA computing - the arrival of biological mathematics). The Mathematical Intelligencer 19, 2 (1997) 9-22

[Vedral10-17] Vedral, V. Decoding Reality : The Universe as Quantum Information. Oxford University Press, 2010

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]