I recently watched a ted talk regarding the ‘Incredible Inventions of Intuitive AI’. This ted talk featured a segment where a car model was generated using an intuitive AI. This segment was brief and did not go into the specifics of what type of AI and how it was achieved, so I decided to try and replicate a smaller scale version of this project, using genetic algorithms.
Why did I pick genetic algorithms? Genetic algorithms, unlike neural network, can generate content easily, without the need to convolute an image and then transpose it back into its original dimensions. Additionally, it is extremely difficult to find data on car models in the right format, so that a GAN or a Neural network can have a reference point to start with.
With the project type outlined, the question remains: How should I simplify the problem?
Concept:
Instead of generating low-air-resistance cars, I will go with the simple idea of creating a shape of the largest area, consisting of n points, in a join-the-dot type fashion.
The area of the shape will be calculated using the Shoelace formula. A brief explanation of how it works can be deduced from the name: The cross multiplication of the coordinates of the points creates a shoelace type pattern.
I will then use a genetic algorithm (adapted from this code to train neural networks to generate shapes) to generate a list of numbers, that can be then converted into coordinates, which draws out a shape, in which the area can be measured.
The Code:
Step 1| Prerequisites:
import random
import numpy as np
from IPython.display import clear_outputdef sigmoid(x):
return 1/(1+np.exp(-x))
def PolyArea(x,y):
return 0.5*np.abs(np.dot(x,np.roll(y,1))-np.dot(y,np.roll(x,1)))
The prerequisites are the basic dependencies that the program needs to function. Random is for the random generation of agents, numpy for the initialization and manipulation of matrices, and IPython display for removing the clutter on the screen.
For the sake of simplicity, the only activation function I will use for this project is the sigmoid function.
The polyarea function is an implementation of the shoelace algorithm using numpy as the mathematical basis.
Step 2| The Agent Blueprint:
class genetic_algorithm:
def execute(pop_size,generations,threshold,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
self.gene_drive = []
def __str__(self):
return 'Loss: ' + str(self.fitness[0])
This is the start of the program, with the creation of the genetic algorithm class and the execute function.
The agent has a blueprint that contains the instructions for a network propagation. Within the agent’s init, a neural network class initialized, and its weights randomly generated based on a given matrix structure.
Step 3| Create Population:
def generate_agents(population, network):
return [Agent(network) for _ in range(population)]
This function, given the population size and network structure as parameters, generates a population of agents, with neural networks of randomly generated weights.
Step 4| Calculate Fitness:
def fitness(agents):
for agent in agents:
total_area = 0
points = agent.neural_network.propagate(np.random.randn(1,semi_epochs))
for shape in points:
x = list(shape[:num_points])
y = list(shape[num_points:])
y.insert(0,0)
x.insert(0,0)
y.insert(-1,0)
x.insert(-1,0)
total_area += PolyArea(x,y)
agent.fitness = total_area/semi_epochs
return agents
We will be feeding latent points as the input to the neural networks. Because of this, the network will have multiply tries to generate the shapes. The average area of these shapes will be recorded.
Theoretically, the algorithm will generate an agent that can consistently generate high area shapes with n points. Observing these shapes will give insight into creating large areas.
Step 5| Selection:
def selection(agents):
agents = sorted(agents, key=lambda agent: agent.fitness, reverse=True)
print('n'.join(map(str, agents)))
agents = agents[:int(0.2 * len(agents))]
return agents
This part of the program is the selection algorithm, that sorts the agents in reverse order, based on their fitness values. It then exterminates all agents that are not in the top fifth of this list.
Step 6| Crossover:
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())
for gene in parent1.gene_drive:
child1_genes[gene] = genes1[gene]
child2_genes[gene] = genes1[gene]
for gene in parent2.gene_drive:
child1_genes[gene] = genes2[gene]
child2_genes[gene] = genes2[gene]
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
Two random parents, from the top 20% of the population are chosen. They then breed. How is this done:
- Their weights are flattened
- A random intersection point is found. This point is where the genetic information of one parent ends, and where the genetic information of one parent begins.
- Two offspring are created that are then added to the list of agents. These children differ from each other, as they have a different intersection point.
This hopefully allows for the good traits of good parents to be passed on to their offspring.
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 agents
For every agent, there is a 10% chance that a mutation will occur. In this case, mutation refers to a certain weight value being replaced with a random float value. This is done by flattening the weights, finding a random weight to change, and then finally reshaping the weights to be reinserted into the agent.
Step 9| Execution:
for i in range(generations):
print('Generation',str(i),':')
agents = generate_agents(pop_size,network)
agents = fitness(agents)
agents = selection(agents)
agents = crossover(agents,network,pop_size)
agents = mutation(agents)
agents = fitness(agents)
if any(agent.fitness > threshold for agent in agents):
print('Threshold met at generation '+str(i)+' !')
if i % 100:
clear_output()
return agents[0]
Paste this final bit of code into the function and the function should run when called.
num_points = 3
semi_epochs = 100
network = [[semi_epochs,100,sigmoid],[None,num_points*2,sigmoid]]
ga = genetic_algorithm
agent = ga.execute(100,100,10,network)
weights = agent.neural_network.weights
One can change the number of points that the program can use to create the shapes, as well as the number of times the program can generate points, to get the average. Change these values around and you might find something interesting!
Conclusion:
You might be thinking: What is the purpose of this project? Why is this project useful? Two reasons.
Firstly, from a pragmatic standpoint, to progress to more complex models, such as those involving physical forces or multi-dimensional shapes, more experience with the program is required.
Secondly, it is useful for curiosity. If I chose to adapt the network to output the number of points as well as the coordinates of the points, I could use Machine Learning to reinforce the theory that hexagons hold the largest area to myself!
My links:
If you want to see more of my content, click this link.