3
$\begingroup$

I can't get my deep genetic algorithm snake game to work and I can't figure out why. At this point, I think it must be either the crossover_rate/mutation_rate or the actual crossover code itself is wrong. I'm hoping someone here can help me with figuring out which.

So, here's my understanding of deep genetic algorithms:

You have a pool of agents. They're randomly generated. You have each of them run, tracking their fitness up until they die. When all agents in the pool are dead, you select some number of the fittest of them.

You then take those models (the parents). You grab two parents and use one of them as the base, swapping in some weight and bias values from the other parent. That's crossover. You then go through those weights and bias values and randomly increase or decrease some of them by just a bit. That's mutation.

As far as I can tell, that understanding is correct. But then again, maybe it isn't. Something is broken here, so maybe I just don't have a clue how a DGA actually works.

But assuming that my understanding is correct, here's my code:

It's initialized with my chosen fitness threshold (a percentage if it's < 1, a number of it's > 1), crossover rate, mutation rate, and the degree to which I mutate a value. It also has a legacy pool where I store the absolute best agents I've ever gotten so I can use them as the parents for the new generation.

(FYI 1: The models are 11 input size, two 128 dense layers, 3 output layer)

(FYI 2: The legacy_pool and new_generation lists are lists of agents where each agent is two item list, with [0] being the model for an agent and [1] being the fitness of the agent)

class GeneticAlgorithm():
    def __init__(self):
        #self.fitness_threshold = 0.10
        self.fitness_threshold = 2
        self.crossover_rate = 0.10
        self.mutation_rate = 0.10
        self.mutation_degree = 0.50

        # Pool of previous parents so we can use the fittest of all time
        self.legacy_pool = None
    

    def _improvement_check(self, new_generation):
        ''' Only allow the parents to be the absolute fittest of all generations. '''
        # For the first time, we just set it to the first generation of parents
        if self.legacy_pool == None:
            self.legacy_pool = new_generation
        # For every other generation, we actually check for improvements
        else:
            # Reverse the lists to increase accuracy
            new_generation.reverse()
            self.legacy_pool.reverse()

            # Check for improvements
            for i in range(len(new_generation)):
                for j in range(len(self.legacy_pool)):
                    if new_generation[i][1] > self.legacy_pool[j][1]:
                        self.legacy_pool[j] = new_generation[i]
                        break # so we only add a new agent once
            
            # Resort the legacy pool
            self.legacy_pool.sort(key=lambda a: a[1], reverse=True)


    def breed_population(self, population):
        '''
        Crossover the weights and biases of the fittest members of the population,
        then randomly mutate weights and biases.
        '''
        # Get the new generation and the number of children each pair needs to have
        new_generation, num_children = population.get_parents(self.fitness_threshold)
        
        # Update the legacy pool of agents to include any members of the new generation
        # that are better than the old generations
        self._improvement_check(new_generation)
        
        # # Get the parent models
        parents = [agent[0] for agent in self.legacy_pool]
        #shuffle(parents) # Shuffle the parents into a random order

        # Initialize children
        children = AgentGA(population.population_size)

        # Crossover and mutate to get the children
        for c in range(num_children):
            for i in range(1, len(parents)-1, 2):
                children.agents[i*c][0] = self.crossover(children.agents[i*c][0], parents[i], parents[i+1])
        return children


    def crossover(self, child, parent_one, parent_two):
        ''' Apply crossover and mutation between two parents in order to get a child. '''
        # Crossover and mutate each layer
        for i in range(len(child.layers)):
            # Get weights and biases of the parents
            # p1 acts as the base for the child
            child_data = parent_one.layers[i].get_weights()
            p2_data = parent_two.layers[i].get_weights()
            
            # Handle the weights
            for x in range(child_data[0].shape[0]):
                for y in range(child_data[0].shape[1]):
                    # Check to see if crossover should occur
                    if (random() < self.crossover_rate):
                        child_data[0][x][y] = p2_data[0][x][y]
                        
                    # Check to see if mutation should occur
                    if (random() < self.mutation_rate):
                        child_data[0][x][y] += child_data[0][x][y] * uniform(-self.mutation_degree, self.mutation_degree)

            # Handle the biases
            for x in range(child_data[1].shape[0]):
                # Check to see if crossover should occur
                if (random() < self.crossover_rate):
                    child_data[1][x] = p2_data[1][x]
                
                # Check to see if mutation should occur
                if (random() < self.mutation_rate):
                    child_data[1][x] += child_data[1][x] * uniform(-self.mutation_degree, self.mutation_degree)

            # Set weights and biases in child
            child.layers[i].build(input_shape=child_data[0].shape[0])
            child.layers[i].set_weights(child_data)
        return child
