Genetic algorithms

Evolution as search

A genetic algorithm (GA) searches by maintaining a whole population of candidate solutions (often bit-strings) and evolving them. Unlike hill-climbing (one current state), the GA explores in parallel and recombines partial solutions. The loop:

1. Initialize a random population $P(0)$.
2. Evaluate fitness — score each candidate with a domain fitness function.
3. Select parents with probability proportional to fitness.
4. Recombine — apply crossover and mutation to make offspring.
5. Replace the weakest members with the offspring; repeat until a fitness threshold is met.

The two operators

- Crossover splits two parents at a cut point and swaps segments — it recombines successful *building blocks* from fit parents. This is exploitation. - Mutation randomly flips a bit in one candidate — it injects diversity crossover cannot create (if no member has a 1 in position 3, only mutation can introduce one). This is exploration.

You need both: crossover alone converges prematurely; mutation alone is random search.

Roulette-wheel selection

Fitness-proportionate (roulette-wheel) selection gives candidate $x$ a selection probability $\propto f(x)/\bar f$ — fitter candidates are picked more often, yet even weak ones keep a *non-zero* chance, preserving genetic material that might carry a useful building block.

Schema theory and genetic programming

Holland’s schema theorem explains *why* GAs work: a schema like 10##01 (with # = don’t-care) names a family of strings, and above-average schemata get sampled exponentially more over generations — “implicit parallelism.” Genetic programming (Koza 1992) evolves *programs* represented as Lisp s-expression trees; subtree crossover always yields a syntactically valid program (given the closure property). A program subtree like (* 4 6) is just a node whose children are swapped during crossover. The exercise runs one GA on a max-ones problem and watches best-fitness climb to the target.