An implementation of a Genetic Algorithm which will try to produce the user specified target string. Parameters: ----------- target_string: string The string which the GA should try to produce. population_size: int The number of individuals (possible solutions) in
| 3 | import numpy as np |
| 4 | |
| 5 | class GeneticAlgorithm(): |
| 6 | """An implementation of a Genetic Algorithm which will try to produce the user |
| 7 | specified target string. |
| 8 | Parameters: |
| 9 | ----------- |
| 10 | target_string: string |
| 11 | The string which the GA should try to produce. |
| 12 | population_size: int |
| 13 | The number of individuals (possible solutions) in the population. |
| 14 | mutation_rate: float |
| 15 | The rate (or probability) of which the alleles (chars in this case) should be |
| 16 | randomly changed. |
| 17 | """ |
| 18 | def __init__(self, target_string, population_size, mutation_rate): |
| 19 | self.target = target_string |
| 20 | self.population_size = population_size |
| 21 | self.mutation_rate = mutation_rate |
| 22 | self.letters = [" "] + list(string.ascii_letters) |
| 23 | |
| 24 | def _initialize(self): |
| 25 | """ Initialize population with random strings """ |
| 26 | self.population = [] |
| 27 | for _ in range(self.population_size): |
| 28 | individual = "".join(np.random.choice(self.letters, size=len(self.target))) |
| 29 | self.population.append(individual) |
| 30 | |
| 31 | def _calculate_fitness(self): |
| 32 | """ Calculates the fitness of each individual in the population """ |
| 33 | population_fitness = [] |
| 34 | for individual in self.population: |
| 35 | loss = 0 |
| 36 | for i in range(len(individual)): |
| 37 | letter_i1 = self.letters.index(individual[i]) |
| 38 | letter_i2 = self.letters.index(self.target[i]) |
| 39 | loss += abs(letter_i1 - letter_i2) |
| 40 | fitness = 1 / (loss + 1e-6) |
| 41 | population_fitness.append(fitness) |
| 42 | return population_fitness |
| 43 | |
| 44 | def _mutate(self, individual): |
| 45 | """ Randomly change the individual's characters with probability |
| 46 | self.mutation_rate """ |
| 47 | individual = list(individual) |
| 48 | for j in range(len(individual)): |
| 49 | if np.random.random() < self.mutation_rate: |
| 50 | individual[j] = np.random.choice(self.letters) |
| 51 | return "".join(individual) |
| 52 | |
| 53 | def _crossover(self, parent1, parent2): |
| 54 | """ Create children from parents by crossover """ |
| 55 | cross_i = np.random.randint(0, len(parent1)) |
| 56 | child1 = parent1[:cross_i] + parent2[cross_i:] |
| 57 | child2 = parent2[:cross_i] + parent1[cross_i:] |
| 58 | return child1, child2 |
| 59 | |
| 60 | def run(self, iterations): |
| 61 | self._initialize() |
| 62 |
nothing calls this directly
no outgoing calls
no test coverage detected