How to improve evolutionary algorithm for dices

Question

I have the task to implement an evolutionary algorithm in which an individial consists of 100 dices. My goal is to get all sixes as values for the dices for the individuals. For this I implemented classes for the dices and for the individuals and also methods for mutation and recombination which we had so far in the course.

import numpy as np
import random

class Die():
    def __init__(self):
        self.number = np.random.randint(1, 7)
    
    def roll(self):
        self.number = np.random.randint(1, 7)


class Individual():
    def __init__(self, dices=None):
        self.dices = dices if dices != None else [Die() for _ in range(100)] 
        self.fitness = self.fitness_function()
        
    def fitness_function(self):
        return sum(1 for die in self.dices if die.number == 6)

    def mutate(self, mutation_rate):
        for die in self.dices:
            if np.random.random() < mutation_rate:
                die.roll()
        self.fitness = self.fitness_function()

def elite_selection(individuals, selection_size):
    sorted_individuals = sorted(individuals, key=lambda individual: individual.fitness, reverse=True)
    selected_individuals = sorted_individuals[:selection_size]
    return selected_individuals


def rank_based_selection(population, selection_size):
    sorted_population = sorted(population, key=lambda individual: individual.fitness, reverse=True)
    selection_probs = [1.0 / (i+1) for i in range(len(sorted_population))]
    total_prob = sum(selection_probs)
    normalized_probs = [p / total_prob for p in selection_probs]
    selected_individuals = list(np.random.choice(sorted_population, size=selection_size, p=normalized_probs))
    return selected_individuals


def one_point_crossover(parent_1, parent_2):
    crossover_point = np.random.randint(0, len(parent_1.dices))
    child_1_genes = parent_1.dices[:crossover_point] + parent_2.dices[crossover_point:]
    child_2_genes = parent_2.dices[:crossover_point] + parent_1.dices[crossover_point:]
    child_1 = Individual(child_1_genes)
    child_2 = Individual(child_2_genes)
    return child_1, child_2


def uniform_crossover(parent_1, parent_2):
    child_1_genes = []
    child_2_genes = []
    for i in range(len(parent_1.dices)):
        if np.random.uniform() < 0.5:
            child_1_genes.append(parent_1.dices[i])
            child_2_genes.append(parent_2.dices[i])
        else:
            child_1_genes.append(parent_2.dices[i])
            child_2_genes.append(parent_1.dices[i])        
    child_1 = Individual(child_1_genes)
    child_2 = Individual(child_2_genes)
    return child_1, child_2


def evolutionary_algorithm(population_size, selection_size, mutation_rate, max_iterations, target_fitness=80):
    population = [Individual() for _ in range(population_size)]

    for _ in range(max_iterations):
        selected_population = elite_selection(population, selection_size)
        new_population = selected_population

        while len(new_population) < population_size:
            parent_1, parent_2 = random.sample(selected_population, 2)
            child_1, child_2 = uniform_crossover(parent_1, parent_2)
            child_1.mutate(mutation_rate)
            child_2.mutate(mutation_rate)
            new_population += [child_1, child_2]

        population = new_population
        
        if np.mean([individual.fitness for individual in population]) >= target_fitness:
            break
        
    return population

population_size = 500
selection_size = 100
mutation_rate = 0.01
max_iterations = 300

indiv = evolutionary_algorithm(population_size, selection_size, mutation_rate, max_iterations)
print(max((i.fitness for i in indiv)), end=" ")

So I've tried the different methods and different hyperparameters but the best fitness I could get was 42. Since im new in this area, I really don't know if this is good or bad. Any help on how to improve my algorithm would be great.

Answer 1

You are reusing the same Die instance for multiple individuals. Later when you call die.roll() this will affect all individuals that have a reference to this Die.

This code below does not copy any of the Die objects. It only creates a new list with the existing references:

child_1_genes = parent_1.dices[:crossover_point] + parent_2.dices[crossover_point:]
child_1 = Individual(child_1_genes)

If you fix that, your algorithm has no problem reaching the maximum score of 100. You can fix that either by implementing a copy() method, or directly in the constructor:

class Die():
    def __init__(self, number=None):
        self.number = number if number is not None else np.random.randint(1, 7)

class Individual():
    def __init__(self, dices=None):
        if dices:
            self.dices = [Die(d.number) for d in dices]
        else:
            self.dices = [Die() for _ in range(100)]

But this code is too complicated for your problem.

The way you model a Die as a class is a bit too much object-oriented thinking. If you think about data instead, you'll notice that it only stores a single number. You don't need a class for that! Just store the number in the list. (In Python a number is also an object, but you cannot change its value after creation, so you won't run into the same proble. If you add two numbers, you get a new, different number object.)

If you later actually need a class for holding data (I'd try to avoid that, but it may happen), then consider keeping it immutable. If you never modify its data except in the constructor, then you never run into this problem.