[Python] How to solve genetic algorithm stagnation in the Zen garden problem?

I have a genetic algorithm problem but I'm stuck in local optimum. As you can see in the snippet, it simply can't solve the problem, no matter how many gens or genomes I add to the generation.

Code:

import random

class ZenGarden:
def __init__(self, width, height, rocks):
self.width = width
self.height = height
self.rock_count = len(rocks)
self.base_grid = [[0] * width for _ in range(height)] # Initialize a base grid

# Place rocks in the base grid as -1
for x, y in rocks:
self.base_grid[y][x] = -1

self.grid = self.copy_garden()
self.max_fitness = width * height - len(rocks)

# Place rocks in the garden as -1
for x, y in rocks:
self.grid[y][x] = -1 # -1 represents a rock

def copy_garden(self):
"""Create a copy of the garden grid for each genome."""
return [row[:] for row in self.base_grid]

def display_garden(self, grid=None):
"""Display the garden grid."""
if grid is None:
grid = self.grid
for row in grid:
print(" ".join(f"{' K ' if cell == -1 else f'{cell:3}'}" for cell in row))
print()

class Gene:
def __init__(self, garden):
# Choose a random edge to start from
width = garden.width
height = garden.height
edge = random.randrange(garden.width + garden.width + garden.height +garden.height)

# Starting from the top edge
if edge < width:
self.start = (0, edge)
self.direction = 'down'

# Starting from the bottom edge
elif width <= edge < height + width :
self.start = (edge - width, width - 1)
self.direction = 'left'

# Starting from the left edge
elif width + height <= edge < width + width + height:
self.start = (height - 1, 2 * width + height - edge - 1)
self.direction = 'up'

# Starting from the right edge
else:
self.start = (2 * (height + width) - edge - 1, 0)
self.direction = 'right'

self.generate_rotation()

def generate_rotation(self):
self.rotation = [
int(a) for a in bin(random.randrange(1024))[2:].zfill(10)
]

class Genome:
def __init__(self, garden, initialize = True):
self.original_garden = garden # Keep a reference to the original garden
self.garden = ZenGarden(garden.width, garden.height, [(x, y) for y in range(garden.height) for x in range(garden.width) if garden.base_grid[y][x] == -1])
self.fitness = 0
self.genes = []

if initialize:
for _ in range(garden.width + garden.height + garden.rock_count):
gene = Gene(self.original_garden) # Pass the reference to original garden
self.genes.append(gene)
self.rake()

def rake(self):
"""Use each gene to rake the garden and calculate fitness."""
g = self.garden
monk_id = 0 # Start monk ID from 1

# Go through each gene (monk)
for gene in self.genes:
pos = list(gene.start) # Current position of the monk
direction = gene.direction # The direction the monk is moving in
ri = 0 # Rotation index

if g.grid[pos[0]][pos[1]] !=0:
continue
monk_id +=1

# Start raking cells
while True:
# If the cell is a rock (-1), stop raking
g.grid[pos[0]][pos[1]] = monk_id

if direction == 'up':
pos[0] -= 1
elif direction == 'down':
pos[0] += 1
elif direction == 'left':
pos[1] -= 1
else:
pos[1] += 1

if pos[0] not in range(g.height) or pos[1] not in range(g.width):
break

if g.grid[pos[0]][pos[1]] == 0:
continue

# Ak je tam prekazka tak sa vratime...
if direction == 'up':
pos[0] += 1
elif direction == 'down':
pos[0] -= 1
elif direction == 'left':
pos[1] += 1
else:
pos[1] -= 1

# ...a vyberieme ine policko
if direction == 'up' or direction == 'down':
n = (
[pos[0], pos[1] - 1],
[pos[0], pos[1] + 1],
)
else:
n = (
[pos[0] - 1, pos[1]],
[pos[0] + 1, pos[1]],
)
nv = []
for p in n:
try:
nv.append(g.grid[p[0]][p[1]])
except IndexError:
nv.append('e')

# Ak je len jedno nepohrabane tak ho vyberieme
if nv.count(0) == 1:
pos = n[nv.index(0)]

