A GENETIC ALGORITHM (GA) is a search and optimisation method inspired by natural selection. It maintains a POPULATION of candidate solutions and improves it over GENERATIONS by SELECTION, CROSSOVER and MUTATION. IT IS A METAHEURISTIC — a general strategy for searching, not a method tied to one problem. Compare the search of ACtE0902: A* explores one path at a time guided by a heuristic, while a GA maintains many candidates at once and has no notion of a path. THE BIOLOGICAL VOCABULARY, mapped to computation: BIOLOGY COMPUTATION ───────────────────────────────────────────────────────────── individual one candidate solution chromosome the encoded representation of it gene one element of the encoding allele the value a gene takes population the set of candidates in the current generation fitness the quality of a candidate, from the objective function generation one iteration of the algorithm selection choosing which candidates reproduce crossover (recombination) combining two parents mutation a random change to one individual ───────────────────────────────────────────────────────────── THE ALGORITHM: initialise a population of N random individuals evaluate the fitness of each repeat until a termination condition holds: SELECT parents according to fitness CROSSOVER pairs of parents to produce offspring MUTATE the offspring with small probability evaluate the offspring's fitness form the next generation return the best individual found THE THREE OPERATORS DO DIFFERENT JOBS, and understanding the division is the key to the topic: SELECTION applies the PRESSURE — it decides what survives, and so it EXPLOITS what has been found CROSSOVER RECOMBINES existing good material, exploring combinations of features already present MUTATION INTRODUCES NEW material that no parent had, which is the only way to recover a value lost from the whole population SELECTION WITHOUT VARIATION CONVERGES IMMEDIATELY AND STOPS; VARIATION WITHOUT SELECTION IS RANDOM SEARCH. The balance between them is the exploration–exploitation trade-off from the reinforcement learning topic, appearing in a new form. ENCODING — the first and most consequential design decision: BINARY STRINGS the classic, and the form the syllabus expects REAL-VALUED VECTORS for continuous parameters PERMUTATIONS for ordering problems such as the travelling salesman, where standard crossover would produce invalid tours and special operators are required TREES for evolving programs — GENETIC PROGRAMMING A GOOD ENCODING MAKES SMALL CHANGES IN THE CHROMOSOME CORRESPOND TO SMALL CHANGES IN THE SOLUTION. If a one-bit flip can transform a good solution into a terrible one, the search cannot make progress — which is the representation argument from the problem-formulation topic, applying again.

THE STANDARD WORKED EXAMPLE (following Goldberg): maximise f(x) = x² for integer x in 0…31, using 5-bit binary chromosomes. ── THE INITIAL POPULATION AND FITNESS ──────────────────────── chromosome x f(x) = x² share of total ───────────────────────────────────────────────────── 01100 12 144 12.5% 11001 25 625 54.1% 00101 5 25 2.2% 10011 19 361 31.3% ───────────────────────────────────────────────────── total fitness 1155 average 288.75 best 625 ── SELECTION ──────────────────────────────────────────────── ROULETTE WHEEL (fitness-proportionate): each individual gets a slice of a wheel proportional to its fitness, and the wheel is spun once per parent needed. 11001 occupies 54.1% of the wheel and 00101 only 2.2%, so the strong candidate is roughly TWENTY-FIVE TIMES more likely to be chosen. THE EXPECTED NUMBER OF COPIES of individual i is fᵢ / f̄ — here 625/288.75 = 2.16 copies of 11001 and 25/288.75 = 0.09 of 00101. THE PROBLEMS WITH ROULETTE WHEEL, and each has a fix: PREMATURE CONVERGENCE — one very fit individual dominates the wheel early, fills the population, and diversity is lost before the space has been explored it fails if fitness can be NEGATIVE, and is distorted if all fitnesses are large and similar (little selection pressure) FIXES: RANK SELECTION — select by rank order rather than raw fitness, so the pressure is constant regardless of the fitness spread TOURNAMENT SELECTION — pick k individuals at random and take the best. Simple, cheap, and the pressure is tuned by k. THE MOST USED METHOD IN PRACTICE. FITNESS SCALING — rescale fitnesses to control the spread ELITISM — copy the best individual(s) unchanged into the next generation, guaranteeing the best solution is never lost. NEARLY ALWAYS USED, because without it a GA can get worse from one generation to the next. ── CROSSOVER ──────────────────────────────────────────────── SINGLE-POINT CROSSOVER: choose a cut position and exchange the tails. parents chosen: 01100 and 11001, cut after position 3: 01100 → 011 | 00 11001 → 110 | 01 offspring: 011|01 = 01101 = 13, f = 169 110|00 = 11000 = 24, f = 576 NOTE THAT ONE CHILD IS WORSE THAN BOTH PARENTS AND ONE IS BETWEEN THEM. Crossover is not guaranteed to improve anything — it explores, and selection does the improving. OTHER FORMS: TWO-POINT CROSSOVER — exchange a middle segment UNIFORM CROSSOVER — decide each gene independently from either parent, which mixes more aggressively ARITHMETIC CROSSOVER — for real-valued encodings, take a weighted average of the parents ORDER-BASED CROSSOVER (OX, PMX) — for permutations, designed so the offspring is still a valid permutation CROSSOVER PROBABILITY p_c is typically 0.6 to 0.9 — most pairs are crossed. ── MUTATION ──────────────────────────────────────────────── Flip each bit with a small probability p_m. 11000 (24, f = 576), flipping bit 1: 11000 → 10000 = 16, f = 256 HERE MUTATION MADE IT WORSE, which is typical — most mutations are harmful, and the useful ones are rare and essential. MUTATION PROBABILITY is typically 1/L, where L is the chromosome length — so on average ONE BIT PER INDIVIDUAL changes. For a 5-bit chromosome that is p_m = 0.2; for a 100-bit chromosome, 0.01. TOO LOW and the population loses diversity and stagnates; TOO HIGH and the search becomes random, destroying the good material selection has accumulated. ── TERMINATION ───────────────────────────────────────────── a fixed number of generations; a fitness threshold reached; no improvement for k generations; or a time budget. A GA HAS NO NATURAL STOPPING POINT — it does not know when it has found the optimum, which is the price of having no optimality guarantee.

