Creating Genetic Algorithms With Python:
Creating Genetic Algorithms With Python:
Introduction:
Everyone knows about neural networks and Gradient Descent, but much less are familiar with unsupervised machine learning algorithms. Today I am here to introduce Genetic Algorithms and their implementation in Python, and hopefully, get you to understand more about genetic algorithms as well.
Genetic Algorithms:
Genetic Algorithms, like other machine learning algorithms, are trying to optimize a set of hyper-parameters to make predictions of a neural network as accurate as possible.
Gradient Descent and other optimization algorithms usually use partial derivatives to find the general direction to minimize the loss function and thus improve the accuracy of the neural network.
Genetic Algorithms, on the other hand, mimic evolution to optimize the network. Here how it works:
- An agent is generated. It contains a set of weights that are compatible with the neural network.
- The agent’s fitness value is calculated by comparing predictions made with the set of weights and the true y-values.
- Repeat this many times until you have a “population” of agents
- Sort the population by their fitness, with the agents with the best fitness at the top of the list.
- “Breed” the top agents together.
- Repeat until a satisfactory loss value has been reached.
Building a Genetic Algorithm:
Disclaimer: This code has been adapted from the code here to make it compatible to optimize neural networks.
Step 1| Prerequisites:
import random
import numpy as npdef sigmoid(x):
return 1/(1+np.exp(-x))These are the most basic dependencies for the project. To make the learning process better, you can add more activation functions for your suitable datasets.
Step 2| The Agent Blueprint:
class Agent:
def __init__(self,network):
class neural_network:
def __init__(self,network):
self.weights = []
self.activations = []
for layer in network:
if layer[0] != None:
input_size = layer[0]
else:
input_size = network[network.index(layer)-1][1]
output_size = layer[1]
activation = layer[2]
self.weights.append(np.random.randn(input_size,output_size))
self.activations.append(activation)
def propagate(self,data):
input_data = data
for i in range(len(self.weights)):
z = np.dot(input_data,self.weights[i])
a = self.activations[i](z)
input_data = a
yhat = a
return yhat
self.neural_network = neural_network(network)
self.fitness = 0
def __str__(self):
return 'Loss: ' + str(self.fitness[0])Each agent has its own set of weights, generated randomly with the architecture of the neural network setup. The argument network is a list that looks like so:
network = [[3,10,sigmoid],[None,1,sigmoid]]Each term in the list is describing a layer in the Neural Network. The first term in each nested list is the number of input neurons for the layer, the second term is the output and the third the activation function to be applied for the layer.
Step 3| Generating Agents:
def generate_agents(population, network):
return [Agent(network) for _ in range(population)]This is used to generate the agents, as detailed in step 1 of the methodology to run a genetic algorithm.
Step 4| Calculate Fitness:
def fitness(agents,X,y):
for agent in agents:
yhat = agent.neural_network.propagate(X)
cost = (yhat - y)**2
agent.fitness = sum(cost)
return agentsThis fitness function is essentially calculating the MSE value for each agent, by using the prediction and the true y-values.
Step 5| Agent Selection:
def selection(agents):
agents = sorted(agents, key=lambda agent: agent.fitness, reverse=False)
print('\n'.join(map(str, agents)))
agents = agents[:int(0.2 * len(agents))]
return agentsThis code essentially sorts the agents by their fitness value, from the lowest value to the highest. Keep in mind that the lower the fitness value, the better. It then shortens the list of agents to only the top 20% of the agents.
Step 6| Agent Crossover:
def unflatten(flattened,shapes):
newarray = []
index = 0
for shape in shapes:
size = np.product(shape)
newarray.append(flattened[index : index + size].reshape(shape))
index += size
return newarray
def crossover(agents,network,pop_size):
offspring = []
for _ in range((pop_size - len(agents)) // 2):
parent1 = random.choice(agents)
parent2 = random.choice(agents)
child1 = Agent(network)
child2 = Agent(network)
shapes = [a.shape for a in parent1.neural_network.weights]
genes1 = np.concatenate([a.flatten() for a in parent1.neural_network.weights])
genes2 = np.concatenate([a.flatten() for a in parent2.neural_network.weights])
split = random.randint(0,len(genes1)-1)child1_genes = np.array(genes1[0:split].tolist() + genes2[split:].tolist())
child2_genes = np.array(genes1[0:split].tolist() + genes2[split:].tolist())
child1.neural_network.weights = unflatten(child1_genes,shapes)
child2.neural_network.weights = unflatten(child2_genes,shapes)
offspring.append(child1)
offspring.append(child2)
agents.extend(offspring)
return agentsThis is the most complex part of the program. In the crossover process two random parents are chosen from within the selected agents. The nested list of weights are reduced to one long list. A splitting point is randomly picked. This determines how much of each parent’s weights the child will be composed of. This child’s weights is then reformatted and the child is added to the list of agents.
Step 7| Mutation:
def mutation(agents):
for agent in agents:
if random.uniform(0.0, 1.0) <= 0.1:
weights = agent.neural_network.weights
shapes = [a.shape for a in weights]flattened = np.concatenate([a.flatten() for a in weights])
randint = random.randint(0,len(flattened)-1)
flattened[randint] = np.random.randn()newarray = []
indeweights = 0
for shape in shapes:
size = np.product(shape)
newarray.append(flattened[indeweights : indeweights + size].reshape(shape))
indeweights += size
agent.neural_network.weights = newarray
return agentsGenetic Algorithms are technically “blind” as they have no insight to how the surface plotted by the loss function looks like. This means it is very easy for the genetic algorithm to get stuck at a certain point. Mutation allows for slight, random, infrequent changes to stir the pot and get the system out of local minimas.
Step 8| Putting it all together:
import random
import numpy as np
from IPython.display import clear_outputdef sigmoid(x):
return 1/(1+np.exp(-x))class genetic_algorithm:
def execute(pop_size,generations,threshold,X,y,network):
class Agent:
def __init__(self,network):
class neural_network:
def __init__(self,network):
self.weights = []
self.activations = []
for layer in network:
if layer[0] != None:
input_size = layer[0]
else:
input_size = network[network.index(layer)-1][1]
output_size = layer[1]
activation = layer[2]
self.weights.append(np.random.randn(input_size,output_size))
self.activations.append(activation)
def propagate(self,data):
input_data = data
for i in range(len(self.weights)):
z = np.dot(input_data,self.weights[i])
a = self.activations[i](z)
input_data = a
yhat = a
return yhat
self.neural_network = neural_network(network)
self.fitness = 0
def __str__(self):
return 'Loss: ' + str(self.fitness[0])
def generate_agents(population, network):
return [Agent(network) for _ in range(population)]
def fitness(agents,X,y):
for agent in agents:
yhat = agent.neural_network.propagate(X)
cost = (yhat - y)**2
agent.fitness = sum(cost)
return agents
def selection(agents):
agents = sorted(agents, key=lambda agent: agent.fitness, reverse=False)
print('\n'.join(map(str, agents)))
agents = agents[:int(0.2 * len(agents))]
return agents
def unflatten(flattened,shapes):
newarray = []
index = 0
for shape in shapes:
size = np.product(shape)
newarray.append(flattened[index : index + size].reshape(shape))
index += size
return newarray
def crossover(agents,network,pop_size):
offspring = []
for _ in range((pop_size - len(agents)) // 2):
parent1 = random.choice(agents)
parent2 = random.choice(agents)
child1 = Agent(network)
child2 = Agent(network)
shapes = [a.shape for a in parent1.neural_network.weights]
genes1 = np.concatenate([a.flatten() for a in parent1.neural_network.weights])
genes2 = np.concatenate([a.flatten() for a in parent2.neural_network.weights])
split = random.randint(0,len(genes1)-1)child1_genes = np.array(genes1[0:split].tolist() + genes2[split:].tolist())
child2_genes = np.array(genes1[0:split].tolist() + genes2[split:].tolist())
child1.neural_network.weights = unflatten(child1_genes,shapes)
child2.neural_network.weights = unflatten(child2_genes,shapes)
offspring.append(child1)
offspring.append(child2)
agents.extend(offspring)
return agents
def mutation(agents):
for agent in agents:
if random.uniform(0.0, 1.0) <= 0.1:
weights = agent.neural_network.weights
shapes = [a.shape for a in weights]flattened = np.concatenate([a.flatten() for a in weights])
randint = random.randint(0,len(flattened)-1)
flattened[randint] = np.random.randn()newarray = []
indeweights = 0
for shape in shapes:
size = np.product(shape)
newarray.append(flattened[indeweights : indeweights + size].reshape(shape))
indeweights += size
agent.neural_network.weights = newarray
return agents
for i in range(generations):
print('Generation',str(i),':')
agents = generate_agents(pop_size,network)
agents = fitness(agents,X,y)
agents = selection(agents)
agents = crossover(agents,network,pop_size)
agents = mutation(agents)
agents = fitness(agents,X,y)
if any(agent.fitness < threshold for agent in agents):
print('Threshold met at generation '+str(i)+' !')
if i % 100:
clear_output()
return agents[0]
return agents
X = np.array([[0, 0, 1], [1, 1, 1], [1, 0, 1], [0, 1, 1]])
y = np.array([[0, 1, 1, 0]]).T
network = [[3,10,sigmoid],[None,1,sigmoid]]
ga = genetic_algorithm
agent = ga.execute(100,5000,0.1,X,y,network)
weights = agent.neural_network.weights
agent.neural_network.propagate(X)Wrap everything up within an execute function, customize arguments and you have got yourself a genetic algorithm. The execute function will return the last agent, which is presumably the best agent to be created.
Final Thoughts:
Apart from optimizing Neural Networks, genetic algorithms have a unique use that other optimizers don’t have. This is for datasets that don’t have y-values that use non-traditional loss functions to evaluate the accuracy of a model.