52 KiB

Raw Permalink Blame History

Lab 2 - Genetic Algorithms¶

Objective¶

The goal of this laboratory session is to become familiar with the operation and tuning of a genetic algorithm, using the knapsack problem as a running example.

Please double-click a cell to edit it.

Before submitting your solution, please fill in the following information:

Name	Student ID	Date
name and surname	student ID number	date

Please upload the completed file (you can export it to html, pdf or ipynb) to your repository.

Submission deadline: Tuesday, November 10th, 2026

Because every submitted report has to be reviewed, please make sure to respect the deadline.

Task Context¶

The task is to solve the knapsack problem: we are given a set of items, each with a specified weight and value. The goal is to select a subset of items that maximizes the total value, subject to the constraint that the total weight must not exceed the backpack's capacity.

The knapsack problem is NP-hard: with 100 items there are $2^{100}$ possible subsets - far too many to check exhaustively. This makes it a perfect playground for a metaheuristic such as a genetic algorithm, which searches the solution space intelligently instead of exhaustively.

Note on seeds¶

Throughout this notebook the seed ensures that the same hyperparameters always produce the same random run (population initialization, selection, crossover, mutation, etc.). Thanks to this, comparing hyperparameter variants happens under identical random conditions, so differences in the results better reflect the actual influence of the parameter rather than the random luck of one particular run.

The multi-seed option runs the same variant several times with different seeds and reports the mean, standard deviation and min/max. A single seed can happen to be atypical; running many seeds shows the stability of the result and the algorithm's true sensitivity to randomness — which matters far more for drawing conclusions than a single number from a single lucky (or unlucky) draw.

Part 1: Defining the Problem¶

Knapsack problem: we are given a set of items, each with a specified weight and value. The goal is to select a subset of items maximizing the total value, while the total weight must not exceed the backpack's capacity.

Problem data - 100 items.

Run the cell below to define the problem data. The items are grouped into thematic categories, from electronics, through food and clothing, to more exotic gear.

In [ ]:

import random
import copy
import matplotlib.pyplot as plt
import numpy as np

# Fix the random seed so results are reproducible
random.seed(666)

