Fase 3 - Algoritmos Genéticos

• 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: