A genetic algorithm searches for a good solution by evolving a population of candidate solutions. It starts with varied candidates, scores how well each works, and uses selected candidates to produce the next generation. It is useful when there are too many possibilities to check one by one, but it does not guarantee the best possible answer. section 4.3 section 4.2
The basic cycle is:
- Create a population of random candidate solutions. Represent each as a chromosome—a sequence of genes describing its choices—and account for the problem’s constraints. section 4.6
- Measure fitness: give each candidate a score for how well it solves the problem. section 4.7
- Select parents based on fitness, then combine their genes and introduce random mutations to make offspring. Use offspring to populate the next generation, repeating the cycle to seek better solutions. section 4.3
Packing a knapsack
Suppose a bag can carry 9 kg and each item has a weight and value. A candidate can use a 1 for an item it includes and a 0 for one it leaves out. Pearls (3 kg, value 4), a crown (4 kg, value 5), and a ring (2 kg, value 5) make a valid 9 kg candidate worth 14. A fitness function adds the values of included items, but gives an overweight candidate a score of 0. That penalty keeps an attractive but unusable packing choice from scoring well. section 4.2 section 4.6 section 4.7
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 |
Use the item table to try other 9 kg combinations and compare their values before considering how an algorithm might find them. section 4.2
Configuration matters. A larger population can offer more diversity but costs more computation per generation; the chromosome encoding, fitness function, and parent-selection method also affect results. Because initialization, selection, and mutation involve randomness, a run may find a good answer without finding the global best. Similar searches can help with delivery routes, truck packing, production order, and feature selection in machine learning. section 4.20 section 4.3 section 4.2 section 4.21