# --- PROBLEM DATA ---
# 100 items: (name, weight_kg, value_pln)
items = [
    # --- Electronics and gadgets ---
    ("Gaming_laptop",        3.0,  800),
    ("Powerbank_XXL",        1.2,  220),
    ("Solar_charger",        0.8,  170),
    ("BT_headphones",        0.2,  100),
    ("Smartwatch",           0.1,  180),
    ("Pocket_drone",         0.9,  450),
    ("E-reader",             0.3,  200),
    ("Bluetooth_speaker",    0.5,  130),
    ("GoPro_camera",         0.4,  500),
    ("3m_cable_useless",     0.1,   10),
    # --- Food and drinks ---
    ("Gummy_bears",          0.3,   40),
    ("Protein_bar",          0.2,   35),
    ("Instant_coffee",       0.4,   90),
    ("Tea_100bags",          0.3,   60),
    ("Dark_chocolate",       0.2,   50),
    ("Dried_mango",          0.3,   70),
    ("Water_5L",             5.0,  300),
    ("Water_1.5L",           1.5,  150),
    ("Stew_can",             0.8,  100),
    ("Army_MRE",             1.0,  200),
    ("Aged_cheese",          0.5,   80),
    ("Oat_cookies",          0.3,   45),
    ("Fudge_sweets",         0.2,   30),
    ("Mixed_nuts",           0.4,   95),
    ("Classic_jerky_sticks", 0.3,   70),
    # --- Clothing ---
    ("Rain_jacket",          0.6,  300),
    ("Fleece_pullover",      0.8,  250),
    ("Pompon_beanie",        0.1,   60),
    ("Wool_socks",           0.1,   40),
    ("Trekking_gloves",      0.1,   55),
    ("Spare_tshirt",         0.2,   30),
    ("Cargo_pants",          0.5,  120),
    ("Camping_sandals",      0.6,   80),
    ("Multifunction_bandana",0.05,  25),
    ("Emergency_poncho",     0.2,   90),
    # --- Tools and survival ---
    ("Swiss_army_knife",     0.2,  200),
    ("Headlamp",             0.15, 180),
    ("Fire_striker",         0.1,  100),
    ("Cord_50m",             0.8,  110),
    ("Duct_tape",            0.3,  120),
    ("Compass",              0.1,   90),
    ("Paper_map",            0.1,   80),
    ("Rescue_whistle",       0.02,  70),
    ("Signal_mirror",        0.05,  60),
    ("Folding_shovel",       0.7,  130),
    # --- Camping and sleep ---
    ("Tent_2person",         3.5,  500),
    ("Down_sleeping_bag",    1.5,  400),
    ("Foam_sleeping_pad",    0.4,  150),
    ("Ultralight_hammock",   0.5,  200),
    ("Inflatable_pillow",    0.1,   60),
    ("Head_mosquito_net",    0.05,  40),
    ("Tarp_3x3",             0.8,  160),
    # --- Hygiene and health ---
    ("First_aid_kit",        0.5,  250),
    ("Sunscreen",            0.2,   60),
    ("Mosquito_repellent",   0.15,  50),
    ("Dr_Bronner_soap",      0.3,   40),
    ("Travel_toothbrush",    0.05,  15),
    ("Microfiber_towel",     0.2,   70),
    ("Toilet_paper",         0.3,   20),
    ("Water_purification_tabs", 0.05, 100),
    # --- Fun and hobbies ---
    ("Book_1000pages",       0.8,  150),
    ("Playing_cards",        0.1,   50),
    ("Frisbee",              0.2,   30),
    ("Binoculars_10x42",     0.7,  250),
    ("Travel_journal",       0.2,   40),
    ("Soprano_ukulele",      0.6,  120),
    ("Rubiks_cube",          0.1,   35),
    ("Magnetic_chess",       0.3,   60),
    # --- Field kitchen ---
    ("Gas_stove",            0.4,  200),
    ("Gas_cartridge",        0.3,   80),
    ("Titanium_mess_tin",    0.2,  180),
    ("Thermal_mug",          0.3,  100),
    ("Folding_cutlery",      0.1,   50),
    ("Tea_strainer",         0.02,  10),
    # --- Unusual but useful ---
    ("Selfie_stick",         0.2,   25),
    ("Sunglasses",           0.05, 150),
    ("Earplugs",             0.01,  30),
    ("Trash_bags_10x",       0.1,   15),
    ("Paperclips_XXL_set",   0.05,  5),
    ("Rubber_bands",         0.02,  5),
    # --- Odd but someone packs them ---
    ("Lucky_mascot",         0.3,   10),
    ("U_travel_pillow",      0.3,   80),
    ("Rubber_hot_water_bottle", 0.4, 60),
    ("Folding_stool",        1.2,  140),
    ("Trekking_umbrella",     0.5,   70),
    ("Inflatable_flamingo",  0.4,   20),
    ("NRC_emergency_blanket", 0.05, 90),
    ("Waterproof_bag",       0.2,  110),
    # --- Photography ---
    ("Mirrorless_camera",    1.5,  700),
    ("Zoom_lens",            0.8,  400),
    ("Carbon_tripod",        1.0,  300),
    ("Polarizing_filter",    0.05, 100),
    ("SD_card_256GB",        0.01, 120),
    # --- Premium and luxury ---
    ("Garmin_watch",         0.08, 350),
    ("Filtering_bottle",     0.3,  180),
    ("Merino_underwear",     0.15, 130),
    ("Merino_socks_2x",      0.15, 100),
    ("Trekking_poles",       0.5,  160),
    ("Boot_gaiters",         0.2,   70),
    ("Inflatable_pouf",      0.3,   50),
]

BACKPACK_CAPACITY = 25  # kg

# Display the data
print(f"Number of items: {len(items)}")
print(f"Backpack capacity: {BACKPACK_CAPACITY} kg")
print(f"Total weight of all items: {sum(p[1] for p in items)} kg")
print(f"Total value of all items: {sum(p[2] for p in items)} PLN")

Part 2: Implementing the Genetic Algorithm¶

Below are the functions implementing the individual stages of the genetic algorithm.

2.1 Generating the initial population¶

Each individual is a list of 0s and 1s of length 100 (the number of items). A value of 1 means the item is packed into the backpack. This binary encoding is the genotype; the packed backpack is the phenotype.

In [ ]:

def generate_population(population_size, chromosome_length):
    # Initialize a random starting population (binary 0/1 chromosomes).
    population = []
    for _ in range(population_size):
        individual = [random.randint(0, 1) for _ in range(chromosome_length)]
        population.append(individual)
    return population

In [ ]:

def calculate_fitness(individual, items, capacity):
    # Objective function: maximize total value; overweight solutions get fitness 0.
    weight = 0
    value = 0
    for i in range(len(individual)):
        if individual[i] == 1:
            weight += items[i][1]
            value += items[i][2]
    if weight > capacity:
        return 0
    return value

In [ ]:

def calculate_weight(individual, items):
    weight = 0
    for i in range(len(individual)):
        if individual[i] == 1:
            weight += items[i][1]
    return weight

2.2 Selection methods¶

For the experiments we use three selection methods: roulette wheel, tournament, and rank-based selection.

Selection is the mechanism that decides which individuals become parents of the next generation. Each method strikes a different balance between exploiting the best solutions and maintaining population diversity:

Roulette wheel — selection probability proportional to fitness; fast but easily dominated by a few very strong individuals.
Tournament — pick a small random group and take its best member; robust and effective even with large populations.
Rank-based — sort by fitness and select proportionally to rank; prevents a single super-individual from taking over the population.

In [ ]:

def roulette_selection(population, fitness_values):
    # Roulette wheel selection — each individual has a selection
    # probability proportional to its fitness.
    total_fitness = sum(fitness_values)
    if total_fitness == 0:
        # If all fitness values are 0, pick randomly
        return random.choice(population)

    # Compute probabilities
    probabilities = [f / total_fitness for f in fitness_values]

    # Draw based on the probability distribution
    r = random.random()
    total = 0
    for i, p in enumerate(probabilities):
        total += p
        if total >= r:
            return population[i]
    return population[-1]


def tournament_selection(population, fitness_values, tournament_size=3):
    # Tournament selection — draw a group of individuals, pick the best of the group.

    # Draw the indices of the tournament participants
    indices = random.sample(range(len(population)), tournament_size)

    # Find the best individual in the tournament
    best_index = indices[0]
    for idx in indices[1:]:
        if fitness_values[idx] > fitness_values[best_index]:
            best_index = idx

    return population[best_index]


def rank_selection(population, fitness_values):
    # Rank-based selection — sort by fitness, assign ranks, select proportionally to rank.

    # Create (index, fitness) pairs and sort ascending
    sorted_pairs = sorted(enumerate(fitness_values), key=lambda x: x[1])

    # Assign ranks: worst = 1, best = N
    ranks = [0] * len(population)
    for rank, (index, _) in enumerate(sorted_pairs, start=1):
        ranks[index] = rank

    # Select proportionally to rank (like in roulette wheel)
    total_ranks = sum(ranks)
    r = random.random()
    total = 0
    for i, rank in enumerate(ranks):
        total += rank / total_ranks
        if total >= r:
            return population[i]
    return population[-1]

2.3 Genetic operators¶

Specifically, crossover (for the exercises we use single-point crossover) and mutation (bit-flip).

Crossover recombines genetic material from two parents, allowing the algorithm to combine the good "building blocks" of different solutions. Mutation introduces random changes gene by gene — it is the primary source of new genetic material and the main defence against getting stuck in a local optimum. Note that the mutation probability applies per gene, not per individual: with a chromosome of 100 genes and p_mutation = 0.05, on average 5 genes of every child will flip.

In [ ]:

def crossover(parent_a, parent_b, p_crossover):
    # Single-point crossover: exchange chromosome fragments between parents.
    if random.random() > p_crossover:
        # No crossover – offspring are copies of the parents
        return copy.copy(parent_a), copy.copy(parent_b)

    # Draw the crossover point (from 1 to N-1)
    point = random.randint(1, len(parent_a) - 1)

    child_a = parent_a[:point] + parent_b[point:]
    child_b = parent_b[:point] + parent_a[point:]

    return child_a, child_b

In [ ]:

def mutate(individual, p_mutation):
    # Bit-flip mutation. Each gene flips (0->1 or 1->0) with probability p_mutation.

    mutated = copy.copy(individual)
    for i in range(len(mutated)):
        if random.random() < p_mutation:
            mutated[i] = 1 - mutated[i]
    return mutated

2.4 Building the genetic algorithm¶

Parameters:
----------
items              : list of tuples (name, weight, value)
capacity           : maximum backpack weight
population_size    : initial population size
n_iterations       : how many generations to run
p_crossover        : crossover probability (0.0 - 1.0)
p_mutation         : per-gene mutation probability (0.0 - 1.0)
n_pairs            : how many parent pairs take part in reproduction
offspring_per_pair : how many children are produced from one pair (1 or 2)
n_remove           : how many weakest individuals are removed from the population
selection_method   : "roulette", "tournament" or "rank"
tournament_size    : tournament size (only for tournament selection)
elitism            : whether to preserve the best individual (True/False)
seed               : random seed (for reproducibility)

Population dynamics:
-------------------
new = n_pairs * offspring_per_pair
change = new - n_remove
  change > 0  -> population grows
  change = 0  -> population is stable
  change < 0  -> population shrinks

Returns:
--------
best_individual   : 0/1 list – the best solution found
best_fitness      : fitness value of the best solution
best_history      : best fitness in every generation
avg_history       : average fitness in every generation
size_history      : population size in every generation

In [ ]:

