#!/usr/bin/python3 # -*- coding: utf-8 -*- # %% """ n-queens We wrote this is class, as a group. """ # %% import sys import string import random from typing import TypedDict class Individual(TypedDict): genome: list[int] fitness: int Population = list[Individual] def initialize_individual(genome: list[int], fitness: int) -> Individual: return {"genome": genome, "fitness": fitness} def initialize_pop(board_size: int, pop_size: int) -> Population: population: Population = [] for _ in range(pop_size): genome = list(range(1, board_size + 1)) # genome = [] # for num in range(board_size): # genome.append(num + 1) random.shuffle(genome) 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 child1_genome = parent1["genome"][:place] for q in parent2["genome"][place:]: if q not in child1_genome: child1_genome.append(q) for q in parent2["genome"][:place]: if q not in child1_genome: child1_genome.append(q) # Child2 child2_genome = parent2["genome"][:place] for q in parent1["genome"][place:]: if q not in child2_genome: child2_genome.append(q) for q in parent1["genome"][:place]: if q not in child2_genome: child2_genome.append(q) 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: point1 = random.randint(0, len(parent["genome"]) - 1) point2 = random.randint(0, len(parent["genome"]) - 1) genome = parent["genome"].copy() genome[point1], genome[point2] = genome[point2], genome[point1] mutant = initialize_individual(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 evaluate_individual(board_size: int, individual: Individual) -> None: # This is overly severe, # double-counting multiple simultaneous conflicts. drama_count = 0 for iq1 in range(board_size): for iq2 in range(iq1 + 1, board_size): if abs(iq2 - iq1) == abs( individual["genome"][iq1] - individual["genome"][iq2] ): drama_count += 1 individual["fitness"] = board_size - drama_count def evaluate_group(board_size: int, individuals: Population) -> None: for ind_index in range(len(individuals)): evaluate_individual(board_size, 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] parents = random.choices(individuals, fitnesses, k=number) return parents def survivor_select(individuals: Population, pop_size: int) -> Population: return individuals[:pop_size] def evolve(board_size: int, pop_size: int) -> Population: population = initialize_pop(board_size=board_size, pop_size=pop_size) evaluate_group(board_size=board_size, individuals=population) rank_group(individuals=population) best_fitness = population[0]["fitness"] perfect_fitness = board_size counter = 0 print("\nBest individual in the initial population:") print(population[0]) while best_fitness < perfect_fitness: counter += 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(board_size=board_size, individuals=mutants) everyone = population + mutants rank_group(individuals=everyone) population = survivor_select(individuals=everyone, pop_size=pop_size) if best_fitness != population[0]["fitness"]: best_fitness = population[0]["fitness"] print("\nIteration number", counter, "with best individual", population[0]) csv_writer.writerow( [counter, population[0]["genome"], population[0]["fitness"], mutate_rate] ) return population if __name__ == "__main__": import json import csv import matplotlib.pyplot as plt import pandas as pd # %% csv_file = open("logfile.csv", "w", newline="") csv_writer = csv.writer(csv_file) data_to_log = ["generation", "genome", "fitness", "mutation_rate"] csv_writer.writerow(data_to_log) if len(sys.argv) == 3: with open(file=sys.argv[1]) as finput: obj_name = finput.readlines() OBJECTIVE = int(obj_name[0].strip()) POP_SIZE = int(obj_name[1]) with open(file=sys.argv[2], mode="w") as foutput: population = evolve(board_size=OBJECTIVE, pop_size=POP_SIZE) foutput.write(json.dumps(population) + "\n") else: BOARD_SIZE = int(input("What size board you like to evolve?\n")) POP_SIZE = int(input("How many individuals would you like to evolve?\n")) population = evolve(board_size=BOARD_SIZE, pop_size=POP_SIZE) print("done") csv_file.close() # just remember to close the file # %% data = pd.read_csv("logfile.csv") generations = data["generation"] fitness = data["fitness"] mutation_rate = data["mutation_rate"] # %% # Create a figure and axis plt.subplots(1, figsize=(10, 10)) plt.plot(generations, fitness) # Add a title plt.title("Fitness Across Generations") # Display the plot plt.show() # %% # Create a figure and axis plt.subplots(1, figsize=(10, 10)) plt.plot(generations, mutation_rate) # Add a title plt.title("Mutation Rate Across Generations") # Display the plot plt.show()