■

Artificial Intelligence

Chapters 3 & 4 — Complete

Study Guide

Local Search & Optimisation Algorithms

CSC525 · Federal University of Technology Minna

Topics: Hill Climbing · Simulated Annealing · Beam Search · Genetic Algorithms ·

4/8-Queens · MSE

Contents
Topic Page

Local Search Overview 2

Cost Function & Objective Function 2

Hill Climbing 3

Greedy Ascent / Greedy Descent 4

Steepest Ascent / Steepest Descent 4

4-Queens Problem 5

8-Queens Problem 5

Simulated Annealing 6

Local Beam Search 7

Genetic Algorithm 7
Mean Square Loss Function 8

Summary Cheat Sheet 9

1. Local Search & the State-Space Landscape
■ Simple Idea: Imagine a hilly map where every point is a possible solution. Local search
starts at some point and keeps moving to better nearby points — without remembering the
full path or every place it has been.

Key characteristics of local search:

• Uses very little memory (only remembers current state)
• Works on huge or infinite state spaces
• Not systematic — may miss solutions
• Perfect for problems where we only care about the final answer, not the path

Examples: Placing queens on a chessboard, scheduling jobs, designing circuits, crop planning,
portfolio management.

Figure 1: The state-space landscape. The algorithm tries to reach the global maximum (highest peak) or global
minimum (deepest valley), but can get trapped at local maxima/plateaus.
2. Cost Function, Objective Function,
Maximisation & Minimisation
These are the scoring systems that tell the algorithm if it is doing well.

Term Simple Meaning Goal Example

Score of how GOOD a Maximise (go Grade in an

Objective Function
state is. Higher = better. UP) exam

Score of how BAD a state Minimise (go

Cost Function Penalty marks
is. Lower = better. DOWN)

Find the state with the

Maximisation Climb uphill Hill climbing
HIGHEST value.

Find the state with the Descend Gradient

Minimisation
LOWEST cost. downhill descent

Figure 2: Left — Maximisation (hill climbing, go UP). Right — Minimisation (gradient descent, go DOWN). Both
strategies are just mirror images of each other.
3. Hill Climbing
■■ Analogy: You are blindfolded on a hilly field. At every step, you feel around with your
foot and step in whichever direction goes uphill. You stop when every direction around you
goes downhill — you assume you are at the top.

How it works (algorithm):

1. Start at any random state.
2. Look at all neighbouring states.
3. Move to the neighbour with the highest value (best score).
4. Repeat until no neighbour is better — that is your answer.

Hill climbing is also called Greedy Local Search because it always grabs the best immediate
neighbour without thinking about the future.

Problems Hill Climbing Faces:

Problem What Happens Fix

Gets stuck at a small peak that is NOT the

Local Maximum Random Restarts
real best answer.

Flat area — no direction is better, Allow sideways

Plateau
algorithm wanders. moves

Narrow mountain ridge — every sideways Stochastic hill

Ridge
step goes downhill. climbing

■ Book Statistic: Steepest-ascent hill climbing gets stuck 86% of the time on the 8-queens
problem. With random restarts, success rate rises to 94%!

Variants of Hill Climbing:

• Stochastic Hill Climbing: Picks randomly from uphill moves (not always the steepest).
Slower but sometimes better.
• First-Choice Hill Climbing: Generates random successors until a better one is found.
Good when there are thousands of neighbours.
• Random-Restart Hill Climbing: If stuck, start over from a new random position. "If at first
you don't succeed, try again."
4. Greedy Ascent, Greedy Descent, Steepest
Ascent & Steepest Descent

Figure 3: Greedy (left) picks the FIRST better neighbour. Steepest (right) checks ALL neighbours first, then picks the
BEST.

Algorithm Direction Strategy Speed

Goes UP Picks FIRST neighbour that

Greedy Ascent Fast
(maximise) is better

Goes DOWN Picks FIRST neighbour that

Greedy Descent Fast
(minimise) is cheaper

Goes UP Checks ALL neighbours, Slower, more

Steepest Ascent
(maximise) picks BEST careful

Goes DOWN Checks ALL neighbours, Slower, more

Steepest Descent
(minimise) picks LOWEST cost careful

■ Key Difference: GREEDY = pick the first good option (fast but risky). STEEPEST = look
at everything first, then pick the absolute best (safer but slower). Ascent = maximise.
Descent = minimise.
5. The 4-Queens Problem
■ Task: Place 4 queens on a 4×4 chessboard so that NO queen attacks another. Queens
attack horizontally, vertically, and diagonally.

Figure 4: Left — a bad state (h=2 attacks shown by red lines). Right — perfect solution (h=0).

How Local Search solves it:

1. Cost function h = number of attacking pairs of queens.
2. Goal: reduce h to 0 (zero attacks).
3. At each step: try moving one queen, pick the move that reduces h the most (steepest
descent).
4. Stop when h = 0 or no move reduces h.

The neighbour relation NA used in your exam question is: swap the row positions of two
queens and count attacks in the new state.
6. The 8-Queens Problem
■■■■■■■■ Same idea as 4-Queens but on an 8×8 board with 8 queens. This is a
classic benchmark for local search algorithms.

Figure 5: Left — attacking state (red queens attack each other, lines show attacks). Right — valid solution (all queens
safe in green).

Key Facts from the Book:

Fact Value

8 queens × 7 positions = 56 successors per

Number of states
state

Cost function h Number of attacking queen pairs (goal: h=0)

Hill climbing success rate Only 14% (gets stuck 86% of the time!)

With random restarts 94% success rate

Random-restart hill climbing solves in

Even for 3 million queens
seconds
7. Simulated Annealing
■■ Analogy: Imagine shaking a bumpy table with a ping-pong ball. At the start, you shake
hard — the ball bounces around, possibly into a deeper dip. Gradually, you shake less and
less until the ball settles in the deepest hole.

Why is it needed?
Hill climbing NEVER goes downhill, so it gets permanently stuck at local maxima. Simulated
Annealing fixes this by sometimes accepting a worse move — especially early on when the
"temperature" is high.

How it works:
1. Start with a high Temperature T (lots of randomness allowed).
2. At each step, pick a RANDOM neighbour (not necessarily the best).
3. If the neighbour is BETTER → always accept it.
4. If the neighbour is WORSE → accept it anyway with probability e∆E/T.
5. Gradually reduce T (cool down). Bad moves become less likely.
6. When T → 0, the algorithm behaves like regular hill climbing.

Figure 6: Left — Temperature drops over time (cooling schedule). Right — At high T (red), bad moves are often
accepted. At low T (blue), almost never.

Feature Hill Climbing Simulated Annealing

Accepts bad moves? Never Yes, early on (when T is high)

Gets stuck in local

Yes, always Can escape them
optima?
Complete? No Yes (with slow enough cooling)

VLSI layout, scheduling, complex

Where used? Simple problems
optimisation
8. Local Beam Search
■ Analogy: Instead of one explorer searching the map, you send k=3 explorers. They all
search simultaneously and share information — if one finds a great area, the others
abandon their current spots and move towards it.

Figure 7: k=3 states are explored simultaneously. All successors are generated. Only the best k=3 are kept for the
next round, passing information between threads.

Key Points:
• Keeps k states in memory (not just 1 like hill climbing)
• Generates ALL successors of ALL k states each round
• Keeps the k BEST successors from the entire pool
• States that do well "attract" the others — information is shared
• Problem: states can cluster together (lack of diversity)

Stochastic Beam Search: Instead of always keeping the top k, it chooses successors randomly
with probability proportional to their score. This increases diversity and avoids clustering.

9. Genetic Algorithm
■ Analogy: Nature's evolution. The best individuals survive and reproduce. Offspring
inherit traits from both parents. Random mutations add new traits. Over generations, the
population gets better and better.
 Figure 8: The 5 stages of a Genetic Algorithm — Population → Fitness → Selection → Crossover → Mutation →
repeat.

The 5 Stages Explained:

Stage What happens 8-Queens example

Start with k random states

1. Population e.g. [24748552, 32752411, ...]
(individuals)

Score each individual (higher = Count non-attacking pairs

2. Fitness
better) (max=28)

Better individuals are more likely State with 24 pairs chosen more
3. Selection
chosen as parents than one with 11

Split two parent strings at a random [327|48552] + [247|52411] →

4. Crossover
point, swap halves [32752411]

Randomly flip a small part of the Move one queen to a random

5. Mutation
offspring square in its column

■ Key Insight: Genetic algorithms are like stochastic beam search + crossover. Crossover
is the secret weapon — it combines useful building blocks from two different parents to
create potentially better offspring.
10. Mean Square Loss Function & Linear
Regression
■ Simple Idea: We have data points (x, y). We want to find the best straight line y = W0 +
W1·x that fits the data. "Best" means the line that minimises the average squared distance
between real values and predicted values.

Symbol Meanings:
Symbol Meaning Simple words

n Number of data points How many (x, y) pairs you have

xi, yi i-th input and output One data point

W1 Slope / weight How steep the line is

W0 Intercept / bias Where the line crosses y-axis

Average of all squared errors — minimise

MSE Mean Squared Error
this!

Worked Example (from your exam):

Dataset: x = [1, 2, 3], y = [2, 3, 5]

Step 1 — Compute sums:

i xi yi xi·yi xi2

1 1 2 2 1

2 2 3 6 4

3 3 5 15 9

Σ 6 10 23 14

Step 2 — Calculate W1:

W1 = (n·Σxiyi − Σxi·Σyi) / (n·Σxi2 − (Σxi)2)

W1 = (3×23 − 6×10) / (3×14 − 36) = (69 − 60) / (42 − 36) = 9/6 = 1.5

Step 3 — Calculate W0:

W0 = (Σyi − W1·Σxi) / n = (10 − 1.5×6) / 3 = 1/3 = 0.333
Step 4 — Predict for x = 4:
y = 0.333 + 1.5 × 4 = 0.333 + 6 = 6.33

Figure 9: Left — regression line fitted to data (green dashed = errors, star = prediction at x=4). Right — loss surface
showing MSE for all W1/W0 combinations (star = optimal weights).
11. Master Cheat Sheet — All Algorithms at a
Glance
Accepts Bad
Algorithm Core Idea Memory Best For
Moves?

Hill Climbing
Move to best Simple, fast
(Greedy Never 1 state
neighbour search
Ascent)

Steepest Check ALL, pick More thorough

Never 1 state
Ascent BEST than greedy

Greedy Move to first Cost

Never 1 state
Descent cheaper state minimisation

Steepest Check ALL, pick Careful

Never 1 state
Descent CHEAPEST minimisation

Simulated Random + cooling Yes (early Escape local

1 state
Annealing schedule on) optima

Local Beam k explorers sharing Parallel

No k states
Search info exploration

Complex
Genetic Evolution: select, Yes (via Populatio
structured
Algorithm crossover, mutate mutation) n
problems

Maximisation vs Minimisation — Quick Reference

Category Algorithms Direction

Hill Climbing, Greedy Ascent, Steepest ↑ Go UP (highest

Maximisation
Ascent value)

Greedy Descent, Steepest Descent, ↓ Go DOWN (lowest

Minimisation
Gradient Descent cost)
■ EXAM TIP: Greedy = pick FIRST improvement (fast). Steepest = check ALL then pick
BEST (thorough). Ascent = maximise (go up). Descent = minimise (go down). Simulated
Annealing escapes local optima via randomness + cooling. Genetic Algorithm uses
crossover + mutation across a population.

Page intentionally left with summary for quick revision before your exam. Good luck! ■