Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement