|
Jupyter at Bryn Mawr College |
|
|
| Public notebooks: /services/public/dblank / CS245 Programming Languages / 2016-Fall / Labs | |||
Lab 06: Evolving Brains
CS371: Cognitive Science
Bryn Mawr College, Fall 2016
Prof. Blank
This is a team-based project.
Please put your "# title" and "## by-line" in the next two cells (respectively), and then delete this cell
YOUR ANSWER HERE
YOUR ANSWER HERE
This lab explores using evolution to find a good Ladybug DNA. First, we have all of our imports and setup that we will need:
from calysto.simulation import DiscreteView, get_robot, DNARobot
from calysto.display import display, clear_output
import random
import string
import copy
%matplotlib inline
For these experiments, we will be using the DNA representation that is:
- exactly 93 characters long
- made up of the characters "0123456789"
Remember that exactly what these 93 bits of DNA are is unknown to us, as is the meaning of each character. We don't know how these DNA encode a Ladybug brain, but we know that somehow they do.
Our mission is to search through the space of possible Ladybug brains and find a good one, if not the best.
Genetic Algorithm¶
Evolutionary algorithms are techniques for searching through a solution landscape in a generally effective manner.
All evolutionary strategies have a core set of properties:
- A "population" of solutions
- Limited resources (not all solutions will survive)
- A measure of performance, called ''fitness''
- Preferential treatment toward the higher measured solutions (the most fit ones)
- Reliance on randomness
A typical evolutionary system follows this basic algorithm:
- Create a random population of solutions
- Compute a fitness measure for each
- Create new members by mutating and/or combining old ones (often selecting the better ones based on fitness)
- Select the most fit for the next generation
- Go to Step #3
Randomized DNA Function¶
First, we make a simple function to make a random DNA string:
alphabet = "0123456789"
def make_dna(length):
return "".join([random.choice(alphabet) for i in range(length)])
dna = make_dna(93)
dna
1.2 Fitness Function¶
Let's let the ladybug move about for a few simulated seconds, or until it dies (whichever happens first). We'll take the fitness to be the average amount of energy that it has over that time.
To make this a bit easier on our ladybug, we'll add an extra cluster of food around it when we test the ladybug.
First, we make a simulation object and get the simulated ladybug:
sim = DiscreteView("Ladybug1")
robot = get_robot()
Nothing is visible, but it exists. This is to make the simulation run fast. Whenever we want, we can see where the ladybug is:
sim.render()
Now, we can define a fitness function. This is a little complicated, because we are using some of the internals of the simulation.
compute_fitness() does the following:
- takes a DNA string
- creates a DNARobot (ie, the ladybug) which needs the original robot, and 93 character DNA
- resets the simulation
- let's it run for some seconds, or until it dies
- computes the fitness avg energy over the run
- returns fitness
def compute_fitness(dna, seconds, show=False):
new_robot = DNARobot(robot, dna)
sim.setRobot(0, new_robot)
sim.reset()
while new_robot.energy > 0 and sim.clock < seconds:
sim.step()
if show:
clear_output(wait=True)
display(sim.render())
fitness = sum(new_robot.history)/len(new_robot.history)
return fitness
Now we try it:
%%time
dna = make_dna(93)
print(dna)
print(compute_fitness(dna, 3, True))
%%time
print(dna)
print(compute_fitness(dna, 3, False))
With the display on, it will take about the number of seconds run. Without the display, the actual time taken is less that seconds given.
1.3 A Mutate Function¶
For all of the search methods (besides Greedy search) we need a method of slightly changing the DNA.
For some search algorithms, we will need a variable amount of mutation. So, we will make our mutate function take two arguments: the DNA to mutate, and an amount. The amount will be the number of mutations to make.
Write your mutate function here:
def mutate(dna, amount):
dna_list = list(dna)
### BEGIN SOLUTION
for i in range(amount):
point = int(random.random() * len(dna))
dna_list[point] = random.choice(alphabet)
### END SOLUTION
return "".join(dna_list)
mutate("XXX", 1)
mutate(dna, 10)
1.4 Putting it altogether¶
We define a make_pop() function that will generate a number of DNA. We return them as a list of pairs:
[[0, DNA1], [0, DNA2], ...]
The zero is a place keeper where we will put the fitness in a moment.
def make_pop(size, dna=None):
pop = []
for i in range(size):
if dna is None:
pop.append([0, make_dna(93)])
else:
pop.append([0, mutate(dna, 10)])
return pop
pop = make_pop(3)
pop
How diverse is the population per position?¶
We define a simple function to show the diversity of the population. Along the top will be each position of the DNA. Along the left side is the possible values for a location (a gene). The matrix is filled with the counts of those genes in that location.
def show_diversity(pop):
counts = [{} for i in range(len(pop[0][1]))]
for i in range(len(pop)):
for j in range(len(pop[i][1])):
c = pop[i][1][j]
counts[j][c] = counts[j].get(c, 0) + 1
print(" 012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012")
print(" ---------------------------------------------------------------------------------------------")
for number in range(9, -1, -1):
print("%s: " % number, end="")
for position in range(len(counts)):
count = int(counts[position].get(str(number), 0)/len(pop) * 10)
if count == 10:
count = "X"
elif count == 0:
count = "."
print(count, end="")
print()
show_diversity(pop)
for i in range(len(pop)):
pop[i][0] = compute_fitness(pop[i][1], 3)
pop.sort(reverse=True)
pop
Crossover Function¶
Crossover exchanges pieces of two genomes. Crossover can be a perfect shuffle, uniform, or point-based. Shuffle simply alternates between each parent. Uniform tosses an even coin to see if the gene comes from the mother or the father. Point-based mutation will only crossover at particular points. Shown here is a single point crossover:
To use crossover, we need a method of selecting good parents:
def select(pop):
"""
Given a population of the form [[FITNESS, DNA], ...]
pick one (with better fitness, more likily to be picked),
and return a copy of the DNA.
"""
partsum = 0.0
sumFitness = sum([item[0] for item in pop])
if sumFitness == 0:
raise Exception("Population has a total of zero fitness")
spin = random.random() * sumFitness
index = 0
while index < len(pop) - 1:
fitness = pop[index][0]
if fitness < 0:
raise Exception("Negative fitness in select: " + str(fitness))
partsum += fitness
if partsum >= spin:
break
index += 1
#print("index:", index)
return copy.copy(pop[index][1])
select(pop)
Our crossover function will replace a segment of the population, given by percentage:
def crossover(pop, percentage):
"""
Given a population and a percentage, replace
that percentage of the population with new
individuals created from higher-fitness individual.
New individuals replace the worst-performing individuals.
"""
old_pop = copy.copy(pop)
for j in range(int(len(pop) * percentage)):
p1 = select(old_pop)
p2 = select(old_pop)
# Pick a crossover point:
point = random.randint(0, len(pop[j][1]) - 1)
child = []
for i in range(len(pop[j][1])):
if i < point:
child.append(p1[i])
else:
child.append(p2[i])
child = "".join(child)
#print("p1:", p1)
#print("p2:", p2)
#print("c :", child)
#print("replacing", len(pop) - j - 1)
pop[len(pop) - j - 1][1] = child
In the following cell, provide settings for all of the parameters, such as:
generations = 2
simulated_seconds = 3
pop_size = 10
mutations_per_individual = 10
crossover_percentage = .33
### BEGIN SOLUTION
generations = 10
simulated_seconds = 5
pop_size = 10
mutations_per_individual = 10
crossover_percentage = .33
### END SOLUTION
And then run the experiment!
best_fitness = []
pop = make_pop(pop_size)
for generation in range(generations):
print("Computing fitness...")
for i in range(len(pop)):
pop[i][0] = compute_fitness(pop[i][1], simulated_seconds)
print("Sorting...")
pop.sort(reverse=True)
print("Generation:", generation + 1, "Best:", pop[0][0])
print(" Best DNA:", pop[0][1])
print("Mutating...")
best_fitness.append(pop[0][0])
for i in range(2, len(pop)):
pop[i][1] = mutate(pop[i][1], mutations_per_individual)
# Crossover:
crossover(pop, crossover_percentage)
1.5 Analysis¶
Now, you can examine different aspects of this evolutionary run.
pop
What does the diversity of the population's DNA look like?
show_diversity(pop)
In the following cell, discuss the diversity of the population. Is this what you expected? Did it "converge"? Or is the population fairly diverse?
YOUR ANSWER HERE
In the following cell, create a matplotlib graph of the best fitnesses over time.
best_fitness
import matplotlib.pyplot as plt
### BEGIN SOLUTION
plt.plot(best_fitness)
plt.xlabel("Generation")
plt.ylabel("Fitness")
plt.ylim(50,200)
plt.show()
### END SOLUTION
As part of any experiment, you'll want to examine different solutions. This section explores how you can watch a DNA control the ladybug, and make a movie for showing.
First, we define two functions:
def watch_one(dna, seconds=10):
new_robot = DNARobot(robot, dna)
sim.setRobot(0, new_robot)
sim.reset()
while new_robot.energy > 0 and sim.clock < seconds:
sim.step()
clear_output(wait=True)
display(sim.render())
print("fitness:", sum(new_robot.history)/len(new_robot.history))
def make_movie(dna, name, seconds=10):
new_robot = DNARobot(robot, dna)
sim.setRobot(0, new_robot)
sim.reset()
frame = 0
while new_robot.energy > 0 and sim.clock < seconds:
sim.step()
canvas = sim.render()
canvas.save("%s-%04d.gif" % (name, frame))
frame += 1
watch_one() takes a DNA string, and simply renders it on each step:
dna = '900499520468472606914876192567498206996983559871961745555167134603951243523914525534679075336'
watch_one(dna)
watch_one(pop[0][1])
make_movie() takes a DNA string and a filename, and makes a bunch of gif files:
make_movie(pop[0][1], "ladybug-0")
You can turn the ladybug-0-*.gif files into a movie named moview-0.gif with this shell command:
! convert -delay 20 -loop 0 ladybug-0-*.gif movie-0.gif
This cell is a markdown cell that shows how to display an animated gif file in your notebook using HTML:
Finally, you may want to delete the extra gif files with this shell command:
! rm ladybug-*.gif
Team Reflection¶
In the next cell, add your reflections, including:
- What was your approach in picking parameters? Explain?
- What is the relationship between size of the population and diversity of the gene pool?
- What could make this evolution more realistic? What is missing?
- From what you know about ladybug control, what could this DNA be representing? Why 93?
YOUR ANSWER HERE