def genetic_algorithm(
    items,
    capacity,
    population_size=50,
    n_iterations=100,
    p_crossover=0.8,
    p_mutation=0.05,
    n_pairs=10,
    offspring_per_pair=2,
    n_remove=10,
    selection_method="tournament",
    tournament_size=3,
    elitism=True,
    seed=None
):
    # seed fixes the reproducibility of the draws
    # (the same sequence of results for the same parameters).
    if seed is not None:
        random.seed(seed)

    # Chromosome length = number of available items.
    length = len(items)

    # --- STEP 1: Initialize the population ---
    population = generate_population(population_size, length)

    # Compute the population size change per iteration
    new_per_iteration = n_pairs * offspring_per_pair
    change = new_per_iteration - n_remove
    print(f"  New offspring/iter: {new_per_iteration}, "
          f"removed/iter: {n_remove}, "
          f"size change: {'+' if change > 0 else ''}{change}/iter")

    # History for the plots
    best_history = []
    avg_history = []
    size_history = []

    # Remember the global best
    global_best = None
    global_best_f = 0

    for iteration in range(n_iterations):

        # Safety net: the population cannot drop below 2
        if len(population) < 2:
            print(f"  Population died out at iteration {iteration}!")
            break

        # --- STEP 2: Evaluate fitness ---
        fitness_values = [calculate_fitness(o, items, capacity) for o in population]

        # Record statistics
        best_f = max(fitness_values)
        avg_f = sum(fitness_values) / len(fitness_values)
        best_history.append(best_f)
        avg_history.append(avg_f)
        size_history.append(len(population))

        # Update the global best
        if best_f > global_best_f:
            idx_best = fitness_values.index(best_f)
            global_best = copy.copy(population[idx_best])
            global_best_f = best_f

        # --- STEP 3: Create offspring ---
        # This part depends the most on the hyperparameters:
        # selection_method, p_crossover, p_mutation, n_pairs, offspring_per_pair.
        offspring = []
        for _ in range(n_pairs):

            # Parent selection
            if selection_method == "roulette":
                parent_a = roulette_selection(population, fitness_values)
                parent_b = roulette_selection(population, fitness_values)
            elif selection_method == "tournament":
                parent_a = tournament_selection(population, fitness_values, tournament_size)
                parent_b = tournament_selection(population, fitness_values, tournament_size)
            elif selection_method == "rank":
                parent_a = rank_selection(population, fitness_values)
                parent_b = rank_selection(population, fitness_values)
            else:
                raise ValueError(f"Unknown selection method: {selection_method}")

            # Crossover (always yields 2 children)
            child_a, child_b = crossover(parent_a, parent_b, p_crossover)

            # Mutation
            child_a = mutate(child_a, p_mutation)
            child_b = mutate(child_b, p_mutation)

            # Take 1 or 2 children from the pair
            offspring.append(child_a)
            if offspring_per_pair == 2:
                offspring.append(child_b)

        # --- STEP 4: Remove individuals ---
        # How many to actually remove (no more than population - 1)
        actually_removed = min(n_remove, len(population) - 1)

        if elitism:
            # KEY POINT: elitism=True protects good individuals (we remove the weakest).
            pairs = list(zip(fitness_values, population))
            pairs.sort(key=lambda x: x[0])
            pairs = pairs[actually_removed:]
            population = [individual for (_, individual) in pairs]
        else:
            # KEY POINT: elitism=False does not protect the leader;
            # random removal may lose the best solution.
            indices_to_remove = set(random.sample(range(len(population)), actually_removed))
            population = [
                individual for idx, individual in enumerate(population)
                if idx not in indices_to_remove
            ]
        # --- STEP 5: Add the offspring ---
        population.extend(offspring)

        # --- STEP 6: Elitism ---
        if elitism and global_best is not None:
            new_fitness_values = [calculate_fitness(o, items, capacity)
                                  for o in population]
            if max(new_fitness_values) < global_best_f:
                # Replace the worst individual with the global best
                min_idx = new_fitness_values.index(min(new_fitness_values))
                population[min_idx] = copy.copy(global_best)

    # Final evaluation
    fitness_values = [calculate_fitness(o, items, capacity) for o in population]
    best_idx = fitness_values.index(max(fitness_values))
    best_individual = population[best_idx]
    best_fitness = fitness_values[best_idx]

    # The global best overrides the result only in the elitist variant.
    if elitism and global_best_f > best_fitness:
        best_individual = global_best
        best_fitness = global_best_f

    return (best_individual, best_fitness,
            best_history, avg_history, size_history)

2.5 Visualization helpers¶

In [ ]:

def display_result(individual, items, capacity):
    # Displays the backpack contents for a given individual.
    print(f"\n{'='*55}")
    print(f"{'BACKPACK CONTENTS':^55}")
    print(f"{'='*55}")
    print(f"{'Nr':<5}{'Name':<22}{'Weight (kg)':<12}{'Value (PLN)':<12}")
    print("-" * 51)

    total_weight = 0
    total_value = 0
    for i in range(len(individual)):
        if individual[i] == 1:
            name, weight, value = items[i]
            print(f"{i+1:<5}{name:<22}{weight:<12}{value:<12}")
            total_weight += weight
            total_value += value

    print("-" * 51)
    print(f"{'TOTAL':<27}{total_weight:<12.1f}{total_value:<12}")
    print(f"Backpack capacity: {capacity} kg")
    print(f"Utilization:       {total_weight:.1f}/{capacity} kg "
          f"({100*total_weight/capacity:.1f}%)")
    print(f"{'='*55}")


