Actividad de Programación 3 – Algoritmos Genéticos

1)      a. Breve descripción del medio ambiente.

                Un triangulo formado por números aleatorios. Cada nivel tiene uno más que el anterior. Iniciando de la punta de la pirámide y eligiendo un camino hacia abajo pasando por cualquiera de los dos números inmediatos inferiores hasta llegar al último nivel (la base del triangulo).

2)       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 consiste en obtener las suma máxima al recorrer el triangulo hacia abajo.

Ej.1)

59

73 41

52 40 09

26 53 06 34

10 51 87 86 81

61 95 66 57 25 68

369

1)      c. Solución planteada al problema utilizando la técnica de Algoritmos Genéticos. Describe con detalle cada elemento del planteamiento:

·         Codificación del cromosoma. De un ejemplo de un patrón al decodificarlo.

o   Las direcciones tomadas al recorrer el triangulo en un arreglo que indica en cada nivel si se fue a la derecha o a la izquierda.

[IDIDD]

·         Función a minimizar o maximizar. ¿Cómo se calcula?

o   La suma de todos los números en el camino es la función a maximizar.

·         Forma de hacer la reproducción – ejemplo utilizando tu codificación.

o   La reproducción la hacemos utilizando el “Residuo de muestreo estocástico sin reemplazo”. Es decir que la parte entera indica el numero de muestras de esos individuos y la parte fraccional son probabilidades para elegir a los individuos restantes.

Antes	Expected Value
[IDDDI]	1.203
[DIDDI]	1.760
[IIDDI]	0.890
[DDDDD]	0.256

Después

[IDDDI]

[DIDDI]

[IIDDI]

[DIDDI]

·         Forma de hacer el crossover – ejemplo utilizando tu codificación.

o   Se elige una pareja al azar y luego se elige un lugar de cruzamiento para ambos. Luego se intercambian los cromosomas a partir de ese lugar hasta el final.

[IDD|DD]

[DDDIDI]

[IDDDI]

[DDDDD]

·         Forma de hacer la mutación – ejemplo utilizando tu codificación.

o   La mutación es simplemente la posibilidad de que al ocurrir el cruzamiento cambien 0 o más valores de todo el cromosoma. La probabilidad de la mutación es de 5/1000.

Antes del cruzamiento: [IDDDD]

Después del cruzamiento: [IDDII]

1)    vi.   Ejemplo de una generación de 4 elementos en la población. 

      El Triangulo inicial 

59

73 41

52 40 09

26 53 06 34

10 51 87 86 81

61 95 66 57 25 68

a.       Población inicial.

	Fitness	Probability	Expected
[IIDDI]	390	0.3	1.2
[DDIDD]	226	0.174	0.696
[IIIID]	315	0.242	0.968
[IDIDD]	369	0.284	1.136
Total	1300	1	4

b.      Población seleccionada para la reproducción.

[IIDDI]

[IDIDD]

[IIIID]

[IIIID]

c.       Población después del cruzamiento.

[IIDID]

[IDIID]

[IIIDD]

[IIIDI]

d.      Población después de la mutación.

	Fitness	Probability	Expected
[DIDID]	290	0.233	0.932
[IDIID]	342	0.275	1.100
[DIDDD]	257	0.206	0.824
[IIIDI]	356	0.286	1.164
Total	1245	1	4

 d.      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.

Elemento mayor: [IIIDI] 356

Elemento menor: [DIDDD] 257

Numero de mutaciones: 3

Numero de cruzamientos: 5

e. Video

 

1)      f. Conclusiones  

La programación del algoritmo genético fue en esencia sencilla y los resultados muy buenos. Se pudo observar que este tipo de algoritmos para la resolución de problemas son bastante rápidos. Pero para su buen uso se tienen que seleccionar problemas adecuados.

Equipo 2: Proyecto: Parte 3: Algoritmos genéticos: El Post

a. Breve descripción del medio ambiente.

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.

Descripción del medio ambiente

Cada partida de StarCraft se realiza en un mapa que el usuario escoge. Dicho mapa varía a otros en dimensiones, recursos disponibles, ubicación de los recursos y topología. Al comienzo de cada partida, el jugador no tiene información sobre el mapa. El jugador tiene un rango de visión el cual determina que tanto puede ver del mapa respecto a cierta posición. Una vez que el jugador ha pasado por un punto en el mapa, todo lo descubra permanecerá visible hasta el fin del partida.

En StarCraft las unidades de ataque serán mucho más efectivas si se mantienen siempre juntas. En el calor de una batalla, mientras las unidades se van perdiendo, las que quedan se encontrarán dispersas en el mapa, siendo más vulnerables a ataques del enemigo. Determinar a dónde deben moverse para así poder reunirse en el menor tiempo posible es un problema de optimización, el cual se puede resolver usando Algoritmos Genéticos.

Algoritmos Genéticos

El objetivo del algoritmo es encontrar un punto equidistante a todas las unidades en el mapa y que éstas se aproximen en el menor tiempo posible.

Codificación del cromosoma

La posición de una unidad en StarCraft está determinada por una tupla, con valores “x” y “y”. Es así como cada unidad puede ser representada simplemente por esta información:

    String binario                                              Valor en “x”                Valor en “y”

(010110, 100111)                                                   22                                39

Función a minimizar

Queremos minimizar la distancia entre todas las unidades en el mapa. Un punto equidistante a todas las unidades se encontrará como:

X=    para las coordenadas en “x”

Y=   para las coordenadas en “y”

La función que deseamos minimizar es la distancia de cada unidad a este punto, la cual está dada por:

Distancia=

donde  es el punto equidistante a las unidades y  son las coordenadas de cada unidad. Como deseamos minimizar esta función, invertimos el valor de la distancia: Fitness=1/Distancia.

Reproducción

Se utiliza el fitness de cada individuo para determinar cuántas veces se utilizara ese cromosoma para el cruzamiento: Actual Count=

    String binario          Valor en “x” Valor en “y” Fitness [punto (16, 10)] Actual count

(010110, 100111)              22                  39      1/29.61=0.0337         0.0337/0.0249=1

(111010, 010101)              58                  21      1/43.41=0.0230         0.0230/0.0249=1

(111101, 011011)              61                  27      1/48.10=0.0207         0.0207/0.0249=1

(000101, 110101)               5                   53      1/44.38=0.0222         0.0222/0.0249=1

Crossover

Se seleccionan dos padres y se combinan sus bits por la mitad en cada componente.

Pto. De cruzamiento                                    Nueva población

(010|110, 100|111)                                    (010010, 100101)

(111|010, 010|101)                                    (111010, 010111)    

Mutación

Con una probabilidad de 1/100 en cada componente, se altera en un bit cada uno.

Mutación  en “x”                                           Nueva población

(010010, 100101)                                        (110010, 100101)

Ejemplo

Generación 1 – Población Inicial

    String binario          Valor en “x”                Valor en “y”            Fitness [punto (16, 10)]         Actual count

(010110, 100111)              22                                39                 1/29.61=0.0337            0.0337/0.0249=1

(111010, 010101)              58                                21                 1/43.41=0.0230            0.0230/0.0249=1

(111101, 011011)              61                                27                 1/48.10=0.0207            0.0207/0.0249=1

(000101, 110101)               5                                 53                 1/44.38=0.0222            0.0222/0.0249=1

AvgF =0.0249

MaxF=0.0337      (22,39)

MinF=0.0207       (61,27)

      CrossOver                  Mate                        Nueva población           Mutación

(010110, 100111)              2                            (010010, 100101)                 -

(111010, 010101)              1                                 (111110, 010111)            -

(111101, 011011)              4                                 (111101, 011101)            -

(000101, 110101)              3                                 (000101, 110011)            -

Generación 2

    String binario          Valor en “x”                Valor en “y”            Fitness [punto (16, 10)]         Actual count

(010010, 100101)              18                                37                 1/27.07=0.0337            0.0336/0.0246=1

(111110, 010111)              62                                23                 1/47.80=0.0209            0.0209/0.0246=1

(111101, 011101)              61                                29                 1/48.84=0.0204            0.0204/0.0246=1

(000101, 110011)               5                                 51                 1/42.44=0.0235            0.0235/0.0246=1

AvgF =0.0246

MaxF=0.0337      (18,37)

MinF=0.0204       (61,29)

      CrossOver                  Mate                        Nueva población           Mutación

(010110, 100111)              4                            (010101, 100101)                 -

(111010, 010101)              3                                 (111101, 010011)            y (111101, 000011)

(111101, 011011)              1                                 (111110, 011111)            -

(000101, 110101)              2                                 (000010, 110101)            -

Generación 3

    String binario          Valor en “x”                Valor en “y”            Fitness [punto (16, 10)]         Actual count

(010101, 100101)              21                                37                 1/27.45=0.0364            0.0334/0.0255=1

(111101, 000011)              61                                 3                  1/45.41=0.0219            0.0219/0.0255=1

(111110, 011111)              62                                31                 1/46.04=0.0217            0.0217/0.0255=1

(000010, 110101)               2                                 53                 1/45.22=0.0221            0.0211/0.0255=1

AvgF =0.0255

MaxF=0.0364      (21,37)

MinF=0.0217       (62,31)

      CrossOver                  Mate                        Nueva población           Mutación

(010110, 100111)              2                            (010010, 100010)                 -

(111010, 010101)              4                                 (111101, 010101)            -                 

(111101, 011011)              1                                 (111010, 011111)            -

(000101, 110101)              3                                 (000101, 110011)            -

Generación 4

    String binario          Valor en “x”                Valor en “y”            Fitness [punto (16, 10)]         Actual count

(010010, 100010)              17                                34                 1/24.02=0.0416            0.0416/0.0263=2

(111101, 010101)              61                                 3                  1/45.54=0.0219            0.0219/0.0263=1

(111010, 011111)              62                                31                 1/50.56=0.0197            0.0197/0.0263=0

(000101, 110011)               2                                 53                 1/45.22=0.0221            0.0211/0.0263=1

AvgF =0.0263

MaxF=0.0416      (17,34)

MinF=0.0197       (62,31)

      CrossOver                  Mate                        Nueva población           Mutación

(010110, 100111)              3                            (010101, 100101)                 x (011101, 100101)

(010110, 100111)              4                                 (010101, 100011)            -                 

(111101, 010101)              2                                 (111110, 010111)            -

(000101, 110011)              1                                 (000110, 110111)            x (000111, 110111)

Conclusiones

Utilizar algoritmos genéticos para minimizar una función lineal no es eficiente, por lo cual este sólo fue en ejercicio para poner en práctica el algoritmo. En StarCraft se presentaron algunas dificultades debido a la inconsistencia de los mapas pero gracias a la función de movimiento que tiene implementada, no causo grandes estragos a nuestro proyecto.

Datos sobre la corrida:
Inicio
Poblacion: 4 Marines
AvgF=658521875
MaxF=2069547693
MinF=26431527


Mitad

AvgF=694636307

MaxF=452599107

MinF=204209326

Final

AvgF=705757887

MaxF=1412658053

MinF=1358270953

# de cruzamientos: 620
# de mutaciones: 1