```
$\endgroup$

2 Answers 2

3
$\begingroup$

You have many 1000s of neural network parameters that need to be set up correctly to generate a policy function for your game. In addition, many of the parameters are co-dependent - a "good" set of weights for one neuron in layer 1 will not be effective unless weights in layer 2 make use of it correctly - so cannot be searched and optimised independently.

This is much too hard a search problem for a basic GA to optimise.

Simple policy functions built out of neural networks can be found using GAs, but you have to radically change the architecture compared to deep learning. A well-established GA/NN combination that should work for your problem is NEAT. There are a few Python implementations, including neat-python.

NEAT does things differently to the approach you have tried. Key differences are:

  • The neural networks have far fewer neurons and weights. This is usually OK for simple control systems. It may not work so well if you wanted the policy function to be driven from screenshots of the game (if that is your eventual goal, I recommend investigating reinforcement learning and algorithms like DQN which have been demonstrated to solve these kinds of problem).

  • The NEAT algorithm makes and tracks "innovations" to neural network architecture (e.g. adding new neurons and links between them), so that it can perform crossover and mutation whilst respecting the co-dependent nature of weights in the NN.

If you don't want to try NEAT, you could try heavily simplifying your 3-layer network. Probably just 10 neurons per hidden layer will be enough for the policy function, and would reduce the size of search space by a few orders of magnitude. Also if your mutation rate is evaluated per weight, you will probably want it to be lower, e.g. 0.01 instead of 0.10 - too many mutations will swamp any forward progress made from selection with random behaviour and cause performance to plateau.

$\endgroup$
2
$\begingroup$

this algorythm is not the best for solving a Snake Game (best proven are RLs), however, I think this can actually work if your model is well built.

As far I understand, your knowledge about DGA is correct.

Maybe the error is in the way you select the best parents for each epoch, you must choose the best agents for breeding. How do you choose the best agents for breeding? The best solution would be choose those who can reach the destination point. Maybe none of them can reach such point, so the problem is: which one did better? I would code it as the one who can reach closer to the destination point.

In case you are not choosing the best parents for breeding, your algorythm will not converge to any better solution. In case you are doing right, try to generate different hidden layer shapes for each agent and use it as a new parameter to crossover and mutation, this should work better than a fixed shape for all agents.

I hope this to be useful!

$\endgroup$
7
  • $\begingroup$ I already have a deep q learning set-up figured out for snake, so I wanted to move on to a deep genetic algorithm. As for my fitness, I increase it by 1 when they get a food and by 0.001 when they move closer to the food and -0.001 when they move further from the food. Since I really want them to actually be getting the food, not just moving near it. $\endgroup$ May 3, 2022 at 13:37
  • $\begingroup$ How do you perform crossover with different layer shapes? $\endgroup$ May 3, 2022 at 13:37
  • $\begingroup$ I would try to measure the distance between the food and the snake as the error of the network, as you can get closer but how closer is important. To crossover the shape, you can inherit a base shape from the parents and add or substract a new neuron for each layer with certain probability (you can define it) and other probability for adding or removing a layer. You can start fixing a number of layers and adding/substracting neurons in the mutation step. $\endgroup$
    – Alverciito
    May 4, 2022 at 9:33
  • $\begingroup$ Does it get the food at any point? If it does not take the food, it is probably the fitness function. $\endgroup$
    – Alverciito
    May 4, 2022 at 9:41
  • $\begingroup$ I does get the food. Some lucky little snakes are even born with the ability to outright get 6 food in a row. (It blows my mind every time I see a randomly generated snake act like it's gone through training.) $\endgroup$ May 5, 2022 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.