Skip to main content
BitsNotes
—

5.2 Local Search and the Mindset Change

The mindset change: in every algorithm studied so far, the answer was the journey. In local search, the answer is the state itself. The professor put it in one line: "the path to the goal is a solution" was the old world; "any state is a solution" is the new one.

5.2.1 The Mindset Change: State as Solution

In every algorithm studied so far — uninformed, informed, and everything in between — the path to the goal was the solution. We did a systematic exploration of the search space. Think of the 4-Queens problem: the board is empty, we place the first queen anywhere, then the second queen, and so on, generating several options at each step, and we keep going until we reach a board where nobody attacks anybody. The 8-puzzle worked the same way: moving the empty tile produces children, and we keep expanding until the goal configuration appears. In all of these, the answer we returned was the journey — the sequence of moves and the path cost from the initial state to the goal state.

Local search flips this completely. The mindset change is that a state itself is a solution to the problem. For many optimization problems the path is irrelevant: we do not care how the queens got placed, we only want a board where no two queens conflict. The state space is nothing but a set of complete configurations, and the job is to find the configuration that satisfies the constraint. The analogy on offer: one philosophy cares about the journey — how do I go from the initial state to the goal, at what cost, along which path. The other philosophy says the state is the destination, and we only ask how good or bad it is. The classic Bucharest route example makes the point: the path A → B → C → D costs 85, while the route A → B → D costs 65 — both are feasible answers, but only one is optimal. The same holds in local search: you hand over any valid state, it is an answer, and only later do we ask whether it is the best one.

A practical consequence: local search keeps track of a single current state. So far, every algorithm had to store a frontier in a queue or a stack — we expanded a node, asked where we can go next, and pushed those children onto the frontier, because the path mattered. Here we are interested only in the current node and its immediate neighbors. We ignore paths entirely.

Why would we want that? Because it uses very little memory — no state-space tree is built, only neighbors. It can often find reasonable solutions in large or even infinite state spaces. And it fits pure optimization problems naturally: all states carry an objective function, and the goal is to find the maximum objective value. There is no path cost, no goal-state formulation, no A* or IDA* running over a whole tree. We search the neighborhood of the current position until an optimal solution is found. The keyword is neighborhood: from the current state we allow only small changes, and we evaluate the states those changes produce.

Dimension Path-based search (so far) Local search (now)
What is the answer? The sequence of moves (path) + its cost The state itself
What is stored? A frontier (queue or stack) One current state (plus its neighbors)
What is explored? The whole search tree, systematically Only the neighborhood of the current state
Cost model Path cost from initial to goal Fitness value of a state
Guarantee Optimal under admissibility/consistency No guarantee of global optimum

When to pick which: use path-based search when reaching the goal is itself the deliverable (route planning, puzzle solving); use local search when only the final configuration matters (feature selection, robotics, hyperparameter tuning).

Worked example — Bucharest, two routes. Suppose you must reach Bucharest from the start city, and two complete routes are known: A → B → C → D with total cost 85, and A → B → D with total cost 65. Both are valid answers: both actually get you there. But 65 < 85, so only the second is optimal. Notice that the question "which route is better" is answered by comparing the final numbers, not by re-walking the roads. That is the local-search attitude: any complete configuration is an answer; the fitness (here, the total cost) tells you how good it is. Sense-check: a shorter route exists, so a "good enough" answer (85) is feasible but not optimal — exactly the gap hill climbing will struggle with later.

Real-world: local search is the natural fit when only the final solution matters, not the path — feature selection, robotics, and hyperparameter tuning are the examples given. A robot is a nice image: it senses the states around its current position and moves only there; it does not plan the entire future from scratch on every step.

5.2.2 Fitness Values versus Heuristics

Optimization is central to AI: many AI problems ask for the best solution among a vast number of possibilities. The terminology for this course:

  • Goal: navigate the state space of a given problem so that the optimal solution is found.
  • Objective: minimize or maximize, depending on the problem.
  • Scope: local — most of these algorithms do not guarantee the global (best) solution; they return a local solution.
  • Fitness value: a number that tells how good or bad a state is.

The fitness value deserves care. It looks like a heuristic, but there is a difference. A heuristic value is given to us — by an SME, or derived from pattern databases, or learned from data. A fitness value is not given; the domain designer defines it, and we compute it for any state we are given. The running summary: with heuristics, the value drove our next steps in advance; with fitness values, we start from a state and evaluate it afterwards. Many books write it as , others as — same idea, different labels.

Exam note: do not be rattled when the terms are swapped; "heuristic value" and "fitness value" are used interchangeably in the exercises. The exam will happily write "heuristic value" on a beam search question where the intended meaning is the fitness. Read it as the fitness.

5.2.3 Categories and Course Scope

Local search splits into two categories. Single-instance-based methods work on one state at a time: hill climbing, local beam search (a variant), simulated annealing, and others. Multiple-instance (population-based) methods work on a set of states at once: genetic algorithms, ant colony optimization (ACO), and particle swarm optimization. This offering of the course was trimmed: we will study hill climbing and its variants, local beam search and its variants, genetic algorithms, and ant colony optimization. We will not study particle swarm optimization or simulated annealing in depth.

Exam note: that scope statement is a syllabus fact — hill climbing plus variants, local beam search plus variants, GA, and ACO are the algorithms of this module. Particle swarm optimization and simulated annealing are context only; do not spend exam revision on their inner workings.

5.2.4 Student Questions and Answers

Q: Is it like we find one solution to a problem and then optimize the solution?

A: Exactly. But whether that optimization actually reaches the global optimum is not guaranteed — none of these algorithms promise the best answer. Among the given states, which one to choose and improve is the whole game. The optimization to the goal solution might happen, and it might not.

Q: How can we decide whether we have reached the goal?

A: Take a random board, say a 4-Queens configuration. Any configuration is an answer. You then evaluate its fitness value to see how good it is, and you take small steps until you are satisfied — that is what the algorithms will do. The answer to "have I reached the goal" comes from evaluating the fitness, not from tracing a path.

Q: Earlier, structured search visited all feasible states. Here we seem to work randomly — is it possible that we recycle states we have already seen?

A: Yes, recycling may sometimes happen. We will see exactly where when we study the algorithms.

5.3 The 4-Queens Problem: Representation and Fitness

Hook: a 4-Queens board with four attacking queens is, in local search, still a "solution" — the word just means something different here. Before we can improve a board, we need two tools: a compact way to store it, and a number that says how good it is.

5.3.1 The Vector Representation

To work with boards in a computer we never draw a board — we store one vector. For a 4-Queens board we write

where denotes the first column, the second column, the third column, and the fourth column, and the value inside tells the row of the queen in that column. The value 2 means "queen in the second row", 4 means "queen in the fourth row", and so on. Every variable can only ever take one of the four values 1, 2, 3, 4.

Worked example: decode the vector (1, 3, 2, 4) into a board.

The position in the vector is the column; the value is the row.

  • : queen in column 1, row 1.
  • : queen in column 2, row 3.
  • : queen in column 3, row 2.
  • : queen in column 4, row 4.

Place the four queens and the board is complete: (1, 3, 2, 4) means "one queen per column, sitting in rows 1, 3, 2, 4 respectively". Sense-check: four values, one per column, each a valid row — this vector always decodes to exactly one board.

This notation is used across the whole topic: the position in the vector is the column, the value is the row. Generation of these states is deterministic — no probability is involved in building neighbors.

5.3.2 The Fitness Value

The fitness value is the tool we use to decide how good a board is. For this course the running example defines it as the number of conflicting pairs of queens — queens that attack each other. Some examples count non-conflicting pairs instead; both are legitimate, and both were used at different moments, which is worth remembering when numbers appear to disagree.

A pair of queens (two queens, whichever they are) is the unit we count. With four queens labelled Q1, Q2, Q3, Q4, the number of possible pairs is the binomial coefficient

Six pairs in total: Q1–Q2, Q1–Q3, Q1–Q4, Q2–Q3, Q2–Q4, Q3–Q4. A pair conflicts if the two queens share a row, share a column, or share a diagonal. In row/column coordinates, sharing a diagonal means the row gap equals the column gap: .

For the 4-Queens problem with the conflicting-pairs definition, the best possible fitness is 0: nobody conflicts with anybody. With the non-conflicting definition, the best is 6: all six pairs are safe.

5.3.3 Worked Example: Counting Conflicts on the Board (2, 4, 2, 2)

Worked example: count the conflicting pairs on the board (2, 4, 2, 2).

The state decodes to: Q1 in column 1 row 2, Q2 in column 2 row 4, Q3 in column 3 row 2, Q4 in column 4 row 2.

Check the six pairs one by one:

  • Q1–Q2: rows 2 and 4, columns 1 and 2. Different row, different column, row gap 2 vs column gap 1 → not a diagonal → non-conflicting.
  • Q1–Q3: both row 2 → same row → conflicting.
  • Q1–Q4: both row 2 → same row → conflicting.
  • Q2–Q3: rows 4 and 2, columns 2 and 3. Row gap 2, column gap 1 → not a diagonal → non-conflicting.
  • Q2–Q4: rows 4 and 2, columns 2 and 4. Row gap 2, column gap 2 → same diagonal → conflicting.
  • Q3–Q4: both row 2 → same row → conflicting.

Conflicting pairs: 4. So the fitness value of (2, 4, 2, 2) under the conflicting-pairs definition is 4, which is not the global optimum (0). The board is a solution — a valid configuration — but not the goal. This distinction is the heart of the mindset change.

Scope: the conflict rule "same row, same column, or same diagonal" is the whole definition of an attack for queens. It assumes a standard square board where columns and rows are the only two axes; in other puzzles (say, knights or bishops) the rule changes, so re-derive it before reusing the formula. The binomial count also assumes we count each pair once — Q1 attacking Q2 and Q2 attacking Q1 are the same pair.

A handy way to picture the board: a 4 × 4 grid, rows numbered 1–4 from bottom to top, columns numbered 1–4 from left to right. A queen on the same "gray" diagonal as another means the two squares lie on the same NW–SE (or NE–SW) slope — walk one step down and one step right from Q2's square at (2, 4) and you land exactly on Q4's square at (4, 2). That is why the professor's diagram shades that diagonal gray.

5.3.4 Student Questions and Answers

Q: Why is a board considered a solution when it does not satisfy the conditions of the problem?

A: Students often think this way. In local search, any valid state is a solution — we are not claiming it is the goal. A solution is a feasible solution: it obeys the basic rules, such as one queen per column. Whether it is good or bad, near the goal or far from it, is decided by evaluating its fitness. So a board with conflicts is still a solution; it is just not the optimal solution. If a student hands in such a board, the evaluation says: feasible, but not optimal.

Q: How are the second and fourth queens conflicting? They look far apart.

A: They are on the same diagonal of the board — in the diagram, the same gray-colored diagonal. Same row, same column, or same diagonal always counts as a conflict.

5.4 Neighbor States and the 1NN Expansion

Hook: you have one board and a fitness value. What is the smallest change you can make, and how many one-change boards can you build from it? The answer — exactly 12 for 4-Queens — is the engine every local search algorithm runs on.

5.4.1 What Counts as a Neighbor

We never explore the whole tree. Instead, from the current state we make one small change and evaluate the result. A neighbor state is any state reachable by exactly one such change. From (2, 4, 2, 2) the neighbor (2, 4, 3, 2) differs only in Q3, which moved from row 2 to row 3; the neighbor (2, 4, 2, 3) differs only in Q4, which moved from row 2 to row 3. Every other component is unchanged, so a single move takes you back to the previous state.