def plot_convergence(best_history, avg_history, title=""):
    # Convergence plot of the genetic algorithm.
    plt.figure(figsize=(10, 5))
    plt.plot(best_history, label="Best fitness", linewidth=2)
    plt.plot(avg_history, label="Average fitness", linewidth=1, alpha=0.7)
    plt.xlabel("Generation (iteration)")
    plt.ylabel("Fitness (backpack value)")
    plt.title(f"Genetic algorithm convergence{' – ' + title if title else ''}")
    plt.legend()
    plt.grid(True, alpha=0.3)
    plt.tight_layout()
    plt.show()


def plot_population_size(size_history, title=""):
    # Plot of the population size over time.
    plt.figure(figsize=(10, 3))
    plt.plot(size_history, label="Population size",
             linewidth=2, color="green")
    plt.xlabel("Generation (iteration)")
    plt.ylabel("Number of individuals")
    plt.title(f"Population size{' – ' + title if title else ''}")
    plt.legend()
    plt.grid(True, alpha=0.3)
    plt.tight_layout()
    plt.show()

Part 3: Running the Baseline Model¶

Run the algorithm with default parameters to obtain a reference point. In the baseline model: 10 parent pairs, 2 offspring per pair = 20 new individuals, we remove the 20 weakest → the population is stable (change = 0).

In [ ]:

# --- BASELINE MODEL ---
# 10 pairs × 2 offspring = 20 new, we remove 20 → stable population

individual, fitness, hist_best, hist_avg, hist_size = genetic_algorithm(
    items=items,
    capacity=BACKPACK_CAPACITY,
    population_size=50,
    n_iterations=200,
    p_crossover=0.8,
    p_mutation=0.05,
    n_pairs=10,
    offspring_per_pair=2,
    n_remove=20,
    selection_method="tournament",
    tournament_size=3,
    elitism=True,
    seed=666
)

print(f"\nBest fitness: {fitness} PLN")
print(f"Final population size: {hist_size[-1]}")
display_result(individual, items, BACKPACK_CAPACITY)
plot_convergence(hist_best, hist_avg, "Baseline model")

In [ ]:

# --- ANALYSIS SETTINGS: fixed seed + randomness ---
# FIXED_SEED: fair comparison between hyperparameter variants (same draws).
FIXED_SEED = 666
# RANDOM_SEEDS: assessing result stability and sensitivity to randomness.
RANDOM_SEEDS = list(range(10))


def run_variant(parameters, seed):
    # Common runner for all experiments — returns the metrics needed for analysis.
    _, fitness, hist_best, _, hist_size = genetic_algorithm(
        items=items,
        capacity=BACKPACK_CAPACITY,
        seed=seed,
        **parameters
    )
    return fitness, hist_best, hist_size[-1]


def statistics(values):
    # Basic statistics for the report: mean, std deviation and range [min, max].
    arr = np.array(values, dtype=float)
    return arr.mean(), arr.std(ddof=0), arr.min(), arr.max()


# --- EXPERIMENT 1: Mutation probability ---
mutation_rates = [0.001, 0.01, 0.05, 0.1, 0.3]
results_mutation_fixed = {}
results_mutation_random = {}

plt.figure(figsize=(12, 5))

for pm in mutation_rates:
    parameters = dict(
        population_size=50,
        n_iterations=200,
        p_crossover=0.8,
        p_mutation=pm,
        n_pairs=10,
        offspring_per_pair=2,
        n_remove=20,
        selection_method="tournament",
        elitism=True,
    )

    fitness_fixed, hist_best_fixed, _ = run_variant(parameters, FIXED_SEED)
    results_mutation_fixed[pm] = fitness_fixed

    random_fitness = [run_variant(parameters, s)[0] for s in RANDOM_SEEDS]
    mean, std, minimum, maximum = statistics(random_fitness)
    results_mutation_random[pm] = (mean, std, minimum, maximum)

    plt.plot(hist_best_fixed, label=f"p_mut={pm} (fixed seed={fitness_fixed})")

plt.xlabel("Generation")
plt.ylabel("Best fitness")
plt.title("Experiment 1: Effect of the mutation probability (fixed seed)")
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

print("\nSummary (fixed seed vs randomness):")
for pm in mutation_rates:
    fs = results_mutation_fixed[pm]
    mean, std, mn, mx = results_mutation_random[pm]
    print(
        f"  p_mutation={pm:<6} -> fixed seed, fitness: {fs:<5} | "
        f"random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}"
    )

Questions¶

Please answer the questions below.

1. How does the solution quality (fitness) change with very low, medium and high mutation rates?

(your answer here)

2. Which p_mutation value gives the best trade-off between exploration and result stability?

(your answer here)

3. Do the conclusions from the fixed seed agree with the multi-seed results (mean/std deviation)?

(your answer here)

In [ ]:

# --- EXPERIMENT 2: Crossover probability ---

crossover_rates = [0.0, 0.3, 0.6, 0.8, 1.0]
results_crossover_fixed = {}
results_crossover_random = {}

plt.figure(figsize=(12, 5))

for pc in crossover_rates:
    parameters = dict(
        population_size=50,
        n_iterations=200,
        p_crossover=pc,
        p_mutation=0.05,
        n_pairs=10,
        offspring_per_pair=2,
        n_remove=20,
        selection_method="tournament",
        elitism=True,
    )

    fitness_fixed, hist_best_fixed, _ = run_variant(parameters, FIXED_SEED)
    results_crossover_fixed[pc] = fitness_fixed

    random_fitness = [run_variant(parameters, s)[0] for s in RANDOM_SEEDS]
    mean, std, minimum, maximum = statistics(random_fitness)
    results_crossover_random[pc] = (mean, std, minimum, maximum)

    plt.plot(hist_best_fixed, label=f"p_cross={pc} (fixed seed={fitness_fixed})")

plt.xlabel("Generation")
plt.ylabel("Best fitness")
plt.title("Experiment 2: Effect of the crossover probability (fixed seed)")
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

print("\nSummary (fixed seed vs randomness):")
for pc in crossover_rates:
    fs = results_crossover_fixed[pc]
    mean, std, mn, mx = results_crossover_random[pc]
    print(
        f"  p_crossover={pc:<4} -> fixed seed, fitness: {fs:<5} | "
        f"random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}"
    )

Questions¶

Please answer the questions below.

4. Does increasing p_crossover improve the result, or does the effect fade beyond a certain point?

(your answer here)

5. How does the absence of crossover (p_crossover=0) affect convergence and the final fitness?

(your answer here)

6. For which p_crossover values are the results most stable across seeds?

(your answer here)

In [ ]:

# --- EXPERIMENT 3: Population size ---

population_sizes = [10, 30, 50, 100, 200]
results_population_fixed = {}
results_population_random = {}

plt.figure(figsize=(12, 5))

