La simplicité mathématique peut être à l'origine de la vitesse d'évolution.

Les informaticiens se tournent vers la biologie évolutive pour trouver l'inspiration pour trouver des solutions optimales dans des ensembles de dimensions astronomiques

En étudiant les vastes espaces de solutions possibles au problème, nous sommes confrontés au fait que la plupart des chemins seront des impasses. Mais l'évolution a peut-être trouvé des moyens d'augmenter les chances de succès.

Les créationnistes aiment insister sur le fait que l'évolution devrait collecter jusqu'à 300 acides aminés dans le bon ordre, uniquement pour créer une seule protéine humaine de taille moyenne. Et comme à chaque position l'un des 20 acides aminés possibles pourrait être localisé, il semblerait qu'il y ait plus de ^{20 300} options de recherche, ce qui est beaucoup plus élevé que le nombre d'atomes dans l'Univers observable. Même si nous trouvons une redondance en raison de laquelle certaines de ces options seront équivalentes, la probabilité que l'évolution soit tombée sur la bonne combinaison par accident et mutations aléatoires semble monstrueusement petite, même avec des milliards d'années.

Le principal inconvénient de tels arguments est que l'évolution n'a pas connu ces séquences par hasard: le processus de sélection naturelle a éliminé l'inutile. En outre, il est probable que la nature ait découvert d'autres solutions de contournement, des moyens de réduire un grand nombre de probabilités à de petits sous-ensembles étudiables qui sont plus susceptibles de fournir des solutions utiles.

Les informaticiens ont des problèmes similaires, qui incluent la recherche de solutions optimales parmi les nombreuses options de taille astronomique. Certains d'entre eux se tournent vers la biologie pour s'en inspirer - malgré le fait que les biologistes eux-mêmes essaient seulement de comprendre comment cela se passe dans la nature.

Les algorithmes génétiques, des méthodes d'optimisation qui sont populaires depuis plusieurs décennies, utilisent les principes de la sélection naturelle pour créer de nouvelles conceptions (pour les robots, les médicaments et les systèmes de transport, entre autres), former des réseaux de neurones ou crypter et décrypter des données. Cette technologie commence par le fait que les solutions aléatoires au problème sont considérées comme des «organismes» qui ont certaines caractéristiques, ou des éléments qui sont «génétiquement» définis dans leur code. Ces solutions ne sont pas particulièrement bonnes, mais elles subissent ensuite diverses mutations aléatoires (et parfois d'autres changements qui copient le processus de réarrangement des gènes) et produisent la deuxième génération d'organismes, qui à leur tour testent leur utilité pour résoudre le problème. En conséquence, après de nombreuses répétitions, ce processus conduit à l'émergence d'un individu ou d'une décision extrêmement bien adapté.

Certains experts poussent cette méthode au niveau supérieur, faisant de la programmation génétique pour obtenir des programmes qui peuvent écrire des programmes et produire des solutions efficaces (ici, les «gènes» peuvent être des lignes de code). Cet objectif s'est révélé particulièrement difficile à atteindre, car les chercheurs doivent tenir compte de certains types de données et de structures, ainsi que de nombreuses autres conditions.

Fait intéressant, ces méthodes de pensée basées sur l'évolution (en particulier la programmation génétique) se croisent conceptuellement avec une théorie mathématique qui a toujours été quelque part à la périphérie de la biologie et de l'informatique. Récemment, certains scientifiques ont essayé de l'utiliser pour comprendre comment l'évolution, naturelle et artificielle, peut fonctionner efficacement, créer quelque chose de nouveau et apprendre à apprendre. L'essentiel ici était un concept spécial de complexité, de caractère aléatoire et d'information, qui n'avait aucune application pratique - jusqu'à aujourd'hui.

Des singes derrière les claviers

Cette théorie, inventée dans les années 1960, fonctionne avec ce qu'on appelle l'information algorithmique. Cela part d'une manière intuitive de penser la probabilité et la complexité: l'idée que pour certaines données d'entrée, il sera plus difficile sur le plan informatique de décrire comment créer quelque chose que de le créer. Prenez l'analogie bien connue avec un singe, en appuyant sur les touches au hasard. Les chances qu'elle imprime les 15 000 premiers chiffres du nombre π sont ridiculement petites - et ils diminuent de façon exponentielle avec l'augmentation du nombre de chiffres.

