Teorema del esquema de Holland

El teorema de los esquemas de Holland, también llamado teorema fundamental de los algoritmos genéticos, es una desigualdad que resulta de una ecuación de la dinámica evolutiva de grano grueso. El teorema de los esquemas dice que los esquemas cortos y de bajo orden con una aptitud superior a la media aumentan exponencialmente su frecuencia en las generaciones sucesivas. El teorema fue propuesto por John Holland en la década de 1970. En un principio, se consideró el fundamento de las explicaciones de la potencia de los algoritmos genéticos. Sin embargo, esta interpretación de sus implicaciones ha sido criticada en varias publicaciones reseñadas en , donde se demuestra que el Teorema del Esquema es un caso especial de la ecuación de Price con la función indicadora del esquema como medida macroscópica.

Un esquema es una plantilla que identifica un subconjunto de cadenas con similitudes en determinadas posiciones de la cadena. Los esquemas son un caso especial de los conjuntos de cilindros y, por tanto, forman un espacio topológico.

Descripción

Considere cadenas binarias de longitud 6. El esquema 1*10*1 describe el conjunto de todas las cadenas de longitud 6 con 1 en las posiciones 1, 3 y 6 y un 0 en la posición 4. El * es un símbolo comodín, lo que significa que las posiciones 2 y 5 pueden tener un valor tanto de 1 como de 0. El orden de un esquema o ( H ) {\displaystyle o(H)} $o(H)$ se define como el número de posiciones fijas en el esquema, mientras que la longitud definitoria δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ es la distancia entre la primera y la última posición específica. El orden de 1*10*1 es 4 y su longitud definitoria es 5. La aptitud de un esquema es la aptitud media de todas las cadenas que coinciden con el esquema. La aptitud de una cadena es una medida del valor de la solución del problema codificado, calculada por una función de evaluación específica del problema. Utilizando los métodos establecidos y los operadores genéticos de los algoritmos genéticos, el teorema del esquema afirma que los esquemas cortos y de bajo orden con una aptitud superior a la media aumentan exponencialmente en las generaciones sucesivas. Expresado como una ecuación:

E ( m ( H , t + 1 ) ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] . {\displaystyle \operatorname {E} (m(H,t+1))\Ngeq {m(H,t)f(H) \Nsobre a_{t}[1-p]. } $\operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p].$

Aquí m ( H , t ) {\displaystyle m(H,t)} $m(H,t)$ es el número de cadenas que pertenecen al esquema H {\displaystyle H} $H$ en la generación t {\displaystyle t} $t$ f ( H ) {\displaystyle f(H)} $f(H)$ es la aptitud media observada del esquema H {\displaystyle H} $H$ y a t {\displaystyle a_{t}} $a_{t}$ es la aptitud media observada en la generación t {\displaystyle t} $t$ . La probabilidad de perturbación p {\displaystyle p} $p$ es la probabilidad de que el cruce o la mutación destruyan el esquema H {\displaystyle H} $H$ . Se puede expresar como

p = δ ( H ) l - 1 p c + o ( H ) p m {\displaystyle p={delta (H) \over l-1}p_{c}+o(H)p_{m}} $p={\delta (H) \over l-1}p_{c}+o(H)p_{m}$

donde o ( H ) {\displaystyle o(H)} $o(H)$ es el orden del esquema, l {\displaystyle l} $l$ es la longitud del código, p m {\displaystyle p_{m}} $p_{m}$ es la probabilidad de mutación y p c {\displaystyle p_{c}} $p_{c}$ es la probabilidad de cruce. Por lo tanto, un esquema con una longitud de definición más corta δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ tiene menos probabilidades de ser interrumpido.
Un punto que a menudo se malinterpreta es por qué el Teorema del Esquema es una desigualdad en lugar de una igualdad. La respuesta es, de hecho, sencilla: el Teorema desprecia la pequeña, aunque no nula, probabilidad de que una cadena perteneciente al esquema H {\displaystyle H} $H$ sea creada "desde cero" por la mutación de una sola cadena (o la recombinación de dos cadenas) que no pertenecía a H {\displaystyle H} $H$ en la generación anterior.

Limitación

El teorema de los esquemas se mantiene bajo el supuesto de un algoritmo genético que mantiene una población infinitamente grande, pero no siempre se traslada a la práctica (finita): debido al error de muestreo en la población inicial, los algoritmos genéticos pueden converger en esquemas que no tienen ninguna ventaja selectiva. Esto sucede en particular en la optimización multimodal, donde una función puede tener múltiples picos: la población puede derivar para preferir uno de los picos, ignorando los otros.

La razón por la que el Teorema del Esquema no puede explicar el poder de los algoritmos genéticos es que se mantiene para todas las instancias del problema, y no puede distinguir entre los problemas en los que los algoritmos genéticos funcionan mal, y los problemas para los que los algoritmos genéticos funcionan bien.

Gráfico de una función multimodal en dos variables.

Preguntas y respuestas

P: ¿Qué es el teorema del esquema de Holland?

R: El teorema del esquema de Holland es un teorema relativo a los algoritmos genéticos que dice que los individuos con una aptitud superior a la media tienen más probabilidades de prevalecer.

P: ¿Quién propuso el teorema del esquema de Holland y cuándo?

R: John Holland propuso el teorema del esquema de Holland en la década de 1970.

P: ¿Qué es un esquema en el contexto de los algoritmos genéticos?

R: En el contexto de los algoritmos genéticos, un esquema es una plantilla que identifica un subconjunto de cadenas con similitudes en determinadas posiciones de las cadenas.

P: ¿Cuál es la interpretación del teorema del esquema de Holland que se utilizó como base para las explicaciones del poder de los algoritmos genéticos?

R: La interpretación del teorema del esquema de Holland que se utilizó como fundamento de las explicaciones del poder de los algoritmos genéticos es que los individuos con una aptitud superior a la media tienen más probabilidades de prevalecer.

P: ¿Qué han demostrado las críticas al teorema del esquema de Holland?

R: Las críticas al teorema del esquema de Holland han demostrado que es un caso especial de la ecuación de Price con la función indicadora del esquema como medida macroscópica.

P: ¿Qué es un caso especial de los conjuntos cilíndricos?

R: Los esquemas son un caso especial de los conjuntos cilíndricos.

P: ¿Qué tipo de espacio forman los esquemas?

R: Los esquemas forman un espacio topológico.