for ps in population_sizes:
    # Scale the replacement parameters proportionally to the population
    pairs = max(2, ps // 5)
    remove = pairs * 2  # stable population

    parameters = dict(
        population_size=ps,
        n_iterations=200,
        p_crossover=0.8,
        p_mutation=0.05,
        n_pairs=pairs,
        offspring_per_pair=2,
        n_remove=remove,
        selection_method="tournament",
        elitism=True,
    )

    fitness_fixed, hist_best_fixed, _ = run_variant(parameters, FIXED_SEED)
    results_population_fixed[ps] = fitness_fixed

    random_fitness = [run_variant(parameters, s)[0] for s in RANDOM_SEEDS]
    mean, std, minimum, maximum = statistics(random_fitness)
    results_population_random[ps] = (mean, std, minimum, maximum)

    plt.plot(hist_best_fixed, label=f"pop={ps} (fixed seed={fitness_fixed})")

plt.xlabel("Generation")
plt.ylabel("Best fitness")
plt.title("Experiment 3: Effect of the population size (fixed seed)")
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

print("\nSummary (fixed seed vs randomness):")
for ps in population_sizes:
    fs = results_population_fixed[ps]
    mean, std, mn, mx = results_population_random[ps]
    print(
        f"  population_size={ps:<4} -> fixed seed, fitness: {fs:<5} | "
        f"random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}"
    )

Questions¶

Please answer the questions below.

7. How does the population size affect the quality of the final solution?

(your answer here)

8. Does a larger population always help, or is there diminishing return in quality relative to computational cost?

(your answer here)

9. Which population size offers the best trade-off: fitness vs stability (std deviation) vs runtime?

(your answer here)

In [ ]:

# --- EXPERIMENT 4: Selection method ---

methods = ["roulette", "tournament", "rank"]
results_selection_fixed = {}
results_selection_random = {}

plt.figure(figsize=(12, 5))

for method in methods:
    parameters = dict(
        population_size=50,
        n_iterations=200,
        p_crossover=0.8,
        p_mutation=0.05,
        n_pairs=10,
        offspring_per_pair=2,
        n_remove=20,
        selection_method=method,
        elitism=True,
    )

    fitness_fixed, hist_best_fixed, _ = run_variant(parameters, FIXED_SEED)
    results_selection_fixed[method] = fitness_fixed

    random_fitness = [run_variant(parameters, s)[0] for s in RANDOM_SEEDS]
    mean, std, minimum, maximum = statistics(random_fitness)
    results_selection_random[method] = (mean, std, minimum, maximum)

    plt.plot(hist_best_fixed, label=f"{method} (fixed seed={fitness_fixed})")

plt.xlabel("Generation")
plt.ylabel("Best fitness")
plt.title("Experiment 4: Comparing selection methods (fixed seed)")
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

print("\nSummary (fixed seed vs randomness):")
for method in methods:
    fs = results_selection_fixed[method]
    mean, std, mn, mx = results_selection_random[method]
    print(
        f"  selection {method:<12} -> fixed seed, fitness: {fs:<5} | "
        f"random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}"
    )

Question¶

Please answer the question below.

10. Which selection method gives the highest fitness, and are the differences significant?

(your answer here)

In [ ]:

# --- EXPERIMENT 5: Population dynamics ---
# We test different combinations of the generational replacement parameters.
# Format: (description, n_pairs, offspring_per_pair, n_remove)

scenarios = [
    ("stable:    3 pairs×2, remove=6",  3, 2,  6),
    ("stable:  10 pairs×2, remove=20", 10, 2, 20),
    ("growing:  10 pairs×2, remove=5", 10, 2,  5),
    ("shrinking: 3 pairs×1, remove=6",  3, 1,  6),
    ("shrinking: 5 pairs×2, remove=15", 5, 2, 15),
]

results_dynamics_fixed = {}
results_dynamics_random = {}

fig, (ax1, ax2) = plt.subplots(2, 1, figsize=(12, 8), sharex=True)

for desc, np_, opp, nr in scenarios:
    parameters = dict(
        population_size=50,
        n_iterations=200,
        p_crossover=0.8,
        p_mutation=0.05,
        n_pairs=np_,
        offspring_per_pair=opp,
        n_remove=nr,
        selection_method="tournament",
        elitism=True,
    )

    fitness_fixed, hist_best_fixed, size_fixed = run_variant(parameters, FIXED_SEED)
    results_dynamics_fixed[desc] = (fitness_fixed, size_fixed)

    random_runs = [run_variant(parameters, s) for s in RANDOM_SEEDS]
    random_fitness = [x[0] for x in random_runs]
    random_sizes = [x[2] for x in random_runs]

    mean_f, std_f, min_f, max_f = statistics(random_fitness)
    mean_r, std_r, min_r, max_r = statistics(random_sizes)
    results_dynamics_random[desc] = (mean_f, std_f, min_f, max_f, mean_r, std_r, min_r, max_r)

    ax1.plot(hist_best_fixed, label=f"{desc} (fixed f={fitness_fixed})")

    _, hist_size_fixed = genetic_algorithm(
        items=items,
        capacity=BACKPACK_CAPACITY,
        seed=FIXED_SEED,
        **parameters
    )[3:5]
    ax2.plot(hist_size_fixed, label=desc)

ax1.set_ylabel("Best fitness")
ax1.set_title("Experiment 5: Population dynamics — progress (fixed seed)")
ax1.legend(fontsize=8)
ax1.grid(True, alpha=0.3)

ax2.set_xlabel("Generation")
ax2.set_ylabel("Population size")
ax2.set_title("Experiment 5: Population dynamics — size (fixed seed)")
ax2.legend(fontsize=8)
ax2.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

print("\nSummary (fixed seed vs randomness):")
for desc, _, _, _ in scenarios:
    fs, rs = results_dynamics_fixed[desc]
    mean_f, std_f, min_f, max_f, mean_r, std_r, min_r, max_r = results_dynamics_random[desc]
    print(
        f"  {desc:<33} -> fixed seed: f={fs}, size={rs} | "
        f"random f: mean={mean_f:.1f}, std={std_f:.1f}, min={min_f:.0f}, max={max_f:.0f}; "
        f"size: mean={mean_r:.1f}, std={std_r:.1f}, min={min_r:.0f}, max={max_r:.0f}"
    )

Question¶

Please answer the question below.

11. How does the dynamics type (stable/growing/shrinking) affect the final fitness? Do strongly growing or strongly shrinking populations degrade the quality or the stability of the results?

(your answer here)

In [ ]:

# --- EXPERIMENT 6: Elitism ---

plt.figure(figsize=(12, 5))
results_elitism_fixed = {}
results_elitism_random = {}

for elit in [True, False]:
    parameters = dict(
        population_size=20,
        n_iterations=200,
        p_crossover=0.8,
        p_mutation=0.05,
        n_pairs=8,
        offspring_per_pair=2,
        n_remove=16,
        selection_method="tournament",
        elitism=elit,
    )

    fitness_fixed, hist_best_fixed, _ = run_variant(parameters, FIXED_SEED)
    label = "with elitism" if elit else "without elitism"
    results_elitism_fixed[label] = fitness_fixed

    random_fitness = [run_variant(parameters, s)[0] for s in RANDOM_SEEDS]
    mean, std, minimum, maximum = statistics(random_fitness)
    results_elitism_random[label] = (mean, std, minimum, maximum)

    plt.plot(hist_best_fixed, label=f"{label} (fixed seed={fitness_fixed})")

plt.xlabel("Generation")
plt.ylabel("Best fitness")
plt.title("Experiment 6: Effect of elitism (fixed seed)")
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

print("\nSummary (fixed seed vs randomness):")
for e in ["with elitism", "without elitism"]:
    fs = results_elitism_fixed[e]
    mean, std, mn, mx = results_elitism_random[e]
    print(
        f"  {e:<20} -> fixed seed: f={fs:<5} | "
        f"random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}"
    )

Question¶

Please answer the question below.

12. How does elitism affect the final result and the risk of losing good solutions?

(your answer here)

In [ ]:

# --- SUMMARY TABLE: fixed seed + randomness ---
print(f"\n{'='*110}")
print(f"{'AGGREGATED EXPERIMENT RESULTS (FIXED SEED VS RANDOMNESS)':^110}")
print(f"{'='*110}")

print(f"\n--- Experiment 1: Mutation probability ---")
for pm in mutation_rates:
    fs = results_mutation_fixed[pm]
    mean, std, mn, mx = results_mutation_random[pm]
    print(f"  p_mutation={pm:<6} -> seed={fs:<5} | random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}")

print(f"\n--- Experiment 2: Crossover probability ---")
for pc in crossover_rates:
    fs = results_crossover_fixed[pc]
    mean, std, mn, mx = results_crossover_random[pc]
    print(f"  p_crossover={pc:<4} -> seed={fs:<5} | random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}")

print(f"\n--- Experiment 3: Population size ---")
for ps in population_sizes:
    fs = results_population_fixed[ps]
    mean, std, mn, mx = results_population_random[ps]
    print(f"  population_size={ps:<4} -> seed={fs:<5} | random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}")

print(f"\n--- Experiment 4: Selection method ---")
for m in methods:
    fs = results_selection_fixed[m]
    mean, std, mn, mx = results_selection_random[m]
    print(f"  selection {m:<12} -> seed={fs:<5} | random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}")

print(f"\n--- Experiment 5: Population dynamics ---")
for desc, _, _, _ in scenarios:
    fs, rs = results_dynamics_fixed[desc]
    mean_f, std_f, min_f, max_f, mean_r, std_r, min_r, max_r = results_dynamics_random[desc]
    print(
        f"  {desc:<33} -> seed: f={fs}, size={rs} | "
        f"random f: mean={mean_f:.1f}, std={std_f:.1f}, min={min_f:.0f}, max={max_f:.0f}; "
        f"size: mean={mean_r:.1f}, std={std_r:.1f}, min={min_r:.0f}, max={max_r:.0f}"
    )

print(f"\n--- Experiment 6: Elitism ---")
for e in ["with elitism", "without elitism"]:
    fs = results_elitism_fixed[e]
    mean, std, mn, mx = results_elitism_random[e]
    print(f"  {e:<20} -> seed={fs:<5} | random: mean={mean:.1f}, std={std:.1f}, min={mn:.0f}, max={mx:.0f}")

Part 4: Running the Optimized Model¶

Please fill in the parameters based on the conclusions drawn from the experiments above. The guiding idea: each value should be justified by what you observed in Parts 3.1–3.6 — there is no single "correct" answer, but there are well- and poorly-justified ones.

In [ ]:

individual_opt, fitness_opt, hist_best_opt, hist_avg_opt, hist_size_opt = genetic_algorithm(
    items=items,
    capacity=BACKPACK_CAPACITY,
    population_size=100,           # <- change this
    n_iterations=300,             # <- change this
    p_crossover=0.8,              # <- change this
    p_mutation=0.05,              # <- change this
    n_pairs=2,                     # <- change this (number of parent pairs)
    offspring_per_pair=2,          # <- change this (1 or 2)
    n_remove=4,                   # <- change this (how many weakest to remove)
    selection_method="tournament", # <- change this
    tournament_size=3,             # <- change this
    elitism=False,                 # <- change this
    seed=666
)

print(f"\nYour optimized fitness: {fitness_opt} PLN")
print(f"Final population size: {hist_size_opt[-1]}")
display_result(individual_opt, items, BACKPACK_CAPACITY)
plot_convergence(hist_best_opt, hist_avg_opt, "Your optimized model")
plot_population_size(hist_size_opt, "Your optimized model")

52 KiB Raw Permalink Blame History Unescape Escape

Lab 2 - Genetic Algorithms¶

Objective¶

Task Context¶

Note on seeds¶

Part 1: Defining the Problem¶

Part 2: Implementing the Genetic Algorithm¶

2.1 Generating the initial population¶

2.2 Selection methods¶

2.3 Genetic operators¶

2.4 Building the genetic algorithm¶

2.5 Visualization helpers¶

Part 3: Running the Baseline Model¶

Questions¶

Questions¶

Questions¶

Question¶

Question¶

Question¶

Part 4: Running the Optimized Model¶

52 KiB

Raw Permalink Blame History