I am tryin my first gentic alorithm to solve the knpsack problem. However, my code returns a list of items that exceeds the wight limit of the knapsack
I have followed along and used the code from this tutorial
from collections import namedtuple
from functools import partial
from random import choices, randint, randrange, random
from typing import List, Callable, Tuple
Genome = List[int]
Population = List[Genome]
FitnessFunc = Callable[[Genome], int]
PopulateFunc = Callable[[], Population]
SelectionFunc = Callable[[Population, FitnessFunc], Tuple[Genome, Genome]]
CrossoverFunc = Callable[[Genome, Genome], Tuple[Genome, Genome]]
MutationFunc = Callable[[Genome], Genome]
Thing = namedtuple('Thing', ['name', 'value', 'weight'])
things = [
Thing('Laptop', 500, 2200),
Thing('Headphones', 150, 160),
Thing('Coffee Mug', 60, 350),
Thing('Notepad', 40, 333),
Thing('Water Bottle', 30, 192),
]
more_things = [
Thing('Mints', 5, 25),
Thing('Socks', 10, 38),
Thing('Tissues', 15, 80),
Thing('Phone', 500, 200),
Thing('Baseball Cap', 100, 70)
]
def generate_genome(length: int) -> Genome:
'''
This function generates the genome of the individual as a set of binary digits representing the presence or absence of a trait in the individual
:param length:
:return:
'''
return choices([0, 1], k=length)
def generate_population(size: int, genome_length: int) -> Population:
'''
Creates a population of the specified number of individuals with different genome sequences
:param size:
:param genome_length:
:return:
'''
return [generate_genome(genome_length) for _ in range(size)]
def fitness(genome: Genome, things: [Thing], weight_limit: int) -> int:
'''
This function will evaluate the fitness of each genome combination and present it as a numerical value
:param genome:
:param things:
:param weight_limit:
:return:
'''
if len(genome) != len(things):
raise ValueError("Genome and things must be of the same length")
weight = 0
value = 0
for i, thing in enumerate(things):
if genome[i] == 1:
weight += thing.weight
value += thing.value
if weight > weight_limit:
return 0
return value
def selection_pair(population: Population, fitness_func: FitnessFunc) -> Population:
return choices(
population=population,
weights=[fitness_func(genome) for genome in population],
k=2
)
def single_point_crossover(a: Genome, b: Genome) -> Tuple[Genome, Genome]:
'''
This function here will splice the different parts oft he genome of the parents in order to create the genome of the offspring
:param a:
:param b:
:return:
'''
# the single point crossover function can only work if the genomes are the same length so we need to chack that
if len(a) != len(b):
raise ValueError("Genomes a and b must be of the same length")
# If the genome is less than 2 long, we just leave it alone
length = len(a)
if length < 2:
return a, b
p = randint(1, length - 1)
return a[0:p] + b[p:], b[0:p] + a[p:]
def mutation(genome: Genome, num: int = 1, probability: float = 0.5) -> Genome:
'''
Creates a statistical probability of genes mutating randomly
:param genome:
:param num:
:param probability:
:return:
'''
# We choose a random index, and if random returns a number higher than the probability, the genome sequence will not mutate
for _ in range(num):
index = randrange(len(genome))
genome[index] = genome[index] if random() > probability else abs(genome[index] - 1)
return genome
def run_evolution(
populate_func: PopulateFunc,
fitness_func: FitnessFunc,
fitness_limit: int,
selection_func: SelectionFunc = selection_pair,
crossover_func: CrossoverFunc = single_point_crossover,
mutation_func: MutationFunc = mutation,
generation_limit: int = 100,
) -> Tuple[Population, int]:
'''
runs the actual evolution of the species
:param populate_func:
:param fitness_func:
:param fitness_limit:
:param selection_func:
:param crossover_func:
:param mutation_func:
:param generation_limit:
:return:
'''
population = populate_func()
for i in range(generation_limit):
population = sorted(
population,
key = lambda genome: fitness_func(genome),
reverse = True
)
# stop the evolution when the genomes are past the fitness threshhold
if fitness_func(population[0]) >= fitness_limit:
break
next_generation = population[0:2]
for j in range(int(len(population) / 2) - 1):
parents = selection_func(population, fitness_func)
offspring_a, offspring_b = crossover_func(parents[0], parents[1])
offspring_a = mutation_func(offspring_a)
offspring_b = mutation_func(offspring_b)
next_generation += [offspring_a, offspring_b]
population = next_generation
population = sorted(
population,
key= lambda genome: fitness_func(genome),
reverse=True
)
return population, i
population, generations = run_evolution(
populate_func= partial(
generate_population, size= 10, genome_length= len(things)
),
fitness_func= partial(
fitness, things=things, weight_limit = 3000
),
fitness_limit=740,
generation_limit= 100
)
def genome_to_things(genome: Genome, things: [Thing]) -> [Thing]:
result = []
for i, thing in enumerate(things):
if genome[1] == 1:
result += [thing.name]
return result
print(f"number of generations: {generations}")
print(f"best solution: {genome_to_things(population[0], things)}")
I have tried following the tutorial as closely as possible and copid everything as closely as I can. However, my results end up including all items which makes it exceed the wight limit.
I am quite new to this and this is the first time I try coding a genetic algorithm, I am not sure what I am doing wrong