---

Teorema del Esquema en los Algoritmos Genéticos

El Teorema del Esquema, propuesto por John Holland, constituye el fundamento teórico principal de los algoritmos genéticos. Este teorema explica cómo ciertas estructuras o patrones dentro de los cromosomas evolucionan y se propagan a través de las generaciones. En esencia, describe por qué los algoritmos genéticos pueden encontrar soluciones eficientes mediante la selección, recombinación y mutación de individuos.

---

1. Concepto de Esquema

Un esquema es un patrón que representa un subconjunto de cadenas dentro de una población genética. Este patrón describe similitudes entre cromosomas en ciertas posiciones específicas.

Los esquemas utilizan un alfabeto extendido:

${0,1,*}$ Donde:

• 0 y 1 representan valores específicos.
• • (don't care) significa que en esa posición puede existir cualquier valor.

Ejemplo:

Esquema:

* * 0 1 0

Este esquema representa todas las cadenas binarias de longitud 5 que tengan:

• Un 0 en la tercera posición
• Un 1 en la cuarta posición
• Un 0 en la quinta posición
• Cualquier valor en las dos primeras posiciones

Este esquema contiene múltiples soluciones posibles.

---

2. Importancia del Esquema

Los esquemas permiten estudiar cómo ciertos patrones útiles dentro de las soluciones evolucionan y sobreviven durante el proceso genético. Holland demostró que los algoritmos genéticos no solo trabajan con individuos, sino con miles de esquemas simultáneamente.

Este fenómeno se conoce como:

Paralelismo implícito

Significa que el algoritmo analiza y mejora múltiples patrones genéticos al mismo tiempo sin evaluarlos individualmente.

---

3. Número de Esquemas Posibles

Si:

• k = número de símbolos del alfabeto
• l = longitud del cromosoma

El número total de esquemas posibles es:

$$(k+1)^l$$

En algoritmos genéticos binarios:

undefined

2^l

$$esquemas diferentes. Si la población tiene **n individuos**, entonces puede contener entre:$$

2^l \leq esquemas \leq n \cdot 2^l

undefined

o(H)

Ejemplo: ``` 0 1 * * 1 ``` Tiene orden 3 porque contiene tres posiciones definidas. --- ### **5.2 Longitud del Esquema** La longitud mide la distancia entre la primera y última posición fija. Se denota como:

\delta(H)

Es importante porque los esquemas largos tienen mayor probabilidad de ser destruidos por el cruzamiento. --- ## **6. Influencia de los Operadores Genéticos** El teorema del esquema analiza cómo tres operadores afectan la supervivencia de los esquemas: --- ### **6.1 Selección** La selección favorece individuos con mayor aptitud. Probabilidad de seleccionar el individuo i:

P_i = \frac{f_i}{\sum f_j}

Donde: - $(f_i)$ = aptitud del individuo - $(\sum f_j)$ = aptitud total de la población El número esperado de esquemas en la siguiente generación depende del promedio de aptitud del esquema. Los esquemas con aptitud superior al promedio aumentan su presencia en la población. --- ### **6.2 Cruzamiento** El cruzamiento puede destruir esquemas si el punto de cruce ocurre dentro de su longitud. Probabilidad de destrucción:

P_d = \frac{\delta(H)}{l-1}

$$Probabilidad de supervivencia:$$

P_s = 1 - \frac{\delta(H)}{l-1}

Esto indica que: - Esquemas cortos tienen mayor probabilidad de sobrevivir. - Esquemas largos son más vulnerables. --- ### **6.3 Mutación** La mutación cambia aleatoriamente los genes. Probabilidad de supervivencia frente a mutación:

(1-P_m)^{o(H)}

$$Para valores pequeños de mutación:$$

1 - o(H)P_m

Esto indica que esquemas con menor orden tienen mayor probabilidad de sobrevivir. --- ## **7. Ecuación Fundamental del Teorema del Esquema** La cantidad esperada de esquemas en la siguiente generación es:

m(H,t+1) \geq m(H,t)\frac{f(H)}{\bar{f}}
\left[1-P_c\frac{\delta(H)}{l-1}\right]
\left[1-o(H)P_m\right]

undefined

O(n^3)

undefined