Teorema del esquema de Holland

El teorema de esquema de Holland , también llamado teorema fundamental de los algoritmos genéticos , ^[1] es una desigualdad que resulta de granular de manera gruesa una ecuación para la dinámica evolutiva . El teorema de esquema dice que los esquemas cortos y de bajo orden con aptitud superior a la media aumentan exponencialmente en frecuencia en generaciones sucesivas. El teorema fue propuesto por John Holland en la década de 1970. Inicialmente se tomó ampliamente como la base para las explicaciones del poder de los algoritmos genéticos . Sin embargo, esta interpretación de sus implicaciones ha sido criticada en varias publicaciones revisadas en, ^[2] donde se muestra que el teorema de esquema es un caso especial de la ecuación de Price con la función indicadora de esquema como la medida macroscópica.

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

Descripción

Consideremos cadenas binarias de longitud 6. El esquema 1*10*1describe 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 de 1 o 0. El orden de un esquema se define como el número de posiciones fijas en la plantilla, mientras que la longitud de definición es la distancia entre la primera y la última posición específica. El orden de es 4 y su longitud de definición es 5. La aptitud de un esquema es la aptitud promedio 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 establece que los esquemas cortos de orden bajo con una aptitud superior a la media aumentan exponencialmente en generaciones sucesivas. Expresado como una ecuación: ${\displaystyle o(H)}$ ${\displaystyle \delta (H)}$1*10*1

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

Aquí está el número de cadenas que pertenecen al esquema en la generación , es la aptitud promedio observada del esquema y es la aptitud promedio observada en la generación . La probabilidad de interrupción es la probabilidad de que el cruce o la mutación destruyan el esquema . Bajo el supuesto de que , se puede expresar como: ${\displaystyle m(H,t)}$ ${\displaystyle H}$ ${\displaystyle t}$ ${\displaystyle f(H)}$ ${\displaystyle H}$ ${\displaystyle a_{t}}$ ${\displaystyle t}$ ${\displaystyle p}$ ${\displaystyle H}$ ${\displaystyle p_{m}\ll 1}$

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

donde es el orden del esquema, es la longitud del código, es la probabilidad de mutación y es la probabilidad de cruce. Por lo tanto, un esquema con una longitud de definición más corta tiene menos probabilidades de ser alterado. Un punto que a menudo se malinterpreta es por qué el Teorema del Esquema es una desigualdad en lugar de una igualdad. De hecho, la respuesta es simple: el Teorema descuida la pequeña, pero no nula, probabilidad de que una cadena que pertenece al esquema se cree "desde cero" por mutación de una sola cadena (o recombinación de dos cadenas) que no pertenecía a la generación anterior. Además, la expresión para es claramente pesimista: dependiendo del compañero de apareamiento, la recombinación puede no alterar el esquema incluso cuando se selecciona un punto de cruce entre la primera y la última posición fija de . ${\displaystyle o(H)}$ ${\displaystyle l}$ ${\displaystyle p_{m}}$ ${\displaystyle p_{c}}$ ${\displaystyle \delta (H)}$
${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle p}$ ${\displaystyle H}$

Limitación

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

El teorema del esquema se cumple 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 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 a preferir uno de los picos, ignorando los otros. ^[3]

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

Referencias

1. Bridges, Clayton L.; Goldberg, David E. (1987). Un análisis de la reproducción y el cruce en un algoritmo genético codificado en binario. 2.ª Conferencia Internacional sobre Algoritmos Genéticos y sus aplicaciones. ISBN 9781134989737.
2. Altenberg, L. (1995). El teorema del esquema y el teorema de Price. Fundamentos de algoritmos genéticos, 3, 23-49.
3. David E., Goldberg; Richardson, Jon (1987). Algoritmos genéticos con compartición para la optimización de funciones multimodales. 2.ª Conferencia Internacional sobre Algoritmos Genéticos y sus aplicaciones. ISBN 9781134989737.

• J. Holland, Adaptación en sistemas naturales y artificiales , The MIT Press; edición reimpresa 1992 (publicada originalmente en 1975).
• J. Holland, Orden oculto: cómo la adaptación crea complejidad , Helix Books; 1996.