Teorema del circuito

Teorema del esquema , o teorema de la plantilla: el teorema principal de la teoría de los algoritmos genéticos , que proporciona una justificación de su eficacia. Formulado y probado por primera vez por J. Holland en 1975.

El concepto de esquema

Un esquema es un subconjunto del conjunto de todos los genotipos posibles que son posibles en una población dada, dado como un cromosoma con valores fijos de algunos bits . El resto de bits pueden tomar cualquier valor, formando ejemplos del esquema. Entonces, ejemplos del esquema 00**1* son los cromosomas 000010, 000011, 000110, 000111, 001010, 001011, 001110 y 001111. El número de bits fijos se denomina orden del esquema y la distancia entre las posiciones fijas extremas ( es decir, la diferencia entre sus números) se denomina longitud definitoria. El orden del circuito anterior es 3 y la longitud que lo define es 5 - 1 = 4. La función de aptitud (FF) del circuito es el valor promedio de la función de aptitud de todos sus ejemplos.

Teorema

El teorema del esquema muestra la propagación exponencial de esquemas bien adaptados con un orden pequeño y una longitud definitoria que ocurre con un cambio de generaciones (tales esquemas con un FP superior al promedio de la población se denominan bloques de construcción ). Matemáticamente, esto se expresa mediante la desigualdad:

N(h,t+1)\geq N(h,t){f(h,t) \over f(t)}[1-p].

Aquí está el número de ejemplos del circuito h en el paso t, y es el mismo en el siguiente paso; es la función de idoneidad del circuito en el paso t; es el valor promedio de la FF para toda la población en el mismo paso; es la probabilidad de destrucción del esquema bajo la acción de operadores genéticos. Esta probabilidad es: ${\ Displaystyle N (h, t)}$ ${\ estilo de visualización N (h, t + 1)}$ ${\ estilo de visualización f (h, t)}$ $pie)$ $pags$

p={\delta (h) \over l-1}p_{c}+o(h)p_{m},

donde es la longitud definitoria del esquema, es el orden, es la probabilidad de cruce y es la probabilidad de mutación . Por lo tanto, la forma completa del teorema se ve así: ${\ estilo de visualización \ delta (h)}$ $Oh)$ $p_{c}$ $pm}$

N(h,t+1)\geq N(h,t){f(h,t) \over f(t)}[1-{\delta (h) \over l-1}p_{ c}-o(h)p_{m}].

El teorema del esquema no da valores exactos, sino solo un límite inferior en el número de instancias de un esquema después del siguiente cambio generacional. Esto se debe al hecho de que existe la posibilidad de que surjan nuevos ejemplos del esquema bajo la acción de operadores genéticos en cromosomas que no estaban relacionados previamente con él.

Véase también

algoritmo genético

Enlaces

JH Holanda. Adaptación en Sistemas Naturales y Artificiales . The MIT Press, edición reimpresa, 1992.
Liles WC Introducción a la teoría de esquemas: una conferencia general sobre la teoría de esquemas exacta y pesimista / WC Liles, Wiegand RP - Serie de conferencias de verano de 2002, Actividades de laboratorio de EC, Departamento de Ciencias de la Computación, Universidad George Mason. texto de la conferencia diapositivas de la conferencia