Mais si nous interprétons les frappes comme du texte aléatoire pour un programme informatique qui affiche le nombre π, alors les chances de succès, ou «probabilité algorithmique», sont radicalement améliorées. Le code pour afficher les 15 000 premiers chiffres du nombre π dans le langage C, par exemple, vous pouvez presser un total de 133 caractères au maximum.

En d'autres termes, la théorie algorithmique de l'information dit que la probabilité de donner certains types de résultats est beaucoup plus élevée lorsque des processus aléatoires opèrent au niveau du programme qui décrit ces données qu'au niveau des données elles-mêmes, car le programme sera court. En ce sens, les structures complexes - par exemple, les fractales - sont beaucoup plus faciles à obtenir par accident.

Cependant, un problème est rapidement apparu avec cette approche: les mathématiciens ont découvert que la complexité algorithmique (également connue sous le nom de complexité de Kolmogorov , du nom d' Andrei Nikolaevich Kolmogorov , l'un des fondateurs de la théorie) des données de sortie données - la longueur du programme le plus court possible qui les produira - ne peut pas être calculée . Par conséquent, les informaticiens ne peuvent pas trouver le moyen idéal pour compresser une chaîne ou un autre objet.


La complexité algorithmique du réseau de gauche est élevée, car pour le décrire, vous devez lister toutes les arêtes reliant les sommets. Au milieu, la complexité est moindre, car en décrivant ce réseau, on peut écrire que le sommet A se connecte à tous les autres. Le bon réseau a le moins de difficulté, car sa description consiste dans le fait que tous les sommets sont reliés deux à deux par des arêtes.

En conséquence, la théorie algorithmique de l'information a été développée principalement dans le domaine des mathématiques pures, où elle est utilisée pour étudier des théorèmes connexes et déterminer les concepts de hasard et de structure. Son utilisation pratique semblait inaccessible. "Mathématiquement, il s'agit d'une mesure simple et belle de la complexité", a déclaré le célèbre mathématicien Gregory Chaitin, l'un des fondateurs de la théorie, qui a travaillé au Thomas J. Watson IBM Center et à l'Université fédérale de Rio de Janeiro. "Mais du point de vue de l'applicabilité dans le monde réel, cela semblait imprenable."

Mais cela ne l'a pas fait reculer. Il espérait que cette théorie pourrait être utilisée pour formaliser l'idée que l'ADN se comporte comme un programme. En 2012, il a publié un livre où il a décrit comment l'évolution peut être représentée comme une marche aléatoire dans l'espace du programme. Il a écrit que les mutations qui se produisent le long de cette voie ne sont pas soumises à une distribution de probabilité statistiquement aléatoire; ils obéissent à une distribution basée sur la complexité de Kolmogorov. Mais il n'a pas pu le vérifier.

Maintenant, certains scientifiques espèrent relancer cette théorie dans ce contexte, et la connecter en même temps à la biologie et à l'informatique.

Le désir de simplicité

Hector Zenil , spécialiste informatique à l'Institut Karolinska en Suède, fait partie de ceux qui tentent de faire revivre cette théorie. Il travaille avec d'autres chercheurs pour utiliser la complexité de Kolmogorov comme métrique pour analyser la complexité des réseaux biologiques - par exemple, les réseaux de régulation des gènes ou l'interaction des protéines dans les cellules. Les chercheurs estiment approximativement le contenu algorithmique du réseau (la valeur exacte n'est pas calculable), puis ils mutent le réseau et vérifient dans quelle mesure il affecte la complexité de Kolmogorov. Ils espèrent que cette méthode leur donnera une idée de l'importance relative des différents éléments du réseau et de sa réponse fonctionnelle aux changements intentionnels.


Le célèbre mathématicien Gregory Chaitin, l'un des fondateurs de la théorie algorithmique de l'information

Dans un récent travail publié sur arxiv.org, ils ont décrit que si vous faites évoluer le réseau vers une complexité croissante de Kolmogorov - en introduisant des mutations qui augmentent le programme de description du réseau - cela conduit généralement à une augmentation du nombre de fonctions qu'il peut exécuter. réseau, tout en le rendant plus sensible aux perturbations. Lorsqu'ils ont forcé le réseau à devenir plus simple, les fonctions sont devenues moins nombreuses et la stabilité a augmenté.

