# knapsack problem - GA

line 142, in <module> print(f"best solutions: {genome_to_things(population[0], things)}") line 136, in genome_to_things result += [thing.name] NameError: name 'thing' is not defined. Did you mean: 'things'?
unknown
python
2 years ago
4.2 kB
4
Indexable
Never
from collections import namedtuple
from functools import partial
from random import choices, randint, randrange, random
from typing import List, Callable, Tuple
import time

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('coffee mug', 60, 350),
Thing('water bottle', 30, 192),
]

more_things = [
Thing('wfrp 2ed', 200, 2000),
Thing('socks', 10, 38),
Thing('tissues', 15, 60),
Thing('wet toilet paper', 120, 160),
Thing('painkillers', 80, 70),
] + things

def generate_genome(length: int) -> Genome:
return choices([0, 1], k=length)

def generate_population(size: int, genome_length: int) -> Population:
return [generate_genome(genome_length) for _ in range (size)]

def fitness(genome: Genome, things: [Thing], weight_limit: int) -> int:
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]:
if len(a) != len(b):
raise ValueError('Genomes a and b must be of the same length')

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:
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]:
population = populate_func()

for i in range(generation_limit):
population = sorted(
population,
key=lambda genome: fitness_func(genome),
reverse=True
)

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

start=time.time()
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,
)
end=time.time()

def genome_to_things(genome: Genome, things: [Thing]) -> [Thing]:
result= []
for i, things in enumerate(things):
if genome[i] == 1:
result += [thing.name]

return result

print(f"number of generations: {generations}")
print(f"time: {end - start}s")
print(f"best solutions: {genome_to_things(population[0], things)}")