Created
August 5, 2019 18:55
-
-
Save DiegoGallegos4/bdc72f801cd059604cb86136a2a23aca to your computer and use it in GitHub Desktop.
Genetic 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 operator | |
import random | |
# an individual with bigger fitness is more likely to succeed. | |
def fitness(password, test_word): | |
if len(test_word) != len(password): | |
return | |
score = 0 | |
for i in range(len(password)): | |
if password[i] == test_word[i]: | |
score += 1 | |
return score * 100 / len(password) | |
# creating individuals (population) | |
# motivation: DNA is composed of genes and each of them come from different alleles (versions of genes) | |
# in this case each character is a gene and value of the letter is the allele | |
# criteria: each individual has a good shape (word of size N) and population can cover all posibilities of words of size N | |
# first population: should cover all possibilities and shouldn't be biased. | |
def generate_first_population(size, password): | |
def generate_word(length): | |
alphabet = "abcdefghijklmnopqrstuvwxyz! " | |
return "".join([random.choice(alphabet) for item in [0] * len(target)]) | |
return [generate_word(len(password)) for i in range(size)] | |
# Selection: From one generation to the next | |
# 1. select a specific part of previous generatic | |
# 2. combine breeders into next batch | |
def sort_population_by_fitness(population, password): | |
performance = {} | |
for individual in population: | |
performance[individual] = fitness(password, individual) | |
return sorted(performance.items(), key=operator.itemgetter(1), reverse=True) | |
def select_breeders(sorted_population, take_best, take_lucky): | |
next_generation = [] | |
for i in range(take_best): | |
next_generation.append(sorted_population[i][0]) | |
for i in range(take_lucky): | |
next_generation.append(random.choice(sorted_population)[0]) | |
random.shuffle(next_generation) | |
return next_generation | |
# Breeding | |
def create_children(breeders, num_children): | |
def create_child(individual_1, individual_2): | |
child = "" | |
for i in range(len(individual_1)): | |
if int(100 * random.random()) < 50: | |
child += individual_1[i] | |
else: | |
child += individual_2[i] | |
return child | |
next_population = [] | |
for i in range(len(breeders) // 2): | |
for j in range(num_children): | |
next_population.append( | |
create_child(breeders[i], breeders[len(breeders) - 1 - i]) | |
) | |
return next_population | |
# Mutation | |
def mutate_population(population, chance_of_mutation): | |
def mutate_word(word): | |
index_modification = int(random.random() * len(word)) | |
if index_modification == 0: | |
word = chr(97 + int(26 * random.random())) + word[1:] | |
else: | |
word = ( | |
word[:index_modification] | |
+ chr(97 + int(26 * random.random())) | |
+ word[index_modification + 1 :] | |
) | |
return word | |
for i in range(len(population)): | |
if random.random() * 100 < chance_of_mutation: | |
population[i] = mutate_word(population[i]) | |
return population | |
target = "im from honduras" | |
population_size = 300 | |
num_children = 8 | |
mutation_rate = 25 | |
population = generate_first_population(population_size, target) | |
def genetic_algorithm(population, target, num_children, mutation_rate): | |
iterations, i = 200, 0 | |
take_best, take_lucky = len(population) // 2, len(population) // 10 | |
output = [("", 0)] | |
while target != output[0][0] and i < iterations: | |
sorted_population = sort_population_by_fitness(population, target) | |
breeders = select_breeders(sorted_population, take_best, take_lucky) | |
population = create_children(breeders, num_children) | |
population = mutate_population(population, mutation_rate) | |
output = sort_population_by_fitness(population, target) | |
i += 1 | |
return output[0] | |
print(genetic_algorithm(population, target, num_children, mutation_rate)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment