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
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.