En este video hablaremos del teorema del esquema presentando un análisis del comportamiento de un algoritmo genético, el cual puede llevarse a cabo observando las similitudes que existen en una población de cadenas y su valor de "fitness" o aptitud para guiar u orientar la búsqueda hacia una mejor solución. El esquema introducido por John Holland es un modelo de similitudes que describe un subconjunto de cadenas con semejanzas en ciertas posiciones de las mismas. Un algoritmo genético simple o básico está formado por cadenas binarias. Los esquemas manejan un elemento más en este alfabeto que es el carácter "no importa", o "don't care", formando cadenas a partir de este alfabeto terciario. Un esquema se relaciona con una cadena en particular, si en cada una de las posiciones se tiene un "uno" relacionado con "uno", un "cero" con un "cero" y un carácter "don't care" con cualquier valor, "uno" o "cero". Como ejemplo, tenemos el esquema "don't care", "don't care", "cero", "uno", "cero", el cual describe un subconjunto formado por cuatro cadenas. Las cadenas son: "cero", "cero", "cero", "uno", "cero"; "cero", "uno", "cero", "uno", "cero"; "uno", "cero", "cero", "uno", "cero"; y "uno", "uno", "cero", "uno", "cero". La finalidad de los esquemas es proporcionar una forma un tanto sencilla de obtener las similitudes de las cadenas que forman una cierta población, a partir de un alfabeto finito, obteniéndose una mayor información y guiándonos hacia una mejor búsqueda. El número total de posibles esquemas está dado por "k más uno, elevado a la l", siendo "k" el número de caracteres que forman el alfabeto y "l" la longitud de las cadenas. Este teorema emplea alfabetos pequeños, ya que maximiza el número de esquemas por bit. Para obtener el lÃmite del número de esquemas en una población, primero se obtiene el número de esquemas posibles en una cadena individual, obteniéndose un lÃmite superior del total de esquemas en la población. En general, una cadena contiene "dos a la l" esquemas distintos. Una población de tamaño "n" tiene entre "dos a la l" y "n, por dos a la l" esquemas, dependiendo de la diversidad de la población. La selección proporcional y los operadores genéticos básicos descritos juegan un papel importante en el número de esquemas procesados por los algoritmos genéticos. El operador de selección da a las cadenas con mayor adaptabilidad una mayor probabilidad de selección, incrementándose el número de muestras del patrón que presenta más similitudes. El operador de cruzamiento deja sin cambios el esquema, si éste no se divide, por lo tanto, los esquemas de longitud más corta quedan sin cambios por efecto de este operador. La mutación, en rangos bajos, no rompe un esquema frecuentemente. Por la alta compactibilidad de los esquemas de longitud corta, que se conocen como bloques constructores, se propagan de generación en generación dando un incremento exponencial de las mejores cadenas, realizándose en paralelo con la población de "n" individuos. Esto se conoce como "paralelismo implÃcito". Con objeto de analizar el teorema del esquema se tomará la siguiente notación. Se asigna a una cadena de una población con letra mayúscula, la cual toma valores del alfabeto "cero" y "uno", y a cada carácter individual que la forma, con letras minúsculas; por lo que podemos tener "A mayúscula" igual a "a minúscula uno", "a minúscula dos", hasta "a minúscula siete". Cada una de las "ai minúscula" representa un solo carácter binario, donde cada carácter puede tomar un "uno" o "cero" que corresponden a los alelos. Las búsquedas genéticas requieren de una población de cadenas individuales "A mayúscula j", contenidas en la población en el tiempo "t". Un esquema se va a representar como "H mayúscula", el cual toma valores del alfabeto extendido "cero", "uno", "don't care". Los esquemas presentan dos propiedades importantes, orden y longitud. El orden de un esquema "H", denotado por "o de H", es el número de posiciones con valores de "uno" o "cero". El esquema "cero", "uno", "cero", "don't care", "don't care", "uno", "don't care", es de orden "cuatro". La longitud de un esquema "H", denotada por "delta de H", es la distancia entre la primera y la última posición del esquema, con un valor especÃfico de cero o uno. Por ejemplo, el esquema "cero", "uno", "cero", "don't care", "don't care", "uno", "don't care", es de orden "cinco", ya que la primera posición con valor fijo está en la posición uno y la posición más alejada con valor fijo está en la posición seis. Para determinar el efecto de la selección en el número esperado de esquemas en una población, Holland se basó en la selección proporcional, en especÃfico, el método de la ruleta. Se parte de un tiempo "t" dado con "m" ejemplos de esquemas en la población "A de t". Durante la reproducción, una cadena "A de i" es seleccionada con probabilidad "pi". Como vimos en los métodos de selección proporcional, "pi" es igual al valor objetivo del individuo "i", dividido entre la suma de los valores objetivos de toda la población. Con esto, se espera tener "m" representaciones del esquema "H" en el tiempo "t más uno" dada por la ecuación siguiente, donde "f de H" es el valor promedio de los valores objetivo de las cadenas que contienen el esquema "H" en el tiempo "t". Como el valor objetivo promedio de la población es igual a la suma de valores objetivos de toda la población entre "n", tenemos el siguiente resultado. Resumiendo, todo esquema en una población crece o decae de acuerdo a sus esquemas promediados bajo la operación de selección. Los esquemas arriba del promedio se mantienen en generaciones posteriores. Los esquemas que se encuentran abajo del promedio decaen. Ahora, veremos qué efectos tiene el operador de cruzamiento en la propagación de esquemas en el proceso evolutivo. El cruzamiento es un proceso de intercambio de información entre cadenas. Para ver cuáles esquemas son afectados por el operador de cruzamiento y cuáles no, Holland consideró el operador de cruza en un punto. Tomando un individuo "A" y dos esquemas, "H1" y "H2", estos están representados en "A". Para ver el efecto del cruzamiento en estos dos esquemas se va a definir un punto de cruce en la posición tres. El esquema "H1" será destruido porque el "uno" en la posición dos y el "cero" en la posición siete serán colocados en diferentes descendientes. El esquema "H2" se va a seguir manteniendo porque el "uno" en la posición cuatro y el "cero" en la posición cinco serán transmitidos a un solo descendiente. El esquema "H1" presenta menos probabilidad de sobrevivencia que el esquema "H2" porque el punto de cruce presenta mayor probabilidad de caer entre las posiciones extremas. Cuantificando, el esquema "H1" tiene una longitud de cinco. Si la localización del cruzamiento se selecciona uniforme y aleatoriamente en las posibles posiciones "l menos uno", y esto es igual a seis, el esquema "H1" es destruido con probabilidad "Pd" igual a "delta de H1, entre l menos uno", donde "delta de H1", la longitud del esquema "H1", es igual a "cinco" dividido entre "l menos uno", que es "seis". Para el esquema "H2", esa probabilidad es igual a un sexto. Un esquema sobrevive cuando la localización del cruce cae fuera de la longitud definida del propio esquema. La probabilidad de sobrevivencia, bajo el cruzamiento, es "Ps" igual a "uno menos Pd", donde "Pd" es la probabilidad de destrucción del esquema. Esto se expresa en la siguiente ecuación. Al considerar la combinación del efecto de los operadores de selección y cruzamiento se obtiene la ecuación siguiente. El efecto combinado del cruzamiento y la selección es obtenido multiplicando el número esperado de esquemas por efecto de la selección, por la probabilidad de sobrevivencia bajo el cruzamiento. Vamos, ahora, a analizar el efecto del operador de mutación en el funcionamiento del algoritmo genético básico. El operador de mutación se aplica a cada una de las posiciones de una cadena de manera independiente, con probabilidad de sobrevivencia por la influencia de este operador de "uno menos Pm", donde "Pm" es la probabilidad de mutación. Un esquema en particular sobrevive cuando cada una de las posiciones de "o de H", el orden del esquema, sobrevive. La probabilidad de sobrevivencia por este operador se obtiene multiplicando "uno menos Pm" por "o de H". Para valores de "Pm" pequeños, la probabilidad de sobrevivencia de un esquema se aproxima a "uno, menos, el orden del esquema por la probabilidad de mutación". A partir de esto, se llega a la expresión que representa el número esperado de copias que va a recibir un esquema en la siguiente generación bajo la influencia de los tres operadores genéticos básicos: selección proporcional, cruza en un punto y mutación aleatoria. Donde "f" representa el valor objetivo; "H", el esquema; "m", el número esperado de esquemas; "delta", la definición de longitud del esquema; "o", el orden del esquema; "Pc", la probabilidad de cruzamiento; "Pm", la probabilidad de mutación; y "l", la longitud de cada cadena. La expresión anterior indica que esquemas con longitudes pequeñas, orden bajo y con valores arriba del promedio de la población reciben un número de elementos, en generaciones posteriores, que se incrementa en forma exponencial. Se ha estimado que un algoritmo genético procesa un orden de "n al cubo" esquemas en cada generación, aún cuando solamente "n" elementos son realmente manipulados. Esta caracterÃstica ha sido denominada como "paralelismo implÃcito". La conclusión anterior es conocida como el "teorema del esquema" o "teorema fundamental de los algoritmos genéticos".