• Codificación del cromosoma. De un ejemplo de un robot al codificar.
En principio se generará una población de cromosomoas aleatorios compuestos por una serie de frames. Cada frame consta de varias listas y que éstas a su vez contienen los elementos (números) que representan el ángulo de movimiento de cada “joint” del cuerpo. Así, ya con esta lista principal de Frames, el robot sabe qué joint va en qué ángulo y para qué frame debe hacerlo, de esta forma se evalúa después en la función objetivo que es la base del algoritmo para identificar el objetivo final.
Ejemplo: un cromosoma con 5 frames seria como sigue:
[0,0,0,0,0,0],[-20,50,10,5,0,0],[0,-50,0,0,0,0],[50,10,40,20,0,0],[0,0,0,0,0,0]
Donde podemos ver que cada frame tiene 6 valores, uno para cada uno de los joints de la pierna. (Esto va a aumentar 20 (todos los joints del robot) cuando apliquemos realmente el algoritmo al proyecto de Robocup).
• Función a minimizar o a maximizar. ¿Cómo se calcula?
La función objetivo se calcula al evaluar cada cromosoma en el robot con la distancia que este avanzo en un tiempo determinado. Si al final del tiempo dado el robot no ha caminado, que puede ser porque se cayó, o avanzó muy poco, la función calcula qué cromosoma o cromosomas fueron los que ayudaron a que fuera un caminado más óptimo, y de éstos saca más números para las siguientes generaciones.
• Forma de hacer la reproducción.
La manera en la que se seleccionan los elementos para la reproducción es utilizando el PSelect que se calcula sumando el número total de elementos entre la suma total de los mismos. Ya teniendo el PSelect se calcula el Counter que es el número de cromosomas que pasarán para la reproducción.
• Forma de hacer la crossover.
El crossover se hace combinando los frames entre cada uno de los cromosomas de la población. No modificamos los valores de los joints al realizar el crossover debido a que nos podría ocasionar problemas por los diferentes rangos que tienen cada uno de ellos.
• Forma de hacer la mutación.
La mutación tendrá una probabilidad fija de .05. Cada elemento de cada frame tendrá esta misma probabilidad, esto para no obligar a que esté mutando tan constantemente, porque no se asegura que cuando se llegue a un cromosoma óptimo, los demás también lo serán, entonces si se muta este cromosoma se perdería el sentido correcto de lo que se tenía con anterioridad.
• Ejemplos de una generación de 4 elementos en la población.
--INITIAL POPULATION--
ELEMENT 1--> F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F7 [100.0, -50.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0],
ELEMENT 2--> F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F9 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0],
ELEMENT 3--> F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F10 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0],
ELEMENT 4--> F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F10 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F10 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F7 [100.0, -50.0, 0.0, 50.0, 0.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0],
--GENERATION # 1--
--REPRODUCTION--
ELEMENT 1--> FITNESS 0.04605520492062051, PSELECT 0.6031265004054416, ECOUNT 2.4125060016217663, SELECTED 2
ELEMENT 2--> FITNESS 0.018206693136792483, PSELECT 0.2384299263129079, ECOUNT 0.9537197052516316, SELECTED 1
ELEMENT 3--> FITNESS 0.010275915992709416, PSELECT 0.13457061502223877, ECOUNT 0.5382824600889551, SELECTED 1
ELEMENT 4--> FITNESS 0.0018229575121629143, PSELECT 0.023872958259411763, ECOUNT 0.09549183303764705, SELECTED 0
--NEW POPULATION--
ELEMENT 1--> F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F7 [100.0, -50.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0],
ELEMENT 2--> F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F7 [100.0, -50.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0],
ELEMENT 3--> F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F9 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0],
ELEMENT 4--> F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F10 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0],
--CROSSOVER--
ELEMENT 1--> F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0],
ELEMENT 2--> F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F9 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0],
ELEMENT 3--> F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F7 [100.0, -50.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0],
ELEMENT 4--> F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F10 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F7 [100.0, -50.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0],
--MUTATION--
ELEMENT 1--> F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0],
ELEMENT 2--> F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F2 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F1 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F9 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0],
ELEMENT 3--> F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F7 [100.0, -50.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0],
ELEMENT 4--> F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F3 [0.0, 0.0, 0.0, 100.0, -50.0, 0.0], F10 [0.0, 0.0, 0.0, 0.0, 0.0, 0.0], F4 [0.0, 0.0, 0.0, 50.0, -30.0, 0.0], F5 [0.0, 0.0, 0.0, 50.0, 0.0, 0.0], F6 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0], F7 [100.0, -50.0, 0.0, 50.0, 0.0, 0.0], F8 [50.0, -30.0, 0.0, 50.0, 0.0, 0.0],
Conclusiones después de la programación
Al comenzar a implementar el algoritmo genético no tuvimos muchos problemas porque lo empezamos desde una aplicación externa, sin integrarlo al momento con el robot. En esta aplicación externa teníamos definidos todos los métodos del algoritmo genético, como reproducción, crossover y mutación, sin embargo, nos faltaba lo más complicado que era jalar la función objetivo del simulador. Esta parte fue la más complicada del proyecto.
Gracias a este proyecto aprendimos una gran cantidad de conceptos del simulador y de algoritmos genéticos. Fue muy complicado por el hecho de tener que entender el código de otro equipo , sin embargo al final con mucho esfuerzo pudimos realizarlo.
Video:
Wednesday, March 25, 2009
Tuesday, March 24, 2009
Fase 3 - Proyecto
Aqui les dejamos nuestra aportación y la docu de nuestra tercera fase. Saludos :) Cualquier duda aquí estamos...
Breve descripción del medio ambiente.
Para este avance del proyecto, desarrollamos un ambiente representado por una matriz de ocho por ocho. Sin embargo dicha matriz, estará dividida en cuatro cuadrantes que serán generados como cuatro ambientes subordinados. Cada cuadrante estará dividido en pequeñas matrices de cuatro por cuatro. En principio cada cuadrante tendrá una figura de dos por dos elementos justo al centro. El ambiente también limita la cantidad de movimientos posibles para cada figura independiente, en los movimientos adyacentes posibles sin romper la pequeña figura de cuatro elementos “nano”.
Descripción detallada del problema de optimización.
Lo que el agente en principio debe de optimizar es la secuencia para generar nuevas figuras a partir de varios elementos independientes “nano”. Esto se optimiza con base en los movimientos posibles de las piezas “nano” independientes para que se genere una pieza final en unidad con los cuatro cuadrantes.
Supongamos que tenemos una figura dada inicial, con base en el ambiente. Y con respecto a las distintas piezas que se pueden mover a distintos lados. El problema de optimización está representado de la siguiente manera:
Figura inicial:
0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0
Figura final:
0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0
0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0
Movimiento uno:
0 0 1 0 0 0 0 0
0 0 1 0 0 1 0 0
0 1 1 0 0 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0
0 1 0 0 0 0 1 0
0 0 0 0 0 0 1 0
Movimiento dos:
0 0 1 0 0 0 0 0
0 0 1 0 0 1 1 0
0 1 1 0 0 1 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 0
0 0 0 0 0 0 0 0
En el ejemplo es visible que el movimiento dos genera en cada uno de los cuadrantes da un resultado más aproximado al final, por lo que las diferentes evaluaciones de selección son con base en esa relación y el que más acercado esté a la figura final será el segundo como el elegido a la selección final. Aunque en el ejemplo sólo se utilizan un par de movimientos, la implementación genera cuatro movimientos posibles. Sin embargo, la optimización con algoritmos genéticos radica en que las configuraciones más aproximadas a la final, son las que se presentan en la siguiente generación para ser producto de una evolución.
Solución planteada usando recocido de simulado.
Codificación del cromosoma.
Para la codificación de los cromosomas se tomarán en cuenta el número de cuadrantes que se generan con respecto al ambiente. Esto quiere decir que serán cuatro elementos dentro de un arreglo general que conserva toda la configuración final.
Está representado de la siguiente manera, por cada cromosoma.
[{0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
Función a maximizar o minimizar.
f(x) = Número de elementos correctos con respecto a la figura final.
-Implementación.
for(chr = 0; chr < MAXPOPUL; chr++)
sum += fx[chr];
avg = (sum / MAXPOPUL);
Reproducción.
-Implementación
for(chr = 0; chr < MAXPOPUL; chr++) //Expected count & Pselect
{
PSelect[chr] = (fx[chr] / (float)sum);
ExpectedC[chr] = (fx[chr] / (float)avg);
ActualC[chr] = (ExpectedC[chr] >= 1.0)? 1 : 0;
}
Crossover.
El crossover se realiza con base en el intercambio de cada uno de los cuadrantes. Se toman los dos cuadrantes y se intercambian entre ellos con los dos cuadrantes restantes. La forma en la que se selecciona el punto de cruce es aleatoria así como las parejas a ser cruzadas.
Mutación.
Para la mutación se considero una probabilidad de 1/1000. Con el objetivo de hacer una mutación en generaciones que estén más aproximadas al resultado final afectando de manera positiva a los cromosomas. Siempre y cuando los elementos de la generación no sean válidos u obtengan un valor menor en comparación al estado final.
Ejemplo.
Cromosoma f(x) Pselect Expected Blog to cross Cross Point Next Generation
[{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
5 .2 .83 0 2 [{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
[{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0}{0 0 0 0 1 1 1 0 0 1 0 0 0 0 0}] 8 .32 1.3 3 1 [{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0} {0 0 0 0 0 1 1 0 0 1 0 0 0 1 0}]
[{0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 1 1 0 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
7 .28 1.16 1 1 [{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0}{0 0 0 0 1 1 1 0 0 1 0 0 0 0 0}]
[{0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 0 0 0 0 1 0 0 1 1 1}]
5 .2 .83 0 3 [{0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 0 0 0 0 1 1 1 0 1 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
Conclusiones después de la programación.
Los algoritmos genéticos son una nueva forma de ver como se optimizan la forma de formar figuras. Lo más interesante de nuestra solución radica en la capacidad de generar una figura final con varias figuras independientes. Lo interesante es que, los elementos “nano” tienen que buscar una solución óptima de cómo llegar a crear con el menor esfuerzo o menor número de movimientos para generalizar las partes particulares. Sin embargo, nos dimos cuenta que la solución con algoritmos genéticos generaría una solución rápida para formar las figuras debido a la cantidad de cromosomas que se generan, por lo que estos algoritmos no generan una buena forma de implementación para nuestro problema.
Breve descripción del medio ambiente.
Para este avance del proyecto, desarrollamos un ambiente representado por una matriz de ocho por ocho. Sin embargo dicha matriz, estará dividida en cuatro cuadrantes que serán generados como cuatro ambientes subordinados. Cada cuadrante estará dividido en pequeñas matrices de cuatro por cuatro. En principio cada cuadrante tendrá una figura de dos por dos elementos justo al centro. El ambiente también limita la cantidad de movimientos posibles para cada figura independiente, en los movimientos adyacentes posibles sin romper la pequeña figura de cuatro elementos “nano”.
Descripción detallada del problema de optimización.
Lo que el agente en principio debe de optimizar es la secuencia para generar nuevas figuras a partir de varios elementos independientes “nano”. Esto se optimiza con base en los movimientos posibles de las piezas “nano” independientes para que se genere una pieza final en unidad con los cuatro cuadrantes.
Supongamos que tenemos una figura dada inicial, con base en el ambiente. Y con respecto a las distintas piezas que se pueden mover a distintos lados. El problema de optimización está representado de la siguiente manera:
Figura inicial:
0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0
Figura final:
0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0
0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0
Movimiento uno:
0 0 1 0 0 0 0 0
0 0 1 0 0 1 0 0
0 1 1 0 0 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0
0 1 0 0 0 0 1 0
0 0 0 0 0 0 1 0
Movimiento dos:
0 0 1 0 0 0 0 0
0 0 1 0 0 1 1 0
0 1 1 0 0 1 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 0
0 0 0 0 0 0 0 0
En el ejemplo es visible que el movimiento dos genera en cada uno de los cuadrantes da un resultado más aproximado al final, por lo que las diferentes evaluaciones de selección son con base en esa relación y el que más acercado esté a la figura final será el segundo como el elegido a la selección final. Aunque en el ejemplo sólo se utilizan un par de movimientos, la implementación genera cuatro movimientos posibles. Sin embargo, la optimización con algoritmos genéticos radica en que las configuraciones más aproximadas a la final, son las que se presentan en la siguiente generación para ser producto de una evolución.
Solución planteada usando recocido de simulado.
Codificación del cromosoma.
Para la codificación de los cromosomas se tomarán en cuenta el número de cuadrantes que se generan con respecto al ambiente. Esto quiere decir que serán cuatro elementos dentro de un arreglo general que conserva toda la configuración final.
Está representado de la siguiente manera, por cada cromosoma.
[{0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
Función a maximizar o minimizar.
f(x) = Número de elementos correctos con respecto a la figura final.
-Implementación.
for(chr = 0; chr < MAXPOPUL; chr++)
sum += fx[chr];
avg = (sum / MAXPOPUL);
Reproducción.
-Implementación
for(chr = 0; chr < MAXPOPUL; chr++) //Expected count & Pselect
{
PSelect[chr] = (fx[chr] / (float)sum);
ExpectedC[chr] = (fx[chr] / (float)avg);
ActualC[chr] = (ExpectedC[chr] >= 1.0)? 1 : 0;
}
Crossover.
El crossover se realiza con base en el intercambio de cada uno de los cuadrantes. Se toman los dos cuadrantes y se intercambian entre ellos con los dos cuadrantes restantes. La forma en la que se selecciona el punto de cruce es aleatoria así como las parejas a ser cruzadas.
Mutación.
Para la mutación se considero una probabilidad de 1/1000. Con el objetivo de hacer una mutación en generaciones que estén más aproximadas al resultado final afectando de manera positiva a los cromosomas. Siempre y cuando los elementos de la generación no sean válidos u obtengan un valor menor en comparación al estado final.
Ejemplo.
Cromosoma f(x) Pselect Expected Blog to cross Cross Point Next Generation
[{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
5 .2 .83 0 2 [{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
[{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0}{0 0 0 0 1 1 1 0 0 1 0 0 0 0 0}] 8 .32 1.3 3 1 [{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0} {0 0 0 0 0 1 1 0 0 1 0 0 0 1 0}]
[{0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 1 1 0 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
7 .28 1.16 1 1 [{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0}{0 0 0 0 1 1 1 0 0 1 0 0 0 0 0}]
[{0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 0 0 0 0 1 0 0 1 1 1}]
5 .2 .83 0 3 [{0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 0 0 0 0 1 1 1 0 1 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
Conclusiones después de la programación.
Los algoritmos genéticos son una nueva forma de ver como se optimizan la forma de formar figuras. Lo más interesante de nuestra solución radica en la capacidad de generar una figura final con varias figuras independientes. Lo interesante es que, los elementos “nano” tienen que buscar una solución óptima de cómo llegar a crear con el menor esfuerzo o menor número de movimientos para generalizar las partes particulares. Sin embargo, nos dimos cuenta que la solución con algoritmos genéticos generaría una solución rápida para formar las figuras debido a la cantidad de cromosomas que se generan, por lo que estos algoritmos no generan una buena forma de implementación para nuestro problema.
Monday, March 23, 2009
Fase 3 (no recuerdo como se llama el equipo)
Esta es nuestra primera entrada del semestre. Este es el proyecto de las quinielas de basquetbol.
a. Breve descripción del medio ambiente.
En esta etapa del proyecto nos enfocamos en la utilización de un algoritmo genético para maximizar la probabilidad de ganar una quiniela deportiva. El programa deberá escoger una combinación que contenga los partidos con mayor probabilidad de ganar. En este programa se seleccionará un grupo de 5 partidos.
b. Descripción detallada del problema de optimización – da al menos un ejemplo en donde se vea por qué es un problema de optimización.
El problema de optimización es buscar la mejor combinación que permita al usuario tener mayor éxito al apostar. Un ejemplo de dos combinaciones de partidos sería:
- {chi,mia,ny,orl,hou}
- {chi,mem,tor,por,gst}
En las combinaciones anteriores solo se consideran algunos equipos. El Algoritmo Genético busca la mejor combinación entre un conjunto de todos los equipos de la semana.
c. Solución planteada al problema utilizando la técnica de Algoritmos Genéticos. Describe con detalle cada elemento del planteamiento:
i. Codificación del cromosoma.
Cada cromosoma tendrá la siguiente forma:
- {X1,X2,X3,X4,X5}
Cada X representa un equipo diferente que además tiene una probabilidad de ganar una apuesta.
De un ejemplo de un robot al decodificar.
{orl,mia,dal,ny,ind}
Donde las probabilidades de cada uno son {50%,55%,75%,53%,48%}
ii. Función a minimizar o maximizar. ¿Cómo se calcula?
Se calcula con la sumatoria de las probabilidades de cada partido.
iii. Forma de hacer la reproducción.
Se eligen los pares que se van a reproducir al azar.
iv. Forma de hacer el crossover.
Se elige un punto dentro del cromosoma a partir del cual se hará el crossover. La selección del punto es al azar. Por ejemplo {X1,X2,X3 | X4,X5}
v. Forma de hacer la mutación.
La mutación ocurre con un valor de 0.01 y cuando ocurre cambia uno de los valores de un cromosoma por otro valor del conjunto de equipos.
vi. Ejemplo de una generación de 4 elementos en la población.
- {chi,mia,ny,orl,hou}
- {la,okc,tor,por,gst}
- {ind,sac,phi,san,dal}
- {chi,mem,tor,por,gst}
d. Conclusiones después de la programación.
El principal problema que tuvimos durante esta etapa del proyecto es que nuestro problema es muy pequeño y simple para el uso de algoritmos genéticos. Consideramos que el conjunto de datos sobre el cual trabaja el algoritmo es muy pequeño. Sin embargo fue una buena experiencia poner en práctica varios de los conceptos vistos en clase.
Fase 3
Proyecto Final
Proyecto Final
a. Breve descripción del medio ambiente.
En esta etapa del proyecto nos enfocamos en la utilización de un algoritmo genético para maximizar la probabilidad de ganar una quiniela deportiva. El programa deberá escoger una combinación que contenga los partidos con mayor probabilidad de ganar. En este programa se seleccionará un grupo de 5 partidos.
b. Descripción detallada del problema de optimización – da al menos un ejemplo en donde se vea por qué es un problema de optimización.
El problema de optimización es buscar la mejor combinación que permita al usuario tener mayor éxito al apostar. Un ejemplo de dos combinaciones de partidos sería:
- {chi,mia,ny,orl,hou}
- {chi,mem,tor,por,gst}
En las combinaciones anteriores solo se consideran algunos equipos. El Algoritmo Genético busca la mejor combinación entre un conjunto de todos los equipos de la semana.
c. Solución planteada al problema utilizando la técnica de Algoritmos Genéticos. Describe con detalle cada elemento del planteamiento:
i. Codificación del cromosoma.
Cada cromosoma tendrá la siguiente forma:
- {X1,X2,X3,X4,X5}
Cada X representa un equipo diferente que además tiene una probabilidad de ganar una apuesta.
De un ejemplo de un robot al decodificar.
{orl,mia,dal,ny,ind}
Donde las probabilidades de cada uno son {50%,55%,75%,53%,48%}
ii. Función a minimizar o maximizar. ¿Cómo se calcula?
Se calcula con la sumatoria de las probabilidades de cada partido.
iii. Forma de hacer la reproducción.
Se eligen los pares que se van a reproducir al azar.
iv. Forma de hacer el crossover.
Se elige un punto dentro del cromosoma a partir del cual se hará el crossover. La selección del punto es al azar. Por ejemplo {X1,X2,X3 | X4,X5}
v. Forma de hacer la mutación.
La mutación ocurre con un valor de 0.01 y cuando ocurre cambia uno de los valores de un cromosoma por otro valor del conjunto de equipos.
vi. Ejemplo de una generación de 4 elementos en la población.
- {chi,mia,ny,orl,hou}
- {la,okc,tor,por,gst}
- {ind,sac,phi,san,dal}
- {chi,mem,tor,por,gst}
d. Conclusiones después de la programación.
El principal problema que tuvimos durante esta etapa del proyecto es que nuestro problema es muy pequeño y simple para el uso de algoritmos genéticos. Consideramos que el conjunto de datos sobre el cual trabaja el algoritmo es muy pequeño. Sin embargo fue una buena experiencia poner en práctica varios de los conceptos vistos en clase.
Algoritmos Geneticos
Breve descripción del medio ambiente.
En esta etapa de desarrollo, el medio ambiente es un mundo virtual en dos dimensiones, representando una cancha de futbol pero con las porterías en las esquinas. El juego cuenta con dos equipos, Rojos y Azules, ambos controlados por agentes. Cada escenario cuenta con dos bases en los extremos del mismo en donde los personajes podrán anotar puntos.
Descripción detallada de la acción a aprender por el agente.
El problema que se optimiza utilizando la técnica de algoritmos genéticos es la de generar a un equipo que tenga los mejores atributos para jugar contra algún equipo predeterminado, es decir si se juega contra el equipo A el algoritmo determina que jugadores fueron los mejores y al terminar el partido se realiza el algoritmo de forma que para las generaciones futuras sobreviven los que tengan mejor desempeño contra un equipo.
Solución planteada usando Algoritmos Genéticos
Codificación del cromosoma: Cada cromosoma es un jugador de un equipo y tiene la siguiente configuración:
Cromosoma=(Equipo, pelota,compañeros, enemigos, inteligencia, especialización, vision en x, vision en y, vision en z, velocidad).
Un ejemplo de un cromosoma es el siguiente:(equipo rojo, pelota, rojos, azules, tonto, atacar, 10,10,10,3)
Funcion a maximizar:
Número de enemigos que elimina, consideramos que para este problema se puede considerar como un buen jugador al que elimina más jugadores enemigos, debido a que son jugadores que estuvieron participando activamente y que seguramente son los más valiosos, es por eso que los que eliminen más contrarios son los jugadores que se esperaría que sobrevivieran para la siguiente ronda
f(X)= muertes enemigas
Forma de hacer la reproducción:
La función que se define previamente es la que determina como se realiza la reproducción y funciona de la siguiente manera:
Enemigos Matados Probabilidad Esperanza Actual
Jugador 1 4 0.007 0.444 0
Jugador 2 231 0.4261 2.566 3
Jugador 3 7 0.012 0.077 0
Jugador 4 3 0.0055 0.033 0
Jugador 5 103 0.19 1.144 1
Jugador 6 194 0.3579 2.155 2
La reproducción en todas las ocasiones se lleva a cabo de la siguiente forma Jugador 1 y Jugador 6, Jugador 2 y Jugador 5, Jugador 3 y Jugador 4.
Forma de hacer el crossover
El crossover se realiza en los mismos puntos en cada una de las generaciones en los puntos 6 y 4 del cromosoma.
Forma de hacer la mutación:
Se evalúa cada uno de los parámetros del cromosoma y con una probabilidad de 0.1% se modifica de valor, es decir si un jugador tiene un atributo con un determinado valor si es necesario realizar una mutación se tomará el siguiente valor que puede tomar el parámetro, por ejemplo si un jugador tiene como valor en el campo Inteligencia = Tonto, si se realiza una mutación se cambiará por Inteligente.
Ejemplo de una generación de 4 elementos
Jugador 1=(Equipo rojo, Pelota, rojos, azules, tonto, atacar, 10,10,10,3)
Jugador 2=(Equipo rojo, Pelota, rojos, azules, Inteligente, defender 13,13,13,2)
Jugador 3=(Equipo rojo, Pelota, rojos, azules,Atacante,atacar,7,7,7,4)
Jugador 4 =(Equipo rojo, Pelota,rojos,azules,tonto, defender 15,15,15,2)
Conclusiones después de la programación
Al terminar la programación terminamos muy sorprendidos ya que entre más juega el equipo genético contra cualquier otro equipo nos dimos cuenta que se adaptan a las circunstancias y generalmente después de un par de corridas el equipo genético resulta vencedor. por otra parte es interesante ver que si juegan con un equipo completamente diferente tardan un poco en adaptarse por lo que sería recomendable tener un registro de configuraciones exitosas contra algunos equipos.
Video:
Kawabonga! Fase 3
Breve descripción del medio ambiente
Breve descripción del problema de optimización.
Raíz((Rata#1 - Rata#2)2 + (Pillo#1 - Pillo#2)2 + (Vago#1 - Vago#2)2)
Raíz((13 - 5)2 + (2 - 11)2 + (2-5)2)
Raíz(64 + 81 + 9)
Raíz(154)
12.409
1/(1+12.409)
0.07457
Solución planteada al problema utilizando la técnica de Algoritmos Genéticos. Describe con detalle cada elemento del planteamiento.
Codificación del cromosoma.
Función a minimizar o maximizar. ¿Cómo se calcula?
f(x) = Suma(Función de similaridad (Mostrada arriba))
Forma de hacer la reproducción.
Forma de hacer el crossover
Forma de hacer la mutación
Dado p = 0.15 y un número r aleatorio entre 0 y 1, si r <>
Ejemplo de una generación de 4 elementos en la población
para el blog F
Conclusiones después de la programación
El Internet es un sistema global de redes interconectadas que intercambian datos.
El ambiente en particular son los blogs que son web escritas en [x]HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente.
El ambiente en particular son los blogs que son web escritas en [x]HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente.
Breve descripción del problema de optimización.
Se tiene una cantidad M de blogs inedexada.
Se selecciona un blog y se pretende encontrar el número N de blogs más parecidos.
La similaridad f(x) entre dos blogs queda definida de la siguiente manera:
Se selecciona un blog y se pretende encontrar el número N de blogs más parecidos.
La similaridad f(x) entre dos blogs queda definida de la siguiente manera:
| Blog | Rata | Pillo | Vago |
|---|---|---|---|
| Blog #1 | 13 | 2 | 2 |
| Blog #2 | 5 | 11 | 5 |
Se calcula la distancia euclideana de ambos blogs de acuerdo a la cantidad de veces que se repitan las palabras en cada uno de ellos.
Raíz((Rata#1 - Rata#2)2 + (Pillo#1 - Pillo#2)2 + (Vago#1 - Vago#2)2)
Raíz((13 - 5)2 + (2 - 11)2 + (2-5)2)
Raíz(64 + 81 + 9)
Raíz(154)
12.409
Se realiza una conversión del número, utilizando 1/(1+resultado)
1/(1+12.409)
0.07457
Al tener un resultado de 0 a 1, donde 0 significa que dos blogs no tienen nada en común, y 1 significa que dos blogs son idénticos, el propósito es encontrar un numero N de blogs que sean más parecidos un blog en específico.
Solución planteada al problema utilizando la técnica de Algoritmos Genéticos. Describe con detalle cada elemento del planteamiento.
Se elige Nb: El numero de blogs que contiene un individuo, cada individuo puede estar compuesto por dos o más blogs.
Se elige P: El tamaño de la población inicial.
Se selecciona un blog y se pretende encontrar el número N de blogs más parecidos. Donde N tiene que ser igual a Nb x P.
Se elige P: El tamaño de la población inicial.
Se selecciona un blog y se pretende encontrar el número N de blogs más parecidos. Donde N tiene que ser igual a Nb x P.
Codificación del cromosoma.
Un cromosoma o individuo puede estar compuesto por 2 o más blogs. Sea N una población de blogs y X,Y,Z,A,B,C blogs en N.
Algunos ejemplos son:
Algunos ejemplos son:
[X,Y,Z]
[A,B,C]
[X,B,Z]
[C,X,A]
[A,B,C]
[X,B,Z]
[C,X,A]
Función a minimizar o maximizar. ¿Cómo se calcula?
f(x) = Suma(Función de similaridad (Mostrada arriba))
Forma de hacer la reproducción.
Remainder stochastic sampling without replacement
Pselect = f(i)/suma(f)
Expected Count = parte entera de [Pselect*n] + "lanzamientos de monedas" con pesos iguales al residuo de [Pselect*n]
Pselect = f(i)/suma(f)
Expected Count = parte entera de [Pselect*n] + "lanzamientos de monedas" con pesos iguales al residuo de [Pselect*n]
Forma de hacer el crossover
Las parejas son elegidas de forma aleatoria.
El punto de cruce es elegido de forma aleatoria.
El punto de cruce es elegido de forma aleatoria.
Forma de hacer la mutación
Dado p = 0.15 y un número r aleatorio entre 0 y 1, si r <>
Ejemplo de una generación de 4 elementos en la población
para el blog F
| Individuo | f(x) | Pselect | Expected | Blogs to cross | Pair /cross point | New Generation |
| [X,Y,Z] | 1.5 | 0.375 | 0+1 | [X,Y,Z] | 4 / 2 | [X,Y,D] |
| [A,B,C] | 1 | 0.25 | 0+1 | [A,B,C] | 3 / 1 | [A,X,D] |
| [D,B,Z] | .5 | 0.125 | 0+0 | [E,X,D] | 2 / 1 | [E,B,C] |
| [E,X,D] | 2 | 0.5 | 0+2 | [E,X,D] | 1 / 2 | [E,X,Z] |
Conclusiones después de la programación
Después de haberlo programado llegamos a la conclusión de que la "dificultad" del algoritmo no radica en la programación (está parte resultó muy sencilla) sino en todo el proceso de diseño. Definir el problema, el formato del cromosoma, crossover, mutación, etcétera, porque si estos no son correctamente definidos, las soluciones a las que llega son erróneas.
Tuesday, March 3, 2009
Fase 2 - Proyecto
Aqui les dejamos la descripción de neustro proyecto para esta fase.
Breve descripción del medio ambiente.
Para este avance del proyecto, desarrollamos un ambiente representado por una matriz de 10 por 10. En principio está llena de ceros, excepto por la parte donde inician los elementos “nano”. La posición inicial, se encuentra aproximadamente en la mitad de la matriz y los elementos “nano” son representados por unos. Entonces, las figuras están formadas por unos, de acuerdo a los movimientos posibles para los elementos “nano”.
Descripción detallada del problema de optimización.
Lo que el agente en principio debe de optimizarse es la forma en la que se hará la figura. Para esto recorrerá los distintos movimientos posibles para formar una figura. El problema se basa en la mejor forma de hacer la figura establecida a realizar, con la mejor selección de movimientos para poder obtener un patrón optimizado de la figura establecida.
Supongamos que tenemos una figura dada inicial, es decir el cuadro en el centro. Y con respecto a las distintas piezas que se pueden mover a distintos lados. El problema de optimización está representado de la siguiente manera:
Figura inicial:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Figura final:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
Movimiento uno:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Movimiento dos:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
En el ejemplo es visible que el movimiento uno genera una solución más acertada a la solución final, sin embargo eso no dice con claridad si el movimiento uno es mejor al movimiento dos con respecto a la figura final. Por lo que, el problema de optimización radica en la realización de la mejor serie de movimientos que generen mejor la figura objetivo o final.
Solución planteada usando recocido de simulado.
Configuración.
Para la configuración de esta fase del proyecto definimos por cuestiones de programación que el arreglo inicial tendría que tener las coordenadas de la matriz donde se encontraran los elementos en cuestión.
{{3,3}, {3,4}, {3,5},{4,3},{4,4}, {4,5},{5,3}, {5,4}, {5,5}}
Donde el primer elemento de cada subconjunto es la posición en “x” y la segunda en “y”.
Reordenamiento.
El reordenamiento es aleatorio, pero se realiza de acuerdo a la serie de movimientos dados por los distintos átomos o elementos del arreglo. De acuerdo a un número de reglas, los átomos sólo se podrán mover adyacentes entre sí, sin romper la estructura base de la figura.
Función objetivo.
Ya que el objetivo es maximizar la construcción de la figura con los mejores movimientos posibles, la función objetivo está representada con el siguiente código:
int assess(int board[MAXR][MAXC], int solution[MAXR][MAXC]){
int cquads= 0;
for(i = 0; i < MAXR; i++)
for(j = 0; j < MAXC; j++ )
if(board[i][j] && solution[i][j]) cquads++;
return cquads;
}
Donde se evalúan el número de posiciones correctas con respecto a la figura final y se ejecutan evalúan los posibles movimientos para el que genere una mejor aproximación a la figura final.
Calendario de recocido.
Para esta parte la temperatura que se eligió una de 100, para poder ir bajando correctamente la temperatura y encontrar la solución en su punto mínimo.
Ti+1 = α Ti
Conclusiones después de la programación.
Es interesante la forma en la que el recocido da resultados, ya que en nuestro caso evaluó una cantidad impresionante de figuras. Sin embargo, los elementos asertivos dieron señal a lo que sería la mejor solución. La optimización fue evidente, ya que cuando fue bajando la temperatura, dieron resultados bastantes interesante como la solución exacta o a veces aproximada de su referencia final, es decir, la silla.
Breve descripción del medio ambiente.
Para este avance del proyecto, desarrollamos un ambiente representado por una matriz de 10 por 10. En principio está llena de ceros, excepto por la parte donde inician los elementos “nano”. La posición inicial, se encuentra aproximadamente en la mitad de la matriz y los elementos “nano” son representados por unos. Entonces, las figuras están formadas por unos, de acuerdo a los movimientos posibles para los elementos “nano”.
Descripción detallada del problema de optimización.
Lo que el agente en principio debe de optimizarse es la forma en la que se hará la figura. Para esto recorrerá los distintos movimientos posibles para formar una figura. El problema se basa en la mejor forma de hacer la figura establecida a realizar, con la mejor selección de movimientos para poder obtener un patrón optimizado de la figura establecida.
Supongamos que tenemos una figura dada inicial, es decir el cuadro en el centro. Y con respecto a las distintas piezas que se pueden mover a distintos lados. El problema de optimización está representado de la siguiente manera:
Figura inicial:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Figura final:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
Movimiento uno:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Movimiento dos:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
En el ejemplo es visible que el movimiento uno genera una solución más acertada a la solución final, sin embargo eso no dice con claridad si el movimiento uno es mejor al movimiento dos con respecto a la figura final. Por lo que, el problema de optimización radica en la realización de la mejor serie de movimientos que generen mejor la figura objetivo o final.
Solución planteada usando recocido de simulado.
Configuración.
Para la configuración de esta fase del proyecto definimos por cuestiones de programación que el arreglo inicial tendría que tener las coordenadas de la matriz donde se encontraran los elementos en cuestión.
{{3,3}, {3,4}, {3,5},{4,3},{4,4}, {4,5},{5,3}, {5,4}, {5,5}}
Donde el primer elemento de cada subconjunto es la posición en “x” y la segunda en “y”.
Reordenamiento.
El reordenamiento es aleatorio, pero se realiza de acuerdo a la serie de movimientos dados por los distintos átomos o elementos del arreglo. De acuerdo a un número de reglas, los átomos sólo se podrán mover adyacentes entre sí, sin romper la estructura base de la figura.
Función objetivo.
Ya que el objetivo es maximizar la construcción de la figura con los mejores movimientos posibles, la función objetivo está representada con el siguiente código:
int assess(int board[MAXR][MAXC], int solution[MAXR][MAXC]){
int cquads= 0;
for(i = 0; i < MAXR; i++)
for(j = 0; j < MAXC; j++ )
if(board[i][j] && solution[i][j]) cquads++;
return cquads;
}
Donde se evalúan el número de posiciones correctas con respecto a la figura final y se ejecutan evalúan los posibles movimientos para el que genere una mejor aproximación a la figura final.
Calendario de recocido.
Para esta parte la temperatura que se eligió una de 100, para poder ir bajando correctamente la temperatura y encontrar la solución en su punto mínimo.
Ti+1 = α Ti
Conclusiones después de la programación.
Es interesante la forma en la que el recocido da resultados, ya que en nuestro caso evaluó una cantidad impresionante de figuras. Sin embargo, los elementos asertivos dieron señal a lo que sería la mejor solución. La optimización fue evidente, ya que cuando fue bajando la temperatura, dieron resultados bastantes interesante como la solución exacta o a veces aproximada de su referencia final, es decir, la silla.
Friday, February 27, 2009
Recocido Simulado en Webots con Naos
Breve descripción del medio ambiente.
El medio ambiente se desarrolla a partir del simulador 3D Simspark, el cual es el simulador oficial para las competencias dentro de la Robocup Standard League y contiene todas las reglas para oficiales para llevar a cabo partidos de fútbol con los robots bípedos llamados Nao. El simulador contiene diferentes elementos básicos que definen las dimensiones de la cancha, así como la ubicación de las porterías y la pelota. Además incluye a diferentes Naos para ambos equipos y con la posibilidad de especializar sus acciones para que sean porteros, defensas o delanteros. El objetivo final primordial para cada jugador de cada equipo será meter la bola en el arco contrario y así realizar un gol para aumentar en un punto el marcador de su equipo.
Para la realización de la fase 2 del proyecto en la implementación de los algoritmos del recocido simulado y LMS de aprendizaje, hemos utilizado el simulador Webots para Windows, el cual contiene características similares a las del Simspark pero posee una interfaz más útil para el desarrollo de nuestras pruebas.
Descripción detallada del problema de optimización – da al menos un ejemplo en donde se vea por qué es un problema de optimización.
El problema para optimizar radica en que el Nao debe encontrar la distancia más deseable para patear la bola, y que el tiro sea efectivo en cuestiones de velocidad y alcance. La interacción entre el Nao y el ambiente nos regresa distintas percepciones como la distancia del Nao a la bola o el saber si la bola se ha movido, esto nos ayudará a calcular la distancia ideal a patear la cual será la variable que se optimizará.
El algoritmo de optimización nos ayudará a encontrar la distancia ideal, considerando que si el Nao patea y no golpea la bola significará que está muy lejos del balón y se necesitará reducir la distancia para patear, de esta forma la próxima vez que patee tratará de acercarse a la bola y patearla correctamente. Existe un caso en que aumentaría la distancia de la cercanía para patear y este se da cuando el Nao mueve la bola sin haber pateado, en esta situación el algoritmo de optimización aumentará la tendencia para aumentar la cercanía entre el Nao y la bola.
Ejemplo del problema de optimización:
Inicialmente el Nao comenzará con una variable aleatoria que definirá su distancia a patear, supongamos que es una distancia de 0.75.
optBallDist = 0.75
El Nao va a tratar de patear al balón desde la distancia actual, pero el éxito o falla del disparó va a determinar si es que es correcta la distancia y definirá la tendencia del posible próximo valor. En este caso indicamos que el Nao patea en el aire sin pegarle a la bola, por lo tanto la optimización va encaminada a disminuir el rango para patear, obteniendo así valores más cercanos a la bola.
optBallDist = 0.7
En el caso que el Nao empiece a probar con valores muy cercanos a la bola, esta distancia hará que Nao no llegue a patearla y ésta se mueva con su caminado. De esta forma la tendencia de la optimización aumentará el rango de cercanía con la bola para que en los próximos intentos no se acerque tanto.
Supongamos ahora que el Nao aún no encuentra la distancia ideal y sigue pateando en el aire, y en otros casos golpea la bola sin antes patear, esto permitirá que se siga ajustando el valor de la variable a:
optBallDist = 0.3
Nuevamente el Nao va a tratar de buscar la bola y patearla, pero esta vez se acerca y la patea exitosamente, esto significa que nuestro algoritmo encontró el valor óptimo o un valor cercano a lo óptimo para la distancia de pateo.
Solución planteada al problema utilizando el método de recocido simulado. Describe con detalle cada elemento del planteamiento:
Para resolver el problema podemos utilizar el método del recocido simulado ya que el Nao tratará de encontrar un punto de equilibrio o un extremo global en una gráfica de valores, para tomarlo como distancia óptima para patear el balón. El algoritmo planteado define rangos que aumentan o disminuyen el espacio de una variable aleatoria que representa la distancia a optimizarse. Considerando esta variación como un cambio de temperatura, la función objetivo analizará el rendimiento de la variable aleatoria para definir el comportamiento gradual de la temperatura.
1) Configuración
El método de optimización se aplica sobre un programa de simulación que contiene la información y estados necesarios para la utilización de los algoritmos implementados, los cuales para el caso de la fase 2 del proyecto obtenemos como información más relevante la ubicación del robot y la bola en la cancha:
[ (X-nao, Y-nao) , (X-bola, Y-bola) ]
Analizando las diferentes posiciones que nos regresan variables adicionales como la distancia entre el Nao y la bola y llegamos a los 3 posibles estados que utiliza el algoritmo del recocido simulado.
· Si el Nao patea antes de mover a la bola.
· Si el Nao patea la bola.
· Si el Nao no patea y mueve la bola.
2) Reordenamiento
El reordenamiento se aplica de igual forma al programa de simulación a través de reglas claves basadas en la Standard Robocup League. Por motivos de una demostración rápida para la optimización de la distancia a patear hemos obviado algunas reglas que básicamente quitan la acción de los contrincantes para que no interfieran con las acciones de nuestro Nao. Debido a que los algoritmos de búsqueda y caminado para el Nao no están optimizados encontramos además diversas limitaciones en nuestros estados:
· El Nao sigue una secuencia de movimientos al patear: se mueve un poco hacia la derecha, luego avanza unos pasos pequeños y procede a patear.
· El Nao al encontrar la bola tiene que direccionarse frente a la bola y frente al arco en posiciones definidas en el programa de simulación.
· La bola y el Nao interactúan con el ambiente, no permitiendo que excedan los límites de la cancha e impactando con los demás objetos que pueden provocar rebotes o caídas.
3) Función objetivo
La función objetivo de nuestro algoritmo está definida por el éxito de la patada con respecto a la bola, esto nos indica que el Nao ha pateado la bola a la distancia optimizada. El algoritmo reproduce variables aleatorias de distancias a patear, y aunque algunas veces podemos obtener una patada exitosa, el algoritmo de optimización sólo analiza las fallas para así limitar estas futuras posiciones.
F (distancia) -> Analiza si se patea la bola correctamente a la distancia indicada.
Ya en el código podemos ver esta función como:
public void checkBallHit(){
if (isBallMoving() == true && hasKicked == true){
hasShot = true;
System.out.println("NAO HIT THE BALL.");
System.out.println();
CalculateNewPoint();
}
}
4) Calendario de recocido
El recocido y el ajuste de la temperatura se comportan con respecto a los estados actuales que disminuyen la temperatura:
· Si el Nao patea antes de mover a la bola. > Disminuye el límite de espacios superior.
· Si el Nao no patea y mueve la bola. > Aumenta el límite de espacios inferior.
La próxima temperatura se define como:
Ti+1 = α Ti
En dónde α representa la velocidad de cambio de la temperatura, que nuestro programa representa a través del aumento y disminución de los límites superior e inferior.
El código que realiza el cambio de temperatura se define como:
public void AdjustTemperature(){
//Si ha pateado o golpeado la bola revisa que esté quieta.
if (hasShot == true && (isBallMoving() == false)){
hasShot = false;
}
checkBallHit();
checkBallMovedNoShot();
checkShotNoHit();
hasKicked = false;
}
Conclusiones después de la programación
Al desarrollar una aplicación con la teoría analizada en clase encontramos soluciones prácticas que resuelven objetivos claves y en el caso específico de nuestro proyecto: una optimización. El medio ambiente siempre es un problema cuando nos ofrece muchas limitaciones e influye en factores importantes para la implementación de nuestros algoritmos. Es por eso que tuvimos que primero modificar el medio ambiente para que permita una demostración clara de nuestras funciones. Luego, al aplicar las funciones nos dimos cuenta de la utilidad del recocido simulado y entender su objetivo primordial. Esto no hubiera sido tan claro si no lo hubiéramos llevado a una aplicación visual.
Lo interesante y útil fue que aprendimos tanto de la teoría de la inteligencia computacional como del simulador Webots. Esto nos ofrece nuevas ideas para optimizar dentro la simulación y para utilizar lo aprendido y desarrollado en aplicaciones futuras. Webots resultó ser un simulador fácil de entender y programar pero muy poderoso y documentado. Para realizar nuestro proyecto nos basamos para los comportamientos del Nao básico en un archivo que venía incluido en el simulador, estos comportamientos son reactivos y utilizan movimientos lentos que impedían pruebas rápidas, esta fue nuestra mayor limitación.
Recocido Simulado - Oriam y su Huerto de Tomates
Breve descripción del medio ambiente.
En esta etapa de desarrollo, el medio ambiente es un mundo virtual en dos dimensiones, representando una cancha de futbol pero con las porterías en las esquinas. El juego cuenta con dos equipos, Rojos y Azules, ambos controlados por agentes. Cada escenario cuenta con dos bases en los extremos del mismo en donde los personajes podrán anotar puntos.
Descripción detallada de la acción a aprender por el agente.
El problema que se optimiza con este algoritmo es la selección de una mejor ruta, para enviar pases. los pases deben ser lo suficientemente buenos para dejar al equipo en una mejor posición. Se pretende realizar una variación del problema del agente viajero, la única diferencia es que no es necesario pasar por todos los puntos, se tratará de elegir la mejor ruta para llegar a la portería enemiga. De no encontrar una ruta lo suficientemente eficiente el agente que tenga posesión de la pelota permanecerá con ella y no la soltará.
Solución planteada usando Recocido Simulado:
Configuración: Para resolver este problema se plantea utilizar una estructura de datos que almacene una serie de tuplas con diversos elementos que se evaluarán. Una configuración se ve de la siguiente forma:
ruta=[(distancia, costo,parámetros)..........]
Reordenamientos: Se realizarán de forma aleatoria, y se probarán las diferentes posibles rutas para cada configuración de jugadores.
ruta2=[(otraDistancia, otroCosto, otroParametro).....] Función objetivo: El objetivo es minimizar el costo de realizar un pase, por lo tanto mientras más bajo sea el valor de la función objetivo la ruta evaluada será mucho mejor.
f(X)= Costo+distancia+parámetros Aparte de la distancia se evaluarán otros parámetros como si el jugador es visible, alcanzable o está detrás de un objeto, pero al carecer de esos elementos nuestro medio ambiente son despreciados.
Conclusiones después de la programación
Al terminar la programación es interesante ver como los agentes deciden por si mismos si pasar la pelota o seguir con ella, y generalmente toman la decisión correcta, al probar los agentes con poca inteligencia contra los que tienen algoritmos más complejos (Recocido Simulado) se puede ver una diferencia bastante grande ya que tienen mejores estrategias y los partidos terminan con una clara ventaja para los agentes más inteligentes.
En esta etapa de desarrollo, el medio ambiente es un mundo virtual en dos dimensiones, representando una cancha de futbol pero con las porterías en las esquinas. El juego cuenta con dos equipos, Rojos y Azules, ambos controlados por agentes. Cada escenario cuenta con dos bases en los extremos del mismo en donde los personajes podrán anotar puntos.
Descripción detallada de la acción a aprender por el agente.
El problema que se optimiza con este algoritmo es la selección de una mejor ruta, para enviar pases. los pases deben ser lo suficientemente buenos para dejar al equipo en una mejor posición. Se pretende realizar una variación del problema del agente viajero, la única diferencia es que no es necesario pasar por todos los puntos, se tratará de elegir la mejor ruta para llegar a la portería enemiga. De no encontrar una ruta lo suficientemente eficiente el agente que tenga posesión de la pelota permanecerá con ella y no la soltará.
Solución planteada usando Recocido Simulado:
Configuración: Para resolver este problema se plantea utilizar una estructura de datos que almacene una serie de tuplas con diversos elementos que se evaluarán. Una configuración se ve de la siguiente forma:
ruta=[(distancia, costo,parámetros)..........]
Reordenamientos: Se realizarán de forma aleatoria, y se probarán las diferentes posibles rutas para cada configuración de jugadores.
ruta2=[(otraDistancia, otroCosto, otroParametro).....] Función objetivo: El objetivo es minimizar el costo de realizar un pase, por lo tanto mientras más bajo sea el valor de la función objetivo la ruta evaluada será mucho mejor.
f(X)= Costo+distancia+parámetros Aparte de la distancia se evaluarán otros parámetros como si el jugador es visible, alcanzable o está detrás de un objeto, pero al carecer de esos elementos nuestro medio ambiente son despreciados.
Conclusiones después de la programación
Al terminar la programación es interesante ver como los agentes deciden por si mismos si pasar la pelota o seguir con ella, y generalmente toman la decisión correcta, al probar los agentes con poca inteligencia contra los que tienen algoritmos más complejos (Recocido Simulado) se puede ver una diferencia bastante grande ya que tienen mejores estrategias y los partidos terminan con una clara ventaja para los agentes más inteligentes.
Link:
Kawabonga! Parte 2
a. Breve descripción del medio ambiente.
El Internet es un sistema global de redes interconectadas que intercambian datos.
El ambiente en particular son los blogs que son web escritas en (x)HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente.
b. Breve descripción del problema de optimización
Dado un de blog y una cantidad M de blogs que podemos elegir para categorizar, encontrar los N blogs más parecidos al blog dado.
La distancia entre estos dos blogs será calculada como una distancia euclidiana a partir del número de palabras iguales que poseen.
Una vez que se tiene la distancia, la convertimos en un numero entre 0 y 1.
Al tener un resultado de 0 a 1 tenemos que 0 significa que dos blogs no tienen nada en común, y 1 quiere decir que dos blogs son idénticos, por lo que para encontrar los blogs más parecidos tendremos que maximizar el resultado.
c. Solución planteada al problema utilizando el método de recocido simulado.
1. Configuración
Una lista de N Elementos [E1,E2...En]
Cada elemento es una tupla de la forma (calificación, url_del_blog)
2. Re-ordenamientos
Se cambia el elemento con calificación menor por otro blog seleccionado al azar
3. Función objetivo
La función objetivo es la distancia (D)
f(x) = 1/(1+D)
D=Raíz(Suma((palabrai1-palabrai2)^2)) para i=[0,n]
4. Calendario de recocido
Temperatura Inicial = 1.0
Temperatura Final = 0.1x10^-6
Alpha = 0.9999
K = 2 (Número de iteraciones para cada temperatura)
e. Conclusiones después de la programación
Después de haber realizado la programación y haber llevado a cabo algunas corridas de prueba, concluimos que la eficiencia del algoritmo (al ser comparado con otros) depende en gran medida del espacio de búsqueda, ya que para espacios pequeños la implementación de 'brute force' es más sencilla e igual de útil. Sin embargo conforme ampliamos el espacio de búsqueda, las ventajas del recocido simulado se fueron haciendo más visibles.
El Internet es un sistema global de redes interconectadas que intercambian datos.
El ambiente en particular son los blogs que son web escritas en (x)HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente.
b. Breve descripción del problema de optimización
Dado un de blog y una cantidad M de blogs que podemos elegir para categorizar, encontrar los N blogs más parecidos al blog dado.
La distancia entre estos dos blogs será calculada como una distancia euclidiana a partir del número de palabras iguales que poseen.
Una vez que se tiene la distancia, la convertimos en un numero entre 0 y 1.
Al tener un resultado de 0 a 1 tenemos que 0 significa que dos blogs no tienen nada en común, y 1 quiere decir que dos blogs son idénticos, por lo que para encontrar los blogs más parecidos tendremos que maximizar el resultado.
c. Solución planteada al problema utilizando el método de recocido simulado.
1. Configuración
Una lista de N Elementos [E1,E2...En]
Cada elemento es una tupla de la forma (calificación, url_del_blog)
2. Re-ordenamientos
Se cambia el elemento con calificación menor por otro blog seleccionado al azar
3. Función objetivo
La función objetivo es la distancia (D)
f(x) = 1/(1+D)
D=Raíz(Suma((palabrai1-palabrai2)^2)) para i=[0,n]
4. Calendario de recocido
Temperatura Inicial = 1.0
Temperatura Final = 0.1x10^-6
Alpha = 0.9999
K = 2 (Número de iteraciones para cada temperatura)
e. Conclusiones después de la programación
Después de haber realizado la programación y haber llevado a cabo algunas corridas de prueba, concluimos que la eficiencia del algoritmo (al ser comparado con otros) depende en gran medida del espacio de búsqueda, ya que para espacios pequeños la implementación de 'brute force' es más sencilla e igual de útil. Sin embargo conforme ampliamos el espacio de búsqueda, las ventajas del recocido simulado se fueron haciendo más visibles.
Friday, January 30, 2009
Fase 1 - Proyecto
1. Descripción detallada del medio ambiente.
El medio ambiente de nuestro proyecto está definido por el espacio directo donde los cubos o figuras (representando los átomos). Los cubos, tienen movimientos regidos por reglas, y los movimientos son adyacentes a los demás cubos con base en su posición actual. Es importante recalcar que los cubos pueden moverse de manera diferente para generar la figura final. En eso se basa el dilema de nuestro proyecto.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
Con el desarrollo del proyecto aún no se ha determinado el lenguaje y la plataforma en la que se hará. Sin embargo, algunos de nuestras ideas dirigen nuestra atención al lenguaje Java o Phyton.
3. ¿Cuáles problemas de optimización se encuentran en dicho medio?
El problema primordial de optimización se ve reflejado en el menor número de movimientos, dada una figura final, para realizar dicha figura a partir de un estado inicial. Esto se logrará con base en el desarrollo de la figura final
4. ¿Qué conocimiento con incertidumbre necesita ser representado?
El conocimiento con incertidumbre se ve reflejado directamente con el desconocimiento de la ruta o serie de movimientos que se tendrán que realizar para generar la figura final. Así como la incertidumbre de saber si es beneficioso o no, para llegar a la figura final, el movimiento independiente de las figuras.
El medio ambiente de nuestro proyecto está definido por el espacio directo donde los cubos o figuras (representando los átomos). Los cubos, tienen movimientos regidos por reglas, y los movimientos son adyacentes a los demás cubos con base en su posición actual. Es importante recalcar que los cubos pueden moverse de manera diferente para generar la figura final. En eso se basa el dilema de nuestro proyecto.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
Con el desarrollo del proyecto aún no se ha determinado el lenguaje y la plataforma en la que se hará. Sin embargo, algunos de nuestras ideas dirigen nuestra atención al lenguaje Java o Phyton.
3. ¿Cuáles problemas de optimización se encuentran en dicho medio?
El problema primordial de optimización se ve reflejado en el menor número de movimientos, dada una figura final, para realizar dicha figura a partir de un estado inicial. Esto se logrará con base en el desarrollo de la figura final
4. ¿Qué conocimiento con incertidumbre necesita ser representado?
El conocimiento con incertidumbre se ve reflejado directamente con el desconocimiento de la ruta o serie de movimientos que se tendrán que realizar para generar la figura final. Así como la incertidumbre de saber si es beneficioso o no, para llegar a la figura final, el movimiento independiente de las figuras.
Chutas: Proyecto Fase 1
Inteligencia Computacional. ¿Cuáles problemas de optimización se encuentran en dicho medio?
Los Naos al ser robots con mayores grados de libertad, existen múltiples situaciones en dónde físicamente se pueden optimizar sus movimientos. El objetivo inicial de la optimización se va a enfocar al movimiento coordinado de los motores y luego de esto se podrán optimizar lo que serían las jugadas y decisiones las cuales incluirán aspectos de la comunicación y el aprendizaje. A continuación analizamos ciertos problemas de optimización que encontramos en nuestro medio básico y que por el momento es factible su realización:
2. Inteligencia computacional. ¿Qué conocimiento con incertidumbre necesita ser representado?.
Cada robot necesita conocer cómo irá a reaccionar conforme su ambiente se vaya modicando; es decir, los robots no conocen qué podrá suceder al siguiente momento, pero lo que sí saben con certeza es cómo reaccionar a una situación en específico, o a un conjunto de situaciones en común.
Los Naos al ser robots con mayores grados de libertad, existen múltiples situaciones en dónde físicamente se pueden optimizar sus movimientos. El objetivo inicial de la optimización se va a enfocar al movimiento coordinado de los motores y luego de esto se podrán optimizar lo que serían las jugadas y decisiones las cuales incluirán aspectos de la comunicación y el aprendizaje. A continuación analizamos ciertos problemas de optimización que encontramos en nuestro medio básico y que por el momento es factible su realización:
- 1. ) Optimización del caminado del Nao.
- 2. ) Optimización de levantamiento del Nao.
- 3. ) Optimización del tiro del Nao.
2. Inteligencia computacional. ¿Qué conocimiento con incertidumbre necesita ser representado?.
Cada robot necesita conocer cómo irá a reaccionar conforme su ambiente se vaya modicando; es decir, los robots no conocen qué podrá suceder al siguiente momento, pero lo que sí saben con certeza es cómo reaccionar a una situación en específico, o a un conjunto de situaciones en común.
Fase 1 - Proyecto
1. Descripción detallada del medio ambiente.
El medio ambiente de nuestro proyecto está definido por el espacio directo donde los cubos o figuras (representando los átomos). Los cubos, tienen movimientos regidos por reglas, y los movimientos son adyacentes a los demás cubos con base en su posición actual. Es importante recalcar que los cubos pueden moverse de manera diferente para generar la figura final. En eso se basa el dilema de nuestro proyecto.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
Con el desarrollo del proyecto aún no se ha determinado el lenguaje y la plataforma en la que se hará. Sin embargo, algunos de nuestras ideas dirigen nuestra atención al lenguaje Java o Phyton.
3. ¿Cuáles problemas de optimización se encuentran en dicho medio?
El problema primordial de optimización se ve reflejado en el menor número de movimientos, dada una figura final, para realizar dicha figura a partir de un estado inicial. Esto se logrará con base en el desarrollo de la figura final
4. ¿Qué conocimiento con incertidumbre necesita ser representado?
El conocimiento con incertidumbre se ve reflejado directamente con el desconocimiento de la ruta o serie de movimientos que se tendrán que realizar para generar la figura final. Así como la incertidumbre de saber si es beneficioso o no, para llegar a la figura final, el movimiento independiente de las figuras.
Web Crawler + Applicacion Web
Un web crawler es un programa que navega de manera automática y sistemática por las páginas web, con el fin mostrar una relación entre palabras y URLs.
- Descripción detallada del medio ambiente.
El Internet es un sistema global de redes interconectadas que intercambian datos.
El ambiente en particular son lás páginas web escritas en (x)HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente. - Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
Utilizaremos Python para hacer los prototipos del Web Crawler debido a que es un lenguaje que permite representar de manera sencilla los algoritmos además de contar con un gran numero de librerías y herramientas que facilitan la programación, como lo son avanzados profilers y debuggers.
Para la aplicación tenemos pensado utilizar LAMP (Linux, Apache, MySQL y P*) para hacer la aplicación que presentara los resultados y hará las búsquedas en las bases de datos. - ¿Cuáles problemas de optimización se encuentran en dicho medio?
Maximizar la rapidez de la búsqueda de resultados de acuerdo a los criterios establecidos por el usuario. Así como minimizar el número de resultados no útiles presentados. - ¿Qué conocimiento con incertidumbre necesita ser representado?
No sabe realmente a dónde se dirigen los links ni sabe si los links funcionan o seguirán funcionando en el futuro. Además de que no se puede saber si el Web Crawler se quedará ciclado en una cierta zona de la web.
Seleccion medio ambiente - Oriam y su huerto de tomates
1. Descripción detallada del medio ambiente.
El medio ambiente será un mundo virtual en 3D diseñado por nosotros, dentro de un videojuego, el medio ambiente contará con plataformas, desniveles y una topología que será distinta en la mayor parte de sus puntos.
El juego se pretende que tenga equipos, uno será controlado por los usuarios y uno por los agentes que programemos, cada escenario contará con dos bases en los extremos del mismo en donde los personajes podrán anotar puntos.
Finalmente, el medio ambiente contara con lugares que dañaran la vida del jugador, incluso matándolo, por lo que los personajes deberán aprender de su medio. De igual manera habrá lugares inaccesibles para los personajes.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
La plataforma que utilizaremos será la que desarrollemos y utilizaremos el lenguaje de programación C++ con las librerías de OpenGL. Estamos considerando el uso de Python, pero por el momento esa opción queda como tentativa.
3. ¿Cuáles problemas de optimización se encuentran en dicho medio?
El videojuego se enfocará en anotar puntos en cada una de las bases y cuando el rival ( agente) tenga el balón/pelota, puede comunicarse con sus compañeros y planear una ruta eficiente de pases para llegar a la zona de anotación.
4. ¿Qué conocimiento con incertidumbre necesita ser representado?
Por ser un videojuego la incertidumbre siempre estará presente, ya que los agentes no conocen el escenario por lo que conforme lo vayan explorando irán conociéndolo y formando estrategias dependiendo de su experiencia, de igual manera la posición del jugador es cambiante, y tiene que saber en qué lugares puede encontrarse o en donde buscarlo, ya sea para atacarlo o bien alejarse de él.
El medio ambiente será un mundo virtual en 3D diseñado por nosotros, dentro de un videojuego, el medio ambiente contará con plataformas, desniveles y una topología que será distinta en la mayor parte de sus puntos.
El juego se pretende que tenga equipos, uno será controlado por los usuarios y uno por los agentes que programemos, cada escenario contará con dos bases en los extremos del mismo en donde los personajes podrán anotar puntos.
Finalmente, el medio ambiente contara con lugares que dañaran la vida del jugador, incluso matándolo, por lo que los personajes deberán aprender de su medio. De igual manera habrá lugares inaccesibles para los personajes.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
La plataforma que utilizaremos será la que desarrollemos y utilizaremos el lenguaje de programación C++ con las librerías de OpenGL. Estamos considerando el uso de Python, pero por el momento esa opción queda como tentativa.
3. ¿Cuáles problemas de optimización se encuentran en dicho medio?
El videojuego se enfocará en anotar puntos en cada una de las bases y cuando el rival ( agente) tenga el balón/pelota, puede comunicarse con sus compañeros y planear una ruta eficiente de pases para llegar a la zona de anotación.
4. ¿Qué conocimiento con incertidumbre necesita ser representado?
Por ser un videojuego la incertidumbre siempre estará presente, ya que los agentes no conocen el escenario por lo que conforme lo vayan explorando irán conociéndolo y formando estrategias dependiendo de su experiencia, de igual manera la posición del jugador es cambiante, y tiene que saber en qué lugares puede encontrarse o en donde buscarlo, ya sea para atacarlo o bien alejarse de él.
Monday, January 26, 2009
Instrucciones del blog
Este es el blog de Inteligencia Computacional TC3023. El objetivo es que vayan documentando su proyecto final y que vayan compartiendo con sus compañeros su trabajo.
Por favor, cuando suban una actividad, pongan en el titulo el titulo de la actividad y en la etiqueta pongan su numero de equipo y nombre. En este caso, yo estoy poniendo el titulo de "Instrucciones del blog" y la etiqueta "0-Jorge".
Si desean usar más etiquetas para clasificar mejor su contribución, por favor háganlo.
Cualquier pregunta, por favor mándenme un correo electrónico, preguntenme en clase, o simplemente den de alta un post y yo lo contesto.
Gracias.
Por favor, cuando suban una actividad, pongan en el titulo el titulo de la actividad y en la etiqueta pongan su numero de equipo y nombre. En este caso, yo estoy poniendo el titulo de "Instrucciones del blog" y la etiqueta "0-Jorge".
Si desean usar más etiquetas para clasificar mejor su contribución, por favor háganlo.
Cualquier pregunta, por favor mándenme un correo electrónico, preguntenme en clase, o simplemente den de alta un post y yo lo contesto.
Gracias.
Subscribe to:
Comments (Atom)