Import the needed libraries:
import random
# random: provides functions for generating random numbers,
# used here for creating individuals, selecting parents,
# and deciding crossover/mutation points.
Items that can be put in the Knapsack: List of [weight, value] pairs 🏋️
# Define list of items: [weight, value]
items = [
[1, 2], # Item 1: weighs 1 unit, worth 2 value units
[2, 4], # Item 2: weighs 2 units, worth 4 value units
[3, 4], # Item 3: weighs 3 units, worth 4 value units
[4, 5], # Item 4: weighs 4 units, worth 5 value units
[5, 7], # Item 5: weighs 5 units, worth 7 value units
[6, 9] # Item 6: weighs 6 units, worth 9 value units
]
print("Available items:\\n", items) # Show items for verification
max_weight = 10 ⚖️# Maximum capacity of the knapsack (weight limit)
max_weight = 10
# Number of candidate solutions (chromosomes) per generation
population_size = 10
# Probability (0–1) that any gene will mutate (flip bit)
mutation_probability = 0.2
# How many generations to evolve the population
generations = 10
print("\\nGenetic algorithm parameters:")
print("Max weight:", max_weight)
print("Population size:", population_size)
print("Mutation probability:", mutation_probability)
print("Generations:", generations, "\\n")
create_individual: Generate a random bit-string of length = number of items 🧬
def create_individual():
"""
Create a new chromosome:
- Length = number of items.
- Each gene is 0 (exclude item) or 1 (include item).
"""
individual = []
for _ in range(len(items)):
bit = random.randint(0, 1)
# Append random 0/1: decides if the corresponding item is chosen
individual.append(bit)
return individual
# Example usage:
sample = create_individual()
print("Sample individual:", sample) # e.g., [1, 0, 1, 0, 1, 1]
def fitness(individual):
"""
Evaluate how good a chromosome is:
1. Compute total weight = sum(weight_i * gene_i)
2. Compute total value = sum(value_i * gene_i)
3. If weight > max_weight, return 0 (invalid; penalize)
4. Else return total value as fitness score.
"""
total_weight = 0
total_value = 0
# Sum over all genes
for i, gene in enumerate(individual):
if gene == 1:
# If gene is 1, include this item's weight and value
total_weight += items[i][0]
total_value += items[i][1]
# Penalize overweight solutions
if total_weight > max_weight:
return 0
# Valid solution: return its total value
return total_value
select_parent(population): Tournament selection (k=3) 🎲
def select_parent(population):
"""
Tournament selection process:
1. Randomly pick 3 individuals from the population.
2. Compare fitness of these 3.
3. Return the individual with the highest fitness.
"""
tournament_size = 3
contenders = random.sample(population, tournament_size)
best = contenders[0]
best_fitness = fitness(best)
# Find the contender with max fitness
for contender in contenders[1:]:
contender_fitness = fitness(contender)
if contender_fitness > best_fitness:
best, best_fitness = contender, contender_fitness
return best