Skip to content

Instantly share code, notes, and snippets.

@marinhoarthur
Last active May 5, 2022 12:39
Show Gist options
  • Save marinhoarthur/6689655 to your computer and use it in GitHub Desktop.
Save marinhoarthur/6689655 to your computer and use it in GitHub Desktop.
A simple genetic algorithm written in Python fully based on an article by Lee Jacobson from his blog theprojectspot.com
from Population import Population
from Individual import Individual
from random import random, randint
class Algorithm():
#Constants
Uniform_rate = 0.5
Mutation_rate = 0.015
Tournament_size = 5
Elitism = True
@staticmethod
def evolve_population(population_passed):
print("Evolving population...")
new_population = Population(population_passed.size(), False)
if Algorithm.Elitism:
new_population.individuals.append(population_passed.get_fittest())
elitism_off_set = 1
else:
elitism_off_set = 0
#Do crossover over the entire population
for i in range(elitism_off_set, population_passed.size()):
individual1 = Algorithm.tournament_selection(population_passed)
individual2 = Algorithm.tournament_selection(population_passed)
new_individual = Algorithm.crossover(individual1, individual2)
new_population.individuals.append(new_individual)
#Do mutation randomly
for i in range(elitism_off_set, population_passed.size()):
Algorithm.mutate(new_population.get_individual(i))
return new_population
@staticmethod
def crossover(individual1_passed, individual2_passed):
new_sol = Individual()
for i in range(individual1_passed.size()):
if random() <= Algorithm.Uniform_rate:
new_sol.set_gene(i, individual1_passed.get_gene(i))
else:
new_sol.set_gene(i, individual2_passed.get_gene(i))
return new_sol
@staticmethod
def mutate(individual_passed):
for i in range(individual_passed.size()):
if random() <= Algorithm.Mutation_rate:
gene = randint(0,1)
individual_passed.set_gene(i, gene)
@staticmethod
def tournament_selection(population_passed):
#Tournament pool
tournament = Population(Algorithm.Tournament_size, False)
""" Tournament selection technique.
How it works: The algorithm choose randomly five
individuals from the population and returns the fittest one """
for i in range(Algorithm.Tournament_size):
random_id = int(random() * population_passed.size())
tournament.individuals.append(population_passed.get_individual(random_id))
fittest = tournament.get_fittest()
return fittest
class FitnessCalc():
Solution = bytearray(64)
@staticmethod
def set_solution(solution_passed):
for i in range(len(solution_passed)):
FitnessCalc.Solution[i] = int(solution_passed[i])
@staticmethod
def get_max_fitness():
return len(FitnessCalc.Solution)
from FitnessCalc import FitnessCalc
from Population import Population
from Algorithm import Algorithm
from time import time
start = time()
FitnessCalc.set_solution("1111000000000000000000000000000000000000000000000000000000001111")
my_pop = Population(50, True)
generation_count = 0
while my_pop.fitness_of_the_fittest() != FitnessCalc.get_max_fitness():
generation_count += 1
print("Generation : %s Fittest : %s " % (generation_count, my_pop.fitness_of_the_fittest()))
my_pop = Algorithm.evolve_population(my_pop)
print("******************************************************")
genes_the_fittest = []
for i in range(len(FitnessCalc.Solution)):
genes_the_fittest.append(my_pop.get_fittest().genes[i])
print("Solution found !\nGeneration : %s Fittest : %s " % (generation_count + 1, my_pop.fitness_of_the_fittest()))
print("Genes of the Fittest : %s " % (genes_the_fittest))
finish = time()
print ("Time elapsed : %s " % (finish - start))
from random import randint
from FitnessCalc import FitnessCalc
class Individual():
DefaultGeneLength = len(FitnessCalc.Solution)
def __init__(self):
self.genes = bytearray(Individual.DefaultGeneLength)
for i in range(Individual.DefaultGeneLength):
gene = randint(0,1)
self.genes[i] = gene
def get_gene(self, index):
return self.genes[index]
def set_gene(self, index, what_to_set):
self.genes[index] = what_to_set
def size(self):
return len(self.genes)
from Individual import Individual
from FitnessCalc import FitnessCalc
class Population():
def __init__(self, population_size, initialise):
self.individuals = []
#Creates the individuals
if (initialise):
for i in range(population_size):
new_individual = Individual()
self.individuals.append(new_individual)
def get_fitness(self, individual_passed):
fitness = 0
for i in range(Individual.DefaultGeneLength):
if individual_passed.genes[i] == FitnessCalc.Solution[i]:
fitness += 1
return fitness
def fitness_of_the_fittest(self):
fitness_of_the_fittest = self.get_fitness(self.get_fittest())
return fitness_of_the_fittest
def get_fittest(self):
fittest = self.individuals[0]
for i in range(len(self.individuals)):
if self.get_fitness(fittest) <= self.get_fitness(self.individuals[i]) :
fittest = self.individuals[i]
return fittest
def size(self):
return len(self.individuals)
def get_individual(self, index):
return self.individuals[index]
def save_individual(self, index, individual_passed):
self.individuals[index] = individual_passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment