Genetic Algorithms: Introduction
Source: Unit 5 §1
A genetic algorithm is a metaheuristic, search-based optimisation technique inspired by genetics and natural selection - Darwin's survival of the fittest, turned into a loop. It was introduced for problem solving by Professor John Holland in 1965, and it finds optimal or near-optimal solutions to problems that would otherwise take a lifetime to solve exactly.
A GA considers multiple points in the solution space simultaneously. That global perspective is what lets it avoid local optima, and it is the answer to almost any "why use a GA?" question.
The connection to optimisation
The set of all possible solutions is the search space, and somewhere in it sits the optimal point (or points). A GA's aim is to find that point.
- It uses only the objective function. No derivatives, no gradients, no auxiliary knowledge.
- Consequently it can handle functions that are non-smooth, non-continuous and non-differentiable - which describes most real problems.
Why bother
| Need | Explanation |
|---|---|
| Solving difficult problems | Many problems are NP-hard; even powerful systems would take years to solve them exactly. |
| Failure of gradient methods | Traditional gradient methods work on unimodal (single-peaked) functions, but get stuck in local optima on multimodal ones. |
| A good solution, fast | Problems like TSP, path finding and VLSI design need a good-enough answer quickly, not a perfect answer eventually. |
The notes say a GA finds "optimal or near-optimal" solutions, and the second half of that phrase is doing real work. The global perspective is what lets a GA escape local optima that trap a gradient method; it is not a proof that the point it returns is the global best. Quote the phrase in full.