ml-finance-python
python scripts for finance machine learning
git clone https://9o.is/git/ml-finance-python.git
genetic_algorithm.py
(4227B)
1 from __future__ import print_function, division
2 import string
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
9 Parameters:
10 -----------
11 target_string: string
12 The string which the GA should try to produce.
13 population_size: int
14 The number of individuals (possible solutions) in the population.
15 mutation_rate: float
16 The rate (or probability) of which the alleles (chars in this case) should be
17 randomly changed.
18 """
19 def __init__(self, target_string, population_size, mutation_rate):
20 self.target = target_string
21 self.population_size = population_size
22 self.mutation_rate = mutation_rate
23 self.letters = [" "] + list(string.ascii_letters)
24
25 def _initialize(self):
26 """ Initialize population with random strings """
27 self.population = []
28 for _ in range(self.population_size):
29 # Select random letters as new individual
30 individual = "".join(np.random.choice(self.letters, size=len(self.target)))
31 self.population.append(individual)
32
33 def _calculate_fitness(self):
34 """ Calculates the fitness of each individual in the population """
35 population_fitness = []
36 for individual in self.population:
37 # Calculate loss as the alphabetical distance between
38 # the characters in the individual and the target string
39 loss = 0
40 for i in range(len(individual)):
41 letter_i1 = self.letters.index(individual[i])
42 letter_i2 = self.letters.index(self.target[i])
43 loss += abs(letter_i1 - letter_i2)
44 fitness = 1 / (loss + 1e-6)
45 population_fitness.append(fitness)
46 return population_fitness
47
48 def _mutate(self, individual):
49 """ Randomly change the individual's characters with probability
50 self.mutation_rate """
51 individual = list(individual)
52 for j in range(len(individual)):
53 # Make change with probability mutation_rate
54 if np.random.random() < self.mutation_rate:
55 individual[j] = np.random.choice(self.letters)
56 # Return mutated individual as string
57 return "".join(individual)
58
59 def _crossover(self, parent1, parent2):
60 """ Create children from parents by crossover """
61 # Select random crossover point
62 cross_i = np.random.randint(0, len(parent1))
63 child1 = parent1[:cross_i] + parent2[cross_i:]
64 child2 = parent2[:cross_i] + parent1[cross_i:]
65 return child1, child2
66
67 def run(self, iterations):
68 # Initialize new population
69 self._initialize()
70
71 for epoch in range(iterations):
72 population_fitness = self._calculate_fitness()
73
74 fittest_individual = self.population[np.argmax(population_fitness)]
75 highest_fitness = max(population_fitness)
76
77 # If we have found individual which matches the target => Done
78 if fittest_individual == self.target:
79 break
80
81 # Set the probability that the individual should be selected as a parent
82 # proportionate to the individual's fitness.
83 parent_probabilities = [fitness / sum(population_fitness) for fitness in population_fitness]
84
85 # Determine the next generation
86 new_population = []
87 for i in np.arange(0, self.population_size, 2):
88 # Select two parents randomly according to probabilities
89 parent1, parent2 = np.random.choice(self.population, size=2, p=parent_probabilities, replace=False)
90 # Perform crossover to produce offspring
91 child1, child2 = self._crossover(parent1, parent2)
92 # Save mutated offspring for next generation
93 new_population += [self._mutate(child1), self._mutate(child2)]
94
95 print ("[%d Closest Candidate: '%s', Fitness: %.2f]" % (epoch, fittest_individual, highest_fitness))
96 self.population = new_population
97
98 print ("[%d Answer: '%s']" % (epoch, fittest_individual))
99
100
101
102
103
104