El teorema del esquema de Holland , también llamado el teorema fundamental de los algoritmos genéticos , [1] es una desigualdad que resulta de una ecuación de grano grueso para la dinámica evolutiva . El teorema del esquema dice que los esquemas cortos de bajo orden con aptitud superior al promedio aumentan exponencialmente en frecuencia en generaciones sucesivas. El teorema fue propuesto por John Holland en la década de 1970. Inicialmente, se consideró ampliamente que era la base de 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 del esquema es un caso especial de laLa ecuación de precio con el indicador de esquema funciona como 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 de cilindros y, por lo 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 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 1*10*1
es 4 y su longitud de definición es 5. La idoneidad de un esquema es la idoneidad media de todas las cadenas que coinciden con el esquema. La aptitud de una cadena es una medida del valor de la solución codificada del problema, 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 bajo orden con una aptitud superior al promedio aumentan exponencialmente en generaciones sucesivas. Expresado como una ecuación:
Aquí es el número de cadenas que pertenecen al esquema en generacion , es la aptitud media observada del esquema y es la aptitud media observada en la generación. La probabilidad de interrupción es la probabilidad de que el cruce o la mutación destruyan el esquema . Puede expresarse como:
dónde es el orden del esquema, es la longitud del código, es la probabilidad de mutación y es la probabilidad de cruce. Entonces, un esquema con una longitud de definición más cortaes menos probable que se interrumpa.
Un punto a menudo mal entendido es por qué el teorema de esquema es una desigualdad en lugar de una igualdad. De hecho, la respuesta es simple: el teorema ignora la probabilidad pequeña, pero distinta de cero, de que una cadena que pertenece al esquemase creará "desde cero" mediante la mutación de una sola cadena (o la recombinación de dos cadenas) que no pertenecía a en la generación anterior.
Limitación
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 una ventaja selectiva. . Esto ocurre 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. [3]
La razón por la que el Teorema de esquema no puede explicar el poder de los algoritmos genéticos es que se aplica a todos los casos de problemas y no puede distinguir entre problemas en los que los algoritmos genéticos funcionan mal y problemas en los que los algoritmos genéticos funcionan bien.
Referencias
- ^ Puentes, Clayton L .; Goldberg, David E. (1987). Un análisis de reproducción y cruce en un algoritmo genético codificado en binario . Segunda Conf. Int. sobre algoritmos genéticos y sus aplicaciones. ISBN 9781134989737.
- ^ Altenberg, L. (1995). El teorema del esquema y el teorema de Price . Fundamentos de los algoritmos genéticos, 3, 23-49.
- ^ David E., Goldberg; Richardson, Jon (1987). Algoritmos genéticos con compartición para la optimización de funciones multimodales . Segunda Conf. Int. sobre algoritmos genéticos y sus aplicaciones. ISBN 9781134989737.
- J. Holland, Adaptación en sistemas naturales y artificiales , The MIT Press; Reimpresión de la edición 1992 (publicada originalmente en 1975).
- J. Holland, Orden oculto: cómo la adaptación genera complejidad , Helix Books; 1996.