|
índice |
|
Tarea #3 |
Evolución de la Estructura de Datos con Programación Genética.
La Programación Genética (GP) es una subclase de Algoritmos Genéticos (GA), en los cuales los programas evolutivos son directamente representados en los cromosomas como árboles. Esto esta establecido por una buena practica de ingeniería genética que asegura que el programa use memoria abstracta de estructura de datos tales como pilas, colas y listas. Estos proveen una interfaz entre el programa y la memoria. La abstracción típica de la estructura de datos soporta múltiples operaciones tales como poner y quitar.
INTRODUCCIÓN: Resientes trabajos de Teller muestran que la Programación Genética puede crear automáticamente programas los cuales usan memoria explícitamente. El ha demostrado que incluso la lectura y escritura primitiva puede ser un lenguaje de Programación Genética completo de Turing. Nosotros anticipamos que la evolución de la computación resolverá muchos problemas, esto debería adoptar un aprovechamiento estructurado. Se demostrara como la GP puede generar estructuras de datos abstractas: Pilas Colas.
EVOLUCIÓN DE UNA PILA Arquitectura: Cada individuo dentro de la población esta compuesto por 5 árboles, cada cual genera una posible solución a una de las 5 operaciones dadas desde el programa de pilas completo. Esta arquitectura de árboles múltiple fue elegida de tal forma que cada árbol contenga un código en cual ha evolucionado apara implementar una operación singular. Cada individuo es creado uno a uno a copia de todos los 5 árboles de Programa Origen (10%) o por vía transversal entre 2 programas origen(90%). Cuando es transversal un tipo de árbol es seleccionado de forma aleatoria y los árboles de los otros tipos son copiados sin modificación desde el primer origen a el nuevo individuo. Los árboles permanentes son creados por atravesamiento entre los árboles de el tipo elegido en cada origen en forma normal de GP. Los nuevos árboles tienen la misma raíz que su origen primario. Cada unión produce un nuevo individuo singular mas de cuyo material genético viene directo del primer árbol origen y solo de uno de ellos.
FUNCIONES Y TERMINALES USADOS EN LA EVOLUCIÓN DE LAS PILAS:
Tabla 1: Definición de un Pseudo código de las 5 operaciones de Pilas.
write(a,x): If A indice valido de memoria then write:= almacena[A]; almacena[a]:= x; Else aborta el programa;
PROPIEDADES DE LAS FUNCIONES:
Las propiedades de las funciones de cada programa individual es el numero de pruebas pasadas (por ejemplo: regresan la respuesta correcta) cuando cada una de estas operaciones constituidas es llamada en una serie de cuatro secuencias de pruebas arregladas, cada una contiene 40 llamadas, habiendo escogido la correcta prueba de la operación de los programas de Pila.
EVOLUCIÓN DE UNA COLA
Al igual que las pilas, las colas tienen 5 operaciones principales y estas son:
Los problemas de colas son muy similares a los de pilas, con reemplazo del ultimo por el de enfrente, el retirar es tambien retirar pero corriendo la cola y, se inseta al igual que en la pila.
PROPIEDADES DE LA FUNCIONES:
A deferencia de las pilas en las colas se utilizan 2 variables auxiliares. Las propiedades de las funciones son basadas en las mismas de las pilas. La secuencia de prueba siempre comienza con la creación de la cola vacía, nunca con la inserción o un retiro.
CONCLUSIÓN:
En este texto se demustra como es posible hacer uso de de la programacion genetica y de los algoritmos geneticos para el desarrollo de indice de memoria, pudiendo asi desarollar programas evolutivos, los cuales implementan la simple abstraccion de la estructura de datos, es decir una pila y una cola.
REFERENCIAS William B. Langdon Computer Science Dept. University College London, Gower Street, London, WC1E 6BT, UK
|
