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