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
3 years ago
4.2 kB
4
Indexable
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('headphones', 150, 160), Thing('coffee mug', 60, 350), Thing('notepad', 40, 333), 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)}")