Esquema (algoritmos genéticos)

Un esquema ( pl.: schemata ) 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 de cadena. Los esquemas son un caso especial de conjuntos de cilindros , que forman una base para una topología de producto en cadenas. ^[1] En otras palabras, los esquemas se pueden utilizar para generar una topología en un espacio de cadenas.

Descripción

Por ejemplo, considere 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 es la distancia entre la primera y la última posición específica. El orden de 1**0*1 es 3 y su longitud de definición 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 una medida del valor de la solución del problema codificada, calculada por una función de evaluación específica del problema. ${\displaystyle \delta (H)}$

Longitud

La longitud de un esquema , denominada , se define como el número total de nodos en el esquema. también es igual al número de nodos en los programas que coinciden con . ^[2] ${\displaystyle H}$ ${\displaystyle N(H)}$ ${\displaystyle N(H)}$ ${\displaystyle H}$

Ruptura

Si el hijo de un individuo que coincide con el esquema H no coincide con H, se dice que el esquema ha sido interrumpido . ^[2]

Propagación del esquema

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 a la siguiente. Por ejemplo, un esquema se propaga si los individuos de la generación actual coinciden con él y también lo hacen los de la siguiente generación. Los de la siguiente generación pueden ser (pero no necesariamente) hijos de padres que coincidieron con él.

Los operadores de expansión y compresión

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

Se definen dos operadores básicos para el esquema: 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 denota un alfabeto, denota todas las palabras de longitud superior al alfabeto , denota el alfabeto con el símbolo extra . denota todo esquema de longitud superior al alfabeto así como el esquema vacío . ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{l}}$ ${\displaystyle l}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma _{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle *}$ ${\displaystyle \Sigma _{*}^{l}}$ ${\displaystyle l}$ ${\displaystyle \Sigma _{*}}$ ${\displaystyle \epsilon _{*}}$

Para cualquier esquema , el siguiente operador , llamado de , se asigna a un subconjunto de palabras en : ${\displaystyle s\in \Sigma _{*}^{l}}$ ${\displaystyle {\uparrow }s}$ ${\displaystyle expansion}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle \Sigma ^{l}}$

$${\displaystyle {\uparrow }s:=\{b\in \Sigma ^{l}|b_{i}=s_{i}{\mbox{ or }}s_{i}=*{\mbox{ for each }}i\in \{1,...,l\}\}}$$

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

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

Los esquemas pueden ordenarse parcialmente . Para cualquier decimos si y solo si . De ello se deduce que es un ordenamiento parcial en un conjunto de esquemas a partir de la reflexividad , antisimetría y transitividad de la relación de subconjunto . Por ejemplo, . Esto se debe a que . ${\displaystyle a,b\in \Sigma _{*}^{l}}$ ${\displaystyle a\leq b}$ ${\displaystyle {\uparrow }a\subseteq {\uparrow }b}$ ${\displaystyle \leq }$ ${\displaystyle \epsilon _{*}\leq 11\leq 1*\leq **}$ ${\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 es el adjunto inferior y el adjunto superior. ^[3] ${\displaystyle \downarrow }$ ${\displaystyle \uparrow }$

La terminación esquemática y la red esquemática

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

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

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

La red esquemática formada a partir de la terminación esquemática del conjunto . Aquí la red esquemática se muestra como un diagrama de Hasse . ${\displaystyle A=\{111,011,001\}}$ ${\displaystyle ({\mathcal {S}}(A),\leq )}$

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

Véase también

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

Referencias

1. Holland, John Henry (1992). Adaptación en sistemas naturales y artificiales (edición reimpresa). The MIT Press. ISBN 9780472084609. Recuperado el 22 de abril de 2014 .
2. "Fundamentos de la programación genética". UCL UK . Consultado el 13 de julio de 2010 .
3. Jack McKay Fletcher y Thomas Wennkers (2017). "Un enfoque natural para estudiar el procesamiento de esquemas". arXiv : 1705.04536 [cs.NE].