WHY A GA CAN WORK AT ALL — the schema theorem, in outline: A SCHEMA is a template with wildcards: 1**01 matches 11001, 11101, 10001 and 10101. It names a SUBSET of the search space sharing certain positions. THE BUILDING BLOCK HYPOTHESIS: a GA works by discovering short, low-order schemata of above-average fitness — BUILDING BLOCKS — and recombining them into better solutions. Holland's SCHEMA THEOREM states that short, low-order, above-average schemata receive exponentially increasing numbers of trials in successive generations. THE HYPOTHESIS IS PLAUSIBLE AND CONTESTED — it does not fully explain GA behaviour, and problems can be constructed (DECEPTIVE problems) where recombining good building blocks leads away from the optimum. IT IS WORTH KNOWING AS THE STANDARD EXPLANATION AND NOT AS A PROOF. THE IMPLICIT PARALLELISM ARGUMENT is stronger: a population of N individuals of length L samples many schemata simultaneously, so a GA evaluates a great deal of structural information with each generation of fitness evaluations. WHEN A GA IS THE RIGHT TOOL: · the search space is LARGE and poorly understood · there is NO GRADIENT — the objective is not differentiable, or is a simulation, or a black box · the landscape is RUGGED with many local optima, where hill climbing gets stuck · a GOOD-ENOUGH answer is acceptable; GAs give no optimality guarantee · fitness is CHEAP TO EVALUATE relative to the number of evaluations needed · the problem is MULTI-OBJECTIVE — a population can maintain a set of trade-off solutions (a PARETO FRONT), which single-solution methods cannot WHEN IT IS NOT: · a gradient exists — then gradient descent is far faster, which is why neural networks are trained by backpropagation and not by evolution · the problem has known structure a specialised algorithm exploits — use the specialised algorithm · fitness evaluation is EXPENSIVE. A GA may need tens of thousands of evaluations, and if each is a ten-minute simulation the budget is impossible. · an exact optimum is required with proof THE HONEST ASSESSMENT: ADVANTAGES · needs no derivative and no model of the objective · escapes local optima better than hill climbing, because a population explores several regions at once · PARALLELISES trivially — every fitness evaluation is independent · applies to almost any problem for which an encoding and a fitness function can be written · handles multi-objective problems naturally DISADVANTAGES · NO GUARANTEE of optimality, and no way to know how close you are · MANY PARAMETERS to tune — population size, p_c, p_m, selection method — and performance is sensitive to them · computationally expensive in fitness evaluations · PREMATURE CONVERGENCE if diversity is lost · the encoding must be designed, and a poor encoding defeats the method entirely · results are STOCHASTIC — two runs give different answers, so experiments must be repeated and averaged A COMPARISON WITH THE SEARCH OF ACtE0902, to place it: A* is COMPLETE and OPTIMAL with an admissible heuristic, and needs a well-defined state space with actions and costs. HILL CLIMBING is cheap and gets stuck in local optima. SIMULATED ANNEALING escapes local optima by accepting worse moves with a decreasing probability — a single-solution method with a temperature schedule. A GENETIC ALGORITHM keeps a POPULATION, so it explores several basins at once and can RECOMBINE partial solutions — which is the one thing none of the single-solution methods can do. THAT RECOMBINATION IS THE GA'S DISTINCTIVE CONTRIBUTION, and whether it helps depends entirely on whether the problem's good solutions are built from independently useful parts.