This "one small change" rule is called the one-neighboring-region expansion, written 1NN. Two words of caution. First, 1NN here has nothing to do with k-nearest neighbors from machine learning — this is a classic mix-up. Second, "one movement" means one queen moved once: from row 4 to row 2 is one movement, not two. You pick the queen up and put it down somewhere else — one move; you do not count the difference in rows.

Scope of 1NN: the rule changes exactly one variable to one new value. Everything else stays fixed. A state that differs from the current one in two components is not a 1NN neighbor — it belongs to 2NN. Keep this boundary crisp: "neighbor" means exactly one component changed.

5.4.2 Worked Example: The 12 Neighbors of (2, 4, 2, 2)

Worked example: enumerate the twelve neighbors of the state (2, 4, 2, 2).

With 1NN we pick exactly one variable and give it one new value (anything except its current value).

  • Change alone: it is 2, so it can become 1, 3, or 4 → (1, 4, 2, 2), (3, 4, 2, 2), (4, 4, 2, 2).
  • Change alone: it is 4, so it can become 1, 2, or 3 → (2, 1, 2, 2), (2, 2, 2, 2), (2, 3, 2, 2).
  • Change alone: it is 2, so it can become 1, 3, or 4 → (2, 4, 1, 2), (2, 4, 3, 2), (2, 4, 4, 2).
  • Change alone: it is 2, so it can become 1, 3, or 4 → (2, 4, 2, 1), (2, 4, 2, 3), (2, 4, 2, 4).

That is 3 + 3 + 3 + 3 = 12 neighbors:

Four variables, each with three alternative values. Any of these twelve is exactly one step away from the original state — one component differs, the other three match. Each neighbor can itself be expanded into twelve more neighbors, and so on, until the fitness evaluation says we are done.

To see why each variable offers exactly three alternatives: has four possible values total (1, 2, 3, 4), and one of them is its current value. Moving requires a different value, so exactly three choices remain. That is the clean way to get the 12 without drawing boards.

5.4.3 2NN, 3NN, and the Cost of Bigger Moves

1NN is not the only option. With 2NN we may move two queens at once. Consider the pair (V1, V2) in the state (2, 4, 2, 2): V1 can be 1, 3, or 4, and V2 can be 1, 2, or 3. Every combination is allowed — (1, 1), (1, 2), (1, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3) — giving combinations for this one pair of columns. There are six ways to choose the pair of columns to change — (V1, V2), (V1, V3), (V1, V4), (V2, V3), (V2, V4), (V3, V4) — and each gives nine, so 2NN on this board yields fifty-four configurations:

Where the 9 comes from (reconciling the walkthrough). During the walkthrough the lecture briefly listed all sixteen pairings (1,1) through (4,4) before settling on 9. The full 4 × 4 = 16 grid is cut down by the rule that both chosen variables must actually move: the 4 pairings where V1 stays at 2 are out, the 4 where V2 stays at 4 are out, and the pairing (2, 4) was removed twice, so . The same rule gives the shorter count directly: three choices for V1 times three choices for V2 = 9. Then six column-pairs, each with nine combinations, gives the stated total 54.

In the same way there are 3NN, 4NN, and even NNN, where anything can move anywhere. If all four queens could move at once to any of their three other rows, you would be looking at combinations — that is why the lecture says "not 81" for 1NN. NNN generates every conceivable board — that is not effective computationally, so we do not use it. In this course, and in the exam, we always stick to 1NN: one queen at a time, one configuration per move.

Exam note: only 1NN is used in exams and assignments; you will never be asked for multiple moves at a time. The 12-neighbor count for 4-Queens and the 54-count for 2NN are worth knowing cold — they are the classic numbers.

5.4.4 Student Questions and Answers

Q: Can the queen in column three move to a different column?

A: No. The variables are fixed: V1 is column one, V2 is column two, V3 is column three, V4 is column four. What changes are the values inside them, which say which row the queen sits in. Every variable can only take the values 1, 2, 3, or 4.

Q: How many steps away is (2, 4, 4, 2) from (2, 4, 2, 2)?

A: One step. Compare the two vectors: three components match, only the third component differs (2 became 4). Do not count the subtraction — moving a queen from row 2 to row 4 is one movement, not two. One step away means exactly one variable changed.

Q: Please explain the 54 configurations again.

A: Keep two columns fixed and play with the other two. In (2, 4, 2, 2), keep V3 = 2 and V4 = 2 constant, and let V1 and V2 vary: V1 can be 1, 3, or 4, V2 can be 1, 2, or 3. That is 3 × 3 = 9 combinations. There are six ways to choose the pair of columns to change, so the total is 54 different configurations. The closing note: with one queen at a time you get exactly 12; with two queens at a time you get 54 — more combinations, more computation.

Q: Is generating all these neighbors computationally heavy?

A: Not for 1NN, because only one value changes. Programmatically we are not drawing boards at all; we hold one vector and change one entry, producing 12 configurations and computing a fitness for each one. 2NN gives 54 configurations, 3NN many more, and NNN explodes. That is why practical problems often stick to small NN values, going to 2NN or 3NN only when 1NN is not good enough.

Q: Is 1NN the same as the k-nearest neighbor algorithm we use in machine learning?

A: No. Students often confuse this. 1NN stands for one neighboring region expansion: you move one queen at a time and you get one new configuration per move. The k-nearest neighbor (k-NN) algorithm from machine learning is a completely different thing — do not confuse the two NNs.

5.5 Hill Climbing

Hook: you have a board, a fitness value, and 12 neighbors. The simplest possible improvement rule — "always step to the best neighbor, stop when none is better" — is a complete algorithm. It is called hill climbing, and it will teach us what "good enough" means.

5.5.1 The Algorithm

