Evolucionabilidad (informática)

El término evolucionabilidad es un marco de aprendizaje computacional introducido por Leslie Valiant en su artículo homónimo. El objetivo de esta teoría es modelar la evolución biológica y categorizar qué tipos de mecanismos son evolucionables. La evolución es una extensión del aprendizaje PAC y del aprendizaje a partir de consultas estadísticas.

Dejar${\displaystyle F_{n}\,}$y${\displaystyle R_{n}\,}$ser colecciones de funciones en${\displaystyle n\,}$variables. Dada una función ideal${\displaystyle f\in F_{n}}$, el objetivo es encontrar mediante búsqueda local una representación${\displaystyle r\in R_{n}}$que se aproxima mucho${\displaystyle f\,}$Esta cercanía se mide por el rendimiento .${\displaystyle \operatorname {Perf} (f,r)}$de${\displaystyle r\,}$con respecto a${\displaystyle f\,}$.

Como ocurre en el mundo biológico, existe una diferencia entre genotipo y fenotipo. En general, puede haber múltiples representaciones (genotipos) que correspondan a la misma función (fenotipo). Es decir, para algunos${\displaystyle r,r'\in R_{n}}$, con${\displaystyle r\neq r'\,}$, aún${\displaystyle r(x)=r'(x)\,}$a pesar de${\displaystyle x\in X_{n}}$Sin embargo, esto no tiene por qué ser así. El objetivo, entonces, es encontrar una representación que se ajuste lo más posible al fenotipo de la función ideal, y el espíritu de la búsqueda local es permitir solo pequeños cambios en el genotipo. Sea el vecindario${\displaystyle N(r)\,}$de una representación${\displaystyle r\,}$ser el conjunto de posibles mutaciones de${\displaystyle r\,}$.

Para simplificar, consideremos las funciones booleanas en${\displaystyle X_{n}=\{-1,1\}^{n}\,}$y dejar${\displaystyle D_{n}\,}$sea ​​una distribución de probabilidad en${\displaystyle X_{n}\,}$. Defina el desempeño en términos de esto. Específicamente,

${\displaystyle \operatorname {Perf} (f,r)=\sum _{x\in X_{n}}f(x)r(x)D_{n}(x).}$

Tenga en cuenta que${\displaystyle \operatorname {Perf} (f,r)=\operatorname {Prob} (f(x)=r(x))-\operatorname {Prob} (f(x)\neq r(x)).}$En general, para funciones no booleanas, el rendimiento no se corresponderá directamente con la probabilidad de que las funciones coincidan, aunque sí existirá alguna relación.

A lo largo de la vida de un organismo, este solo experimentará un número limitado de entornos, por lo que su rendimiento no puede determinarse con exactitud. El rendimiento empírico se define por ${\displaystyle \operatorname {Perf} _{s}(f,r)={\frac {1}{s}}\sum _{x\in S}f(x)r(x),}$ dónde${\displaystyle S\,}$es un multiconjunto de${\displaystyle s\,}$selecciones independientes de${\displaystyle X_{n}\,}$de acuerdo a${\displaystyle D_{n}\,}$. Si${\displaystyle s\,}$es lo suficientemente grande, evidentemente${\displaystyle \operatorname {Perf} _{s}(f,r)}$estará cerca del rendimiento real${\displaystyle \operatorname {Perf} (f,r)}$.

Dada una función ideal${\displaystyle f\in F_{n}}$, representación inicial${\displaystyle r\in R_{n}}$tamaño de la muestra${\displaystyle s\,}$y tolerancia${\displaystyle t\,}$, el mutador${\displaystyle \operatorname {Mut} (f,r,s,t)}$es una variable aleatoria definida de la siguiente manera. Cada${\displaystyle r'\in N(r)}$se clasifica como beneficioso, neutral o perjudicial, dependiendo de su desempeño empírico. Específicamente,

• ${\displaystyle r'\,}$es una mutación beneficiosa si${\displaystyle \operatorname {Perf} _{s}(f,r')-\operatorname {Perf} _{s}(f,r)\geq t}$;
• ${\displaystyle r'\,}$es una mutación neutral si${\displaystyle -t<\operatorname {Perf} _{s}(f,r')-\operatorname {Perf} _{s}(f,r)<t}$;
• ${\displaystyle r'\,}$es una mutación perjudicial si${\displaystyle \operatorname {Perf} _{s}(f,r')-\operatorname {Perf} _{s}(f,r)\leq -t}$.

