Last active
October 16, 2017 00:56
-
-
Save jvmaia/cbceda29481afaa0cc4e1b73df516da2 to your computer and use it in GitHub Desktop.
a simple example of 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
| from string import ascii_uppercase | |
| from random import choice, randint | |
| key = input("write the key: ").upper() | |
| def get_letter(): | |
| return choice(ascii_uppercase) | |
| def create_chromosome(): | |
| chromosome = '' | |
| for i in range(len(key)): | |
| chromosome += get_letter() | |
| return chromosome | |
| def get_score(chrom): | |
| ppchar = 1 / len(chrom) | |
| pp = 0.0 | |
| for keychar in key: | |
| if keychar in chrom: | |
| if key.index(keychar) == chrom.index(keychar): | |
| pp += 1.0 | |
| result = ppchar * pp | |
| return result | |
| def selection(chromosomes_list): | |
| GRADED_RETAIN_PERCENT = 0.3 # best individuals | |
| NONGRADED_RETAIN_PERCENT = 0.2 # randomly selected | |
| selecteds = [] | |
| chromosomes_list = sorted(chromosomes_list, key=get_score, reverse=True) | |
| len_list = len(chromosomes_list) | |
| for i in range(int(len_list * GRADED_RETAIN_PERCENT)): | |
| selecteds.append(chromosomes_list[i]) | |
| for i in range(int(len_list * NONGRADED_RETAIN_PERCENT)): | |
| selecteds.append(choice(chromosomes_list)) | |
| return selecteds | |
| def crossover(parent1, parent2): | |
| half_parent1 = parent1[:int(len(parent1)/2)] | |
| half_parent2 = parent2[int(len(parent2)/2):] | |
| child = half_parent1 + half_parent2 | |
| return child | |
| def mutation(chrom): | |
| gene_replaced = randint(0, len(chrom)) | |
| new_chrom = '' | |
| for i in range(len(chrom)): | |
| if i == gene_replaced: | |
| new_chrom += get_letter() | |
| else: | |
| new_chrom += chrom[i] | |
| return new_chrom | |
| def is_answer(chrom): | |
| if chrom == key: | |
| return True | |
| else: | |
| return False | |
| def create_population(pop_size): | |
| population = [] | |
| for i in range(pop_size): | |
| population.append(create_chromosome()) | |
| return population | |
| def generation(population): | |
| select = selection(population) | |
| children = [] | |
| while len(children) < len(select): | |
| parent1 = choice(select) | |
| parent2 = choice(select) | |
| child = crossover(parent1, parent2) | |
| children.append(child) | |
| gen = select + children | |
| new_gen = [] | |
| for chrom in gen: | |
| if randint(1,100) < 10: | |
| new_gen.append(mutation(chrom)) | |
| else: | |
| new_gen.append(chrom) | |
| return new_gen | |
| def algorithm(): | |
| population_size = 14 | |
| population = create_population(population_size) | |
| answers = [] | |
| i = 0 | |
| while not answers: | |
| print(i) | |
| population = generation(population) | |
| for chrom in population: | |
| print('chrom {} is with {} of success'.format(chrom, get_score(chrom)), end=' ') | |
| if is_answer(chrom): | |
| print('CORRECT') | |
| answers.append(chrom) | |
| break | |
| else: | |
| print('INCORRECT') | |
| i+=1 | |
| algorithm() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment