Skip to content

Instantly share code, notes, and snippets.

@fbwright

fbwright/backpack.py

Created June 23, 2015 11:55
Show Gist options
  • Save fbwright/992087b7238384049e63 to your computer and use it in GitHub Desktop.
Save fbwright/992087b7238384049e63 to your computer and use it in GitHub Desktop.
Download ZIP
[2015-06-17] Challenge #219 [Hard] The Cave of Prosperity
Raw
backpack.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#An attempt at finding a solution to the challenge #219 of /r/DailyProgrammer
#(http://www.reddit.com/r/dailyprogrammer/comments/3aewlg/)
#I am using a genetic algorithm to find an (usually approximate) solution.
from __future__ import print_function, division
import genetic_algorithm as ga
import sys, random, argparse
if sys.version_info.major < 3:
input = raw_input
def parse_input(input):
nuggets = []
for i, line in enumerate(input.splitlines()):
if i == 0:
backpack_size = float(line)
continue
elif i == 1:
continue
nuggets.append(float(line))
return backpack_size, nuggets
def generate(genome_size):
def _generate_inner():
genome = []
for j in range(genome_size):
genome.append(random.randint(0, 1))
return genome
return _generate_inner
def fitness(target, sizes):
size = len(sizes)
def _fitness(gene):
fitness = 0
for i in range(size):
fitness += gene[i] * sizes[i]
fitness /= target
if fitness > 1:
fitness = 0
return fitness
return _fitness
def mutate(size):
def _mutate(gene):
index = random.randint(0, size-1)
gene[index] = 0 if gene[index] else 1
return _mutate
def crossover(length):
half = length // 2
def _crossover(parent_a, parent_b):
child = parent_a[:half] + parent_b[half:]
return child
return _crossover
if __name__ == "__main__":
parser = argparse.ArgumentParser(description="Finds a solution to the knapsack problem using genetic programming.")
parser.add_argument('infile', type=argparse.FileType('r'),
help="The file from which to read the problem to solve.")
parser.add_argument('-p', '--population', type=int, default=100,
metavar='P', help="size of the population to evolve (default: %(default)s)")
parser.add_argument('-r', '--retain', type=float, default=0.2,
metavar='R', help="percent of individuals to retain (default: %(default)s)")
parser.add_argument('-d', '--diversity', type=float, default=0.05,
metavar='D', help="percent of individuals to retain to improve genetic diversity (default: %(default)s)")
parser.add_argument('-m', '--mutation', type=float, default=0.01,
metavar='M', help="mutation rate (default: %(default)s)")
parser.add_argument('-t', '--target', type=float, default=0.99,
metavar='T', help="target fitness (default: %(default)s)")
parser.add_argument('-g', '--generation', type=int, default=None,
metavar='G', help="maximum number of generations (default: %(default)s)")
parser.add_argument('-v', '--verbose', action='count',
help="show a more detailed output")
args = parser.parse_args()
backpack_size, nuggets = parse_input(args.infile.read())
genome_width = len(nuggets)
backpack = ga.GeneticAlgorithm(
population = args.population,
retain = args.retain,
random_select = args.diversity,
mutation_rate = args.mutation,
generate_function = generate(genome_width),
fitness_function = fitness(backpack_size, nuggets),
mutate_function = mutate(genome_width),
crossover_function = crossover(genome_width)
)
solution = backpack.evolve_until(
fitness = args.target,
generation = args.generation,
update_each = args.generation // 20 if args.generation else 100,
silent = not args.verbose,
)
if args.verbose: print()
print(backpack.fitness(solution) * backpack_size)
for i, present in enumerate(solution):
if present: print(nuggets[i])
Raw
genetic_algorithm.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import print_function, division
import random
class GeneticAlgorithm(object):
def __init__(self, retain=0.2, random_select=0.05, mutation_rate=0.01,
population=1000, generate_function=None, fitness_function=None,
mutate_function=None, crossover_function=None):
#Initializations
self.generation = 0
self.retain = retain
self.random_select = random_select
self.mutation_rate = mutation_rate
if generate_function is not None:
self.generate = generate_function
if fitness_function is not None:
self.fitness = fitness_function
if mutate_function is not None:
self.mutate = mutate_function
if crossover_function is not None:
self.crossover = crossover_function
#Generate the initial population
self.size = population
self.population = []
for ii in range(self.size):
self.population.append(self.generate())
def evolve(self):
graded = self.grade(self.population)
parents_number = int(self.retain * self.size)
#Select the parents
parents = graded[:parents_number]
#Select other individuals at random
parents_size = parents_number + int(self.random_select * self.size)
while len(parents) < parents_size:
index = random.randint(parents_number, self.size-1)
if self.population[index] not in parents:
parents.append(self.population[index])
#Mutate
parents_size = len(parents)
mutations_number = int(self.mutation_rate * parents_size)
for i in range(mutations_number):
index = random.randint(0, parents_size-1)
self.mutate(parents[index])
#Crossover
self.population = [x for x in parents]
while len(self.population) < self.size:
parent_a = random.choice(parents)
parent_b = random.choice(parents)
if parent_a != parent_b:
child = self.crossover(parent_a, parent_b)
self.population.append(child)
self.generation += 1
def evolve_until(self, fitness=None, generation=None, update_each=1000, silent=False):
if not silent: self.print_banner(fitness, generation)
try:
while True:
self.evolve()
if generation and (generation <= self.generation):
break
graded = self.grade(self.population)
if fitness and (self.fitness(graded[0]) >= fitness):
break
if update_each and (self.generation % update_each == 0):
average_fitness = sum(map(self.fitness, graded)) / self.size
print("Generation %6s - Average fitness: %f%%" % (self.generation, average_fitness * 100))
except KeyboardInterrupt:
pass
solution = self.grade(self.population)[0]
if not silent:
print("\nEvolution stopped at generation %s." % self.generation)
print("Best solution found has fitness %f%%" % (self.fitness(solution)*100))
return solution
def print_banner(self, fitness, generation):
print(" Starting evolution ".center(79, "="))
print(" Simulation parameters ".center(79, "-"))
print("Population: %s" % self.size)
print("Individuals retained: %s%%" % (self.retain * 100))
print(" %s%% (to preserve diversity)" % (self.random_select * 100))
print("Mutation rate: %s%%" % (self.mutation_rate * 100))
print("-"*79)
if fitness: print("Target fitness: %s" % fitness)
if generation: print("Maximum generations: %s" % generation)
print("\nYou can stop the evolution by pressing CTRL+C.")
print("-"*79)
def grade(self, population):
graded = [(self.fitness(genome), genome) for genome in population]
graded = [item[1] for item in sorted(graded, reverse=True)]
return graded
def generate(self):
pass
def fitness(self, genome):
pass
def mutate(self, genome):
pass
def crossover(self, parent_a, parent_b):
pass
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment