hacer - codigo fuente de un algoritmo genetico python

Algoritmo genético/w Red neuronal tocando serpiente no está mejorando

Question

Estoy intentando crear un algoritmo genético para entrenar una red neuronal, con el objetivo de jugar al juego serpiente.

El problema que tengo es que el estado físico de las generaciones no está mejorando, o bien se queda quieto en el estado físico que uno podría esperar de no aportar nada al juego, o solo empeora después de la primera generación. Sospecho que se trata de un problema con la red neuronal, sin embargo, no sé qué es.

Configuración de red neuronal

24 nodos de entrada

2 capas ocultas

8 nodos por capa

4 nodos de salida (uno para cada dirección que puede tomar la serpiente)

La entrada es una matriz de cada dirección que la serpiente puede ver. Para cada dirección verifica la distancia a una pared, una fruta o a sí misma. El resultado final es una matriz con una longitud de 3*8 = 24 .

Los pesos y sesgos son flotantes aleatorios entre -1 y 1, que se generan cuando se crea la red.

Configuración del algoritmo genético

Tamaño de la población: 50000

Padres elegidos por generación: 1000

Manténgase arriba por generación: 25000 (Nueva variable, viendo mejores resultados)

Posibilidad de mutación por niño: 5%

(He intentado diferentes proporciones de tamaño, aunque todavía no estoy seguro de cuál es una proporción típica).

Estoy usando un punto de cruce. Cada conjunto de pesos y sesgos se cruza entre los padres y se transmite a los niños (un niño por cada "versión" del cruce).

Estoy usando lo que creo que es la selección de la ruleta para seleccionar a los padres, publicaré el método exacto a continuación.

La condición física de una serpiente se calcula con: age * 2**score (no más, más información en actualización), donde la edad es el número de turnos que sobrevivió la serpiente y la puntuación es la cantidad de frutas que recolectó.

Detalles

Aquí hay algunos pseudocódigos para tratar de resumir cómo funciona (debería) mi algoritmo genético:

pop = Population(size=1000)
while True: # Have yet to implement a ''converged'' check
pop.calc_fitness()
new_pop = []
for i in range(n_parents):
parent1 = pop.fitness_based_selection()
parent2 = pop.fitness_based_selection()
child_snake1, child_snake2 = parent1.crossover(parent2)
if rand() <= mutate_chance:
child_snake.mutate()
new_pop.append(child_snake1, child_snake2)
pop.population = new_pop
print(generation_statistics)
gen += 1

Aquí está el método que utilizo para seleccionar un padre:

def fitness_based_selection(self):
"""
A slection process that chooses a snake, where a snake with a higher fitness has a higher chance of being
selected
:return: The chosen snake''s brain
"""
sum_fitnesses = sum(list([snake[1] for snake in self.population]))
# A random cutoff digit.
r = randint(0, sum_fitnesses)
current_sum = 0
for snake in self.population:
current_sum += snake[1]
if current_sum > r:
# Return brain of chosen snake
return snake[0]

Vale la pena señalar que la self.population es una lista de serpientes, donde cada serpiente es una lista que contiene la NeuralNet que la controla y la aptitud que la red logró.

Y aquí está el método para obtener una salida de una red de una salida del juego, ya que sospecho que hay algo que estoy haciendo mal aquí:

def get_output(self, input_array: np.ndarray):
"""
Get output from input by feed forwarding it through the network
:param input_array: The input to get an output from, should be an array of the inputs
:return: an output array with 4 values of the shape 1x4
"""
# Add biases then multiply by weights, input => h_layer_1, this is done opposite because the input can be zero
h_layer_1_b = input_array + self.biases_input_hidden1
h_layer_1_w = np.dot(h_layer_1_b, self.weights_input_hidden1)
h_layer_1 = self.sigmoid(h_layer_1_w) # Run the output through a sigmoid function
# Multiply by weights then add biases, h_layer_1 => h_layer_2
h_layer_2_w = np.dot(h_layer_1, self.weights_hidden1_hidden2)
h_layer_2_b = h_layer_2_w + self.biases_hidden1_hidden2
h_layer_2 = self.sigmoid(h_layer_2_b)
# Multiply by weights then add biases, h_layer_2 => output
output_w = np.dot(h_layer_2, self.weights_hidden2_output)
output_b = output_w + self.biases_hidden2_output
output = self.sigmoid(output_b)
return output

Cuando se ejecuta la red neuronal manualmente, con una versión gráfica del juego habilitada, queda claro que la red casi nunca cambia de dirección más de una vez. Esto me confunde, ya que tenía la impresión de que si todos los pesos y sesgos se generan de forma aleatoria, la entrada se procesaría de forma aleatoria y daría una salida aleatoria, en cambio, la salida parece cambiar una vez en el primer turno del juego, nunca cambia significativamente de nuevo.

Cuando se ejecuta el algoritmo genético, la aptitud más alta de cada generación casi nunca supera la aptitud que uno esperaría de una serpiente sin entrada (en este caso 16), que supongo que está relacionada con el problema con la red neuronal. Cuando se exceda, las próximas generaciones volverán a 16 nuevamente.

Cualquier ayuda con su problema sería apreciada inmensamente, todavía soy nuevo en esta área, y lo encuentro realmente interesante. Con mucho gusto responderé más detalles si es necesario. Mi código completo se puede encontrar here , si alguien se atreve a profundizar en eso.

Actualizar:

Cambié un par de cosas:

• Se corrigió la generación peso / sesgo, anteriormente solo generaban entre 0 y 1.
• Edité mi método cruzado para devolver dos hijos por grupo de padres en lugar de solo uno.
• Se cambió la función de aptitud para que sea igual a la edad de la serpiente (para propósitos de prueba)
• Se modificaron las variables de población.

Ahora el algoritmo se desempeña mejor, la primera generación generalmente encuentra una serpiente con una condición física de 14-16, lo que significa que la serpiente se da vuelta para evitar la muerte, sin embargo, casi siempre solo va cuesta abajo desde allí. La primera serpiente en realidad habrá logrado una táctica de giro cuando esté cerca de los bordes este y norte / sur, pero nunca del borde oeste. Después de la primera generación, la condición física tiende a empeorar, y eventualmente vuelve a la condición física más baja posible. Estoy en una pérdida por lo que está mal, pero tengo la sensación de que podría ser algo grande que he pasado por alto.

Actualización # 2:

Pensé que también podría mencionar algunas cosas que probé que no funcionaron:

• Cambió los nodos por capa oculta de 8 a 16, lo que hizo que las serpientes tuvieran un rendimiento significativamente peor.
• Permitió que la serpiente se volviera a sí misma, esto también hizo que las serpientes tuvieran un desempeño peor.
• Grandes (creo que son grandes, no estoy seguro de cuál es el tamaño de un pop estándar). El tamaño de la población es de ~ 1 000 000, con ~ 1000 padres, sin cambios positivos.
• 16 o 32 nodos por capa oculta, aparentemente tuvieron poco o ningún impacto.
• Se corrigió la función de mutación para asignar correctamente valores entre -1 y 1, sin impacto notable.

Actualización # 3:

Cambié un par de cosas y comencé a ver mejores resultados. En primer lugar, evité el desove de las frutas para simplificar el proceso de aprendizaje, y en su lugar les di a las serpientes una condición física que era igual a su edad (cuántos giros / cuadros sobrevivieron), y después de desactivar la normalización de la matriz de entrada obtuve una serpiente con una Fitness de 300! 300 es la edad máxima que una serpiente puede tener antes de morir de vejez.

Sin embargo, el problema sigue existiendo, ya que después de las primeras dos generaciones la condición física caerá en picado, las primeras 1 a 5 generaciones pueden tener una capacidad física de 300 (a veces no lo hacen, y en cambio tienen una condición física baja, pero supongo que esto no funciona). al tamaño de la población.), pero después de eso, la condición física de las generaciones caerá a ~ 20-30 y se mantendrá allí.

Además, si vuelvo a encender las frutas, las serpientes vuelven a tener una forma física abismal. A veces, la primera generación logrará una serpiente capaz de moverse en bucles y, por lo tanto, obtener una condición física de 300 sin recoger ninguna fruta, pero esto casi nunca se transfiere a la siguiente. Generacion.

Answer 1

Noté que en su pseudocódigo, al crear cada nueva generación, la generación principal se elimina completamente y solo se retiene la generación secundaria. Esto, naturalmente, puede llevar a reducir los niveles de condición física, ya que no hay nada que garantice que la descendencia tendrá niveles de condición física comparables a los de la generación de padres. Para asegurarse de que los niveles de condición física no disminuyan, debe combinar las generaciones padre e hijo y podar a los miembros más débiles (lo que recomendaría), o puede exigir que la función de generación de descendencia produzca descendencia al menos como corresponda. Como los padres (por muchas pruebas y errores).

Si decide enfocarse en el generador de descendencia, una manera de (de alguna manera) garantizar la mejora de la descendencia es implementar la reproducción asexual simplemente agregando una pequeña cantidad de ruido a cada vector de peso. Si el nivel de ruido es lo suficientemente pequeño, puede generar una descendencia mejorada con una tasa de éxito de hasta el 50%. Sin embargo, los mayores niveles de ruido permiten una mejora más rápida y ayudan a saltar fuera de los óptimos locales, incluso si tienen tasas de éxito inferiores al 50%.

Answer 2

Solo está mutando el 5% de la población, no el 5% del "genoma". Esto significa que su población se solucionará de manera increíblemente rápida ( https://en.wikipedia.org/wiki/Fixation_(population_genetics) .

Esto tiene sentido porque a la población no le está yendo muy bien, porque solo está explorando un área muy pequeña del paisaje físico ( https://en.wikipedia.org/wiki/Fitness_landscape ).

Debe cambiar la función de mutación para mutar el 5% del genoma (es decir, ponderaciones entre nodos). Siéntase libre de jugar también con la tasa de mutación: diferentes problemas funcionan mejor a diferentes tasas de mutación.

Si está preocupado por perder el "mejor genoma" actual, un enfoque típico en la computación evolutiva es copiar al individuo con la aptitud más alta a la siguiente generación sin mutación.

(Lo sentimos, probablemente debería haber sido un comentario pero no tengo suficiente reputación).