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.
Subscribe to:
Posts (Atom)