No need to type, just download code and play with it :)
Links are on the slides, follow them here:
Don't afraid to ask questions!
The dojo part will be about using evolutionary algorithms to solve a real life problem.
smallest number
three numbers that sum to zero (3SUM)
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
O(N) O(N^2) O(N^3)
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
1 6 sec 36 sec 3.5 min
10 60 sec 60 min 60 hours
100 10 min 100 hours 6.7 years
1000 100 min 1 year 6.8 millenias
10000 17 hours 114 years 6.8 million years
--- order at a dinner table
--- combination opening a lock
"""""""""""""""""""""""""""""""""""""""""""""
O(N!) O(k^N)
"""""""""""""""""""""""""""""""""""""""""""""
1 1 sec 10 sec
5 2 min 27 hours
10 42 days 317 years
20 5.6 AotU 230 AotU
from __future__ import print_function
import string
import itertools
TARGET = "CHARLES DARWIN"
CHARACTERS = string.ascii_uppercase + " "
for candidate in itertools.product(CHARACTERS, repeat=len(TARGET)):
candidate = "".join(candidate)
print(candidate, end="\r")
if candidate == TARGET:
break
best = len(TARGET)
for candidate in itertools.product(CHARACTERS, repeat=len(TARGET)):
distance = evaluate(candidate)
if distance < best:
best = distance
print("{0:02} {1}".format(distance, "".join(candidate)))
def evaluate(solution):
return sum(1 for s,t in zip(solution, TARGET) if s != t)
# C-style distance calculation
def evaluate(solution):
distance = 0
for i in range(len(TARGET)):
if solution[i] != TARGET[i]:
distance += 1
return distance
best = len(TARGET)
while(True):
candidate = [random.choice(CHARACTERS) for i in range(len(TARGET))]
distance = evaluate(candidate)
if distance < best:
best = distance
print("{0:02} {1}".format(distance, "".join(candidate)))
best = [random.choice(CHARACTERS) for i in range(len(TARGET))]
fitness = evaluate(best)
for i in range(1000000):
candidate = best[:]
k = random.randrange(0, len(TARGET))
candidate[k] = random.choice(CHARACTERS)
distance = evaluate(candidate)
print("[{0: 4}] {1:02} {2}".format(i, distance, "".join(candidate)), end="\r")
if distance < fitness:
fitness = distance
best = candidate
if fitness == 0:
print()
break
MUTATION_CHANCE = 0.1
def mutate(solution):
f = lambda x: random.choice(CHARACTERS) if random.random() < MUTATION_CHANCE else x
return [f(x) for x in solution]
...
for i in range(1000000):
candidate = mutate(best)
distance = evaluate(candidate)
...
GENERATIONS = 50
POPULATION_SIZE = 100
MUTATION_PROBABILITY = 0.9
population = [init() for i in range(POPULATION_SIZE)]
fitnesses = [evaluate(individual) for individual in population]
def init():
return [random.choice(CHARACTERS) for i in range(len(TARGET))]
for i in range(GENERATIONS):
population = variate(population)
fitnesses = [evaluate(individual) for individual in population]
def variate(population):
for i in range(len(population)):
if random.random() < MUTATION_PROBABILITY:
population[i] = mutate(population[i])
return population
fitnesses.sort()
params = fitnesses[0], fitnesses[-1], fitnesses[POPULATION_SIZE / 2]
print("best={0}, worst={1}, median={2}".format(*params))
for i in range(GENERATIONS):
chosen = select(population, len(population), TOURNAMENT_SIZE)
population = variate(chosen)
def select(population, k, tournament_size):
chosen = []
for i in range(k):
candidates = random.sample(population, tournament_size)
chosen.append(min(candidates))
return chosen
from collections import namedtuple
Individual = namedtuple("Individual", "solution, fitness")
def init():
solution = [random.choice(CHARACTERS) for i in range(len(TARGET))]
return Individual(solution, evaluate(solution))
from copy import deepcopy
from operator import attrgetter
def select(population, k, tournament_size):
chosen = []
for i in range(k):
candidates = random.sample(population, tournament_size)
winner = min(candidates, key=attrgetter("fitness")) # pick by fitness
chosen.append(deepcopy(winner)) # append a copy, not a reference
return chosen
for i in range(len(population)):
new_fitness = evaluate(population[i].solution)
population[i] = population[i]._replace(fitness=new_fitness)
def variate(population):
for i in range(1, len(population), 2):
if random.random() < CROSSOVER_PROBABILITY:
crossover(population[i-1].solution, population[i].solution)
...
def crossover(a, b):
"""
One point crossover: AAA|BBBBBBB, BBB|AAAAAAA.
"""
point = random.randrange(1, min(len(a), len(b)))
a[point:], b[point:] = b[point:], a[point:]
def crossover_uniform(a, b, probability=0.5):
"""
Uniform crossover: AAABBABBABB, BBBAABAABAA.
"""
size = min(len(a), len(b))
for i in range(size):
if random.random() < probability:
a[i], b[i] = b[i], a[i]
http://xkcd.com/287/
ITEMS_NAME = [
"Mixed Fruit", "French Fries", "Side Salad",
"Hot Wings", "Mozzarella Sticks", "Sampler Plate"
]
ITEMS_PRICE = [2.15, 2.75, 3.35, 3.55, 4.2, 5.8]
solution = selection of items
def init():
return selection of 3 random items
def evaluate(solution, target_price):
return abs(price_of_selected_items - target_price)
def mutate(solution):
if random.random() > 0.5:
solution.add(random_item)
else:
solution.subtract(random_item)
crossover = uniform_crossover