Genetic Algorithms, Ant Colony Optimization, and Neural Architecture Search

6.1 Genetic Algorithms: Foundations and Terminology

6.1.1 Where We Left Off: Local Search and Its Two Branches

This session opens exactly where the previous one ended. The whole module so far has been about local search — techniques where the state itself is an answer, and we try to improve that answer by making local changes and checking whether we get closer to something better. Nothing external scores the states against a far-away goal; every state is already a candidate solution, and the search walks from one candidate to a slightly changed neighbour.

Inside local search there are two broad categories:

• Single-instance local search works with exactly one state at a time. The techniques studied there were hill climbing and local beam search along with their variations, and the plan was to stop there — no other single-instance methods.
• Multiple-instance local search keeps several states alive at once. There are many such methods, and the course covers exactly two of them — the two topics of today: genetic algorithms and ant colony optimization.

The last discussion of the previous session was about beam search. In beam search, K random states start working in parallel. The important concluding point was that those K states cannot collaborate with each other — they work side by side, and if one of them finds the answer, it simply tells the others. The most striking feature of genetic algorithms is precisely the opposite: the individuals in a genetic algorithm can collaborate — they mate with each other, exchange genetic material, and produce offspring. That is the difference that makes genetic algorithms a new idea rather than just another beam-search variant.

The one-line version: if states can mate, the search stops being a collection of parallel attempts and becomes a population that evolves. That is the seed of today's first topic.

6.1.2 What Is a Genetic Algorithm?

A genetic algorithm (GA) is a search technique for optimization problems — the same job that hill climbing and beam search were doing. What changes is the inspiration: genetic algorithms belong to a family called bio-inspired (or nature-inspired) algorithms, and there is a well-known book collecting nature-inspired algorithms — a whole catalog of algorithms copied from nature, from ant colonies to fireflies. Among all those, genetic algorithms are the ones modeled on evolution — specifically human (and more generally animal) evolution.

The high-level flow should feel familiar at first: we pick a population, we calculate a fitness function — so far it is the same bookkeeping as before. The genuinely new part starts after the fitness calculation, and that is the heart of the algorithm. From here on, the algorithm is inspired by human evolution: we perform parent selection, we create children from those parents, and we give the children some traits (through mutation). If we still do not have a solution, we repeat the whole cycle. Those three steps — parent selection, child creation, trait-giving — are unique to genetic algorithms and do not appear in the earlier local-search methods.

A quick check against the earlier analogy: in previous classes, when we said "how good or bad is this state," we called that quality a heuristic value. In genetic algorithms the same idea gets a biological name — fitness — the healthiness of an individual. Same measurement, new vocabulary. From now on, the lecture reserves "heuristic" for the informed-search material and uses "fitness" inside genetic algorithms; the two words point at the same underlying number, but on the exam, "fitness" is the term attached to this topic.

A little history puts the method in place: the idea of a fitness landscape — a surface whose height at every point is how good that candidate is — goes back to Sewall Wright (1931), and genetic algorithms were championed as optimization tools by John Holland in the 1960s and 1970s. The biological model behind them is the one from the theory of evolution: in DNA, an organism is a string over the four-letter alphabet A, C, G, T; in a genetic algorithm, an individual is a string over the alphabet your problem defines — digits, bits, or rows of a board. Variation happens by point changes (mutation) and by combining long sections of two parents (crossover), and better individuals reproduce more often. That is the whole recipe, and the rest of this section just names its ingredients.

6.1.3 The Terminology of Genetic Algorithms

The vocabulary of genetic algorithms is a short list, and each term maps to something you already know:

• Population — the collection of individuals, or equivalently the collection of states, being evolved at one time. The population is the multiple-instance part of the method: instead of one state, we carry a whole generation of states.
• Fitness — a measure of how healthy an individual is; the analogue of the heuristic value from the earlier local-search lectures. Bigger fitness means a healthier (better) parent.
• Selection — choosing the most biological parents for the next generation, the way nature (or a matchmaker) chooses who gets to reproduce.
• Crossover — from a bunch of parents, creating new children by mixing their genetic material.
• Mutation — changing some of the children afterwards, to give them unique traits that neither parent had.

These names all become concrete once we solve a complete example, but it is worth knowing the skeleton first. The standard description is a seven-step process. The first three steps are already familiar from every algorithm so far: (1) represent the problem in some state form, (2) generate the initial population, (3) apply the fitness function. The next three steps are peculiar to genetic algorithms: (4) parent selection, (5) successor generation through crossover, (6) mutation. Step 7 is the loop: check the stopping conditions, and either stop or go back to the fitness/selection steps.

As a flow:

(1) represent the problem → (2) generate initial population → (3) compute fitness
                                                                        ↓
    (7) check stopping criteria ← (6) mutation ← (5) crossover ← (4) parent selection
             ↓ yes
           STOP

Steps 1–3 are bookkeeping you already know. Steps 4–6 are where the biology enters, and step 7 is the loop that turns one generation into the next. Keep this skeleton in view for the whole lecture: the four-queens example in sections 6.2–6.5 walks it once, step by step.

6.1.4 The Three Stopping Criteria

A genetic algorithm needs a way to decide when to stop. There are exactly three stopping criteria, and at least one of them always fires eventually:

1. The threshold fitness is reached. The threshold means the maximum achievable fitness for the problem — for the four queens problem that maximum is 6 (all six queen pairs non-attacking). If any individual reaches it, the problem is over and the algorithm stops.
2. A predefined number of new states (or generations) is exhausted. We may say, "generate 10 new states and beyond that don't go; whatever you have there is the best — stop." In exams this is normally given to you explicitly.
3. No change between successive iterations. If an iteration and the next iteration give exactly the same results (iteration N and iteration N+1 identical — or, say, N+3 and N+4 identical), nothing is improving, so stop.

Recap + bridge. A genetic algorithm is the multiple-instance local search method in which individuals collaborate: pick a population, score it with fitness, select parents, create children by crossover, mutate for unique traits, and loop until a stopping criterion fires. With the vocabulary fixed — population, fitness, selection, crossover, mutation, and the three stopping criteria — the next section runs the whole machine on a concrete problem: the four queens puzzle, where fitness becomes a real number and the loop becomes arithmetic.

Real-world connection. Genetic algorithms are the workhorses of nature-inspired optimization. In industry they appear wherever the search space is structured but too large for exhaustive search: circuit layout, job-shop scheduling, and — closer to this course — automatically evolving the architecture of deep neural networks, which is exactly the neural architecture search topic at the end of this lecture. The catalogue of nature-inspired algorithms that the lecture mentions collects dozens of such methods, from ant colonies to bee colonies, and the genetic algorithm is the evolution-shaped member of that family.

6.2 Genetic Algorithms: The Four Queens Problem — Setup, Fitness, and Probabilities

6.2.1 Setting Up K Random Board Configurations

The running example is the four queens problem: place four queens on a 4×4 board so that no queen threatens another. The first step of the genetic algorithm is to select K random states. In this problem K is given as 4, so we create four different board configurations.

Each configuration is represented as a vector of four numbers, exactly as in the previous session. The meaning of the vector 1 4 2 2: the first number says the queen in column 1 sits in row 1, the second number says the queen in column 2 sits in row 4, the third says the queen in column 3 sits in row 2, and the fourth says the queen in column 4 sits in row 2. In general, position i of the vector is the row of the queen in column i.

The four boards are named B1, B2, B3, B4. From the narration: B1 = 1422, B3 = 1432, B4 = 2141. B2's exact vector is garbled in the audio; what the lecture states cleanly is B2's fitness — 4 non-attacking pairs — so any reconstruction of B2 must be a vector whose six pairs contain exactly two threatening pairs. One consistent choice, for example, is 1324, which places queens at (1,1), (2,3), (3,2), (4,4): the pairs Q1–Q4 and Q2–Q3 attack diagonally, and the other four pairs do not, giving $6-2=4$ non-attacking pairs. Since every downstream step uses only B2's fitness (4), this ambiguity never changes the rest of the computation.

A key difference from hill climbing: these four boards are random and independent. In hill climbing we took one state and produced neighbors by making small changes to it. Here, when K = 4 is given, the four configurations are generated from scratch and have nothing to do with each other — they are not neighbors of anything.

6.2.2 The Fitness Function and the Threshold

The next step is to compute the fitness value for each board. First we must fix the fitness function. Two natural choices exist for this problem: the number of attacking queen pairs, or the number of non-attacking queen pairs. The example uses the usual choice — the number of non-attacking pairs. Note what this choice does to the direction of the search: bigger fitness means a better board, and the best possible board scores the maximum.

The computation is exactly what we practiced last session: enumerate all pairings of the four queens. With queens Q1, Q2, Q3, Q4 there are six pairs — Q1Q2, Q1Q3, Q1Q4, Q2Q3, Q2Q4, Q3Q4 — and for each pair we check whether it is conflicting (same row, same column, or same diagonal) or non-conflicting. Two queens conflict exactly when they share a row, a column, or a diagonal; with one queen per column, the column check is already satisfied by the representation, so only rows and diagonals remain.

For B3 = 1432, queens at (1,1), (2,4), (3,3), (4,2): Q1–Q3 attack diagonally, Q2–Q3 attack diagonally, Q2–Q4 attack diagonally, and Q3–Q4 attack diagonally — 4 attacking pairs, so the fitness is $6-4=2$. For B4 = 2141, queens at (1,2), (2,1), (3,4), (4,1): Q1–Q2 attack diagonally, Q1–Q3 attack diagonally, and Q2–Q4 share row 1 — 3 attacking pairs, so the fitness is $6-3=3$.

The four fitness values are:

• B1 = 1422 → fitness 4
• B2 → fitness 4 (vector unreadable in the audio, fitness given)
• B3 = 1432 → fitness 2
• B4 = 2141 → fitness 3

The threshold fitness — the maximum attainable value — is 6, which would mean all six pairs are non-attacking. None of the four boards reaches 6, so we do not stop; we proceed into the genetic algorithm proper.

6.2.3 From Fitness to Probability

Before selection, each individual's fitness is converted into a selection probability: each board's probability equals its fitness divided by the total fitness.

$$p_i=\frac{f_i}{{\sum }_j{f}_j}$$

where $f_i$ is the fitness of board $i$ and the sum runs over all boards in the population. The denominator ${\sum }_j{f}_j$ is just the total fitness of the whole population — one number — and the numerator $f_i$ is that one board's fitness. Because every numerator is a fitness (a count of non-attacking pairs, always $\ge 0$) and the denominator is the sum of all of them, every $p_i$ lands in $[0,1]$ and the four probabilities add up to 1: this is a genuine probability distribution over the population, which is exactly what the roulette wheel in the next section needs.

The total fitness is $4+4+2+3=13$. So:

• $p(\text{B1})=4/13$
• $p(\text{B2})=4/13$
• $p(\text{B3})=2/13$
• $p(\text{B4})=3/13$

As percentages those are 31%, 31%, 15%, and 23% (for example $4/13\approx 0.3077\approx 31\%$). This is why the pie (a ring, really) has two fat 31% slices, a 23% slice, and a thin 15% slice: a larger fitness value means a larger chunk of the pie, and a larger chunk means a larger chance of being selected when the wheel stops. The probability computation needs nothing beyond the fitness values — the 13 is simply the sum of all fitness values, and each numerator is that one board's fitness.

So far, only two steps of the genetic algorithm have happened: generate K random states (four independent boards) and compute their fitness values — plus the derived probabilities. All familiar material. From here, the three steps that are unique to genetic algorithms begin.

Recap + bridge. Four independent random boards, each scored by counting non-attacking queen pairs out of six, give fitnesses 4, 4, 2, 3 and selection probabilities 4/13, 4/13, 2/13, 3/13. The threshold 6 was not reached, so the search continues — and now the biology starts: step four of the process turns those probabilities into actual couples on a roulette wheel.

Real-world connection. This fitness-to-probability conversion is the same idea a cricket selector or a hiring committee uses under the hood: the better the score, the more chances to reproduce — but nobody is guaranteed a spot. In industry terms, fitness-proportionate selection is the standard first step of every evolutionary optimization package, from scheduling solvers to automated machine-learning pipelines, and getting the fitness function's direction right is the classic first bug in real genetic-algorithm projects.

6.3 Genetic Algorithms: Parent Selection with the Roulette Wheel

6.3.1 The Roulette Wheel Method

Step four of the process is parent selection: from the four board configurations, choose a few individuals who will become parents of the next generation. The biological analogy is matchmaking — in the human world, someone (parents, matchmaking platforms) picks who forms a couple. Here we must decide which boards pair up.

Several parent-selection methods exist — tournament, ranking, and others — but this course always uses the roulette wheel (also called the fitness-proportionate wheel). The description: the population is divided on a wheel according to each individual's percentage of the total fitness, and fixed point(s) are placed on the wheel — you can use two fixed points, but the example uses just one, a blue arrow. The wheel is spun, and the individual at which the fixed point points when the wheel stops is selected. It is exactly the gambling-wheel mechanism you see in casinos and fun arenas.

The wheel is spun multiple times. The first spin gives the first parent; the second spin gives the second parent, and those two form the first couple. If the same individual wins twice, that second result is ignored (we do not eliminate anyone — more on this below) and the wheel is spun again until a different individual comes up, because a couple must contain two distinct parents. Whether a repeated result forces a re-run depends on whether the repeats block the required couples — see the example.

6.3.2 Running the Wheel in the Example

The wheel carries the four probabilities computed earlier: 31% for B1, 31% for B2, 15% for B3, 23% for B4. Picture the wheel: a ring cut into four slices — two fat 31% slices side by side for B1 and B2, a 23% slice for B4, and a thin 15% slice for B3 — with a single blue arrow fixed at the top. When the wheel stops, the slice under the arrow names the selected parent. A 31% slice lands under the arrow roughly twice as often as the 15% slice, but every slice can win.

Two validity rules must hold. First, the couples themselves must be distinct — you may not have couple (B4, B1) and couple (B1, B4), which is the same pair of individuals again. Second, within a couple the two parents must be distinct — (B1, B1) is not a couple. In this example both rules held: B1 appears in two different couples, which is fine — B1 got lucky, appearing twice — because each couple is a different pair and, as the joke goes, while the judicial system may not allow it, genetic algorithms allow one individual to pair with multiple partners at different times.

What about run 3 giving B1 again? It was not discarded, because the fourth run then produced B3, so both couples could still be formed. But consider what would have happened if run 4 had again produced B4: then the couples would be (B4, B1) and (B1, B4) — the same couple twice — and that is not allowed, so we would have re-run the wheel. The general rule: if you cannot form the required number of distinct couples with distinct members, you re-run the wheel. This is why the number of runs cannot be fixed in advance — repeated outcomes may force extra spins.

And B2? Sad about B2 — in this example B2 never got a chance to be in a relationship; it was never selected. That is simply how the luck fell.

6.3.3 Student Questions and Answers

Recap + bridge. Parent selection turns the fitness probabilities into real couples: spin a fitness-proportionate wheel, ignore repeated picks, re-run only when distinct couples cannot form, and keep every individual available for multiple pairings. The couples are now fixed — (B4, B1) and (B1, B3) — and the next step of the algorithm decides what those couples produce: crossover.

Real-world connection. Fitness-proportionate selection is the step that keeps diversity alive in evolutionary software: a genuinely new (but currently mediocre) design keeps a real chance of reproducing, which is how these methods escape the traps that greedy selection falls into. Real-world genetic-algorithm libraries implement exactly this wheel — the same arithmetic of slice sizes and random spins — for problems from antenna design to factory scheduling, and the "keep everyone eligible" rule is what the lecture's marriage joke encodes.

6.4 Genetic Algorithms: Crossover — Generating Children

6.4.1 What Crossover Does

Once the parents (the couples) are selected, the next step is successor generation — creating children. In biological terms: children are a byproduct of parents; their DNA inherits traits from both parents. That is what crossover does — it mixes the genetic material of the two parents to form the next generation's individuals.

Two things are fixed by the problem, not by the algorithm: how many couples to form, and how many children each couple produces. There is no limit on children per couple — bio-inspired again: one couple may have one child, another two, and so on, and the question tells you how many children to generate in every iteration. In this example, four children are required in every iteration.

There are three crossover techniques: single-point crossover, multi-point (two-point) crossover, and uniform crossover. They differ only in how the parents' strings get cut and swapped; the number of children each operation produces follows from the technique, as we see next.

6.4.2 Single-Point Crossover

Single-point crossover is the simplest technique. Take the two parents' strings (bits, or in our problem the numbers of a vector — whatever you imagine the DNA to be). Pick any one position in the string and draw a line there. From that point onwards, the two tails are swapped: the first part comes from one parent and the second part from the other.

The in-class illustration used arbitrary strings unrelated to the queens problem — just a DNA-like example. Parent one was read as 4 3 2 1 0 5 7 8 and parent two as 1 2 3 4 5 1 2 3. The line was drawn after the sixth position, and swapping the tails gave:

A quick consistency check justifies the reconstruction: child one's tail (2 3) can only come from parent two's tail, and child two's tail (7 8) can only come from parent one's tail, so the parents are exactly 43210578 and 12345123 — the strings the slide shows. The line could be drawn after the first position, after the fourth, after the seventh — anywhere; wherever it is drawn, the children change accordingly.

One consequence of single-point crossover: one crossover operation always produces two children. If the question asks for four children, apply single-point crossover twice at two different positions and you get four; if you need three, apply it twice and ignore one child.

6.4.3 Two-Point Crossover

Two-point crossover draws two lines, splitting each parent into three segments — call them X, Y, Z (X1 Y1 Z1 for parent one, X2 Y2 Z2 for parent two). The middle segment is swapped: one child is X1 Y2 Z1 and the other is X2 Y1 Z2. In the illustration, X1 and Z1 came from parent one, and the middle Y2 came from parent two — and symmetrically for the second child. The lines can be placed anywhere.

The number of distinct children is fixed by the segment combinations — X1 Y1 Z2, X1 Y2 Z1, X2 Y1 Z2, X2 Y2 Z1, and so on — and you pick as many as the question asks. For multi-point crossover the count is not unbounded; it is this fixed set of combinations. The important limit to notice: two lines create at most a small handful of recombined strings, not an endless supply.

6.4.4 Uniform Crossover

Uniform crossover chooses random subsets of bits and swaps only those. In the illustration, two parents of bits (strings like 1 0 1 0 0 0 1 1 1 0) were shown, with some bits marked (underlined) as "kept as is" — one child kept those bits from parent one and took everything else from parent two, and the second child did the mirror image.

The percentage version is important for exams. When a question says "perform uniform crossover with 50%", it means: out of the bits, change 50%. For an 8-bit string like 1 0 0 1 0 0 1 0, you can take half from one parent and half from the other and merge them — or you can take every alternate bit from each parent, which is also 50%. If a percentage like 25% or 75% is given, that many bits are swapped. Uniform crossover resembles multi-point crossover, but the percentage logic (swap a stated fraction of the bits) is the distinguishing feature.

6.4.5 Crossover in the Four Queens Problem

Back to the queens: the two couples are (B4, B1) and (B1, B3), and the problem asks for four children in every iteration — two from each couple.

Couple two — (B1, B3): two-point crossover. B1 = 1422 and B3 = 1432. The narration keeps the outer bits as they are and swaps the inner parts: the kept bits are 1, 2 from one side and 1, 2 from the other, and the swapped pieces are 42 and 43. Writing both parents as three segments: B1 = 1 | 42 | 2 and B3 = 1 | 43 | 2. Swapping the middle segments gives child one = 1 | 43 | 2 = 1432 and child two = 1 | 42 | 2 = 1422 — the children are C3 = 1432 and C4 = 1422. Because the two parents differ only in the middle segment, the two-point swap reproduces the parent strings themselves; that is a special case of the technique, not a mistake — the mutation step next in the algorithm is what finally changes these children.

At this point every child is still just a combination of its parents' genes — C1 = 2422 has nothing that was not in B4 or B1. Even if a child's configuration looks new, the individual bits all come from one parent or the other. In the real world that is not the whole story — both parents may lack a skill the child has — and that extra something arrives in the next step, mutation.

6.4.6 Student Questions and Answers

Recap + bridge. Crossover mixes the two parents' strings into children — one line for single-point (two children, tails swapped), two lines for two-point (middle segment swapped, a fixed set of combinations), random subsets for uniform (swap a stated percentage of bits). The four children C1 = 2422, C2 = 1141, C3 = 1432, C4 = 1422 are pure combinations of their parents' genes — and that is precisely why the algorithm needs its sixth step, mutation, to give each child something neither parent had.