Hill climbing is the simplest local search algorithm. The steps:

  1. Select a random state. In local search that state is a solution by definition — valid, but not necessarily good. (A goodie went to whoever answered this correctly in class.)
  2. Evaluate the fitness score of the state.
  3. Evaluate the fitness scores of all successors of this state. With 1NN on a 4-Queens board that means 12 configurations. Some authors call them successors, others call them neighbors; both words appear in this course.
  4. If any successor has a better fitness value than the current state, move to the best one and repeat from step 3.
  5. If no successor is better, stop and return the current state as the answer.

What the algorithm is, in one line: hill climbing is a greedy local search — it grabs the best immediate neighbor and never looks ahead. Inputs: a state representation, a fitness function, and a move rule (1NN). Output: the local maximum it found. Rationale of each step: the random start gives a complete (feasible) configuration; the fitness evaluation gives a baseline; the full successor sweep prevents stopping too early; the "move to the best" rule is the greedy step; the stopping rule is what makes the algorithm come to an end.

Note what the algorithm never does: it never looks beyond the immediate neighbors. It cannot see the global optimum two moves away unless one of the current neighbors leads there. That is why the result is a local maximum (or local minimum) rather than necessarily the global one.

5.5.2 Worked Example: Stuck at a Local Maximum

Worked example: hill climbing on a random board gets stuck at a local maximum with fitness 4.

Start from the random state (1, 4, 2, 2) — interestingly, this is one of the 12 neighbors of the state (2, 4, 2, 2) from the previous section. Take the fitness as the number of non-conflicting pairs.

The six pairs, with Q1 at (1, 1), Q2 at (2, 4), Q3 at (3, 2), Q4 at (4, 2):

  • Q1–Q2: non-conflicting. Q1–Q3: non-conflicting. Q1–Q4: non-conflicting. Q2–Q3: non-conflicting.
  • Q2–Q4: conflicting — same diagonal.
  • Q3–Q4: conflicting — same row.

Non-conflicting pairs: 4. The global optimum would be 6 (all six pairs non-conflicting); we are at 4.

Generate all 12 successors with 1NN and evaluate each one. One of the twelve was worked out pair by pair — the one with fitness 2, which is the board (2, 4, 2, 2) reached by moving Q1 from row 1 to row 2. Its pairs: Q1–Q2 non-conflicting, Q1–Q3 conflicting (same row), Q1–Q4 conflicting (same row), Q2–Q3 non-conflicting, Q2–Q4 conflicting (same diagonal), Q3–Q4 conflicting (same row). Only two non-conflicting pairs remain, so its fitness is 2 — the same board whose conflicting count was 4 in section 5.3, since .

Across all 12 successors, none beats 4 — every neighbor is at 4 or worse. The vanilla hill climbing rule says: stop, and return the state (1, 4, 2, 2) with fitness 4 as the answer. The verdict: four of the six pairs are non-conflicting, two betrayed us. The answer is a solution, but not the optimal solution. Hill climbing gives up at that point and reports what it found. That is why we say hill climbing does not guarantee the global optimum: in this run it returned a local maximum (4) instead of the global maximum (6). Sense-check: with 1NN, every neighbor is one queen away; if the goal state is two moves away from every neighbor, the algorithm can never reach it from this start — the stop is correct for this rule.

5.5.3 Termination and Guarantees

Picture the state space as a hilly landscape. The fitness value is the height. A global maximum is the highest peak of all; a local maximum is a peak whose neighbors are all lower. Hill climbing walks uphill one step at a time and stops at the top of whatever hill it started on. If you are lucky and your hill is the global one, you reach the global maximum; otherwise you stop at a local maximum. The same picture works for minimization: the global minimum is the lowest point, and a local minimum is a valley with no lower neighbor. Which target you chase depends on whether you maximize or minimize your fitness.

For the visual: draw a 1D landscape with the state space on the x-axis and the fitness (height) on the y-axis. The curve rolls up and down like a mountain range. Mark the highest peak (global maximum), a lower peak surrounded by lower neighbors (local maximum), and a flat stretch on the way down (a plateau). A hiker who always walks uphill will end at whichever peak their starting point's slope feeds into — the map of possible stopping points is exactly the local maxima. One-sentence takeaway: in hill climbing you do not choose the peak, the starting point does.

Three standard termination conditions appeared:

  1. Stop when no successor has a better fitness value — return the best found.
  2. Stop when the global maximum is attained — you found the best possible answer.
  3. With random restart, stop after a predefined number K of restarts.

Guarantee: hill climbing does not guarantee the global optimum; it returns the local maximum it finds. It also cannot escape a plateau — a flat area where no neighbor is better — because no uphill exit exists from a flat local maximum. And it can wander along a ridge, a sequence of local maxima, where greedy moves bounce between peaks without climbing the ridge itself. These failures are properties of the landscape, not bugs in the algorithm.

Complexity-wise, local search is far cheaper than systematic uninformed search: it never builds the full tree. If you have done an algorithms course: O(n²) is perfectly fine — bubble sort is O(n²) — while 2^n is the bad kind. Local search stays on the cheap side.

Recap + bridge: hill climbing is a greedy walk over neighbors that stops at a local optimum — fast, memory-light, but with no global guarantee. That weakness is exactly what the next two algorithms attack: random restart changes the starting point, and stochastic hill climbing changes the selection rule.

5.5.4 Student Questions and Answers

Q: For the global answer, should the count be six and not four?

A: Yes. Six is the global optimum: all six pairs of queens must be non-conflicting, which means nobody attacks anybody. Our board (1, 4, 2, 2) has only four non-conflicting pairs — two queens conflict — so it is not the global solution.

Q: How can a conflicting position also be a solution?

A: We are in local search. Anything you hand over is a solution — that goes back to the very first slides of the topic. The question is whether it is the best solution. Here we evaluate and see that it is not optimal; two pairs conflict. But it is still a feasible solution. Think of it as grading: a student's answer that is correct in spirit gets partial marks — four of six pairs are correct — even though it is not the perfect answer.

Q: Do we need to check all the successor configurations?

A: Yes, all twelve. Do not skip any. The honest admission from the example: mistakes were made by leaving dots instead of all twelve boards — do not copy that; draw all twelve, compute every fitness value, and verify.

Q: Should the non-conflicting pairs be six and the conflicting pairs be zero?

A: Both statements describe the same goal, but it depends on which fitness definition you chose. If your fitness counts conflicting pairs, the best value is zero and you are minimizing. If it counts non-conflicting pairs, the best value is six and you are maximizing. Pick one definition and stay with it for the whole problem — switching definitions mid-way is where confusion starts.

Exam note: expect a numerical hill climbing question where you generate all successors and compute every fitness value. The marking will reward the full 12-board sweep: every neighbor listed, every fitness computed, and the stopping decision justified.

5.6 Hill Climbing with Random Restart

Hook: hill climbing stopped at a local maximum with fitness 4. Does "stop" have to mean "give up"? No — throw the board away, pick a brand new random one, and climb again. That simple retry loop is the whole algorithm.

5.6.1 The Problem: Some Starts Can Never Reach the Goal

With 1NN, one move changes one queen. From some starting boards, no sequence of single moves can ever reach the goal within the first neighborhood — for example, if all four queens start in one row, the 12 neighbors still have several queens in one row, and the goal board is not among them. The goal might be reachable only with multiple queen moves at once. So even a perfect hill-climbing run can be doomed by the starting state. When hill climbing gets stuck on a local maximum and no neighbor helps, we do not have to give up: we restart from a fresh random state.

5.6.2 Worked Example: A Lucky First Move to the Global Optimum

Worked example: random restart from a fresh state finds the global optimum with one move.

After a dead end, randomly restart: pick a brand new random board and run hill climbing again from there.

New random state: (3, 4, 4, 2). Board: Q1 in column 1 row 3, Q2 in column 2 row 4, Q3 in column 3 row 4, Q4 in column 4 row 2. Check the six pairs:

  • Q1–Q2: rows 3 and 4, columns 1 and 2 → row gap 1, column gap 1 → same diagonal → conflicting.
  • Q1–Q3: rows 3 and 4, columns 1 and 3 → gaps 1 and 2 → safe.
  • Q1–Q4: rows 3 and 2, columns 1 and 4 → gaps 1 and 3 → safe.
  • Q2–Q3: both row 4 → same row → conflicting.
  • Q2–Q4: rows 4 and 2, columns 2 and 4 → row gap 2, column gap 2 → same diagonal → conflicting.
  • Q3–Q4: rows 4 and 2, columns 3 and 4 → gaps 2 and 1 → safe.

So three pairs conflict and three are non-conflicting — fitness 3 (non-conflicting definition).

Apply 1NN and generate the 12 children. One of them is the state (3, 1, 4, 2): move the queen in column 2 from row 4 to the first row. Now Q2 sits at (2, 1). Checking all six pairs:

  • Q1–Q2: (1, 3) vs (2, 1) → gaps 1 and 2 → safe.
  • Q1–Q3: (1, 3) vs (3, 4) → gaps 2 and 1 → safe.
  • Q1–Q4: (1, 3) vs (4, 2) → gaps 3 and 1 → safe.
  • Q2–Q3: (2, 1) vs (3, 4) → gaps 1 and 3 → safe.
  • Q2–Q4: (2, 1) vs (4, 2) → gaps 2 and 1 → safe.
  • Q3–Q4: (3, 4) vs (4, 2) → gaps 1 and 2 → safe.

All six non-conflicting — fitness 6, and the run finds the global optimum. The algorithm stops and reports it. The point of the example: this start was promising because most queens were already close to the goal, and a single 1NN move finished the job. Sense-check: fitness 6 is the maximum possible (all six pairs safe), so no further move can improve it — the stopping rule "global maximum attained" fires.

5.6.3 When to Stop Restarting

How long can we keep restarting? The standard answer is a predefined number K. Run hill climbing; if no optimum is found, restart from another random state; repeat up to K times. If K = 5, we try five starts; if a run succeeds before that, we stop; if all five fail, we stop and report the best we saw. If K = 1, we are back to plain hill climbing — one start, one run, done. In real practice, people sometimes switch strategy on later restarts — for example, try 2NN instead of 1NN on the second restart, since the first strategy failed. That is allowed and common.

One question that always comes up: how do we know the optimum is 6? Because for a given problem, subject matter experts know the optimal value — for 4-Queens the answer is known. If nobody knows the optimal value for a problem, then the problem is NP-hard, and NP-hard problems are research problems that nobody has solved; this course avoids them.

Scope: random restart only makes sense when two things hold: the optimal value is known (so we can recognize success), and restarts are cheap compared to a single climb. When the optimal value is unknown, we cannot even detect the goal — that is the NP-hard territory the course stays out of. Also note that random restart does not remove the possibility of failure; it only gives the algorithm more independent chances, and each chance is still a gamble on the landscape.

Recap + bridge: random restart fixes bad starting points by buying more starts; it never fixes the greedy selection rule itself. The next variant attacks the other weakness — hill climbing's single-minded "take the best" move — with probability. That is stochastic hill climbing.

5.6.4 Student Questions and Answers

Q: Will the global answer always be inside one of the successor states?

A: Not necessarily. With 1NN you move one queen, so from some starting boards the goal is never among the 12 successors — it needs multiple moves. If your start is close to the goal, one move may finish it; if not, you restart and hope for a better start. That is exactly why random restart exists.

Q: How long can we keep restarting, and how do we know the optimum value?

A: Set a number K of restarts in advance; when K runs are exhausted without success, stop. As for knowing the optimum: subject matter experts know the optimal value for a given problem. When the optimal value is unknown, the problem is NP-hard — a research problem nobody has solved — and we do not deal with those here.

Q: After a restart, can we switch to moving two queens at a time?

A: Yes. In real life people do exactly that: 1NN ditched me, I have two restarts left, let me try 2NN on the next restart.

Exam note: random restart runs with a predefined K; when K = 1 it reduces to normal hill climbing. In a question, you will be told K — for example, "restart at most 5 times" — and you simply execute that many runs, stopping early if a run hits the optimum.

5.7 Stochastic Hill Climbing

Hook: vanilla hill climbing always takes the best neighbor; random restart throws the board away when stuck. What if, instead, you let the neighbors compete by lottery — better boards get bigger tickets? That is stochastic hill climbing.

5.7.1 From Greedy to Probabilistic Selection

Vanilla hill climbing always moves to the best successor. Random restart sometimes picks a state that is even poorer than the current one. Stochastic hill climbing sits between the two: it still generates all successors, but it chooses the next state by probability, favoring the promising ones without committing blindly to a single best. The motivation: the fitness graph may look very stochastic — jagged, with many similar peaks — so picking by probability over a window is safer than a single max-or-min decision. There is a lot of theory behind this in the course textbook; the mechanics here are what matter for the exercises.

5.7.2 Worked Example: Probabilities from Fitness Frequencies

Worked example: build the probability table from the fitness frequencies.

From the random state (1, 4, 2, 2), generate the 12 successors and compute the fitness of each (non-conflicting pairs). The distinct fitness values that appear among the 12 are 1, 2, 3, and 4. Count how many boards have each value: fitness 1 appears in 2 boards, fitness 2 in 5 boards, fitness 3 in 4 boards, fitness 4 in 1 board. Check the count: 2 + 5 + 4 + 1 = 12 boards.

The probability of picking a successor with a given fitness is the frequency divided by the total, 12:

So:

Reconciled decimals: computing 2/12, 5/12, 4/12, 1/12 gives about 0.17, 0.42, 0.33, and 0.08, and the probabilities sum to 1 (0.17 + 0.42 + 0.33 + 0.08 = 1.00). Sense-check: every probability lies in [0, 1], the row with the highest frequency (fitness 2, five boards) indeed gets the highest probability, and the totals agree with the 12 neighbors.

Scope: this probability scheme needs a fixed total — here, 12 neighbors — and a fitness definition held constant for the whole run. If you switched to conflicting-pairs counting mid-example, the frequencies would change and the table would no longer sum to 1 with the same meaning. The theory behind weighting by frequency (why "appears in more boards" means "more promising") is covered in the course textbook; the exam asks for the mechanics shown here.

5.7.3 Choosing the Next State

Look at the row with the highest probability — here fitness 2 with 0.42. If several fitness values share the top probability, pick any one of them; it does not matter. Select one of the boards with that fitness as the next state, then repeat: 1NN expansion, fitness evaluation, probability table, selection. Keep going until the global optimum is reached or no successor improves the current state.

Quick summary of the three variants: plain hill climbing generates neighbors and takes the best; random restart abandons everything and starts from a fresh random state; stochastic hill climbing computes probabilities and picks one of the current neighbors accordingly.

Recap + bridge: the three hill climbing variants form a spectrum — greedy (take the best), lottery (weighted by fitness), and retry (new start). All three still explore one board's neighborhood at a time. Beam search, next, keeps the same three ideas but runs several boards in parallel.

5.7.4 Student Questions and Answers

Q: Why not simply take the successor with the highest fitness?

A: You could, and sometimes that is exactly what the algorithm does in effect. But stochastic hill climbing chooses probabilistically because the landscape can be very stochastic — many similar peaks. A probability window over the first iteration is safer than committing to a single max. The theory is in the course textbook.

Q: What do we do when two probabilities are equal?

A: Pick either one of them. It makes no difference — if several fitness values have the same probability, any of those boards can be the next state.

Q: In random restart, do we pick one of the twelve configurations?

A: No — that is the difference, and students often mix these two up. Random restart abandons the current board and starts the whole algorithm over from a brand new random state. Stochastic hill climbing stays with the current board: it computes probabilities for the twelve neighbors and keeps picking a promising one from the current twelve, based on probability, and continues from there.

Q: Why do you compute the probability from the frequency of fitness values?

A: Because a fitness value that appears in many of the boards is more promising — more configurations carry it, so it is a better bet. That is the intuition; the formal theory is in the course textbook.

Exam note: the stochastic hill climbing computation is fixed: divide the frequency of a fitness value by the total number of neighbors (12), then select the next state by the highest probability. Show the table — fitness values, frequencies, probabilities — and the chosen row.

5.9 Population-Based Methods: Genetic Algorithms and Ant Colony Optimization

Hook: beam search ran K searches side by side but never let them talk. The next family of algorithms, population-based methods, throws that restriction away — the states share data, combine, and mutate. Genetic algorithms model human evolution; ant colony optimization models how ants find food.

Genetic algorithms reuse most of the machinery we just built. Representing individuals is the same vector notation we used for boards. The initial population is exactly like the random states of local search. Applying a fitness function gives each individual a fitness value — the same conflicting-pairs idea. So the representation, the fitness evaluation, and the idea of improving states all carry over unchanged.

5.9.2 What Makes Genetic Algorithms Different: Collaboration

The steps unique to genetic algorithms are the ones that introduce collaboration: you generate parents, use the parents to produce the next generation of children, and mutate some of them — the individuals use each other's data. In beam search each thread kept its own neighbors and its own configurations; nothing was shared. Genetic algorithms merge, recombine, and mutate boards from a shared population, which is a genuinely different way to search. The algorithm is inspired by human evolution, and ant colony optimization (ACO) is inspired by how ants search for food — both are population-based methods created from life itself.

