What is the problem in this genetic algorithm?

Question

I recently started learning AI and i watched this video of Code Bullet, presenting a very simple genetic algorithm of a simple game where dots need to reach to a goal. I wanted to recreate this game in python using pygame. Since it didn't work at all, I tried redesigning it a bit.

Here is the code:

import pygame as pg
from DotGame.DotGameFunctions import *
import random as r
import time

pg.init()
WIN_WIDTH = 500
WIN_HEIGHT = 500

win = pg.display.set_mode((WIN_WIDTH, WIN_HEIGHT))
pg.display.set_caption('DotGame')

SPAWN = Vector2(WIN_WIDTH / 2, WIN_HEIGHT - 40)
GOAL = Vector2(WIN_WIDTH / 2, 10)


class Dot:
    def __init__(self, pos: Vector2):
        self.pos = pos
        self.dead = False
        self.reachedGoal = False
        self.is_best = False
        self.fitness = 0

        self.brain = Brain(1000)
        self.vel = Vector2()

    def move(self):
        if self.brain.step < len(self.brain.directions):
            self.vel = self.brain.directions[self.brain.step]
            self.brain.step += 1
        else:
            self.dead = True

        self.pos = self.pos + self.vel

    def update(self):
        if not self.dead and not self.reachedGoal:
            self.move()
            if self.pos.x < 5 or self.pos.y < 5 or self.pos.x > WIN_WIDTH - 5 or self.pos.y > WIN_HEIGHT - 5:
                self.dead = True
            elif dis(self.pos.x, self.pos.y, GOAL.x, GOAL.y) < 5:
                self.reachedGoal = True

        if self.is_best:
            color = (0, 255, 0)
            width = 7
        else:
            color = (0, 0, 0)
            width = 5
        if self.fitness > .005:
            color = (0, 0, 255)
            width = 7
        pg.draw.circle(win, color, tuple(self.pos), width)

    def calculate_fitness(self):
        if self.reachedGoal:
            self.fitness = 1 / 16 + 10000 / self.brain.step
        else:
            distance_to_goal = dis(self.pos.x, self.pos.y, GOAL.x, GOAL.y)
            self.fitness = 1 / distance_to_goal

    def make_baby(self):
        baby = Dot(SPAWN)
        baby.brain = self.brain.clone()
        return baby


class Goal:
    def __init__(self):
        self.pos = GOAL

    def update(self):
        pg.draw.circle(win, (255, 0, 0), tuple(self.pos), 10)


class Brain:
    def __init__(self, size):
        self.size = size
        self.step = 0
        self.directions = []
        self.randomize()
        self.mutationRate = 1

    def randomize(self):
        self.directions = []
        for i in range(self.size):
            self.directions.append(Vector2.from_angle(r.random() * 2 * math.pi) * 4)

    def clone(self):
        clone = Brain(len(self.directions))
        clone.directions = self.directions
        return clone

    def mutate(self):
        for i in range(len(self.directions) - 1):
            rand = r.random()
            if rand < self.mutationRate:
                self.directions[i] = Vector2.from_angle(r.random() * 2 * math.pi) * 4


