Simple genetic-ish algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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