5.9.3 What Comes Next

The next session covers genetic algorithms and ant colony optimization in depth. Together with local search, hill climbing, and beam search, that completes this module: hill climbing and its variants, local beam search and its variants (single-instance methods), plus genetic algorithms and ant colony optimization (population-based methods). Particle swarm optimization and simulated annealing were mentioned for context only.

Exam note: the module scope is fixed — hill climbing and variants, local beam search and variants, genetic algorithms, and ant colony optimization only. Particle swarm optimization and simulated annealing are out of scope for this offering; do not spend revision time on their details.

Exam Guidance Summary

What is in scope

  • Single-instance methods: hill climbing and its three variants (plain, random restart, stochastic) and local beam search (plain and stochastic).
  • Population-based methods: genetic algorithms and ant colony optimization — covered next session.
  • Explicitly out of scope for this offering: particle swarm optimization and simulated annealing.
  • 1NN everywhere: every neighbor generation in this course uses one queen at a time; multiple moves per step will not be asked. The 12-neighbor count for 4-Queens and the 54-count for 2NN are worth knowing.
  • Beam width K will be given in exam and assignment questions.

Question patterns to expect

  • A numerical hill-climbing or beam-search question: draw the state, compute the fitness (conflicting or non-conflicting pairs), generate all 12 successors, compute every fitness value, and show the stopping decision. The standing advice: check all twelve, do not skip any.
  • A stochastic hill climbing question: build the frequency table, divide by 12, and pick by the highest probability.
  • Terminology traps: "heuristic value" is used interchangeably with "fitness value" in the exercises; "successors" and "neighbors" mean the same thing; 1NN is not the ML k-nearest neighbor algorithm.
  • Random restart: know the K-stops rule and the fact that K = 1 collapses to plain hill climbing.

How to practice

  • Replay the session at 0.75× speed, pause whenever a question is asked, attempt it, then compare. Work through every exercise in the course materials, including the beam search exercise where K is given. The standing advice: do not trust the given diagrams — draw all twelve boards yourself and verify every fitness value.
  • Drill the counts: why 12 for 1NN, 54 for 2NN, and where 81 would come from — the reasoning is as examinable as the numbers.

Marks and logistics

  • The first assignment is live and worth 12 marks: a group assignment (a team of four) with a contribution declaration for each member, everything specified in the single problem-statement PDF. No solo submissions. All doubts about it go through the dedicated thread.
  • The problem statement PDF also covers group formation and the contribution format — read it before asking questions. There is a fixed deadline; it will not be extended.

Key Industry Applications

Where local search is used

  • Feature selection, robotics, and hyperparameter tuning: problems where only the final configuration matters, not how you reached it. In feature selection, a team of features is a state and the fitness is a model's validation score; in hyperparameter tuning, a setting vector is a state and the fitness is the measured performance.
  • Robotics in particular: a robot operates on its immediate neighborhood — it senses the states around its current position and moves only there, which is local search in action.
  • The N-Queens problem itself: a puzzle that researchers spent years on; hill climbing produces a decent configuration quickly, which is why such heuristics are valuable. The same idea powers classic scheduling and routing heuristics in operations research.
  • The partial-marks view of fitness carries into industry: many real problems are solved with "good feasible" answers when "perfect" is out of reach, and a fitness value is exactly the number that says how close you are.

Distributed search and nature-inspired methods

  • Local beam search maps naturally onto Hadoop-style distributed computing and multi-threaded programming: K independent searches on K machines, with a stop signal when one finds the goal. Wall-clock time can drop below a single hill climb when the compute is available.
  • Genetic algorithms and ant colony optimization bring biology into optimization — evolution for GA, ant foraging behavior for ACO — and are used broadly in industry for hard combinatorial problems: scheduling, routing, network design, and automated design of machine learning pipelines. Because the individuals share data, these methods explore far more of the landscape per generation than any single-instance search.

ACI Lecture 5 notes · Local Search Algorithms and Introduction to Evolutionary Algorithms

Artificial Computational Intelligence· postgraduate· 2026-08-13

Sections Breakdown

1Where We Have Been: Foundations for Local Search

Recap of the course journey from history and rational agents to uninformed and informed search, ending with the bridge into local search.

2Local Search and the Mindset Change

The state itself is the solution; fitness values versus heuristics, and the categories of local search in course scope.

3The 4-Queens Problem: Representation and Fitness

Vector representation of a board and the fitness value as the number of conflicting (or non-conflicting) queen pairs.

4Neighbor States and the 1NN Expansion

What counts as a neighbor, the twelve neighbors of (2, 4, 2, 2), and the cost of 2NN, 3NN, and NNN moves.

5Hill Climbing

The greedy algorithm: random start, full successor sweep, move to the best, stop at a local maximum; termination and guarantees.

6Hill Climbing with Random Restart

Escaping bad starts by restarting from fresh random states up to K times, with a worked example that reaches the global optimum.

7Stochastic Hill Climbing

Choosing the next state probabilistically from a table of fitness frequencies, with the full worked probability computation.

8Local Beam Search

K independent hill climbing instances in parallel; stochastic beam search, and choosing the beam width K.

9Population-Based Methods: Genetic Algorithms and Ant Colony Optimization

What carries over from local search and what changes: collaboration between individuals in population-based methods.

10Exam Guidance Summary

Exam scope, question patterns, practice method, and assignment marks and logistics.

11Key Industry Applications

Where local search is used in industry, and distributed search plus nature-inspired methods.

Postgraduate students in Artificial Intelligence

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Where We Have Been: Foundations for Local Search

Must-know: The course so far treated the path to the goal as the solution; local search treats the state itself as the answer.