class Population:
    def __init__(self, size):
        self.size = size
        self.Dots = []
        for i in range(size):
            self.Dots.append(Dot(SPAWN))

        self.minStep = 20
        self.gen = 0
        self.bestDot = 0
        self.fit_sum = 0

    def update(self):
        for d in self.Dots:
            d.update()

    def fitness(self):
        for d in self.Dots:
            d.calculate_fitness()

    def end_of_generation(self):
        for d in self.Dots:
            if not d.dead and not d.reachedGoal:
                return False

        return True

    def natural_selection(self):
        self.fitness()

        new_dots = sorted(self.Dots, key=lambda x: x.fitness)
        new_dots.reverse()
        new_dots = new_dots[:len(new_dots)//2] * 2
        print([i.fitness for i in new_dots])
        self.Dots = [d.make_baby() for d in new_dots]

        self.Dots[0].is_best = True
        for d in range(len(self.Dots) // 2, len(self.Dots)):
            self.Dots[d].brain.mutate()


test = Population(100)
goal = Goal()

run = True
while run:
    win.fill('white')
    goal.update()

    if test.end_of_generation():
        test.natural_selection()
        time.sleep(1)
    else:
        test.update()

    # for event in pg.event.get():
    #     if event.type == pg.QUIT:
    #         run = False

    pg.display.update()
    time.sleep(0.005)

pg.quit()

The important part of this code is the natural_selection() function in the population class:

def natural_selection(self):
        self.fitness()

        new_dots = sorted(self.Dots, key=lambda x: x.fitness)
        new_dots.reverse()
        new_dots = new_dots[:len(new_dots)//2] * 2
        print([i.fitness for i in new_dots])
        self.Dots = [d.make_baby() for d in new_dots]

        self.Dots[0].is_best = True
        for d in range(len(self.Dots) // 2, len(self.Dots)):
            self.Dots[d].brain.mutate()

What it does (or supposed to do) is to calculate the fitness of the dots, sort the list of dots by fitness from highest to lowest, cuts the list in half and duplicating it, so the first and second halves are the same, and then sets the first dot to be the best and mutates the second half. The problem is that as the print in line 6 shows, it doesn't really mutate the dots, and the result is that in every generation it just takes the same repeating list and sorts it, and the fitnesses look like this:

[0.003441755148372998, 0.0034291486755453414, 0.003070574887525978, 0.0030339596318951327, 0.003030855079397534,...]
[0.00481387362410465, 0.00481387362410465, 0.003468488512721536, 0.003468488512721536, 0.0032419920180191478,...]
[0.004356736047656708, 0.004356736047656708, 0.004356736047656708, 0.004356736047656708, 0.003056862712974015,...]

I checked the brain.mutate function and it seems to work just fine.

Answer 1

I've rewritten your natural_selection method to be a little more structured (to me at least), and it seems to work for my simple test case. Can you try if this works for you? I added some comments to explain my steps.

    def natural_selection(self):

        # Calculate fitness
        self.fitness()

        # Print initial generation
        print(pop.Dots)

        # Sort dots by fitness
        new_dots = sorted(self.Dots, key=lambda x: x.fitness)
        new_dots.reverse()

        # Save first half of best individuals
        best_half = new_dots[:len(new_dots)//2]

        # Get offspring dots from best half 
        offspring = [d.make_baby() for d in best_half]

        # copy best half and mutate all dots
        mutated_offspring = [d.make_baby() for d in best_half]
        for d in mutated_offspring:
            d.brain.mutate()

        # Join original best half and mutated best half to get new dots
        new_dots = offspring + mutated_offspring

        # Set first new dot as best dot
        new_dots[0].is_best = True

        # Set new_dots as self.Dots
        self.Dots = new_dots

        # Print new generation
        self.fitness()
        print(pop.Dots)

Full test case:

import random


# Brains only consist of some random number.
# Mutations just add one to that number.
class Brain:
    def __init__(self):
        self.num = self.randomize()

    def clone(self):
        clone = Brain()
        clone.num = self.num
        return clone

    def randomize(self):
        return random.randint(1000, 9000)

    def mutate(self):
        self.num += 1

# Dots consist of a brain an a fitness.
# Fitness is simply the brain's number.
class Dot:

    def __init__(self):
        self.brain = Brain()
        self.fitness = None

    def __repr__(self):
        return str(self.fitness)

    def make_baby(self):
        baby = Dot()
        baby.brain = self.brain.clone()
        return baby


class Population:

    def __init__(self):
        self.Dots = [Dot() for i in range(10)]

    def fitness(self):
        for d in self.Dots:
            d.fitness = d.brain.num

    def natural_selection(self):

        # Calculate fitness
        self.fitness()

        # Print initial generation
        print(pop.Dots)

        # Sort dots by fitness
        new_dots = sorted(self.Dots, key=lambda x: x.fitness)
        new_dots.reverse()

        # Save first half of best individuals
        best_half = new_dots[:len(new_dots)//2]

        # Get offspring dots from best half 
        offspring = [d.make_baby() for d in best_half]

        # copy best half and mutate all dots
        mutated_offspring = [d.make_baby() for d in best_half]
        for d in mutated_offspring:
            d.brain.mutate()

        # Join original best half and mutated best half to get new dots
        new_dots = offspring + mutated_offspring

        # Set first new dot as best dot
        new_dots[0].is_best = True

        # Set new_dots as self.Dots
        self.Dots = new_dots

        # Print new generation
        self.fitness()
        print(pop.Dots)



random.seed(1)
pop = Population()
pop.natural_selection()

Returns:

[2100, 5662, 7942, 7572, 7256, 1516, 3089, 1965, 5058, 7233]
[7942, 7572, 7256, 7233, 5662, 7943, 7573, 7257, 7234, 5663]

So the original population fitness is printed on the first line. In the second line, the mutated population fitness is shown. My mutations simply add one to the dots brain value, so the second half is a copy of the first half with 1 added to each value.

Answer 2

Moved from an edit to the question by the OP to an answer.

There is a problem with copying the list in natural_selection:

from copy import deepcopy

...

    def natural_selection(self):

        # Sort dots by fitness
        new_dots = sorted(self.Dots, key=lambda x: x.fitness)
        new_dots.reverse()

        # Save first half of best individuals
        best_half = new_dots[:len(new_dots)//2]

        # Get offspring dots from best half
        offspring = [d.make_baby() for d in best_half]

        # copy best half and mutate all dots
        mutated_offspring = deepcopy(offspring)
        for d in mutated_offspring:
            d.brain.mutate()

        # Join original best half and mutated best half to get new dots
        new_dots = best_half + mutated_offspring

        # Set first new dot as best dot
        new_dots[0].is_best = True

        # Set new_dots as self.Dots
        self.Dots = new_dots