A solution is a candidate answer to a problem. It represents choices that can be checked against rules and scored by how well they meet an objective. Optimization problems often have many valid solutions, but some are more valuable or efficient than others. section 4.2
A solution is useful when it can be represented, checked, and compared:
- Validity means satisfying the problem’s constraints, such as keeping a knapsack’s total weight within its limit and avoiding duplicate items. section 4.2 section 4.6
- Fitness measures how good a solution is, such as assigning a higher score to a knapsack with greater total value. section 4.3
- Representation turns a real problem into data that an algorithm can process; a knapsack solution can use binary genes indicating whether each item is included. section 4.6 section 2.3
- A repair function can adjust an invalid solution instead of discarding it, such as removing an item from an overweight knapsack. section 4.6
Comparing knapsack solutions
Suppose a bag holds 9 kg. Including items 1, 4, and 6 weighs 8 kg and produces value $8, so it is valid. Including items 1, 3, and 7 weighs 9 kg and produces value $14, making it better. Including items 2, 3, and 6 produces value $15 but weighs 15 kg, so it violates the constraint and is not a valid solution. section 4.2
Figure 4.9 Genetic algorithm life cycle
The life-cycle diagram shows how populations of solutions are generated, evaluated, selected, combined, mutated, and carried into later generations. section 4.3