⚠️ Top pitfall: Forgetting that heuristics came from SMEs, pattern databases, or learned from data — a contrast that matters when fitness values arrive in section 5.2.

Self-check: Which problems were formulated as search problems earlier in the course?

Connects to: Local Search and the Mindset Change (5.2), The 4-Queens Problem (5.3).

Local Search and the Mindset Change

Must-know: In local search any valid state is a solution; the fitness value (heuristic value, used interchangeably) measures how good it is, and the global optimum is not guaranteed.

⚠️ Top pitfall: Confusing the heuristic, which is given in advance, with the fitness value, which the domain designer defines and we compute after picking a state.

Self-check: Name the two categories of local search and which algorithms are in course scope.

Connects to: Foundations for Local Search (5.1), The 4-Queens Problem (5.3).

The 4-Queens Problem: Representation and Fitness

Must-know: The fitness value is the number of conflicting pairs (best 0) or non-conflicting pairs (best 6); a board with conflicts is still a feasible solution, just not the goal.

⚠️ Top pitfall: Counting the same attacking pair twice (Q1-Q2 and Q2-Q1 are one pair) or forgetting the diagonal rule |row gap| = |column gap|.

Self-check: How many conflicting pairs does the board (2, 4, 2, 2) have?

Connects to: Local Search and the Mindset Change (5.2), Neighbor States and the 1NN Expansion (5.4).

Neighbor States and the 1NN Expansion

Must-know: 1NN means one queen moved once: 12 = 4 variables × 3 alternatives for 4-Queens; 2NN gives 54 = 6 column-pairs × 9 combinations; only 1NN is examinable.

⚠️ Top pitfall: Treating 1NN as the machine-learning k-nearest neighbor, or counting a 2-row move as two steps instead of one movement.

Self-check: How many neighbors does (2, 4, 2, 2) have under 1NN, and why is each variable limited to three alternatives?

Connects to: The 4-Queens Problem (5.3), Hill Climbing (5.5).

Hill Climbing

Must-know: Hill climbing is greedy local search: evaluate all 12 successors, move to the best, stop when none is better; it returns a local maximum and never guarantees the global optimum.

⚠️ Top pitfall: Skipping successors, or switching the fitness definition (conflicting vs non-conflicting) mid-problem; stick to one definition for the whole run.

Self-check: Why does (1, 4, 2, 2) with fitness 4 stop under vanilla hill climbing?

Connects to: Neighbor States and the 1NN Expansion (5.4), Hill Climbing with Random Restart (5.6), Stochastic Hill Climbing (5.7).

Hill Climbing with Random Restart

Must-know: Random restart repeats hill climbing from fresh random states up to K times; K = 1 reduces to plain hill climbing, and the optimal value is known via subject matter experts unless the problem is NP-hard.

⚠️ Top pitfall: Confusing restart (abandon the board, new random start) with picking a neighbor; also assuming more restarts guarantee the global optimum — they only raise the chance.

Self-check: Why can a start like all-queens-in-one-row never reach the goal under 1NN?

Connects to: Hill Climbing (5.5), Stochastic Hill Climbing (5.7).

Stochastic Hill Climbing

Must-know: P(f) = frequency of fitness f among the 12 neighbors divided by 12; pick the row with the highest probability, any row if tied.

⚠️ Top pitfall: Mixing up random restart (brand new random state) with stochastic hill climbing (pick a promising neighbor from the current twelve by probability).

Self-check: With frequencies 2, 5, 4, 1 over twelve neighbors, which fitness value is the next state drawn from?

Connects to: Hill Climbing (5.5), Hill Climbing with Random Restart (5.6), Local Beam Search (5.8).

Local Beam Search

Must-know: Beam search = K parallel independent hill climbs; K = 1 collapses to hill climbing; plain beam selects next K states randomly, only stochastic beam search uses probability.

⚠️ Top pitfall: Believing the K threads collaborate (they do not — that is genetic algorithms), or applying probability to plain beam search.

Self-check: What happens when K = 1, and who announces a global optimum?

Connects to: Hill Climbing (5.5), Stochastic Hill Climbing (5.7), Population-Based Methods (5.9).

Population-Based Methods: Genetic Algorithms and Ant Colony Optimization

Must-know: Module scope: hill climbing and variants, local beam search and variants, genetic algorithms, ant colony optimization; particle swarm and simulated annealing are context only.

⚠️ Top pitfall: Assuming beam search threads collaborate — they do not; collaboration is the new ingredient genetic algorithms add.

Self-check: What carries over unchanged from local search to genetic algorithms?

Connects to: Local Beam Search (5.8).

Exam Guidance Summary

Must-know: In scope: hill climbing and variants, local beam search and variants, genetic algorithms, ant colony optimization; 1NN everywhere; K always given.

⚠️ Top pitfall: Skipping successors in numerical questions and confusing heuristic/fitness and successor/neighbor terminology.

Self-check: Which algorithms are explicitly out of scope for this offering?

Connects to: Local Search and the Mindset Change (5.2), Neighbor States and the 1NN Expansion (5.4), Hill Climbing (5.5), Stochastic Hill Climbing (5.7).

Key Industry Applications

Must-know: Local search shines when only the final configuration matters; beam search parallelizes onto distributed compute; GA and ACO apply evolution and ant foraging to combinatorial optimization.

⚠️ Top pitfall: None specific to this appendix section.

Self-check: Why does a robot's movement naturally match local search?

Connects to: Local Search and the Mindset Change (5.2), Local Beam Search (5.8), Population-Based Methods (5.9).

Previous LectureLecture 04 · Heuristics: Evaluation, Design, and Relaxation
Next LectureLecture 06 · Genetic Algorithms, Ant Colony Optimization, and Neural Architecture Search

Was this lecture useful?

Loading comments…
🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot
Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

🔑 Enter API key above to fetch live models from provider, or enter model name manually.
OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.