An individual is one candidate solution in an evolutionary algorithm’s population. It is represented by a chromosome, a collection of genes that encodes a possible solution; in a knapsack problem, each binary gene indicates whether an item is included. section 5.22 section 4.6
A practical individual moves through the algorithm like this:
- Create it with randomly chosen genes, while ensuring that the encoded solution is valid or repairing violations. section 4.6
- Measure its fitness, which indicates how well the solution performs against the problem’s objective and constraints. section 4.7
- Give fitter individuals a greater chance of becoming parents, while still allowing other individuals to contribute traits. section 4.8
- Retain or replace it according to the population model: steady-state models replace part of the population, while generational models replace all of it. section 4.9
A knapsack individual
Suppose a chromosome contains one binary gene per item: 1 means “pack this item,” and 0 means “leave it out.” The algorithm adds the weights and values for every gene set to 1. If the total weight exceeds the limit, the individual receives a fitness score of 0; otherwise, its fitness is the total item value. A high-value, valid individual is therefore more likely to help produce the next generation. section 4.6 section 4.7 section 4.8
def calculate_individual_fitness(individual, maximum_weight):
total_individual_weight = 0
total_individual_value = 0
for gene_index in range(len(individual)): #A
gene_switch = individual[gene_index]
if gene_switch == '1': #B
total_individual_weight
➥+= knapsack_items[gene_index][KNAPSACK_ITEM_WEIGHT_INDEX] #C
total_individual_value
➥+= knapsack_items[gene_index][KNAPSACK_ITEM_VALUE_INDEX] #C
if total_individual_weight > maximum_weight: #D
return 0
return total_individual_value #E
Inspect the fitness calculation to see how an individual’s genes become weight, value, validity, and final score. section 4.7
