Finding an efficient delivery plan can mean comparing many routes, schedules, and resource allocations. A genetic algorithm searches for a good combination by repeatedly testing and changing candidate solutions. It is an optimization technique inspired by natural selection, not a way to guarantee the best possible answer. section 2.5
The search proceeds in generations:
- Start with a population of possible solutions and evaluate each one against chosen measures, such as delivery time and cost. section 2.5
- Select better-performing solutions and combine parts of them through crossover. For example, pair one plan’s faster route with another’s resource allocation. section 2.5
- Occasionally make a random change, called mutation, to explore another option. Repeat with the new population until improvement stops or a set number of cycles has passed. section 2.5
Table 2.2 Complexity of the genetic algorithm for the school bus route example
|
Number of locations to visit
|
Number of possible routes to compare
|
|---|---|
|
1
|
1
|
|
2
|
2
|
|
3
|
6
|
|
4
|
24
|
|
10
|
3,628,000
|
|
20
|
2,432,902,008,176,640,000
|
The school-bus route table shows why comparing every possibility becomes difficult: ten locations have 3,628,000 possible routes, while twenty have more than two quintillion. section 2.5
The useful result depends on how candidates are evaluated: a plan judged only on speed may not meet a cost goal. Genetic algorithms can also play one part in a larger system; a proposed fraud-prevention combination uses them to optimize model parameters alongside other AI techniques. section 2.5 section 11.7
