Chapitre 1 : Calcul évolutionnaire
Le terme « calcul évolutionnaire » fait référence à la fois à un domaine de l'intelligence artificielle et de l'informatique douce dans le domaine de l'informatique qui étudie divers algorithmes d'optimisation et à une famille d'algorithmes d'optimisation globale qui s'inspirent de l'évolution biologique. Pour parler plus techniquement, ils appartiennent à la famille des résolveurs de problèmes par essais et erreurs basés sur la population qui ont une saveur d'optimisation métaheuristique ou stochastique.
Le processus de calcul évolutionnaire commence par la génération d'un pool préliminaire de solutions possibles, qui est ensuite amélioré de manière itérative. Afin de développer chaque nouvelle génération, nous supprimons d'abord les solutions les moins souhaitables à l'aide d'un processus stochastique, puis nous effectuons des ajustements aléatoires minutieux. Dans le langage de la biologie, une population de solutions potentielles est « mutée » après avoir été exposée à la sélection naturelle (voire à la sélection artificielle). En conséquence, la population finira par évoluer pour croître en fitness, à savoir la fonction de fitness que l'algorithme a sélectionnée pour représenter la fitness.
En raison de sa capacité à fournir des solutions hautement optimales dans une grande variété de contextes de problèmes, les approches informatiques évolutionnistes prennent de plus en plus d'importance dans le domaine de l'informatique. Il existe de nombreuses autres versions et extensions disponibles, chacune d'entre elles étant adaptée à une famille particulière de problèmes ou à une structure de données. Dans le domaine de la biologie évolutive, le calcul évolutionniste est également utilisé à l'occasion sous la forme d'une méthode expérimentale in silico pour étudier divers aspects des processus évolutifs généraux.
L'idée d'imiter les processus évolutifs afin de résoudre des problèmes remonte à une époque antérieure à l'invention des ordinateurs et comprend des exemples tels que la proposition d'Alan Turing en 1948 d'une technique connue sous le nom de recherche génétique. L'objectif principal de Holland était d'utiliser des algorithmes génétiques pour rechercher l'adaptation et comprendre comment elle pouvait être reproduite, contrairement aux autres techniques, qui étaient largement axées sur la recherche de solutions aux problèmes. Une technique de sélection artificielle a été utilisée pour modifier les populations de chromosomes, qui étaient chacun représentés par des chaînes de bits. Cette procédure sélectionnait certains bits d'allèle inclus dans la chaîne de bits. Les interactions entre les chromosomes étaient l'une des nombreuses approches utilisées pour reproduire la recombinaison de l'ADN qui se produit naturellement entre divers types d'animaux. Les algorithmes génétiques de Holland surveillaient d'énormes populations, alors que les systèmes précédents ne pouvaient suivre qu'une seule créature optimale à la fois (en faisant rivaliser la progéniture avec leurs parents) (en faisant rivaliser de nombreux organismes à chaque génération).
Dans les années 1990, une nouvelle méthode de calcul évolutionniste est apparue, qui serait plus tard connue sous le nom de programmation génétique. John Koza était l'une des nombreuses personnes qui soutenaient cette ligne de pensée. Dans ce genre d'algorithme, ce qui évoluait était vraiment un programme qui avait été créé dans un langage de programmation de haut niveau (il y avait eu quelques tentatives antérieures dès 1958 pour utiliser du code machine, mais elles avaient rencontré peu de succès). Les programmes utilisés par Koza étaient appelés Lisp S-expressions, et vous pouvez conceptualiser ces expressions comme des arbres composés de sous-expressions. Ce modèle permet aux programmes d'échanger des sous-arbres, ce qui est similaire au mélange de matériel génétique. La mesure dans laquelle un programme est capable de mener à bien une tâche prédéterminée lui vaut un score, qui est ensuite utilisé dans un processus de sélection artificiel. Le concept de programmation génétique a été utilisé avec succès dans un certain nombre de domaines, notamment la planification, l'induction de séquences et la reconnaissance de formes.
Bien que leurs contributions ne relèvent pas nécessairement de l'une des principales branches historiques du sujet, un grand nombre d'autres personnes ont joué un rôle dans le développement de l'informatique évolutive tout au long de son histoire. Nils Aall Barricelli a développé les premières simulations informatiques de l'évolution en 1953, en utilisant des algorithmes évolutionnaires et des approches de vie artificielle. Les premiers résultats de ces simulations ont été publiés en 1954.
La plupart du temps, les méthodes d'optimisation métaheuristiques sont impliquées dans les stratégies de calcul évolutionnistes. Le domaine peut être divisé en plusieurs catégories :
Modélisation basée sur les agents
Optimisation des colonies de fourmis
Systèmes immunitaires artificiels
Vie artificielle (voir aussi organisme numérique)
Algorithmes culturels
Évolution différentielle
Développement ou évolution en deux phases
Les techniques d'estimation des distributions
Algorithmes évolutifs
Programmation évolutive
Stratégie d'évolution
Programmation de l'expression génique
Algorithme génétique
Programmation génétique
Évolution grammaticale
Modèle d'évolution apprenant
Systèmes de classification d'apprentissage
Algorithmes mémétiques
Neuroévolution
Optimisation de l'essaim de particules
L'auto-organisation, y compris l'utilisation de cartes d'auto-organisation, ainsi que l'apprentissage compétitif
Intelligence en essaim
Le domaine du calcul évolutionnaire contient un sous-domaine connu sous le nom d'algorithmes évolutionnaires. Les algorithmes évolutionnaires sont un sous-domaine du calcul évolutionniste car, en général, ils n'impliquent que des techniques qui mettent en ouvre des mécanismes évolutifs inspirés de l'évolution biologique. Ces mécanismes évolutifs comprennent la reproduction, la mutation, la recombinaison, la sélection naturelle et la survie du plus apte. Les solutions candidates au problème d'optimisation agissent en tant que membres d'une population, et la fonction de coût est responsable de déterminer l'environnement dans lequel les solutions « vivent » (voir aussi fonction d'aptitude). Après avoir soumis à plusieurs reprises la population aux opérateurs susmentionnés, l'évolution de la population finira par avoir lieu.
Deux facteurs principaux sont à l'ouvre dans ce processus qui, ensemble, constituent la base des systèmes évolutifs : la recombinaison La variété essentielle et, par conséquent, la capacité d'originalité sont produites par la mutation et le croisement, tandis que la sélection fonctionne comme une force motrice pour améliorer la qualité génétique.
La stochasticité peut être observée dans de nombreuses facettes d'un processus évolutif comme celui-ci. Les bits d'information qui ont été modifiés à la suite d'une recombinaison et d'une mutation sont sélectionnés au hasard. D'autre part, les opérateurs de sélection peuvent être soit déterministes, soit stochastiques selon la situation. Dans le deuxième scénario, les personnes qui ont une meilleure condition physique ont une plus grande probabilité d'être choisies que les personnes qui ont une condition physique inférieure, mais dans la plupart des cas, même les personnes les moins en forme ont une chance de devenir parent ou de vivre.
La théorie des systèmes dynamiques est liée aux algorithmes génétiques car ils sont utilisés pour faire des prédictions sur les états futurs d'un système. Ces prédictions peuvent être utilisées pour modéliser les systèmes biologiques et la biologie des systèmes. Les algorithmes génétiques donnent des méthodologies de modélisation. Ce n'est qu'une méthode dramatique pour attirer l'attention sur la nature ordonnée, bien contrôlée et hautement organisée du développement en biologie ; Néanmoins, cela peut être trompeur.
Malgré cela, l'application des algorithmes et de l'informatique, en particulier la théorie informatique, est également cruciale pour le processus de compréhension de l'évolution elle-même ; Cela est vrai même lorsque la similitude avec les systèmes dynamiques est ignorée.
La valeur de cette théorie est qu'elle reconnaît qu'il n'y a pas de régulation centrale du développement ; Au contraire, la croissance des organismes est la conséquence d'interactions locales à l'intérieur et entre les cellules. Les concepts qui semblent conduire à une ressemblance apparemment étroite entre les processus qui se déroulent à l'intérieur des cellules et le fonctionnement de bas niveau des ordinateurs actuels sont ceux qui nous semblent être les théories les plus prometteuses concernant les parallèles entre le développement de programmes.
Le parallèle entre l'informatique et l'interaction entre les systèmes d'hérédité et la structure biologique, qui est largement considéré comme l'un des défis les plus graves dans la compréhension des débuts de la vie, est également inclus dans cette comparaison.
Automates évolutifs.
La liste des chercheurs actuellement en activité est intrinsèquement fluide et n'a pas vocation à être exhaustive. L'année 2007 a vu la publication d'une étude qui a analysé le réseau...
