Suppose a crate has limited capacity and you must choose which goods to send to Mars. In a genetic algorithm, an individual is one candidate choice. Its chromosome encodes that choice; a fitness value lets the algorithm compare it with other individuals. section 18.1.2 section 18.1.6
For the 0–1 knapsack problem, the chromosome is a bit string with one gene per item: 1 includes the item, and 0 leaves it behind. The chromosome is the genotype; the resulting selection of goods is the phenotype. Here, identical chromosomes produce identical selections and fitness values. Other problems may need continuous-valued genes and operators that preserve restrictions on their values. section 18.1.2
Listing 18.1 Class Individual
class Individual #1 #type array chromosome #2 function Individual(chromosome) #3 function fitness() #4
The minimal Individual interface stores a chromosome array and provides a fitness method; the chromosome’s contents and fitness calculation depend on the problem. section 18.1.2
A genetic algorithm works with a population of individuals rather than tuning one solution. To initialize it, create the requested number of individuals with a problem-specific chromosome generator. For knapsack, that generator can assign a random 0 or 1 to each item. section 18.1.3
Fitness affects which individuals continue:
- Elitism carries high-fitness individuals into the next generation unchanged; thresholding bars low-fitness individuals from passing on their genes. section 18.1.6
- Tournament selection samples individuals and returns the fittest sampled candidate. section 18.1.6
Random bit strings can violate a knapsack weight limit. Check constraints during generation or assign invalid solutions low fitness. For a population of size n with g genes per chromosome, the shown initialization loops perform n × g gene assignments and store n chromosomes of g genes; other costs depend on the chosen fitness and selection methods. section 18.1.3 section 18.1.6
