José Iván Ferrer Ruiz, 468659
Daniel Salas Fukutake, 468938
José Alberto Ugalde del Rosal, 1161567
Actividad de Programación 2: Recocido Simulado
A) El medio ambiente es una superficie que cuenta con diferentes propiedades físicas, incluyendo viento y fricción en la superficie. En el se encuentra un pequeño bloque y aleatoriamente se selecciona un punto u objetivo. El bloque cuenta con “propulsores” simulados que apuntan desde cada uno de sus lados y pueden ejercer un impulso inicial en diferentes intensidades moviéndolo a través del medio.
B) El objetivo de la simulación es acercar el bloque al punto final lo más posible en un periodo corto de tiempo. Se debe optimizar la distancia que el bloque recorre en el periodo de tiempo, la mejor distribución de los propulsores para llegar al objetivo. Si se corre continuamente se busca optimizar el camino que sigue el bloque (aproximando a una línea).
C) Solución planteada usando Recocido Simulado.
Configuración:
((ox, oy), m, (wx, wy), wf, (pxn, pxp, pyn, pyp))
donde:
(ox, oy) -> Posición del bloque.
m -> Masa del bloque.
(wx, wy) -> Fuerza del viento.
wf -> Fricción.
(pxn, pxp, pyn, pyp) -> Intensidades usadas en cada propulsor.
Ejemplos:
s1: ((58, 294), 190, (476, 446), (-149.44838339381619, -249.45895066606923), (168.77246735900459, 252.01837423622706, 77.607627925924334, 269.74872001041877))
f(s1) = 576.059892655
s2: ((58, 294), 190, (476, 446), (-149.44838339381619, -249.45895066606923), (184.0264545952796, 301.57066221021796, 112.57185068902984, 210.17509796748897))
f(s2) = 610.623109614
s3: ((58, 294), 190, (476, 446), (-149.44838339381619, -249.45895066606923), (128.5459172769589, 118.65525456155197, 93.871981155212438, 237.23015248433393))
f(s3) = 741.920412938
Reordenamientos:
Los reordenamientos involucran mutar la tupla (pxn, pxp, pyn, pyp) para asignar nuevos valores a cada propulsor.
Ejemplos:
(643.6223, 133.7548, 121.3245, 021.9974) ->
(266.4353, 932.7348, 213.4443, 269.2228) ->
(024.8762, 176.4358, 021.3243, 573.8237)
Función objetivo:
La función objetivo toma todas las fuerzas que actúan sobre el bloque y calcula la posición final del objeto. La energía equivale a la distancia entre la posición final y el punto el objetivo, que el algoritmo busca minimizar.
Calendario de recocido:
T inicial = 100
T final = 0
dT por ciclo = 0.001
El calendario fue seleccionado aleatoriamente, pero después de varias pruebas se determinó que proporcionaba resultados aceptables.
D) Video
E) Conclusiones después de la programación.
La programación del algoritmo como tal fue sumamente rápida, resultó más complicado el encontrar funciones objetivo y de reordenamiento adecuadas para generar resultados aceptables. Una vez definidas, el algoritmo funcionó correctamente y permitió hacer cambios fácilmente para experimentar con diferentes valores.
El algoritmo fue programado de tal forma que sea independiente de esta implementación por lo que resultaría sencillo reutilizarlo en otro caso. Creemos que fue una buena experiencia para aprender de que forma funcionan estos algoritmos.
Friday, February 19, 2010
Thursday, February 18, 2010
Actividad 2 - Equipo 1 - Biokterii
Biokterii
Inteligencia Computacional
Grupo 1
Alejandro Morales A01161376
Jonathan Valle A01161110
Rafael Santos A01161734
18 de febrero de 2010
Equipo 1 : ./42
Actividad 1
Grupo 1
Alejandro Morales A01161376
Jonathan Valle A01161110
Rafael Santos A01161734
18 de febrero de 2010
Equipo 1 : ./42
Actividad 1
Descripción del medio ambiente
El medio ambiente dentro del que se desarrolla Biokterii es el interior de un ser vivo, donde el virus maligno debe infectar la mayoría de células posibles antes de morir, para lo cual debe optimizar su recorrido, sin embargo el virus no se encuentra solo, pues en su recorrido encontrará lugares donde puede recuperar su energía.
Descripción breve del problema de optimización
Este problema es muy similar al problema del viajero, pues se debe cubrir una ruta recorriendo la menor cantidad posible de distancia. Pero a diferencia del problema del viajero tradicional, nuestro virus cuenta con una vida limitada y cuenta con "estaciones de recarga" que le permiten completar su recorrido a través del ser vivo.
Solución con recocido simulado
Configuración
El primer ejemplo de configuración es el siguiente:
Como podemos observar en la ilustracion anterior la ruta se encuentra completamente al azar y es muy poco óptima, existen crueces y las estación de recarga se encuentra en el final.
En la imagen anterior podemos observar la ruta que encontró el algoritmo, al poner las células en esta disposición es fácil de observar como es que el algoritmo funciona y como en este caso arrojó una solución, que al menos a simple vista, es bastante óptima y mucho mejor que la configuración que se tenía anteriormente.
El segundo ejemplo de configuración es un poco más interesante:
Como podemos observar, la ruta que ha construido para esta configuración es bastante óptima, pues incluso considera el utilizar la estación de recarga a medio recodido, en vez de desperdiciarlo utilizandolo al principio, es importante mencionar que el virus tiene una salud máxima, por lo que utilizar la estación al principio del recorrido no es una decisión muy inteligente u óptima.
Por último tenemos este tercer ejemplo:
Aquí podemos observar una vez más una configuración y un camino óptimos.
Reordenamientos
En cada reordenamiento se intercambia aleatoriamente una célula o estación de recarga con otra elegida también aleatoriamente.
Función objetivo
EL objetivo es minimizar el daño que recibe el virus al pasar por las diferentes células y estaciones de recarga. Además se ponderan algunos casos especiales para alterar un poco la forma en la que toma en cuenta cada estación de recarga.
Conclusiones
En nuestra simulación es posible observar como funciona el algoritmo de recocido simulado, pues las lineas o rutas se van pintando conforme va aceptando configuraciones para poder apreciar las primeras soluciones y como ésta va evolucionando hasta llegar a una solución óptima.
En cada reordenamiento se intercambia aleatoriamente una célula o estación de recarga con otra elegida también aleatoriamente.
Función objetivo
EL objetivo es minimizar el daño que recibe el virus al pasar por las diferentes células y estaciones de recarga. Además se ponderan algunos casos especiales para alterar un poco la forma en la que toma en cuenta cada estación de recarga.
Si la configuración tiene una estación de recarga al inicio, se penaliza con 1000 puntos (pues estaría desperdiciando dicha estación). Si no, entonces se acumulan las distancias entre cada célula de la lista en una variable.
Si el siguiente elemento a analizar de la lista es una estación de recarga, entonces se resta el daño que recuperaría de dicha estación de la variable donde se están acumulando las distancias y se penaliza ligeramente si no aprovecha en su totalidad la estación (si la utiliza con la vida llena).
Finalmente, se revisa si el virus moriría en algún punto del recorrido al restarle a su vida las distancias recorridas. Si el virus muere, se penaliza con 10,000 puntos.
Calendario de recocido
La temperatura inicial es de 1000.
Calendario de recocido
La temperatura inicial es de 1000.
El control de la temperatura se divide uniformemente entre la temperatura inicial y la cantidad de iteraciones que se generan. Por lo anterior, la temperatura se reduce en cada iteración una pequeña cantidad.
El recocido se detiene cuando la temperatura llega a 0.001.
Conclusiones
En nuestra simulación es posible observar como funciona el algoritmo de recocido simulado, pues las lineas o rutas se van pintando conforme va aceptando configuraciones para poder apreciar las primeras soluciones y como ésta va evolucionando hasta llegar a una solución óptima.
El algoritmo de recocido simulado sí funciona para nuestro proyecto porque lo que se intenta hacer es optimizar el recorrido del virus minimizando el daño que recibe. Como el algoritmo minimiza la función objetivo, se puede llegar a una solución óptima o que se acerca mucho a la óptima.
Video:
Actividad 2 Equipo 3
Jorge Dorantes 1011377
Alberto Barbosa 465635
Gerardo Basurto 01013754
Descripción del medio ambiente
Cada partida de Starcraft se realiza en un mapa que el usuario escoge. Dicho mapa varía a otros en dimensiones, recursos disponibles, ubicación de los recursos y topología. Al comienzo de cada partida, el jugador no tiene información sobre el mapa. El jugador tiene un rango de visión el cual determina que tanto puede ver del mapa respecto a cierta posición. Una vez que el jugador ha pasado por un punto en el mapa, todo lo descubra permanecerá visible hasta el fin del partida.
Recocido Simulado
En nuestro ambiente tenemos un agente que se encarga de tomar decisiones respecto a eventos que ocurren en el medio ambiente. El objetivo del agente es aprender una técnica de rush denominada “5 Pool Zerg Strategy”. Se utilizó recocido simulado para encontrar una asignación óptima de acciones que se aproximaran a ésta estrategia de juego.
5 Pool Zerg Strategy:
5 Pool is a very common Zerg Rush strategy used to take advantage of the fast zerg economy. The idea behind this strategy is to arm a pack of zerlings and attack the enemy as quickly as possible.
5-Pool is as follows :
1.- Build one (1) Drone.
2.- Send Drones to mine minerals.
3.- Send Overlord to scout start positions.
4.- Wait for 200 minerals to build up, then build Spawning Pool.
5.- Build one (1) more drones.
6.- Build three (3) sets of Zergling, and attack.
7.- Build 2nd Overlord AFTER Zergling.
Configuración
Se pueden realizar varias acciones y también se pueden registrar ciertos eventos. 3 ejemplos serían.
1. Información - Tengo 400 minerales, 5 obreros, 3 guerreros y no sé dónde está el enemigo.
Posibles acciones - Construir obreros, guerreros, scouts, no atacar.
2. Información Tengo 150 minerales, 0 obreros, 0 guerreros y se dónde está el enemigo..
Posibles acciones - Construir obreros, guerreros, scouts.
3. Información Tengo 300 minerales, 5 obreros, 0 guerreros y se dónde está el enemigo.
Posibles acciones - Construir obreros, guerreros, scouts.
Reodenamientos
Los reordenamientos se hacen de manera aleatoria dentro de un rango permitido (respetando el límite de los recursos disponibles). Para los recursos disponibles en el ejemplo anterior, una posible reconfiguración de cada uno seria:
1. Construir 2 obreros, 1 guerreros, 0 scouts, atacar à Construir 0 obreros, 3 guerreros,1 scout, atacar.
2. Construir 2 obreros, 0 guerreros, 2 scouts, no atacar à Construir 0 obreros, 3 guerreros, no atacar
3. Construir 0 obreros, 5 guerreros, 1 scouts, atacar à Construir 0 obreros, 3 guerreros, no atacar
Función objetivo
El objetivo de nuestro agente en Starcraft será el de aproximar la “5 Pool Zerg Strategy”. De esta forma las configuraciones se evaluaran con respecto a que tanto se acercan a las acciones que dictarían dicha estrategia.
Calendario de recocido
Temperatura inicial de 150. La temperatura disminuye en 10%.
Conclusiones
La “5 Pool Zerg Strategy” es una estrategia de juego muy sencilla, por lo que no tuvimos que preocuparnos por limitaciones de recursos y espacios en general. Dado que la estrategia tiene bien establecida el número óptimo de unidades a construir y bajo que situaciones atacar al enemigo, la función objetivo pudo ser fácilmente definida y ponderada.
Wednesday, February 17, 2010
Actividad 2
Gianfranco Arroyo Orrico 1162878
Barbara Cervantes 1161223
Felix Horta 1162183
Actividad de Programación 2 – Recocido Simulado
Breve descripción del medio ambiente.
Un triangulo formado por números aleatorios. Cada nivel tiene uno más que el anterior. Iniciando de la punta de la pirámide y eligiendo un camino hacia abajo pasando por cualquiera de los dos números inmediatos inferiores hasta llegar al último nivel (la base del triangulo).
Descripción detallada del problema de optimización – da 3 ejemplos en donde se aprecie por qué es un problema de optimización.
El problema de optimización consiste en obtener las suma máxima al recorrer el triangulo hacia abajo.
Ej.1)
59
73 41
52 40 09
26 53 06 34
10 51 87 86 81
61 95 66 57 25 68
369
Ej.2)
59
73 41
52 40 09
26 53 06 34
10 51 87 86 81
61 95 66 57 25 68
390
Ej.3)
59
73 41
52 40 09
26 53 06 34
10 51 87 86 81
61 95 66 57 25 68
226
Solución planteada al problema utilizando el método de recocido simulado. Describe con detalle cada elemento del planteamiento:
Configuración – da al menos 3 ejemplos de configuraciones.
Una matriz de números que muestra un triangulo y ademas un arreglo que indica el camino que se utiliza para recorrer el triangulo.
59
73 41
52 40 09
26 53 06 34
10 51 87 86 81
61 95 66 57 25 68
[IDIDD]
59
73 41
52 40 09
26 53 06 34
10 51 87 86 81
61 95 66 57 25 68
[IIDDI]
59
73 41
52 40 09
26 53 06 34
10 51 87 86 81
61 95 66 57 25 68
[DDIDD]
Reordenamientos – da al menos 3 ejemplos de reordenamientos.
El reordenamiento consiste en cambiar aleatoriamente un valor del arreglo que indica el camino a seguir.
[DDIDD]
[DDIDI]
[DIIDI]
Función objetivo
La suma negativa de todos los números en el camino.
Calendario de recocido
T = 50
α = 0.999
Tn+1 = α*Tn
Conclusiones después de la programación.
No se llega a la solución óptima pero se llega a una solución muy cercana. Si la temperatura inicial es muy baja entonces es muy difícil que llegue a una buena solución.
Thursday, February 4, 2010
Selección del Medio Ambiente
José Iván Ferrer Ruiz, 468659
Daniel Salas Fukutake, 468938
José Alberto Ugalde del Rosal, 1161567
Actividad de Programación 1: Selección del medio ambiente
1. El medio ambiente es una superficie que cuenta con diferentes propiedades físicas, incluyendo viento y fricción en la superficie. En el centro se encuentra un pequeño bloque y aleatoriamente se selecciona un punto u objetivo. El bloque cuenta con “propulsores” simulados que apuntan desde cada uno de sus lados, consumen combustible y pueden ejercer fuerza en diferentes intensidades moviéndolo a través del medio.
2. Se utilizará como plataforma de desarrollo el lenguaje Python y los paquetes pygame y PyGTK para la creación de la interfaz gráfica. Todos funcionan correctamente sobre Linux y Windows.
3. La optimización se puede realizar al encontrar la intensidad con la que los propulsores deben ser usados de tal forma que el bloque se acerque al objetivo lo más posible dadas las condiciones del ambiente, minimizando la distancia al objetivo y el combustible usado.
4. Las características del ambiente, como el viento y la fricción de la superficie, hacen que sea incierta la forma en la que el bloque debe controlar los “propulsores” de tal forma que pueda propulsarse y frenar para ubicarse correctamente cerca del objetivo.
Daniel Salas Fukutake, 468938
José Alberto Ugalde del Rosal, 1161567
Actividad de Programación 1: Selección del medio ambiente
1. El medio ambiente es una superficie que cuenta con diferentes propiedades físicas, incluyendo viento y fricción en la superficie. En el centro se encuentra un pequeño bloque y aleatoriamente se selecciona un punto u objetivo. El bloque cuenta con “propulsores” simulados que apuntan desde cada uno de sus lados, consumen combustible y pueden ejercer fuerza en diferentes intensidades moviéndolo a través del medio.
2. Se utilizará como plataforma de desarrollo el lenguaje Python y los paquetes pygame y PyGTK para la creación de la interfaz gráfica. Todos funcionan correctamente sobre Linux y Windows.
3. La optimización se puede realizar al encontrar la intensidad con la que los propulsores deben ser usados de tal forma que el bloque se acerque al objetivo lo más posible dadas las condiciones del ambiente, minimizando la distancia al objetivo y el combustible usado.
4. Las características del ambiente, como el viento y la fricción de la superficie, hacen que sea incierta la forma en la que el bloque debe controlar los “propulsores” de tal forma que pueda propulsarse y frenar para ubicarse correctamente cerca del objetivo.
Thursday, January 28, 2010
Descripción del medio ambiente
Inteligencia Computacional
Grupo 1
Alejandro Morales A01161376
Jonathan Valle A01161110
Rafael Santos A01161734
26 de enero de 2010
Equipo 1 : ./42
Actividad 1
Ambiente: Cuerpo de un ser vivo (sistema inmunológico).
1. Descripción detallada del medio ambiente.
Todo se desarrolla en el momento en el que un virus, o conjunto de virus intenta infectar el cuerpo de un ser vivo. Dentro del cuerpo se encuentra un sistema inmunológico, basado en anticuerpos.
Puede haber diferentes escenarios, que involucren multiagentes reproduciéndose, o un ambiente centralizado en el que un agente controla la estrategia de todos los demás, o un solo agente que debe encontrar el camino para infectar la célula principal.
La construcción física de los escenarios dependerá de los conceptos que se deseen enfatizar con esa actividad de programación, sin embargo las bases del funcionamiento serían siempre las mismas, tal y como se describen en el párrafo anterior.
Cada tipo de agente puede tener diferentes propiedades o comportamientos, así como definir una estrategia de ataque o defensa para cada tipo de agente.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado. ¿Por qué?
El desarrollo se realizará de forma local en una aplicación de escritorio. Se utilizará el lenguaje de programación: Python (2.6), combinado con GTK a través del binding de pyGTK para la interfaz gráfica.
Decidimos utilizar este lenguaje por su facilidad de uso, lo cual nos permitirá concentrarnos más en la parte de resolver los problemas y hacer los algoritmos, en lugar de lidiar con problemas sintácticos o morfológicos.
Además, algunos miembros del equipo contamos con cierta experiencia utilizando python+pygtk, lo cual facilita el proceso de desarrollo.
3.- ¿Cuáles problemas de optimización se encuentran en dicho medio?
Se puede tener un escenario en el que el virus, con un tiempo de vida establecido, necesite infectar células que se encuentran en diferentes lugares. El virus necesita optimizar su recorrido para lograr infectar el mayor número de células posibles antes de morir.
También se puede tener un escenario en el que un agente centralizado del virus necesite decidir que tipo de células debe mandar (suponiendo que hay diferentes tipos de células con diferentes tipos de propiedades) utilizando un recurso finito como que se consume de diferente manera cada vez que se crea una nueva célula. El agente centralizado necesita optimizar sus recursos para tener la mejor combinación de células para atacar.
4.- ¿Qué conocimiento con incertidumbre necesita ser representado?
Un ejemplo de ello lo encontramos en el escenario donde se libra una batalla campal entre virus y anticuerpos, ya que no se sabe exactamente el número de enemigos que aún se encuentran dentro del medio ambiente, pues este número va cambiando por las unidades que han sido eliminadas y las que se han reproducido. En este caso el equipo contrario no conoce el número exacto de enemigos, solo un estimado, y dependiendo de dicho número decidirá que estrategia utilizar.
También se puede dar el caso que el virus saben que deben infectar unas células en específico pero no saben donde están, dado que esas células también se mueven. Conforme los virus se mueven por el ambiente , deben tratar de estimar la posición de dichas células, basándose en las cosas que recopilan entre todos.
Grupo 1
Alejandro Morales A01161376
Jonathan Valle A01161110
Rafael Santos A01161734
26 de enero de 2010
Equipo 1 : ./42
Actividad 1
Ambiente: Cuerpo de un ser vivo (sistema inmunológico).
1. Descripción detallada del medio ambiente.
Todo se desarrolla en el momento en el que un virus, o conjunto de virus intenta infectar el cuerpo de un ser vivo. Dentro del cuerpo se encuentra un sistema inmunológico, basado en anticuerpos.
Puede haber diferentes escenarios, que involucren multiagentes reproduciéndose, o un ambiente centralizado en el que un agente controla la estrategia de todos los demás, o un solo agente que debe encontrar el camino para infectar la célula principal.
La construcción física de los escenarios dependerá de los conceptos que se deseen enfatizar con esa actividad de programación, sin embargo las bases del funcionamiento serían siempre las mismas, tal y como se describen en el párrafo anterior.
Cada tipo de agente puede tener diferentes propiedades o comportamientos, así como definir una estrategia de ataque o defensa para cada tipo de agente.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado. ¿Por qué?
El desarrollo se realizará de forma local en una aplicación de escritorio. Se utilizará el lenguaje de programación: Python (2.6), combinado con GTK a través del binding de pyGTK para la interfaz gráfica.
Decidimos utilizar este lenguaje por su facilidad de uso, lo cual nos permitirá concentrarnos más en la parte de resolver los problemas y hacer los algoritmos, en lugar de lidiar con problemas sintácticos o morfológicos.
Además, algunos miembros del equipo contamos con cierta experiencia utilizando python+pygtk, lo cual facilita el proceso de desarrollo.
3.- ¿Cuáles problemas de optimización se encuentran en dicho medio?
Se puede tener un escenario en el que el virus, con un tiempo de vida establecido, necesite infectar células que se encuentran en diferentes lugares. El virus necesita optimizar su recorrido para lograr infectar el mayor número de células posibles antes de morir.
También se puede tener un escenario en el que un agente centralizado del virus necesite decidir que tipo de células debe mandar (suponiendo que hay diferentes tipos de células con diferentes tipos de propiedades) utilizando un recurso finito como que se consume de diferente manera cada vez que se crea una nueva célula. El agente centralizado necesita optimizar sus recursos para tener la mejor combinación de células para atacar.
4.- ¿Qué conocimiento con incertidumbre necesita ser representado?
Un ejemplo de ello lo encontramos en el escenario donde se libra una batalla campal entre virus y anticuerpos, ya que no se sabe exactamente el número de enemigos que aún se encuentran dentro del medio ambiente, pues este número va cambiando por las unidades que han sido eliminadas y las que se han reproducido. En este caso el equipo contrario no conoce el número exacto de enemigos, solo un estimado, y dependiendo de dicho número decidirá que estrategia utilizar.
También se puede dar el caso que el virus saben que deben infectar unas células en específico pero no saben donde están, dado que esas células también se mueven. Conforme los virus se mueven por el ambiente , deben tratar de estimar la posición de dichas células, basándose en las cosas que recopilan entre todos.
Proyecto - Inteligencia Computacional
Equipo 3
Alberto Barbosa
Jorge Dorantes
Gerardo Basurto
Descripciòn del medio ambiente:
- Starcraft, definido como un juego de acciòn/estrategia en el cual dos jugadores compiten por la dominaciòn del mapa a travès de la recolecciòn de recursos y combate bèlico.
Plataforma y lenguaje a utilizar:
- Starcraft API, es una extensiòn progamada en C/C++ con instrucciònes que permiten el control de la Inteligencia Artificial del juego, con el fin de programar algoritmos de inteligencia artificial.
Problemas de optimizaciòn:
- Hallar rutas y optimizaciòn de recursos y unidades.
Conocimiento con incertidumbre:
- Decisiones de micro y macroeconomia, asi como modulaciòn de estrategias.
Alberto Barbosa
Jorge Dorantes
Gerardo Basurto
Descripciòn del medio ambiente:
- Starcraft, definido como un juego de acciòn/estrategia en el cual dos jugadores compiten por la dominaciòn del mapa a travès de la recolecciòn de recursos y combate bèlico.
Plataforma y lenguaje a utilizar:
- Starcraft API, es una extensiòn progamada en C/C++ con instrucciònes que permiten el control de la Inteligencia Artificial del juego, con el fin de programar algoritmos de inteligencia artificial.
Problemas de optimizaciòn:
- Hallar rutas y optimizaciòn de recursos y unidades.
Conocimiento con incertidumbre:
- Decisiones de micro y macroeconomia, asi como modulaciòn de estrategias.
Subscribe to:
Posts (Atom)