#!/usr/bin/python3 # -*- coding: utf-8 -*- """ Knapsack problem """ # %% import sys import string import random from typing import TypedDict class Individual(TypedDict): genome: str fitness: int Population = list[Individual] def initialize_individual(genome: str, fitness: int) -> Individual: return {"genome": genome, "fitness": fitness} def initialize_pop(bitlen: int, pop_size: int) -> Population: population: Population = [] for _ in range(pop_size): genome = "".join(random.choice("01") for _ in range(bitlen)) individual = initialize_individual(genome=genome, fitness=0) population.append(individual) return population def recombine_pair(parent1: Individual, parent2: Individual) -> Population: place = random.choice(range(len(parent1["genome"]))) child1_genome = parent1["genome"][:place] + parent2["genome"][place:] child2_genome = parent2["genome"][:place] + parent1["genome"][place:] child1 = initialize_individual(genome=child1_genome, fitness=0) child2 = initialize_individual(genome=child2_genome, fitness=0) return [child1, child2] def recombine_group(parents: Population, recombine_rate: float) -> Population: children: Population = [] for ipair in range(0, len(parents) - 1, 2): if random.random() < recombine_rate: child1, child2 = recombine_pair( parent1=parents[ipair], parent2=parents[ipair + 1] ) else: child1, child2 = parents[ipair], parents[ipair + 1] children.extend([child1, child2]) return children def mutate_individual(parent: Individual, mutate_rate: float) -> Individual: new_genome = "".join( [ (random.choice("01") if random.random() < mutate_rate else ch) for ch in parent["genome"] ] ) mutant = initialize_individual(genome=new_genome, fitness=0) return mutant def mutate_group(children: Population, mutate_rate: float) -> Population: mutants: Population = [] for child in children: mutants.append(mutate_individual(parent=child, mutate_rate=mutate_rate)) return mutants def genotype_phenotype_decoder( individual: Individual, bitlen: int, max_weight: int, knapsack_values: list[int], knapsack_weights: list[int], ) -> tuple[int, int]: running_weight = 0 running_total_value = 0 for x in range(0, bitlen): if individual["genome"][x] == "1" and max_weight >= ( running_weight + knapsack_weights[x] ): running_weight += knapsack_weights[x] running_total_value += knapsack_values[x] return running_weight, running_total_value def evaluate_individual( knapsack_values: list[int], knapsack_weights: list[int], max_weight: int, bitlen: int, individual: Individual, ) -> None: individual["fitness"] = genotype_phenotype_decoder( individual=individual, bitlen=bitlen, max_weight=max_weight, knapsack_weights=knapsack_weights, knapsack_values=knapsack_values, )[1] def evaluate_group( knapsack_values: list[int], knapsack_weights: list[int], max_weight: int, bitlen: int, individuals: Population, ) -> None: for ind_index in range(len(individuals)): evaluate_individual( knapsack_values, knapsack_weights, max_weight, bitlen, individuals[ind_index], ) def rank_group(individuals: Population) -> None: individuals.sort(key=lambda ind: ind["fitness"], reverse=True) def parent_select(individuals: Population, number: int) -> Population: parents: Population = [] fitnesses = [i["fitness"] for i in individuals] try: parents = random.choices(individuals, fitnesses, k=number) except: parents = random.choices(individuals, k=number) return parents def survivor_select(individuals: Population, pop_size: int) -> Population: return individuals[:pop_size] def evolve( knapsack_values: list[int], knapsack_weights: list[int], bitlen: int, max_weight: int, pop_size: int, ) -> Population: population = initialize_pop(bitlen=bitlen, pop_size=pop_size) evaluate_group( knapsack_values=knapsack_values, knapsack_weights=knapsack_weights, max_weight=max_weight, bitlen=bitlen, individuals=population, ) rank_group(individuals=population) best_fitness = population[0]["fitness"] perfect_fitness = sum(knapsack_values) counter = 0 no_improvement = 0 while best_fitness < perfect_fitness and counter <= 4000 and no_improvement < 500: print(population) counter += 1 no_improvement += 1 parents = parent_select(individuals=population, number=pop_size) children = recombine_group(parents=parents, recombine_rate=0.8) mutate_rate = (1 - (best_fitness / perfect_fitness)) / 5 mutants = mutate_group(children=children, mutate_rate=mutate_rate) evaluate_group( knapsack_values=knapsack_values, knapsack_weights=knapsack_weights, max_weight=max_weight, bitlen=bitlen, individuals=mutants, ) everyone = population + mutants rank_group(individuals=everyone) population = survivor_select(individuals=everyone, pop_size=pop_size) if best_fitness != population[0]["fitness"]: no_improvement = 0 best_fitness = population[0]["fitness"] print("Iteration number", counter, "with best individual", population[0]) if no_improvement >= 200: print("Data is not improving at a fast enough rate, program done evolving.") print("Number of iterations - ", counter) print("Items given and weights below it") print(knapsack_values) print(knapsack_weights) print("Items/values in knapsack.") # TODO turn this into a decoder function, called in eval to? running_weight, running_total_value = genotype_phenotype_decoder( individual=population[0], bitlen=bitlen, max_weight=max_weight, knapsack_weights=knapsack_weights, knapsack_values=knapsack_values, ) print() print( "All items (the best possible fitness, without weight constraint:", perfect_fitness, ) print("Total Value in knapsack - ", running_total_value) print( "Weight of knapsack is ", running_weight, ". The max weight you gave is ", max_weight, ) return population def main() -> None: yesno = str(input("Do you want to input custom data?(y/n)?\n")) if yesno == "y": knapsack_values = [] knapsack_weights = [] num_items = int(input("How many items for knapsack?\n")) for _ in range(0, num_items): item_value = int(input("Give item value?\n")) item_weight = int(input("Give item weight?\n")) knapsack_values.append(item_value) knapsack_weights.append(item_weight) max_weight = int(input("What is max weight of knapsack?\n")) POP_SIZE = int(input("How many individuals would you like to evolve?\n")) population = evolve( knapsack_values=knapsack_values, knapsack_weights=knapsack_weights, bitlen=len(knapsack_values), max_weight=max_weight, pop_size=POP_SIZE, ) else: knapsack_values = [12, 10, 8, 14, 20, 18, 24] knapsack_weights = [2, 3, 1, 4, 6, 5, 7] max_weight = 20 POP_SIZE = 4 population = evolve( knapsack_values=knapsack_values, knapsack_weights=knapsack_weights, bitlen=len(knapsack_values), max_weight=max_weight, pop_size=POP_SIZE, ) if __name__ == "__main__": main()