Résumé - Simuler l'évolvabilité comme algorithme d'apprentissage : Enquêtes empiriques sur la sensibilité aux distributions, la robustesse et les compromis liés aux contraintes

Simuler l'évolvabilité comme algorithme d'apprentissage : Enquêtes empiriques sur la sensibilité aux distributions, la robustesse et les compromis liés aux contraintes

2025-07-24 04:32:31

{"Nicholas Fidalgo","Puyuan Ye"}

{cs.CC}

Ce papier investigate le concept d'évolubilité, introduit par Valiant en 2009, qui formnalise l'évolution comme un algorithme d'apprentissage contraint opérant sans exemples étiquetés ou connaissance structurale. Les auteurs implémentent un algorithme génétique qui simule le modèle de Valiant et conductent des expériences extensives sur six classes de fonctions booléennes : conjonctions monotones, disjonctions monotones, parité, majorité, conjonctions générales, et disjonctions générales. L'étude examine l'évolubilité sous des distributions uniformes et non uniformes, investigate les effets des hypothèses initiales fixes et la suppression des mutations neutres, et met en lumière comment ces contraintes altèrent le comportement de convergence. Les auteurs valident des résultats connus (par exemple, l'évolubilité des conjonctions monotones, l'inévolubilité de la parité) et offrent la première preuve empirique sur l'évolubilité des classes booléennes générales et de majorité. Les résultats révèlent des baisses soudaines de performance à des dimensions intermédiaires (par exemple, n = 10) et exposent le rôle essentiel des mutations neutres pour éviter les plateaux de fitness. Les auteurs démontrent également que l'évolubilité peut dépendre fortement de la distribution des entrées. Ces insights clarifient les limites pratiques de la recherche évolutionnaire et suggèrent de nouvelles directions pour les travaux théoriques, y compris des refinements potentiels aux définitions et bornes de l'évolubilité. L'implémentation fournit un cadre rigoureux et extensible pour l'analyse empirique et sert de banc d'essai pour des explorations futures de l'apprentissage par évolution. L'étude contribue à une conversation croissante en sciences théoriques des ordinateurs sur les limites de l'apprentissage possible et fournit des insights précieux sur le comportement pratique de la recherche évolutionnaire et les facteurs qui influencent son succès.