next up previous
Next: 9.5 Puntos a considerar Up: 9. Algoritmos Genéticos Previous: 9.3 Algoritmo Básico

9.4 El teorema de esquemas

Proporciona el fundamento teórico de porqué los GA pueden resolver diversos problemas. En su análisis se considera el proceso de selección y los operadores de cruce y mutación.

Un esquema se construye utilizando un nuevo símbolo (*) para representar un comodín (no importa) que puede aparear ambos valores (0 o 1). E.g., el esquema 11*00* representa las cadenas: 111001, 111000, 110001, 110000.

El orden de un esquema es el número de elementos que no son ``*'' dentro del esquema.

La longitud que define a un esquema es la distancia entre la primera posición fija y la última posición fija.

El teorema dice que si exiten $N(S,t)$ instancias de un esquema $S$ en una población al tiempo $t$, en el siguiente tiempo el valor esperado de instancias en la nueva población esta acotado por:

\begin{displaymath}
E[N(S,t+1)] \geq \frac{F(S,t)}{\overline{F}(t)} N(S,t)[1 - \epsilon(S,t)]
\end{displaymath}

donde $F(S,t)$ es la aptitud del esquema $S$, $\overline{F}(t)$ es la aptitud promedio de la población, y $\epsilon(S,t)$ es un término que refleja el potencial del algoritmo genético de destruir instancias del esquema $S$.

El teorema regresa solo un valor esperado de la siguiente generación, por lo que tratar de extrapolar y decir que los esquemas buenos crecen exponencialmente en las siguientes generaciones (como a veces se dice) es completamente absurdo.

Existen también argumentos sobre la hipótesis de bloques constructores, en donde pequeños esquemas o bloques constructores se usan para construir la solución óptima, sin embargo, no existe evidencia de esto.


next up previous
Next: 9.5 Puntos a considerar Up: 9. Algoritmos Genéticos Previous: 9.3 Algoritmo Básico
Eduardo Morales Manzanares 2004-11-02