Real-world connection. Crossover is the recombination operator that real evolutionary systems — from genetic algorithms scheduling airline crews to genetic programming growing software functions — rely on to combine good building blocks found in different individuals. The lecture's DNA analogy is not decorative: the reason crossover works at all is the same reason sexual reproduction works — if a partial design is useful on its own (like the first three queens in safe positions), combining it with another useful partial design can inherit both advantages, a property that holds only when the string's parts mean something individually.

6.5 Genetic Algorithms: Mutation and the Complete Iteration

6.5.1 What Mutation Does

Step six is mutation — a gene change. Children produced by crossover are only combinations of their parents: C1 = 2422, for instance, is just B4's 2 glued to B1's 422. We want the children to have unique traits, and mutation provides them. In the real world this is the "both parents lack a skill, but the child has it" phenomenon — the DNA of a child is a combination of the two parents, but not only a combination; some changes happen.

The mechanics are simple and fully random. For each child, pick one bit — any bit, your choice — and change it to any allowed value except the current one. In the queens problem a position can only hold 1, 2, 3, or 4, so if the chosen bit is 2, it may become 1, 3, or 4; if it is 1, it may become 2, 3, or 4; and so on.

How many bits should change? The preference is one bit — or at most two. If you change all four bits, the child becomes completely different from its parents; that also happens in the real world, so it is not a hard-and-fast rule, but usually we change one or two bits so that the child is still recognizably a child of its parents while carrying its own unique qualities. Different authors prefer different conventions, but one-bit mutation is the standard practice.

6.5.2 Mutation in the Example

The four children after crossover were C1 = 2422, C2 = 1141, C3 = 1432, C4 = 1422. One bit is picked per child — again at random — and changed:

• C1 = 2422: the chosen bit is a 2. The board already contains 2s and a 4, so to bring in new flavor the 2 is changed to 1 (picking 3 would also have been fine) → C1' = 1422. Since 2422 and 1422 differ in exactly one position — the leading 2 became 1 — the mutated bit is the first position.
• C2 = 1141: the chosen bit is a 1, so it may become 2, 3, or 4. The chosen value is 3, so a 3 replaces one of the three 1s. The lecture does not announce which position changed; the valid outcomes are 3141, 1341, and 1143, and any of them is a correct mutation. The trace below uses 3141 as one valid instance.
• C3 = 1432: the chosen bit is the 3, which may become 1, 2, or 4. The chosen value is 2 → C3' = 1422.
• C4 = 1422: the chosen bit is a 2, which may become 1, 3, or 4. The chosen value is 3 → C4' = 1432.

Whatever we get here is the ultimate child — the individual that moves on. The vectors are then translated back into board configurations using the same rule as before (a 2 means the queen sits in row 2 of that column, and so on), and the first iteration of the genetic algorithm is complete.

6.5.3 Completing One Iteration — and Then the Loop

"First iteration" means: compute the fitness value for each child. The method is the same pair-enumeration as before — six pairs per board, count the non-attacking ones. For C1' = 1422 the computation works out as before: two attacking pairs (Q2–Q4 diagonally, Q3–Q4 in the same row), fitness 4. Two of the other children repeat boards whose fitness we already found in section 6.2.2 — 1422 scored 4 and 1432 scored 2 — so only C2' is genuinely new; its fitness follows from the same six-pair count, and computing it is the practice the lecture gives you. If any child's fitness is 6 — the threshold — that child is the answer and the algorithm stops.

If nobody reaches 6, the loop continues, and this is the most interesting part of the algorithm: every parent was once a child. The children become the parents of the next generation: compute their probabilities, put them on the roulette wheel, select couples, perform crossover, perform mutation, and repeat. At each new iteration you compare generations: if the fitness values of one iteration and the next are exactly the same as a set, nothing has improved and the algorithm stops (stopping criterion 3); if there is a change, continue. If a fixed iteration count was given (say, 5 iterations), stop there even without the optimum.

A side note on versions: in the vanilla (original) version, no states are saved — the algorithm simply stops with the last child. In coding, it is technically possible to retain the final vector and fitness value of every generation, loop through them, and return the maximum — that is a valid implementation choice, but the original algorithm as taught does not do it.

6.5.4 Student Questions and Answers

6.5.5 Applications and Exam Notes

Genetic algorithms are used for creative tasks and planning problems, among other things. There is also an online/offline distinction worth knowing: are you doing the computation during runtime (online) or are you precomputing and keeping the results (offline)? Both styles exist; the earlier example in this course was patent databases — precompute and keep, reuse later.

Real-world: the framing here is that genetic algorithms give you a "good enough" answer, not a promise of the best one. A student example that was confirmed in class: a traffic management system cannot afford to wait for the most optimized solution in real time — by the time it is computed, it becomes obsolete; the model has to act, so we look at a good solution, and that is exactly what this class of algorithms provides.

Real-world: the sustainability angle — these algorithms are computationally expensive, and that connects to the global debate about whether AI is harmful, since running such complex algorithms is not sustainable in the long run.

Recap + bridge. One complete iteration of the genetic algorithm is: random boards → fitness → probabilities → roulette parent selection → crossover → mutation → fitness of the children → check the stopping criteria (threshold 6, generation cap, or identical successive iterations). If none fires, the children become the next iteration's parents, and the loop repeats. With the whole loop visible — selection, crossover, mutation, and their limits — the lecture now leaves genetics behind and copies a different animal: ants finding food.

Real-world connection. The "good enough in time" property is why genetic algorithms run inside real-time decision systems: route planning for delivery fleets, crew scheduling for airlines, antenna and circuit design, and even game-playing programs. The same loop you just traced — score, select, mix, mutate, repeat — is what those systems do millions of times per second, and the same caveat applies to all of them: no guarantee of the global optimum, only a strong probable answer delivered inside the time budget.

6.6 Ant Colony Optimization: The Biological Motivation

6.6.1 The Setup: Nest, Food, and Two Paths

Ant colony optimization (ACO) is the second multiple-instance local search technique of the course. Like genetic algorithms, it is bio-inspired — but where genetic algorithms copy human evolution, ACO copies how ants find their food. The motivation story is simple and beautiful, and the exam-side of it is even simpler: big formulas, all given, substitute and go. The motivation is what you should really absorb.

Imagine a nest with many ants — A1, A2, A3, and so on — and, somewhere away, food. Between the nest and the food there are two possible paths: a short one and a long one. Two ants, A1 and A2, start their journey toward the food. Both move along the same initial segment (only one path existed so far), and both continuously release a hormone as they walk — that hormone is the pheromone. Pheromones are the ants' communication medium: other ants can smell that some ants have visited these places.

The two ants reach a decision point where the path splits. A1 takes the top (short) path; A2 takes the bottom (long) path. Both keep releasing pheromones on their way.

6.6.2 The First Return: How Pheromone Density Decides

The key quantity is the pheromone density — measured, in the narration's own way, in Boolean terms: if one ant has released pheromone on a stretch, the density is 1; if two ants have released, the density is 2.

While A2 is still slowly walking the long path, A1 has already reached the food. Now A1 must come back to the nest, retracing the short path in reverse — and at the decision point it faces the same choice again. The heart of the algorithm is right here: the ant checks the pheromone density on each option. On the top (short) path the density is 1 — A1 itself deposited pheromone going out. On the bottom (long) path, at that moment, the density is 0 — no ant has come back through there yet, because A2 has not even reached the food, let alone returned. A1 reasons, in effect: this path has density 1, that one has 0, so take this route. It continues releasing pheromone and reaches the nest.

Now A2 finishes its long journey, finds the food, and comes back the same way. At the decision point, A2 also checks densities — but by now the numbers have changed. The short path has density 2: A1 went out once and came back once, two traversals. The long path has density 1: only A2 has been there. So A2 also takes the short path, raising its density to 3, then 4, then 5, as more and more ants use the common route.

So even though A2 never walked the optimal path itself, the colony as a whole found the shortest route after roughly one iteration — because the first ant back from the food, plus the pheromone arithmetic, made the short path the obvious choice for everyone.

6.6.3 Evaporation, Convergence, and the Glitch

Why does the long path not stay competitive? Because pheromones evaporate. The single unit of pheromone on the long path slowly evaporates away to zero — while on the short path, ants are constantly depositing fresh pheromone, so its density never drops to zero. The path with the higher pheromone density attracts the next ant, which deposits more, which attracts more — the classic positive feedback that converges the colony onto one route.

This is not speculation about ant behavior; real observational studies were done in the 1970s, with real ants. Initially, when no territory is known and there are no pheromone values, ants at a decision point go in different routes. Then, using their pheromones, they start communicating, and eventually they all follow the same path.

Real-world: if you watch a clan of ants at home, they all follow each other, moving in a group — that follow-the-group behavior is the real-world basis of the algorithm.

6.6.4 Student Questions and Answers

Recap + bridge. ACO copies how ants find food: walk, drop pheromone, and at every decision point choose the route with the higher pheromone density; used routes keep getting reinforced while unused routes evaporate to nothing. The mechanism works only if the good route is discovered early, and it never guarantees the global optimum. The next step turns this story into mathematics: the travelling salesman problem, a transition probability formula, and a pheromone updation formula — the two formulas the ants in the exam will need.

Real-world connection. The same follow-the-scent logic, formalized by Marco Dorigo in the early 1990s, now routes packets in communication networks, plans delivery routes, and schedules vehicles — any problem where many cheap agents sharing a cheap memory can outperform one clever planner. And the glitch matters in practice too: field deployments of ant-based routing have to handle exactly the "first ant was unlucky" scenario, which is why the formulas include an evaporation term to let bad trails die out.

6.7 Ant Colony Optimization: Formal Model and Formulas

6.7.1 The Problem: Travelling Salesman Problem

The exam-shaped problem for ACO is the Travelling Salesman Problem (TSP). Given N cities arranged as a graph — a complete graph, so no city is disconnected — the goal is to find the shortest path that goes through all the cities, visiting each one exactly once, and returns to the starting city. Every edge has a cost given in the problem data.

The algorithm works as follows: each ant builds its own tour starting from the starting city. At every step, the ant chooses the next city to go to with a probability (the transition probability formula below), while keeping track of the visited list so it never revisits a city. When the tour is complete, the ant lays pheromones on the edges it used, and those pheromones influence the next round. In a typical exam question you are given the graph, the nodes, the costs, and a pile of parameter values, and you must find the path the ants take using the formulas.

Picture the standard figure: N dots spread in a ring, every pair joined by a line, each line labelled with its cost. The ant starts at one dot, and at each dot the outgoing labels are the candidate costs; the formula below turns those labels into probabilities. That figure — a complete weighted graph — is the entire input of the problem.

6.7.2 Parameters and Symbols

All the parameters below are given in the question (for exams) and predefined by you from domain expertise (in real problems):

• $N$ — the total number of ants; must be greater than one.
• $\tau$ (tau) — the pheromone amount. The initial pheromone values on all edges, ${\tau }_0$, are given in the question.
• ${\tau }_{ij}$ — the amount of pheromone deposited while traversing from node $i$ to node $j$.
• ${\eta }_{ij}$ (eta) — a desirability term defined as one over the cost of the link: ${\eta }_{ij}=\frac{1}{\text{cost}(i,j)}$. If the link $i$ to $j$ costs 70, then ${\eta }_{ij}=1/70$. It is nothing but one-by-the-cost: cheap links get a big eta, expensive links a small one.
• $\alpha$ (alpha) — the importance coefficient of the pheromone density; it appears as a power on $\tau$.
• $\beta$ (beta) — the importance coefficient of the route cost; it appears as a power on $\eta$.
• $\rho$ (rho) — the evaporation coefficient, a number in $(0,1)$ that decides how fast unused pheromones decay.
• $Q$ — the importance constant that scales how much pheromone a used edge receives.
• $L_k$ (written $F_k$ in some slides) — the route (tour cost) taken by ant $k$.
• visited list — the list of nodes the ant has already visited; the ant may only move to nodes not on this list.

A piece of intuition worth keeping about evaporation: if you keep multiplying a big number by a smaller number — the $(1-\rho )$ factor — it keeps diminishing and tends toward zero. Technically it will not become exactly zero; it becomes a very small, insignificant number. That is what evaporation does to unused paths.

6.7.3 The Transition Probability

The first formula tells the ant where to go next. Standing at node $i$, the probability of moving to node $j$ — the next transition probability $P_{ij}$ — is:

$$P_{ij}=\frac{{\tau }_{ij}^{\alpha }\cdot {\eta }_{ij}^{\beta }}{{\sum }_{h\in \text{allowed}(i)}{\tau }_{ih}^{\alpha }\cdot {\eta }_{ih}^{\beta }}$$

where the sum runs over all nodes $h$ the ant can still visit (the unvisited ones; visited nodes are excluded so the ant never returns to a city it has already covered). The numerator is the pheromone term raised to alpha times the eta term raised to beta; the denominator is the sum of those same expressions over every allowed choice, which normalizes the result into a probability. Because $\eta$ is just one-over-cost, the whole formula is "nothing but one-by-the-cost" weighted by pheromones.

Build it step by step. First, the desirability of a single move $i\to j$ combines two signals: how much pheromone sits on that edge, ${\tau }_{ij}$, and how cheap the edge is, ${\eta }_{ij}=1/\text{cost}(i,j)$. Raising the first to $\alpha$ and the second to $\beta$ lets the problem designer control which signal dominates: a large $\alpha$ makes the ant a scent-follower, a large $\beta$ makes it a cost-hunter. Then the denominator adds the desirability of every alternative move, so the fraction says: "this move's desirability, as a share of all desirability on the table."

Notation note: many textbooks write the exponent terms as ${\tau }_{ij}^{\alpha }{\eta }_{ij}^{\beta }$ exactly as here, and call the result the transition probability $P_{ij}^k$ for ant $k$; the lecture keeps it as $P_{ij}$ to match the slides.

Two sanity checks that are worth memorizing along with the formula. First, the probabilities of all allowed moves from $i$ add to 1, because every numerator is a slice of the same denominator. Second, the limiting case $\alpha =\beta =0$ — no pheromone, no cost — makes every allowed move equally likely with probability $1/|\text{allowed}(i)|$, which is exactly the uniform random walk an ant performs before any information exists.

6.7.4 Pheromone Updation

After the ant moves, a second, very important step follows: pheromone updation — the ants deposit pheromone on the path they just used. The new pheromone value on edge $i$–$j$ is:

$${\tau }_{ij}^{\text{new}}=(1-\rho ){\tau }_{ij}^{\text{old}}+\Delta {\tau }_{ij}$$

The $(1-\rho ){\tau }_{ij}^{\text{old}}$ term is the evaporation part, and it applies to every edge — even unused edges must be updated, or their pheromones would never evaporate. The extra term $\Delta {\tau }_{ij}$ is present only on the edge the ant actually traversed:

$$\Delta {\tau }_{ij}=\{\begin{array}{ll}\frac{Q}{L_k}& \text{if ant }k\text{ passed through }i\to j\\ 0& \text{otherwise}\end{array}$$

For all other edges the delta is zero — they only lose pheromone through evaporation.

The structure of the updation deserves one careful look, because it is two effects in one equation:

• Evaporation for everyone: every edge, used or not, multiplies its old pheromone by $(1-\rho )$. With $\rho =0.1$, every edge keeps 90% of its pheromone per iteration. Repeating this shrinks an unused edge geometrically: $\tau \to 0.9\tau \to 0.81\tau \to \dots$ — it never hits exactly zero, but it becomes insignificant, which is the intuition from the ant story.
• Deposit for the traveller only: the edge the ant actually used adds $\Delta {\tau }_{ij}=Q/L_k$. A shorter route (smaller $L_k$) earns a bigger deposit — exactly the positive feedback that made the short path attractive in the story. Note that in the lecture's version $L_k$ is the cost of the leg just traversed, so the deposit is $Q$ divided by that leg's cost; some standard presentations instead use the full tour length of ant $k$ — the relationship is the same (shorter tours, bigger deposits), but in this course's problems, use the leg cost as the slides do.

Notation note: the delta is often written $\Delta {\tau }_{ij}^k$ in the literature to make explicit that ant $k$'s deposit applies only to its own edges.

Recap + bridge. Two formulas run the whole method: the transition probability $P_{ij}$ decides where the ant goes next, and the pheromone updation ${\tau }_{ij}^{\text{new}}=(1-\rho ){\tau }_{ij}^{\text{old}}+\Delta {\tau }_{ij}$ with $\Delta {\tau }_{ij}=Q/L_k$ on the used edge refreshes the trails. Every step of an ACO problem is those two formulas repeated. The next section applies both to a complete five-city example — the exact question shape the exam uses.

Real-world connection. These two formulas are the entire engine of ant-based routing systems: telecommunications networks use them to route packets around failed links, delivery companies use them to replan routes when a truck is delayed, and the same $(1-\rho )$ evaporation term that protects the ant colony from a stale short-cut also lets a routing network forget an old traffic pattern within a few minutes. The design lesson is universal: a small amount of forgetting is what keeps a learning system from being stuck with its first discovery.

6.8 Ant Colony Optimization: Worked Example — Five Cities

6.8.1 The Given Data

The example: number of ants = number of cities = 5 (this equality is a choice, not a rule — more on that in the Q&A), with the ants starting at city 4. The constants are $\alpha =0.5$, $\beta =0.75$, $\rho =0.1$, and $Q=100$. All of this is given in the question.

The graph is translated into a cost adjacency matrix — in data structures terms, a matrix where entry $(i,j)$ is the cost of the edge from city $i$ to city $j$. Because this is a travelling salesman problem, the graph is bidirectional — going from Mumbai to Delhi costs the same as Delhi to Mumbai — so the matrix is symmetric: $\text{cost}(i,j)=\text{cost}(j,i)$. The costs announced in the lecture are cost(1,2) = 65, cost(1,3) = 52, cost(4,1) = 69, cost(4,2) = 28, cost(4,3) = 72, cost(2,3) = 39; the slide's full $5\times 5$ matrix supplies the remaining entries (the costs of the edges touching city 5 and the 1–4 direction's mirror). In an exam, every entry is printed on the graph.

The initial pheromone values are also given: ${\tau }_{12}=0.54$ (and ${\tau }_{21}$ the same, since the table is symmetric), ${\tau }_{41}=0.35$, ${\tau }_{42}=0.39$, ${\tau }_{43}=0.32$, ${\tau }_{45}=0.68$ — these are the values the narration actually uses, and by symmetry ${\tau }_{14}=0.35$, ${\tau }_{24}=0.39$, ${\tau }_{34}=0.32$, ${\tau }_{54}=0.68$. The remaining initial entries come from the slide.

There are only two steps per move, and the whole problem is just these two steps repeated: step one — where to go next (transition probability), step two — after reaching the destination, update the pheromones. One simplification: if only one unvisited city remains, skip the probability computation entirely and move directly.

6.8.2 Step 1: Transition Probabilities from City 4

From city 4 the ant can go to 1, 2, 3, or 5. So we compute $P_{41}$, $P_{42}$, $P_{43}$, and $P_{45}$ and move to the largest.

Take $P_{41}$ in full. With $i=4$, $j=1$:

$$P_{41}=\frac{{\tau }_{41}^{\alpha }\cdot {\eta }_{41}^{\beta }}{{\tau }_{41}^{\alpha }{\eta }_{41}^{\beta }+{\tau }_{42}^{\alpha }{\eta }_{42}^{\beta }+{\tau }_{43}^{\alpha }{\eta }_{43}^{\beta }+{\tau }_{45}^{\alpha }{\eta }_{45}^{\beta }}$$

Substituting the given values: ${\tau }_{41}=0.35$, $\alpha =0.5$, ${\eta }_{41}=1/\text{cost}(4,1)=1/69$, and $\beta =0.75$. So the numerator is:

$${\text{num}}_{41}=0.35^{0.5}\times {\left(\frac{1}{69}\right)}^{0.75}$$

Worked with a calculator: $0.35^{0.5}=0.5916$, $(1/69{)}^{0.75}=(0.01449{)}^{0.75}=0.0418$, so ${\text{num}}_{41}\approx 0.5916\times 0.0418\approx 0.0247$.

The denominator is the sum of the same expression over all four choices, and this is where the reuse trick lives. Compute the other numerators once:

$${\text{num}}_{42}=0.39^{0.5}\times {\left(\frac{1}{28}\right)}^{0.75}\approx 0.6245\times 0.0822\approx 0.0513$$

$${\text{num}}_{43}=0.32^{0.5}\times {\left(\frac{1}{72}\right)}^{0.75}\approx 0.5657\times 0.0404\approx 0.0229$$

$${\text{num}}_{45}=0.68^{0.5}\times {\left(\frac{1}{\text{cost}(4,5)}\right)}^{0.75}$$

with ${\eta }_{42}=1/28$, ${\eta }_{43}=1/72$, and $\text{cost}(4,5)$ read from the slide's matrix (the audio does not announce it — but the probability sum must close at 1, which pins it down as discussed below).

Now the payoff: the numerator of $P_{42}$ — $0.39^{0.5}\times (1/28{)}^{0.75}\approx 0.0513$ — appears identically inside the denominator of $P_{41}$. If you do the first probability carefully, you have already computed the terms you need for the others; each subsequent probability is just a new numerator divided by the same denominator:

$$P_{41}=\frac{0.0247}{0.0247+0.0513+0.0229+{\text{num}}_{45}}\approx 0.17$$

$$P_{42}=\frac{0.0513}{0.0247+0.0513+0.0229+{\text{num}}_{45}}\approx 0.35$$

$$P_{43}=\frac{0.0229}{0.0247+0.0513+0.0229+{\text{num}}_{45}}\approx 0.16$$

The slide reports the winner: $P_{42}\approx 0.35$ is the maximum among the four (the audio garbles the smaller decimals, and the remaining probability $P_{45}$ comes out at about 0.31–0.32 so that the four sum to 1 — the ranking is what matters: P42 wins). The ant moves from 4 to 2.

6.8.3 Pheromone Updation after 4 → 2

Now step two: update the pheromone table with

$${\tau }_{ij}^{\text{new}}=(1-\rho ){\tau }_{ij}^{\text{old}}+\Delta {\tau }_{ij}$$

Why do we apply the $(1-\rho )$ factor to the edges we did not use? That is exactly the evaporation from the ant story: when a path is not used, its pheromones slowly evaporate. If we did not update the unused edges, they would never decay.

6.8.4 The Rest of the Tour

The same two steps repeat:

