Esquema (algoritmos genéticos)

Un esquema ( pl.: esquemas ) es una plantilla en informática utilizada en el campo de los algoritmos genéticos que identifica un subconjunto de cadenas con similitudes en ciertas posiciones. Los esquemas son un caso especial de conjuntos cilíndricos , que forman la base de una topología de producto en cadenas. ^{[ 1 ]} En otras palabras, los esquemas pueden utilizarse para generar una topología en un espacio de cadenas.

Por ejemplo, consideremos cadenas binarias de longitud 6. El esquema 1**0*1 describe el conjunto de todas las palabras de longitud 6 con 1 en la primera y sexta posición y un 0 en la cuarta posición. El * es un símbolo comodín , lo que significa que las posiciones 2, 3 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${\displaystyle \delta (H)}$es la distancia entre la primera y la última posición específica. El orden de 1**0*1 es 3 y su longitud definitoria es 5. La aptitud de un esquema es la aptitud promedio de todas las cadenas que coinciden con el esquema. La aptitud de una cadena es la puntuación numérica que indica qué tan buena es la solución que representa, calculada mediante una regla diseñada para el problema específico.

En la computación evolutiva, como los algoritmos genéticos y la programación genética , la propagación se refiere a la herencia de características de una generación por la siguiente. Por ejemplo, un esquema se propaga si los individuos de la generación actual coinciden con él, al igual que los de la siguiente. Estos últimos pueden ser (pero no necesariamente) hijos de padres que coincidieron con dicho esquema.

Recientemente se han estudiado esquemas utilizando la teoría del orden . ^{[ 3 ]}

Para los esquemas se definen dos operadores básicos: expansión y compresión. La expansión asigna un esquema a un conjunto de palabras que representa, mientras que la compresión asigna un conjunto de palabras a un esquema.

En las siguientes definiciones${\displaystyle \Sigma }$denota un alfabeto,${\displaystyle \Sigma ^{l}}$denota todas las palabras de longitud${\displaystyle l}$sobre el alfabeto${\displaystyle \Sigma }$,${\displaystyle \Sigma _{*}}$denota el alfabeto${\displaystyle \Sigma }$con el símbolo adicional${\displaystyle *}$.${\displaystyle \Sigma _{*}^{l}}$denota todos los esquemas de longitud${\displaystyle l}$sobre el alfabeto${\displaystyle \Sigma _{*}}$así como el esquema vacío${\displaystyle \epsilon _{*}}$.

Para cualquier esquema${\displaystyle s\in \Sigma _{*}^{l}}$ el siguiente operador${\displaystyle {\uparrow }s}$, llamado el${\displaystyle expansión}$de${\displaystyle s}$, que mapea${\displaystyle s}$a un subconjunto de palabras en${\displaystyle \Sigma ^{l}}$:

$${\displaystyle {\uparrow }s:=\{b\in \Sigma ^{l}|b_{i}=s_{i}{\mbox{ o }}s_{i}=*{\mbox{ para cada }}i\in \{1,...,l\}\}}$$

Donde el subíndice${\displaystyle i}$denota el carácter en la posición${\displaystyle i}$en una palabra o esquema. Cuando${\displaystyle s=\epsilon _ {*}}$entonces${\displaystyle {\uparrow }s=\emptyset }$Dicho de forma más sencilla,${\displaystyle {\uparrow }s}$es el conjunto de todas las palabras en${\displaystyle \Sigma ^{l}}$que se puede hacer intercambiando el${\displaystyle *}$símbolos en${\displaystyle s}$con símbolos de${\displaystyle \Sigma }$. Por ejemplo, si${\displaystyle \Sigma =\{0,1\}}$,${\displaystyle l=3}$y${\displaystyle s=10*}$entonces${\displaystyle {\uparrow }s=\{100,101\}}$.

Por el contrario, para cualquier${\displaystyle A\subseteq \Sigma ^{l}}$definimos${\displaystyle {\downarrow }{A}}$, llamado el${\displaystyle compresión}$de${\displaystyle A}$, que mapea${\displaystyle A}$en un esquema${\displaystyle s\in \Sigma _{*}^{l}}$: $${\displaystyle {\downarrow }A:=s}$$ dónde${\displaystyle s}$es un esquema de longitud${\displaystyle l}$de tal manera que el símbolo en la posición${\displaystyle i}$en${\displaystyle s}$se determina de la siguiente manera: si${\displaystyle x_{i}=y_{i}}$a pesar de${\displaystyle x,y\in A}$entonces${\displaystyle s_{i}=x_{i}}$de lo contrario${\displaystyle s_{i}=*}$. Si${\displaystyle A=\emptyset }$entonces${\displaystyle {\downarrow }A=\epsilon _ {*}}$. Se puede pensar en este operador como apilando todos los elementos en${\displaystyle A}$y si todos los elementos de una columna son equivalentes, el símbolo en esa posición en${\displaystyle s}$toma este valor, de lo contrario hay un símbolo comodín. Por ejemplo,${\displaystyle A=\{100.000.010\}}$entonces${\displaystyle {\downarrow }A=**0}$.

Los esquemas pueden estar parcialmente ordenados . Para cualquier${\displaystyle a,b\in \Sigma _{*}^{l}}$decimos${\displaystyle a\leq b}$si y solo si${\displaystyle {\uparrow }a\subsetequ {\uparrow }b}$De ello se deduce que${\displaystyle \leq }$es un ordenamiento parcial en un conjunto de esquemas a partir de la reflexividad , la antisimetría y la transitividad de la relación de subconjunto . Por ejemplo,${\displaystyle \epsilon _{*}\leq 11\leq 1*\leq **}$Esto se debe a que${\displaystyle {\uparrow }\epsilon _{*}\subseteq {\uparrow }11\subseteq {\uparrow }1*\subseteq {\uparrow }**=\emptyset \subseteq \{11\}\subseteq \{11,10\}\subseteq \{11,10,01,00\}}$.

Los operadores de compresión y expansión forman una conexión de Galois , donde${\displaystyle \downarrow }$es el adjunto inferior y${\displaystyle \uparrow }$el adjunto superior. ^{[ 3 ]}

Para un conjunto${\displaystyle A\subseteq \Sigma ^{l}}$, llamamos al proceso de calcular la compresión en cada subconjunto de A, es decir${\displaystyle \{{\downarrow }X|X\subsetequ A\}}$, la finalización esquemática de${\displaystyle A}$, denotado${\displaystyle {\mathcal {S}}(A)}$. ^{[ 3 ]}

Por ejemplo, dejemos${\displaystyle A=\{110,100,001,000\}}$. La finalización esquemática de${\displaystyle A}$, da como resultado el siguiente conjunto: $${\displaystyle {\mathcal {S}}(A)=\{001,100,000,110,00*,*00,1*0,**0,*0*,***,\epsilon _{*}\}}$$

El poset${\displaystyle ({\mathcal {S}}(A),\leq )}$siempre forma una red completa llamada red esquemática.

La red esquemática es similar a la red conceptual que se encuentra en el análisis formal de conceptos .

• Teorema del esquema de Holland
• Análisis formal de conceptos