Cependant, on ne sait pas encore si la complexité de Kolmogorov peut jouer un rôle plus important qu’un simple outil - par exemple, comme le croit Chaytin, être le principal moteur du changement. Malgré tous les problèmes, l'information algorithmique semble être une théorie intéressante pour la biologie. Traditionnellement, pour décrire la dynamique évolutive, les mathématiques étaient utilisées dans le domaine de la génétique des populations - des modèles statistiques décrivant la fréquence des gènes dans la population. Cependant, la génétique des populations a ses propres limites: elle ne décrit pas l'origine de la vie et d'autres processus transitoires biologiques de base, ni l'apparition de gènes complètement nouveaux. "Dans cette belle théorie mathématique, l'idée de la créativité biologique a été en quelque sorte perdue", a déclaré Chaitin. Mais si nous prenons en compte les informations algorithmiques, a-t-il dit, "alors la créativité s'intègre naturellement dans le tableau d'ensemble".

Ainsi que l'idée que le processus évolutif s'améliore avec le temps et augmente l'efficacité. «Je suis convaincu que l'évolution est en train d'apprendre», a déclaré Daniel Polanyi , spécialiste des technologies de l'information et professeur d'intelligence artificielle à l'Université du Hertfordshire en Angleterre. "Je ne serai pas surpris si cela peut s'exprimer par une diminution asymptotique de la complexité algorithmique."

Zenil et l'équipe ont décidé de tester expérimentalement les conséquences biologiques et informatiques de l'influence de la plateforme de complexité algorithmique. En utilisant la même technique d'estimation de la complexité qu'ils ont utilisée pour analyser et perturber les réseaux, ils ont mené «l'évolution» des réseaux génétiques artificiels vers des objectifs spécifiques - des matrices de zéros et des dénotant des interactions génétiques - en choisissant des mutations qui ont produit des matrices moins de complexité algorithmique. En d'autres termes, ils ont fait une sélection en faveur de structures plus grandes.


Hector Zenil, spécialiste en informatique, Caroline Institute

Récemment, ils ont publié les résultats dans la revue Royal Society Open Science, d'où il ressort que, par rapport aux mutations statistiquement aléatoires, leur sélection de mutations a conduit à une accélération significative du développement de réseaux vers des solutions. D'autres caractéristiques sont également apparues, par exemple des structures constantes et régulières - des sections de matrices qui avaient déjà atteint un certain degré de simplicité, que les nouvelles générations ne pouvaient guère améliorer. "Les régions individuelles étaient plus ou moins sensibles aux mutations simplement parce qu'elles avaient déjà atteint un certain niveau de simplicité", a déclaré Zenil. "C'était très similaire aux gènes." Cette mémoire génétique a permis à de grandes structures d'émerger plus rapidement - les chercheurs pensent qu'il s'ensuit que des mutations algorithmiquement probables peuvent conduire à des poussées de diversité et d'extinction.

"Cela signifie", a déclaré Zenil, "qu'il sera très fructueux de considérer les processus de calcul dans l'étude de l'évolution." Il espère utiliser cette compréhension du caractère aléatoire et de la complexité pour identifier les voies d'échange qui peuvent être plus sensibles aux mutations, ou pour comprendre pourquoi certaines interactions génétiques peuvent être associées à des maladies telles que le cancer.

Evolution du programme

Zenil espère comprendre si l'évolution biologique fonctionne selon les mêmes règles de calcul, mais la plupart des experts ont des doutes. Il n'est pas clair quel mécanisme naturel pourrait être responsable d'une estimation approximative de la complexité algorithmique ou de forcer les mutations à se développer de manière ciblée. De plus, «croire que la vie est complètement codée en quatre lettres serait faux», a expliqué Giuseppe Longo , mathématicien au Centre national de la recherche scientifique. "L'ADN est extrêmement important, mais n'a pas de sens en dehors de la cellule, de l'organisme ou de l'écosystème." D'autres interactions fonctionnent et l'utilisation d'informations algorithmiques ne peut couvrir toute cette complexité.

Néanmoins, ce concept a suscité un certain intérêt - en particulier parce que de telles vues sur l'évolution et les processus informatiques ont quelque chose en commun, au moins un thème commun, dans le but de la programmation génétique - pour obtenir un programme qui peut évoluer.

Il y avait déjà des allusions assez intrigantes au lien potentiel entre les idées de Chaitin et Zenil liées à la complexité de Kolmogorov et aux méthodes de programmation génétique. Par exemple, en 2001, une équipe de chercheurs a signalé que la complexité de la production d'un programme génétique est limitée par la complexité de Kolmogorov du programme d'origine.

