Skip to content

Instantly share code, notes, and snippets.

@mitchellvitez
Last active Aug 5, 2019
Embed
What would you like to do?
Simple genetic-ish algorithm
import random
POPULATION_SIZE = 1000
HEIGHT = 5
WIDTH = 20
MUTATION_CHANCE = 1 / (WIDTH * HEIGHT)
def randChar():
"""Get a random gene.
Used for initial population gene pool creation as well as for
adding mutations in later
"""
return chr(random.randrange(32, 125))
def initialPopulation():
"""Creates an initial population with entirely random genes."""
gs = []
for g in range(POPULATION_SIZE):
grid = []
for row in range(HEIGHT):
grid.append([])
for col in range(WIDTH):
grid[row].append(randChar())
gs.append(grid)
return gs
def score(grid):
"""Return a fitness score for this individual. Lower is better.
This is done to later apply selection pressure. Scores don't have to be
normalized, but should have meaning relative to one another.
The simple scoring mechanism we'll use here is number of characters that are
an 'A'. We should see populations converge towards "AAAAAAAA" etc.
"""
score = 0
for row in range(HEIGHT):
for col in range(WIDTH):
if grid[row][col] == 'A':
score -= 1
return score
def crossover(a, b):
"""Perform crossover to combine best-scoring grids into children grids.
This simulates the two grids becoming parents to a new offspring. We'll
select each gene at random from one of the parents, with some
chance of random mutations.
Mutation introduces a bit of extra randomness that helps keep our population
from getting "stuck".
"""
offspring = []
for _ in range(POPULATION_SIZE):
child = []
for row in range(HEIGHT):
child.append([])
for col in range(WIDTH):
if random.random() < MUTATION_CHANCE:
child[row].append(randChar())
elif random.choice([True, False]):
child[row].append(a[row][col])
else:
child[row].append(b[row][col])
offspring.append(child)
return offspring
def display(grid):
"""Print an individual."""
for row in grid:
print(''.join(row))
print()
def show(population):
"""Print a population."""
for grid in population:
display(grid)
def print_score(score):
"""Normalizes a score for printing.
The score is a number between 0 and -WIDTH * HEIGHT, where lower scores are
better. Normalize this to a positive percentage.
"""
return "{}%".format(round(abs(score) / (WIDTH * HEIGHT) * 100))
if __name__ == '__main__':
population = initialPopulation()
for generation in range(100):
print(f'*** Generation {generation+1} ***\n')
# selection pressure
scores = sorted(population, key=score)
# crossover and mutation
population = crossover(*scores[:2])
show(population[:2])
print(f'Fitness: {print_score(score(scores[0]))}\n')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment