PRESENTACION DEL TRABAJO

Los resultados del trabajo investigativo fueron presentados en la Primera Jornada Académica del Programa de Ingenieria de Sistemas de la Universidad del Magdalena. El trabajo fue la unica ponencia realizada por estudiantes en el evento. Las demas ponencias fueron realizadas por docentes investigadores del programa.

Resumen

En el presente trabajo, se explora la factibilidad de los autómatas celulares como técnica para la predicción de series de tiempo. En primera instancia, se realiza un resumen de las diferentes técnicas utilizadas para predecir y se establecen el conjunto de series a simular. Luego, se realiza un análisis de la configuración que debe poseer un autómata para simular la serie de tiempo, en el cual se incluye un cálculo de los recursos computacionales. Se utiliza un algoritmo genético para generar las regla locales de evolución. Finalmente, se presentan los resultados obtenidos junto con las conclusiones de la investigación.

Conclusiones de la Investigación

Los modelos de autómatas celulares pueden ser utilizados como técnica predictiva que no solo puede ofrecer mejores grados de confiabilidad sino que permiten obtener gramáticas que describan las relaciones entre los elementos que interactúan en el sistema. A su vez, los AC como herramienta de análisis de variables discretas ofrecen una mejor aproximación a las series de tiempo discreto.

Para el caso de una serie monovariable, el grado de adaptación del autómata generado fue aceptable, sin embargo, para el caso de la serie binaviable no se encontraron individuos aceptables.

La capacidad de computo al alcance fue insuficiente para realizar una simulación de mayor complejidad y eficiencia pero debe tenerse en cuenta que los adelantos tecnológicos cada vez ofrecen mayores recursos que posibilitaran su aplicación. Una implementación de este sistema en una tecnología computacional basa en AC eliminaría la barrera y muy seguramente se obtendrán mejores resultados.

Avance 2.0 - Arquitectura del Sistema

Como se ha mencionado anteriormente, se utilizaran algoritmos evolutivos para encontrar las reglas que permitan generar los comportamientos deseados. Por ello, hemos establecido la arquitectura del sistema que nos permita realizar los experimentos. Aquí presentamos una grafica que mostrar como debe estar construido el sistema.

Avance 2.1 - Evaluación de Individuos

A continuación presentamos el diseño de la función de evaluación de los Individuos en l os Algoritmos Genéticos a utilizar. Nótese que el algoritmo solicita simulaciones del autómata celular según la regla codificada en un individuo.

Como se ha mencionado anteriormente, se utilizaran algoritmos evolutivos para encontrar las reglas que permitan generar los comportamientos deseados.

Nótese que la evaluación consta de dos partes:

1. Determinación del error del individuo en el seguimiento de una serie de tiempo. Esto se hace utilizando mínimos cuadrados.
2. A partir de los errores se calcula el total de error de la población y se establece el menor de los errores. Con estos datos se calcula el Fitness del Individuo el cual debe ser inversamente proporcional a su error.

Avance 1.0

Realizando un análisis, consideramos que el entregable final del proyecto (articulo) deberá contener los siguientes elementos:

ESTRUTURACION DEL ARTÍCULO.

1) Resumen
2) Palabras Claves.
3) Introducción.
4) Formulación del Problema
..........4.1 - La necesidad de Predicción
..........4.2 - Las técnicas clásicas de predicción y desventajas
..........4.3 - Las técnicas modernas de preedición y sus desventajas
5) Marco Teórico
..........5.1 - Autómatas Celulares
..........5.2 - Algoritmos Genéticos
..........5.3 - AGs en la Optimización de ACs
6) Diseño del Autómata Celular
7) Diseño del Algoritmo Genético
..........7.1 - Codificación de Individuos
..........7.2 - Función de Aptitud
..........7.3 - Operador de Selección
..........7.3 - Operador de Cruzamiento
..........7.3 - Operador de Mutación
8) Diseño Experimental
..........8.1 - Series Monovariables (AC con 2 Estados)
....................8.1.1 ACS con estado inicial estático
....................8.1.2 ACS con estado inicial dinámico
.......... .........8.1.3 CHC con estado inicial estático
....................8.1.4 CHC con estado inicial dinámico
.........8.2 - Series Bivariables
....................8.1.1 ACS con estado inicial estático
....................8.1.2 ACS con estado inicial dinámico
....................8.1.3 CHC con estado inicial estático
....................8.1.4 CHC con estado inicial dinámico
9) Resultados y Análisis de Resultados
.........9.1 - Desempeño de los Algoritmos Genéticos
.........9.2 - Desempeño de los Autómatas Celulares
.........9. - Presentación del Mejor Individuo Obtenido
10) Conclusiones y recomendaciones.
.........10.1 - Ventajas y Desventajas
.........10.2 - Inconvenientes
.........10.2 - Recomendaciones
11) Bibliografía.

Comentario 0.1

Individuos:

Los Individuos generados por el AG, corresponden a una cadena de numeros en base tres (3) de 242 digitos, en realidad no existen 242 Estados, sino que cada AC podria tener 242 Tranciciones posibles, es decir desde 00000 hasta 22222, donde cada digito representa el estado de sus vecinos.