Si hay alguna mutación beneficiosa, entonces${\displaystyle \operatorname {Mut} (f,r,s,t)}$es igual a uno de estos al azar. Si no hay mutaciones beneficiosas, entonces${\displaystyle \operatorname {Mut} (f,r,s,t)}$es igual a una mutación neutral aleatoria. En vista de la similitud con la biología,${\displaystyle r\,}$Se requiere que esté disponible como mutación, por lo que siempre habrá al menos una mutación neutral.

La intención de esta definición es que en cada etapa de la evolución, todas las mutaciones posibles del genoma actual se prueban en el ambiente. De entre las que prosperan, o al menos sobreviven, se elige una para ser la candidata a la siguiente etapa. Dado${\displaystyle r_{0}\in R_{n}}$, definimos la secuencia${\displaystyle r_{0},r_{1},r_{2},\ldots }$por${\displaystyle r_{i+1}=\operatorname {Mut} (f,r_{i},s,t)}$. De este modo${\displaystyle r_{g}\,}$es una variable aleatoria que representa qué${\displaystyle r_{0}\,}$ha evolucionado hasta después${\displaystyle g\,}$generaciones .

Dejar${\displaystyle F\,}$ser una clase de funciones,${\displaystyle R\,}$ser una clase de representaciones, y${\displaystyle D\,}$una clase de distribuciones en${\displaystyle X\,}$Decimos que${\displaystyle F\,}$es evolucionable por${\displaystyle R\,}$encima${\displaystyle D\,}$si existen polinomios${\displaystyle p(\cdot ,\cdot )}$,${\displaystyle s(\cdot ,\cdot )}$,${\displaystyle t(\cdot ,\cdot )}$, y${\displaystyle g(\cdot ,\cdot )}$de tal manera que para todos${\displaystyle n\,}$y todo${\displaystyle \epsilon >0\,}$para todas las funciones ideales${\displaystyle f\in F_{n}}$y representaciones${\displaystyle r_{0}\in R_{n}}$, con probabilidad al menos${\displaystyle 1-\epsilon \,}$,

${\displaystyle \operatorname {Perf} (f,r_{g(n,1/\epsilon )})\geq 1-\epsilon ,}$

donde los tamaños de los vecindarios${\displaystyle N(r)\,}$para${\displaystyle r\in R_{n}\,}$son como máximo${\displaystyle p(n,1/\epsilon )\,}$, el tamaño de la muestra es${\displaystyle s(n,1/\epsilon )\,}$, la tolerancia es${\displaystyle t(1/n,\epsilon )\,}$y el tamaño de la generación es${\displaystyle g(n,1/\epsilon )\,}$.

${\displaystyle F\,}$es evolucionable a lo largo del tiempo${\displaystyle D\,}$si es evolucionable por algún${\displaystyle R\,}$encima${\displaystyle D\,}$.

${\displaystyle F\,}$Es evolucionable si es evolucionable en todas las distribuciones.${\displaystyle D\,}$.

La clase de conjunciones y la clase de disyunciones pueden evolucionar sobre la distribución uniforme para conjunciones y disyunciones cortas, respectivamente.

La clase de funciones de paridad (que se evalúan como la paridad del número de literales verdaderos en un subconjunto dado de literales) no son evolucionables, ni siquiera para la distribución uniforme.

La capacidad de evolución implica la capacidad de aprendizaje PAC .

• Valiant, LG (2006), Evolubilidad , ECCC TR06-120 .

• Fidalgo, Nicholas; Ye, Puyuan (24 de julio de 2025). "Simulación de la capacidad de evolución como algoritmo de aprendizaje: investigaciones empíricas sobre la sensibilidad a la distribución, la robustez y las compensaciones de las restricciones". arXiv : 2507.18666 [ cs.CC ].