# A ak su dve tak jedno vyberieme
elif nv.count(0) == 2:
# Create a mapping of directions to indices in `n`
direction_map = {
'up': 0, # Choose the first element from `n` for 'up'
'down': 1, # Choose the second element from `n` for 'down'
'left': 0, # Choose the first element from `n` for 'left'
'right': 1 # Choose the second element from `n` for 'right'
}

# Use the direction_map to get the correct index
pos = n[direction_map[gene.direction]]
ri += 1
if ri == len(gene.direction):
ri = 0

# Ak ani jedno nie je nepohrabane tak koncime
else:
# Ak sme skoncili v strede mapy tak uz sa neda pokracovat
# na dalsi gen
if 'e' not in nv:
self.set_fitness()
return
break

# Nastavime novy smer pohybu
if direction in ('up', 'down'):
direction = 'left' if n.index(pos) == 0 else 'right'
else:
direction = 'up' if n.index(pos) == 0 else 'down'

self.set_fitness()

def set_fitness(self):
"""Calculate the fitness as the number of raked cells."""
self.fitness = sum(1 for x in sum(self.garden.grid, []) if x > 0 ) # Count only raked cells

def crossover(self, other):
"""Create a new genome by crossing over genes from two parents."""
new = Genome(self.original_garden)

# Randomly choose the crossover type
p = random.random()
if p < 0.30:
# One-point crossover: take part from the first parent, part from the second
point = random.randrange(len(self.genes))
new.genes = self.genes[oint] + other.genes[point:]
elif p < 0.60:
# Uniform crossover: randomly choose genes from either parent
new.genes = [random.choice([self.genes, other.genes]) for i in range(len(self.genes))]
else:
# Full copy: take all genes from one parent
new.genes = random.choice([self.genes, other.genes])

# Mutations: new gene generation or rotation regeneration
for i in range(len(new.genes)):
p = random.random()
if p < 0.2: # 5% chance to generate a new gene
new.genes = Gene(self.original_garden)
elif p < 0.05: # 10% chance to regenerate rotations
new.genes.generate_rotation()

# After crossover, rake the garden with the new genome
new.rake()

return new
def rank_selection(population):
"""Rank selection to select parents based on their fitness."""
# Sort the population based on fitness (higher fitness first)
sorted_population = sorted(population, key=lambda x: x.fitness, reverse=True)

# Assign ranks and calculate probabilities for selection
total_ranks = sum(range(1, len(population) + 1)) # Sum of all ranks
probabilities = [rank / total_ranks for rank in range(1, len(population) + 1)]

# Select a genome based on the rank probabilities
selected = random.choices(sorted_population, weights=probabilities, k=2)
return selected[0], selected[1] # Return two selected parents for crossover


def solve_hybrid_selection(rocks, width=12, height=10):
"""Solve the ZenGarden problem using hybrid selection (rank selection + crossover)."""
garden = ZenGarden(width, height, rocks)
population_size = 100
generations = 1000 # Run for 1000 generations
population = [Genome(garden) for _ in range(population_size)]

for gc in range(generations):
best = max(population, key=lambda x: x.fitness)
next_generation = [best] # Preserve the best genome

# Hybrid strategy: 60% crossover, 40% direct rank selection
num_crossover = int(0.6 * (population_size - 1))
num_rank_selected = population_size - 1 - num_crossover

# Generate offspring by crossover (60%)
for _ in range(num_crossover):
parent1, parent2 = rank_selection(population)
child = parent1.crossover(parent2)
next_generation.append(child)

# Select remaining directly from rank selection (40%)
for _ in range(num_rank_selected):
parent, _ = rank_selection(population)
next_generation.append(parent)

population = next_generation

# Print generation stats
print(f'Generation: {gc + 1}, Best Fitness: {best.fitness}/{garden.max_fitness}')

# Check if the best genome solved the garden
if best.fitness == garden.max_fitness:
print("Solution found!")
garden.display_garden(best.garden.grid)
break
else:
print(f"No solution found after {generations} generations. Missing {garden.max_fitness - best.fitness}")
garden.display_garden(garden.grid)
garden.display_garden(best.garden.grid)

# Example usage
rocks = [(5, 3), (2, 6), (9, 1), (3, 1), (8, 6), (9, 6)]
solve_hybrid_selection(rocks)


I've tried a lot of mutation probabilities and adding new selection methods but I simply can't get over it.

Continue reading...