Evolutionary computation searches for good solutions by working with a population of candidates rather than following one candidate at a time. Like biological evolution, it produces variation, favors candidates that fit their environment better, and repeats over generations. In computing, that “environment” is the problem the candidates must solve. section 4.1 section 4.2
It is especially useful for optimization problems with many possible valid answers, where some answers are better than others. A population can explore several areas of the solution space when a single searcher might get trapped at a local optimum. The trade-off is computational expense. section 4.2
The basic cycle is:
- Generate diverse candidate solutions. section 4.1
- Select candidates that perform better on the problem. section 4.1
- Produce new variants through reproduction and mutation, then repeat across generations. section 1.20 section 4.1
Packing a knapsack
Suppose a knapsack holds at most 9 kg, and eight available items have different weights and values. Each choice of items is a candidate solution. Choosing items 1, 3, and 7 gives a valid 9 kg load worth $14; choosing items 2, 3, and 6 gives $15 but weighs 15 kg, so it breaks the limit. Evolutionary search aims to find high-value choices that also meet the constraint. Even this small puzzle has 256 possible item combinations. section 4.2
Table 4.1 Knapsack weight capacity: 9 kg
|
Item ID |
Item name |
Weight (kg) |
Value ($) |
| 1 |
Pearls |
3 |
4 |
| 2 |
Gold |
7 |
7 |
| 3 |
Crown |
4 |
5 |
| 4 |
Coin |
1 |
1 |
| 5 |
Axe |
5 |
4 |
| 6 |
Sword |
4 |
3 |
| 7 |
Ring |
2 |
5 |
| 8 |
Cup |
3 |
1 |
The item weights and values make the knapsack’s competing goals—high value and limited weight—concrete. section 4.2
The same approach can search over machine-learning feature choices, electronic circuit configurations, or molecular structures. Genetic algorithms are one evolutionary approach; encoding, crossover, mutation, and selection are techniques for adapting them to different problems. section 4.21 section 5.23
