Un esquema es una plantilla en informática utilizada en el campo de los algoritmos genéticos que identifica un subconjunto de cadenas con similitudes en determinadas posiciones de cadena. Los esquemas son un caso especial de juegos de cilindros ; y así formar un espacio topológico . [1]
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 unos 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 idoneidad de un esquema es la idoneidad media de todas las cadenas que coinciden con el esquema. La aptitud de una cadena es una medida del valor de la solución codificada del problema, calculada por una función de evaluación específica del problema.
Largo
La longitud de un esquema , llamada , se define como el número total de nodos del esquema. también es igual al número de nodos en los programas que coinciden . [2]
Ruptura
Si el hijo de un individuo que coincide con el esquema H no coincide en sí mismo con H, se dice que el esquema se ha alterado . [2]
Propagación de 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 los de la siguiente generación. Los de la próxima generación pueden ser (pero no tienen que ser) hijos de padres que la igualaron.
Los operadores de expansión y compresión
Recientemente se han estudiado los esquemas utilizando la teoría de órdenes . [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 sobre el alfabeto , denota el alfabeto con el símbolo extra . denota todo el esquema de longitud sobre el alfabeto así como el esquema vacío .
Para cualquier esquema el siguiente operador , llamó al de , que mapas a un subconjunto de palabras en :
Donde subíndice denota el personaje en la posición en una palabra o esquema. Cuándo luego . Dicho de manera más simple, es el conjunto de todas las palabras en que se puede hacer intercambiando el símbolos en con símbolos de . Por ejemplo, si, y luego .
Por el contrario, para cualquier definimos , llamó al de , que mapas en un esquema :
Los esquemas se pueden ordenar parcialmente . Para cualquier decimos si y solo si . Resulta quees un ordenamiento parcial en un conjunto de esquemas de la reflexividad , antisimetría y transitividad de la relación de subconjunto . Por ejemplo,. Esto es porque.
Los operadores de compresión y expansión forman una conexión de Galois , donde es el adjunto inferior y el contiguo superior. [3]
La terminación esquemática y el entramado esquemático
Para un juego , llamamos al proceso de calcular la compresión en cada subconjunto de A, es decir , la terminación esquemática de , denotado . [3]
Por ejemplo, deja . La terminación esquemática de, da como resultado el siguiente conjunto:
El poset siempre forma una celosía completa llamada celosía esquemática.
La celosía esquemática es similar a la celosía de conceptos que se encuentra en el análisis de conceptos formal .
Ver también
Referencias
- ^ Holanda, John Henry (1992). Adaptación en sistemas naturales y artificiales (reimpresión ed.). La prensa del MIT. ISBN 9780472084609. Consultado el 22 de abril de 2014 .
- ^ a b "Fundamentos de la Programación Genética" . UCL Reino Unido . Consultado el 13 de julio de 2010 .
- ^ a b c Jack McKay Fletcher y Thomas Wennkers (2017). "Un enfoque natural para estudiar el procesamiento de esquemas". arXiv : 1705.04536 [ cs.NE ].