En realidad el espacio de busqueda equivale a 3^242 (8,719e+115), es decir el número total de individuos que podrian formarse para dar solución al problema es una cifra moderadamente grande como para hacer una exploración uno-uno.

Por esta razón concideramos pertinente implementar un AG que nos ayudara a buscar el mejor AC.

Avance 0.3

Condiciones:
Se han establecido 3 estados. Estudiantes activos, aspirantes y personas indiferentes = {2,1,0} respectivamente

Queremos desarrollar el aplicativo de la siguiente forma:

• Una módulo que se encargue de modelar (apartir de una regla cifrada como un digito) el comportamiento del AC con una regla que es obtenida como parametro de entrada del modulo, esta regla se constituye como el individuo a evolucionar.

• Una módulo se encargará de desarrollar el mejor individuo (reglas locales) y determinar su aptitud (teniendo en cuenta los datos sumnistrados por Adminiciones y registros) con el modulo (1) .
  

Nuestras primeras observaciones:

• La desventaja de hacer esta practica con AC y no con RNA es que los AC no generalizan situaciones (es decir dar solucion parcial) con una mayor velocidad*.

• La ventaja principal de AC radica en su capacidad de generar una semantica de la situacion a modelar, por ejemplo podriamos encontrar relaciones como las siguientes: Un estudiante dejaria de estudiar si tiene una cantidad N de personas no interesadas (a lo mejor ocurre lo ocurre en la costa y se desmotiva a seguir estudiando) ó que un aspirante se convierte en estudiante si el número de estudiante es lo suficientemente grande como para motivarlo.
• De la literatura observada y de los calculos prelimires se ha llegado a una conclucion muy particular; La computacion actual no es lo suficientemente apta para desarrollar modelos computacionales basados en el desarrollo de elementos masivos y paralelos, esto ha de ser tema a tratar en el articulo.
  
  

Avance 0.2

Bueno, ayer se logró determinar lo siguiente:

Considerando que:

Hacer un AC con D = 2 , k = 3 , r = 2 genera alrededor de 847’288’609’443 Diferentes reglas es realmente muy complejo intentar hacer un individuo con ese número de reglas pues genera un enorme gasto computacional y en la actualidad no contamos con esos recursos computacionales, añadiendo que se deben hacer para cada generación un número i de individuos es decir i veces la cantidad de reglas.

Además hacer un AC con D = 2 , k = 3 , r = 1 genera 19683 Diferentes reglas, aunque la cantidad es moderada, aun consideramos que el número de estados posibles es demasiado.

Se concluyó parcialmente que:

Se va a trabajar con la vecindad de “cruz” (i,j) – (i,j-1) – (i+1,j) – (i,j+1) – (i-1,j), y en total se constituirán 242 combinaciones posibles de estados de los vecinos, esta cantidad es moderada y de fácil manejo.

El estados de los vecinos es la j-esima del gen de un individuos i, de esta forma se hace mas rápido y comprensible la interpretación del cromosoma.

Avance 0.1

Referencias Bibliografias
Evolución de Automatas celulares utilizando Algoritmos geneticos.
Observaciones: Es un articulo muy aproximado a nuestro trabajo, es bastante interesante y de agradable lectura.

Actualización:
Haciendo unas observaciones referenciadas en este articulo, se ha podido definir el espacio de busqueda de las reglas.

Sea D el número de dimenciones.
Sea k el número de estados.
Sea r el radio del AC.

sea C el número de configuraciones de cada regla.
C = (2r + 1) ^ D

Sea Regla el número total de reglas a trabajar
Reglas = k ^ C

Un ejemplo si nuestro proyecto fuese de r = 2 , k = 3 , D = 2 el número estimado de reglas seria unas 847'288'609.443

Definición de Objetivos

Se plantean los siguientes objetivos para el desarollo de la propuesta a investigar:

Objetivo General:

Determinar el conjunto de reglas locales que deben regir a un autómata celular que permitan generar comportamientos similares al del crecimiento estudiantil de una universidad en particular.

Objetivos Específicos:

• Determinar el conjunto de datos a simular.
• Determinar los parámetros del AC.
• Diseñar e implementar un Algorítmo Genético que permita encontar reglas para el AC que se ajusten a los datos.
• Analizar los resultados obtenidos.

Cualquier tipo de sugerencias (por parte del profesor, claro) serán bien recibidas.

Propuesta Investigativa con AC's

Un saludo de antemano para todos nuestros lectores. En este primer post queremos dar a conocer nuestra propuesta investigativa para desarrollar en la asignatura Intesiva Autómatas Celulares. Estamos considerando trabajar sobre una población estudiantil (la perteneciente a la universidad del magdalena, por ejemplo) para mostrar el grado de crecimiento que esta pueda tener en un tiempo determinado utilizando como base, datos proporcionados que nos muestren el índice de crecimiento.

Para lograr lo anterior, pensamos implementar un Algoritmo Genético que se encargue de realizar una búsqueda de las posibles configuraciones del AC que describan comportamientos similares o análogos al crecimiento de una deteminada población estudiantil.