Bueno pues ya tenemos la primera versión del Juego de la Vida (programado en C#) para probar con ella.
Descargar el fichero adjunto, descomprimir con unrar y ejecutar.
http://www.megaupload.com/?d=MMPVB6CD
El resto de instrucciones es sencillo, configurar los parámetros de la simulación y experimentar con los resultados.
domingo, 23 de enero de 2011
domingo, 16 de enero de 2011
Juego de la Vida de Conway
Este ejemplo de AC, fue diseñado por el matemático británico John Horton Conway en 1970.
Según la Wikipedia "
...El juego de la vida es en realidad un juego de cero jugadores, lo que quiere decir que su evolución está determinada por el estado inicial y no necesita ninguna entrada de datos posterior. El "tablero de juego" es una malla formada por cuadrados ("células") que se extiende por el infinito en todas las direcciones. Cada célula tiene 8 células vecinas, que son las que están próximas a ella, incluso en las diagonales. Las células tienen dos estados: están "vivas" o "muertas" (o "encendidas" y "apagadas"). El estado de la malla evoluciona a lo largo de unidades de tiempo discretas (se podría decir que por turnos). El estado de todas las células se tiene en cuenta para calcular el estado de las mismas al turno siguiente. Todas las células se actualizan simultáneamente.
Las transiciones dependen del número de células vecinas vivas:
A continuación voy a intentar programar este juego en C# para poder ver su comportamiento en real...
Según la Wikipedia "
...El juego de la vida es en realidad un juego de cero jugadores, lo que quiere decir que su evolución está determinada por el estado inicial y no necesita ninguna entrada de datos posterior. El "tablero de juego" es una malla formada por cuadrados ("células") que se extiende por el infinito en todas las direcciones. Cada célula tiene 8 células vecinas, que son las que están próximas a ella, incluso en las diagonales. Las células tienen dos estados: están "vivas" o "muertas" (o "encendidas" y "apagadas"). El estado de la malla evoluciona a lo largo de unidades de tiempo discretas (se podría decir que por turnos). El estado de todas las células se tiene en cuenta para calcular el estado de las mismas al turno siguiente. Todas las células se actualizan simultáneamente.
Las transiciones dependen del número de células vecinas vivas:
- Una célula muerta con exactamente 3 células vecinas vivas "nace" (al turno siguiente estará viva).
- Una célula viva con 2 ó 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por "soledad" o "superpoblación").
A continuación voy a intentar programar este juego en C# para poder ver su comportamiento en real...
Autómata Celular (AC)
Un Autómata Celular (AC) podríamos definirlo como una cuadrícula espacial regular de "células", cada una de las cuales puede tener sólo uno de un número finito de estados. El estado de las células en la cuadricula se actualiza simultáneamente y el estado de la cuadrícula completa avanza en pasos de tiempo discretos. El estado de cada célula en la cuadricula se actualiza de acuerdo a una regla local que puede depender del estado de la célula y sus vecinos en el paso temporal anterior (Foldoc).
Uno de los autómatas celulares más representativos y clásicos es el Juego de la Vida de Conway.
Uno de los autómatas celulares más representativos y clásicos es el Juego de la Vida de Conway.
Vida Artificial (A-Life)
La Vida Artificial (A-Life), es el intento de conseguir modelar el estilo las formas de la naturaleza por medio de un ordenador. Por ello la Vida Artificial está estrechamente relacionada con la IA, los AG y los Autómatas Celulares (AC).
martes, 11 de enero de 2011
Algoritmo Evolutivo (AE)
Un Algoritmo Evolutivo, podría definirse como una potente técnica de busqueda y optimización, permitiendo así mismo resolver gran cantidad de problemas propios de los procesos de aprendizaje.
Un AE tipicamente mantiene una población de soluciones potenciales (individuos) del problema, las cuales evolucionan de acuerdo a reglas de selección y otros operadores, tales como combinación y mutación. Cada individuo es evaluado, recibiendo una medida de adecuación (fitness) en su entorno. La selección enfoca su atención en los individuos de adecuación alta, explotando así la información de las adecuaciones disponibles. La recombinación y mutación modifican los individuos, proporcionando una heurística general de exploración.
Se pude definir un AE que trabaja sobre una población (P) como:
1) Inicializar (P(0));
2) Generación = 0;
3) mientras (no criterio de parada) hacer
4) Evaluar (P(generación));
5) Padres = Seleccionar (P(generación));
6) Hijos = Aplicar Operadores Evolutivos (padres);
7) NuevaPoblación = Reemplazar (hijos, P(generación));
8) Generación ++;
9) P(generación) = NuevaPoblación;
10) fin
11) retornar MejorSoluciónEncontrada;
Como hemos comentado anteriormente, un AE trabaja sobre individuos que representan potenciales soluciones al problema, codificados de acuerdo a un mecanismo prefijado. Los individuos son evaluados de acuerdo a una función de fitness que toma en cuenta la adecuación de cada solución al problema que intenta resolver.
La operativa del AE comienza con una etapa de inicialización de los individuos, que puede ser completamente aleatoria o guiada de acuerdo a características del problema a resolver.
La evolución propiamente dicha se lleva a cabo en el ciclo que genera nuevos individuos a partir de la población actual mediante un procedimiento de aplicación de operadores estocásticos. En este ciclo se distinguen 4 etapas:
1) Evaluación.
Etapa que consiste en asignar un valor de adecuación (fitness) a cada individuo de la población.
2) Selección.
Proceso que determina candidatos adecuados, de acuerdo a sus valores de fitness, para la aplicación de los operadores evolutivos con el obejtivo de engendrar la siguiente generación de individuos.
3) Apliación de los operadores evolutivos.
Etapa que genera un conjunto de descendientes a partir de los individuos seleccionados en la etapa anterior.
4) Reemplazo.
Mecanismo que realiza el cambio generacional, sustituyendo individuos de la generación anterior por descendientes creados en la etapa anterior.
Un AE tipicamente mantiene una población de soluciones potenciales (individuos) del problema, las cuales evolucionan de acuerdo a reglas de selección y otros operadores, tales como combinación y mutación. Cada individuo es evaluado, recibiendo una medida de adecuación (fitness) en su entorno. La selección enfoca su atención en los individuos de adecuación alta, explotando así la información de las adecuaciones disponibles. La recombinación y mutación modifican los individuos, proporcionando una heurística general de exploración.
Se pude definir un AE que trabaja sobre una población (P) como:
1) Inicializar (P(0));
2) Generación = 0;
3) mientras (no criterio de parada) hacer
4) Evaluar (P(generación));
5) Padres = Seleccionar (P(generación));
6) Hijos = Aplicar Operadores Evolutivos (padres);
7) NuevaPoblación = Reemplazar (hijos, P(generación));
8) Generación ++;
9) P(generación) = NuevaPoblación;
10) fin
11) retornar MejorSoluciónEncontrada;
Como hemos comentado anteriormente, un AE trabaja sobre individuos que representan potenciales soluciones al problema, codificados de acuerdo a un mecanismo prefijado. Los individuos son evaluados de acuerdo a una función de fitness que toma en cuenta la adecuación de cada solución al problema que intenta resolver.
La operativa del AE comienza con una etapa de inicialización de los individuos, que puede ser completamente aleatoria o guiada de acuerdo a características del problema a resolver.
La evolución propiamente dicha se lleva a cabo en el ciclo que genera nuevos individuos a partir de la población actual mediante un procedimiento de aplicación de operadores estocásticos. En este ciclo se distinguen 4 etapas:
1) Evaluación.
Etapa que consiste en asignar un valor de adecuación (fitness) a cada individuo de la población.
2) Selección.
Proceso que determina candidatos adecuados, de acuerdo a sus valores de fitness, para la aplicación de los operadores evolutivos con el obejtivo de engendrar la siguiente generación de individuos.
3) Apliación de los operadores evolutivos.
Etapa que genera un conjunto de descendientes a partir de los individuos seleccionados en la etapa anterior.
4) Reemplazo.
Mecanismo que realiza el cambio generacional, sustituyendo individuos de la generación anterior por descendientes creados en la etapa anterior.
Definición Algoritmo Genético (AG)
Los Algoritmos Genéticos son una de las más conocidas y originales técnicas de resolución de problemas dentro de lo que se ha definido como "Computación Evolutiva" (o "Algoritmos Evolutivos"), término que agrupa a:
- Programación Evolutiva.
- Estrategías Evolutivas.
- Algoritmos Genéticos.
La analogía en que se basan los AG estriba en reconocer el mecanismo esencial del proceso evolutivo de la naturaleza.
Expuesto de otra forma, un AG es una técnica de programación que imita a la evolución biológica como estrategia para resolver problemas. Dado un problema específico a resolver, la entrada del AG es un conjunto de soluciones potenciales a ese problema, codificadas de alguna manera, y una métrica llamada función de aptitud que permite evaluar cuantitativamente a cada candidata. Estas candidatas pueden ser soluciones que ya se sabe que funcionan, con el objetivo de que el AG las mejore, pero se suelen generar aleatoriamente.
Más tarde veremos con más detalle los AG.
- Programación Evolutiva.
- Estrategías Evolutivas.
- Algoritmos Genéticos.
La analogía en que se basan los AG estriba en reconocer el mecanismo esencial del proceso evolutivo de la naturaleza.
Expuesto de otra forma, un AG es una técnica de programación que imita a la evolución biológica como estrategia para resolver problemas. Dado un problema específico a resolver, la entrada del AG es un conjunto de soluciones potenciales a ese problema, codificadas de alguna manera, y una métrica llamada función de aptitud que permite evaluar cuantitativamente a cada candidata. Estas candidatas pueden ser soluciones que ya se sabe que funcionan, con el objetivo de que el AG las mejore, pero se suelen generar aleatoriamente.
Más tarde veremos con más detalle los AG.
Definición Computación Evolutiva (CE)
Según consta en Wikipedia "
...La Computación Evolutiva es una rama de la inteligencia artificial que involucra problemas de optimización combinatoria (Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.). Se inspira en los mecanismos de la Evolución biológica.
..."
También podemos definir la CE diciendo que usa procesos evolutivos como elementos clave en el diseño e implementación de sistemas que resuelven problemas basados en una computadora"
...La Computación Evolutiva es una rama de la inteligencia artificial que involucra problemas de optimización combinatoria (Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.). Se inspira en los mecanismos de la Evolución biológica.
..."
También podemos definir la CE diciendo que usa procesos evolutivos como elementos clave en el diseño e implementación de sistemas que resuelven problemas basados en una computadora"
Suscribirse a:
Entradas (Atom)