La población de nuestro algoritmo consiste en cañones acomodados en círculo apuntando hacia el centro. El algoritmo busca una combinación de ángulo/velocidad que le permita al cañón disparar un proyectil que pase lo más cerca posible de un objetivo ubicado en el centro del círculo. La altura del objetivo, la distancia a la que se encuentran los cañones y la gravedad del medio ambiente son seleccionados al azar al momento de crear el mundo. El objetivo puede moverse durante la simulación para observar la forma en la que se adapta la población a la nueva situación.
La interfaz tridimensional despliega los cañones, los ángulos a lo que apuntan, el objetivo flotante y las trayectorias de los proyectiles. Las trayectorias de los proyectiles disparados por los cañones con el 'fitness' más alto (aquellas que pasan más cerca del objetivo) se despliegan de color rojo, el resto se despliegan de color blanco.
b. Descripción detallada del problema de optimización.
El objetivo de la simulación es que un proyectil disparado desde un cañón pase lo más cerca posible de un blanco flotante. Los proyectiles son afectados por la gravedad del medio ambiente, llegando a una altura máxima. Se busca optimizar la diferencia de alturas entre el blanco y el proyectil cuando pasa por el centro, modificando el ángulo y la velocidad de disparo de los cañones.
c. Solución planteada al problema utilizando la técnica de Algoritmos Genéticos:
i. Codificación del cromosoma.
Los cromosomas constan de 32 bits:
[0, 16) -> Ángulo de disparo.
[16, 32) -> Velocidad de disparo.
Las secuencias binarias representan cantidades decimales con el punto ubicado a la mitad.
Para obtener el valor se suman los bits en binario, por ejemplo:
[00010011.10110100, 01001011.01010111]
Ángulo = 19.703125 Velocidad = 75.33984375
ii. Función a minimizar o maximizar.
La función objetivo es:
f(x) = 1 / (error + 1)
En donde el error corresponde a la diferencia de alturas entre el blanco y el proyectil al pasar por el centro.
iii. Forma de hacer la reproducción.
La forma que usamos para hacer la reproducción es muestreo estocástico con reemplazo (selección normal).
iv. Forma de hacer el 'crossover'.
Para realizar el 'crossover', se selecciona aleatoriamente una posición en el cromosoma y se combinan los segmentos para generar la nueva población. Por ejemplo:
A = [00010|011.10110100, 01001011.01010011]
B = [10110|110.01001011, 01010010.01010111]
A' = [00010|110.01001011, 01010010.01010111]
B' = [10110|011.10110100, 01001011.01010011]
v. Forma de hacer la mutación.
Para la mutación se cambia cada bit con una probabilidad de 1/100. Por, ejemplo:
A' = [00010110.01001011, 01010010.01010111]
A'' = [00010110.01001011, 01010010.01010111]
d. Ejemplo de una generación de 4 elementos en la población:
i. Población inicial.
[10011110100110011100010011101110] error: 175.728 f: 0.006 ps: 0.096
[01110101101000111011110100011010] error: 79.745 f: 0.012 ps: 0.210
[11001011101001000100100010111000] error: 106.241 f: 0.009 ps: 0.158
[10000110001010010111101111011001] error: 30.714 f: 0.032 ps: 0.535
ii. Población seleccionada para la reproducción.
[10000110001010010111101111011001] error: 30.714 f: 0.032 ps: 0.535
[10000110001010010111101111011001] error: 30.714 f: 0.032 ps: 0.535
[10000110001010010111101111011001] error: 30.714 f: 0.032 ps: 0.535
[01110101101000111011110100011010] error: 79.745 f: 0.012 ps: 0.210
iii. Población después del cruzamiento.
[11000110001010010111101111011001] error: 109.215 f: 0.009 ps: 0.083
[10000110001010010111101111011001] error: 30.714 f: 0.032 ps: 0.288
[01110100001010010111101111011001] error: 88.906 f: 0.011 ps: 0.102
[10000111101000111011110100011010] error: 16.346 f: 0.058 ps: 0.527
iv. Población después de la mutación.
[11000110001010010101101111011001] error: 109.215 f: 0.009 ps: 0.083
[10000110001010010111101111011001] error: 30.714 f: 0.032 ps: 0.288
[01110100101010010111101111011001] error: 88.906 f: 0.011 ps: 0.102
[10000111101000111011110100011010] error: 16.346 f: 0.058 ps: 0.527
v. Estadísticas del promedio de la población, elemento mayor (cantidad y fitness), elemento menor (cantidad y fitness), número de veces que se realizó una mutación y un cruzamiento.
Generación 1:
Peor: [10011110100110011100010011101110] error: 175.728 f: 0.006 ps: 0.096
Mejor: [10000110001010010111101111011001] error: 30.714 f: 0.032 ps: 0.535
Fitness sum: 0.059
Avg. fitness: 0.015
Cantidad de mutaciones: 2
Generación 2:
Peor: [11000110001010010111101111011001] error: 109.215 f: 0.009 ps: 0.083
Mejor: [10000111101000111011110100011010] error: 16.346 f: 0.058 ps: 0.527
Fitness sum: 0.168
Avg. fitness: 0.042
e. Video
f. Conclusiones:
Implementar una solución usando algoritmos genéticos a un problema nos permitió darnos cuenta de la forma en la que estos algoritmos pueden ser usados para solucionar problemas. La implementación del algoritmo es bastante simple pero esto no afecta su efectividad al resolver el problema que planteamos para esta sección de nuestro proyecto.
El agregar una parte interactiva al programa también nos mostró que es posible usar el algoritmo para aplicaciones interactivas ya que, aunque fue implementado en un lenguaje de 'scripting' que realiza miles de operaciones por cuadro, esto no afecta drásticamente el desempeño de la aplicación.
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.