• From city 2: the ant cannot go back to 4 (it came from there), so compute $P_{21}$, $P_{23}$, and $P_{25}$ with the same formula. The maximum is $P_{23}$ — the ant moves 2 → 3. Update: only the 2–3 edge gets $\Delta =100/39$, since cost(2,3) = 39; all other edges get $0.9\times$ their current value.
• A very common student mistake: in this second updation, students go back to the pheromone values from the question. Wrong — the pheromones were already updated after the first leg. The values used here are the first-iteration pheromone values, the ones just computed: for example, the 1–2 edge starts this step at 0.486, not 0.54.
• From city 3: the ant cannot return to 2, so only 1 and 5 remain — compute $P_{31}$ and $P_{35}$. The reuse trick pays off here: the numerator of $P_{31}$ equals the numerator computed earlier for the 1–3 direction (the tau and eta values are symmetric: ${\tau }_{31}={\tau }_{13}$ and ${\eta }_{31}={\eta }_{13}=1/52$), so you can reuse the value already on your page. The maximum is $P_{35}$ — the ant moves 3 → 5. Update: only the 3–5 edge gets $\Delta =Q/\text{cost}(3,5)=100/\text{cost}(3,5)$ (the slide's value for cost(3,5) is not announced in the audio; the formula is the same $Q/L_k$ with $L_k$ the cost of this leg).
• From city 5: the only unvisited city left is 1. This is a no-brainer — no probability calculation needed; the ant moves 5 → 1 directly, and the pheromone updation is done for the 5–1 edge alone: $\Delta =100/\text{cost}(5,1)$, the rest evaporating at $0.9\times$.
• From city 1: the travelling salesman must return to the origin. City 4 is the starting city, so the final move 1 → 4 is forced — again no formula, just the updation: ${\tau }_{14}^{\text{new}}=0.9\times {\tau }_{14}^{\text{old}}+100/69$, because cost(1,4) = 69.

6.8.5 Interpreting the Result

The final tour is 4 → 2 → 3 → 5 → 1 → 4. That is the answer: the path the ants took, given the pheromones and the costs.

One thing this answer is not: it is not guaranteed to be the optimal tour. The computation simply reports the probable solution the ant colony produced under the given pheromones — a probable solution to the travelling salesman problem. Whether it is optimal is a separate question; ACO does not guarantee it, as the counter-argument Q&A below established.

Real-world: the travelling salesman problem is a classic computer science problem — a travelling salesman who has to visit different cities to sell and then come back home can use exactly this method to choose a route.

Real-world: this style of question mirrors the route-optimization assignment — where you must also know that ACO may or may not return the optimum, and that a statement of that limitation earns credit in a write-up.

The example is not difficult and not too lengthy if you reuse the intermediate terms — do the hard work once and the rest falls out.

6.8.6 Student Questions and Answers

Recap + bridge. Two steps repeated five times produced the tour 4 → 2 → 3 → 5 → 1 → 4: compute the transition probabilities from the current city, move to the maximum (or move directly when only one city remains), then update every edge with $(1-\rho )$ and add $Q/L_k$ on the used edge only — always from the current pheromone table. That completes the second multiple-instance local search technique. The module's last topic is a different animal entirely: using genetic algorithms to design neural networks.

Real-world connection. This five-city example is the smallest honest instance of what delivery and logistics software do at city scale: the route-optimization assignment uses the same two formulas on larger graphs, and the lesson to carry into it is that ACO returns a probable solution — stating that limitation explicitly is itself worth credit. The reuse trick matters in the exam and in code: computing each numerator once and dividing by a shared denominator is what lets the algorithm scale from five cities to hundreds without redoing work.

6.9 Neural Architecture Search (NAS)

6.9.1 What Is NAS — The Era of Self-Designing AI

The module has now covered uninformed search, heuristic functions, and local search. The one remaining piece is neural architecture search (NAS) — a different kind of topic, based on research papers rather than textbook algorithms, and one the course enters slowly.

The motivation answers a question students kept asking: why do we manually design heuristics and manually design fitness functions — can this be automated? Yes, and a seed of the idea already appeared earlier in this course: patent databases, where we pre-compute and keep results so we can reuse them later, instead of recomputing at runtime. Something similar can be done for search itself. And today's topic, genetic algorithms, gives a concrete route: with a genetic algorithm you can perform an automated search that automatically creates a neural network. That is the era of self-designing AI, and NAS is its name.

Two research papers are linked for this session; both are on arXiv and free to download, and both deserve at least a glance even if you do not fully follow them yet — reading research papers is slightly tricky when you are not used to it, but the course will go through the ideas in class.

6.9.2 CoDeepNEAT: Evolving Deep Neural Networks

The main paper is CoDeepNEAT — Co-Evolving Deep Neural Networks by Augmenting Topologies. It is an automated method for designing deep neural network architectures. Traditionally, network architectures rely on human experts who design them manually; CoDeepNEAT replaces that manual design with evolutionary search — and of the two evolutionary algorithms in this course (genetic algorithms and ant colony optimization), the paper uses the genetic one.

The mechanism will be familiar: inspired by natural evolution, architectures are gradually improved through selection, mutation, and recombination — where selection is the parent selection we practiced, recombination is the crossover, and mutation is the gene modification. The goal of the paper's method: automatically evolve a neural network that can accurately classify images such as cat and dog, without any manual design decision.

Why bother? Manually designing neural networks is challenging because the state space of architectures and parameters is enormous, and human experts rely on trial and error and prior knowledge — which limits them to fairly conventional architectures. An evolutionary search can explore that space and occasionally produce novel children — architectures a human would never have tried. The paper combines the genetic algorithm with gradient descent: the genetic level evolves the architecture, and the weights are trained by gradient descent — a hybrid optimization approach.

The lineage of the idea is worth keeping straight, because the paper builds on it: NEAT (NeuroEvolution of Augmenting Topologies) was the earlier method — "augmenting topologies" meaning the architecture grows by adding nodes and connections as evolution proceeds. The paper first extends NEAT into DeepNEAT, which evolves the topology and hyperparameters of deep networks, and then goes further to CoDeepNEAT, which co-evolves two kinds of structures — modules (small reusable network building blocks) and blueprints (how the modules are assembled) — so that repetitive, deep structures can be assembled automatically. The paper's results match the state of the art on the CIFAR-10 image-classification benchmark, evolve LSTM structures for language modeling, and even build a real captioning application for an online magazine. Each method has its own slides in the course material describing what it is, what problem it solves, and how its networks are generated.

6.9.3 Neural Evolution: GA Concepts Mapped to Networks

The central idea is neural evolution — using genetic algorithms to evolve neural networks. Every network is evolved by the same principles just studied:

1. Create an initial population — many random networks.
2. Train each network once (a single training run).
3. Measure performance — that is the fitness.
4. Select the best performers — that is parent selection.
5. Generate new networks — first crossover, then mutation.

The vocabulary maps cleanly:

The loop is the same loop as the four-queens example: score the networks, select the best as parents, combine them with crossover, perturb with mutation, and repeat — each cycle is one generation of the population of networks. The only difference is that the "individual" is now a whole neural network architecture instead of a four-digit board vector, and its fitness comes from actually training it once and measuring performance.

6.9.4 The Plan, the Papers, and Exam Notes

The plan for the next session: walk through the paper step by step — what each step of the method does — and then solve an example. The example is distinctive because the problem looks like a neural network question (an image classification / caption generation type problem) but the solution mechanism is genetic: show the iteration of the phenotype, the fitness value, selection, crossover, and mutation. Mostly the session will solve that one example; the theory parts will be glanced through quickly. After NAS, the module moves to game playing.

Practice exercises: every section of the material carries one or two exercises — for example, given parents, use single-point crossover to generate 2 children, a question from a past mid-semester. A very similar question appeared in a recent webinar session. Solving these exercises is the recommended preparation.

Recap + bridge. Neural architecture search automates the design of neural networks with the same genetic machinery as the four-queens problem: a population of networks, fitness from training, parent selection, crossover, mutation, and a loop over generations. CoDeepNEAT is the paper version — NEAT extended to deep networks and then to co-evolved modules and blueprints — and its example iteration is what the next class will solve. With that, the local-search module closes, and the course moves to game playing.

Real-world connection. NAS is the research backbone of automated machine learning: the same recipe — evolution or search over architectures, gradient descent for weights — now designs production networks for image classification, speech recognition, and language models, replacing years of human trial and error. The cat-versus-dog classifier in the paper is the toy scale of what this machinery does at industrial scale, and the hybrid design (evolution for architecture, gradient descent for weights) is the pattern every serious NAS system since has followed.

Exam Guidance Summary

Genetic algorithms:

• Exam problems will normally ask for one iteration of the algorithm and tell you to stop — you will be told how many iterations or states to generate. You rarely choose stopping points yourself.
• The initial boards are chosen by you, randomly; the count to start with (K) is given in the question. The boards will not be provided.
• The three stopping criteria (threshold reached, predefined generation count, no change between iterations) are core vocabulary.
• The roulette wheel is the parent-selection method used in this course — tournament and ranking exist but are not practiced here.
• Expect the crossover family: single-point (draw one line, swap tails, always two children), two-point (swap the middle segment), uniform (swap a stated percentage of bits, e.g. 50% or 25%). A past mid-semester question asked for single-point crossover producing two children from given parents; a similar question appeared in the webinar.
• Mutation: change one bit per child (one or two bits, not more) to any allowed value other than the current one.
• Solving a linear equation with a genetic algorithm was a past mid-semester question — same flow as the queens example: random initialization, fitness, probabilities, selection, crossover, mutation. An uploaded solution is available.
• Do not expect GA to guarantee optimality — the entire class is local search; that limitation itself is exam-relevant.

Ant colony optimization:

• The mid-semester is closed book — the transition probability formula and the pheromone updation formula must be memorized.
• If an ACO question appears, it is worth roughly three to four marks, with fewer nodes and simpler numbers than the worked example.
• Reuse intermediate terms: the numerator of one transition probability appears inside the denominators of the others — compute once, save time.
• Remember that only the used edge gets the delta $Q/L_k$; all edges still get the $(1-\rho )$ evaporation factor. Use the updated pheromone values from the previous iteration, never the original table.
• $\rho$ is commonly 0.1 in many problems — slow evaporation.
• ACO does not guarantee the global optimum — and stating that counter-argument is itself worth credit (about a mark) in an assignment write-up.

Neural architecture search:

• NAS theory will not be asked; the example-style genetic algorithm iteration (phenotype, fitness, selection, crossover, mutation) is what to practice.
• Read the two linked papers on arXiv at least once, even a glance.

General: solve the exercises at the end of each section — they recycle past mid-semester questions.

Key Industry Applications

• Genetic algorithms — creative tasks and planning problems; solving linear equations; route optimization (the assignment); any situation where a good-enough answer must be found fast, such as traffic management systems, where the most optimized solution would become obsolete before it could be used.
• Genetic algorithms and sustainability — these algorithms are computationally expensive, and that cost is part of the wider debate about AI sustainability.
• Ant colony optimization — the travelling salesman problem, a classic computer science problem (a salesman visiting cities and returning home); route optimization in the assignment; the real-world ant behavior it copies (ants following each other in groups).
• Online vs offline computation — the choice of computing during runtime versus precomputing and keeping results; the patent-databases style of reuse was the course's earlier example.
• Neural architecture search — automated design of deep neural network architectures, e.g. evolving a network that classifies cat versus dog images without manual design; the era of self-designing AI, built on evolutionary search (genetic algorithms) plus gradient descent for the weights.