Mais pour la plupart, la complexité de Kolmogorov n'a pas joué un rôle dans les tentatives des informaticiens de comprendre ces idées. Ils ont essayé d'autres façons de changer la génétique et les mutations. Certains groupes ont changé la vitesse des mutations, d'autres ont forcé le système à tendre vers des mutations qui ont remplacé de gros morceaux de code. «Les gens ont mis au point des dizaines, et peut-être des centaines, de versions différentes de mutations et de génotypes», a déclaré Lee Spector , spécialiste en informatique au Hampshire College dans le Massachusetts. Spector a récemment dirigé une équipe qui a démontré les avantages d’ ajouter et de supprimer des mutations dans tout le génome du corps par rapport au remplacement direct d’un gène par un autre. Ce nouveau type d'opérateur génétique a augmenté de façon exponentielle le nombre de chemins à travers l'espace de recherche génétique et a finalement conduit à de meilleures solutions.


Lee Spector, spécialiste en informatique au Hampshire College, Massachusetts

Cependant, de nombreux chercheurs sont allés dans la direction opposée, à la recherche de moyens ingénieux pour accélérer le processus, rétrécissant le champ des recherches, mais ne le limitant pas tellement que la recherche manquerait des résultats optimaux. Une idée était de faire de la simplicité un objectif: dans les années 1960, Eugene Wigner a noté «l'efficacité déraisonnable des mathématiques dans les sciences naturelles» et les informaticiens ont constaté que des modèles souvent plus simples et plus élégants sont plus efficaces et plus souvent applicables. "La question est", a déclaré Spector, "ce fait nous dit quelque chose de profond sur la structure de l'Univers, ou non?" Et cela nous sera-t-il utile? »

Il avertit également que les tentatives de pousser les programmes en évolution vers la simplicité peuvent être destructrices: récompenser les programmes pour leur brièveté peut réduire ce qui semble être des ordures maintenant, mais il peut être utile pour les générations futures, entraînant le sacrifice de solutions optimales. "Et nous sommes coincés", a-t-il dit.

Cependant, la simplicité reste un objectif séduisant, qui a d'ailleurs démontré son utilité. Dans un article publié l'année dernière, Spector et ses collègues ont constaté que si vous réduisez la taille des programmes - parfois de seulement 25% de la longueur d'origine - après avoir appliqué des techniques de programmation génétique, alors les programmes pourraient faire mieux avec de nouvelles données et pourraient être utilisés sur un plus large éventail de problèmes.

En particulier, pour cette raison, il suit les travaux dans le domaine de la théorie algorithmique de l'information, bien qu'il affirme que son impact sur ce domaine de la recherche reste à voir.

Apprendre de la vie

Peut-être que l'équipe Zenil a fait le premier pas dans la recherche de cette influence - cependant, pour une application réaliste de leur travail, ils doivent d'abord tester leur méthode sur d'autres types de problèmes de recherche.

Et pourtant, "ils ont démontré de manière convaincante la nécessité de contraintes basées sur la structure", a déclaré Larisa Albantakis , neuroscientifique et théoricienne à l'Université du Wisconsin, qui a également travaillé pour accélérer les algorithmes génétiques en limitant l'espace de recherche. "La nature est structurée, et si vous prenez cela comme point de départ, il serait insensé d'essayer de tester toutes les mutations homogènes possibles." Et elle a ajouté: "Tout ce qui a du sens pour nous est en quelque sorte structuré."

Et bien que Spector soit sceptique quant au fait que le travail de Zenil peut être appliqué à quelque chose en dehors de la portée de la tâche spécifique qu'il a étudiée, "la théorie de l'information qui sous-tend leurs concepts est intrigante et potentiellement très importante", a-t-il déclaré. "Cela me semble intéressant, en partie parce qu'il semble en quelque sorte étranger." Il y a peut-être des idées que les camarades de notre communauté ignorent. » En effet, les informations algorithmiques concernent un large éventail d'idées que certains experts en programmation génétique peuvent ne pas inclure dans leur travail, par exemple, la nature illimitée de l'évolution.

"J'ai un fort sentiment de quelque chose d'important dans ce domaine", a déclaré Spector. Cependant, at-il ajouté, jusqu'à présent "il y a une énorme distance entre leur travail et leurs applications pratiques".

"L'idée d'imaginer la vie comme un programme en évolution est très fructueuse", a déclaré Chaitin, bien que sa valeur soit encore trop tôt pour être déterminée. Que nous parlions de vie artificielle ou biologique, "nous devons voir jusqu'où nous pouvons aller".