Week2MainPoints (2)

1.

Summary

2.

Greedy Search
At every iteration, the algorithm examines the
solutions that are immediately available from
the current position. It evaluates their objective
function values and moves to the neighbour
with the best value.
The decision is greedy because the algorithm
selects what looks best right now, without
considering where that choice might lead later.
Key idea:
Greedy search answers the question:
○ Which available move gives me
the largest immediate
improvement?
○ It does not plan several steps ahead
and therefore does not guarantee that
the globally best solution will be found.

3.

Neighbourhood function
The neighbourhood function defines which solutions can
be reached from the current solution in one search step.
If the current solution is (x), a simple neighbourhood
could be defined as:
[N(x) = {x' : |x' - x| E r}]
where (r) determines the size of the neighbourhood.
A small neighbourhood considers only solutions
close to the current point. A large neighbourhood
considers solutions farther away.
Key idea:
The neighbourhood function defines what the
algorithm is allowed to consider as its next move.
Changing the neighbourhood therefore changes the
behaviour of the optimization algorithm, even if the
objective function remains exactly the same

4.

Small Neighbourhood
With a small neighbourhood, the algorithm makes gradual
movements through the search space.
This can provide precise local exploration, but it also
creates an important problem. Once the algorithm
reaches a point where all nearby solutions are worse, it
stops.
This point is a local optimum.
A better solution may exist elsewhere in the search
space, but the algorithm cannot reach it because doing
so would first require moving through worse solutions or
considering more distant candidates.
Key idea:
The algorithm only knows that there is no better solution
inside its current neighbourhood.
Remember the idea with exploration vs exploitation. How
to balance between those two. Later in the course,
algorithms will balance between those two

5.

Large Neighbourhood
A larger neighbourhood allows the algorithm to evaluate solutions
farther from its current position.
This increases the possibility of discovering a better region of the
search space and can sometimes help the search move away from a
poor local optimum.
However, there is a tradeoff.
A larger neighbourhood usually means:
more candidate solutions must be evaluated;
each iteration becomes computationally more expensive;
the search can make larger movements;
fine local exploration may become less precise.
A smaller neighbourhood provides more detailed local search, while a
larger neighbourhood provides broader exploration.
Key idea:
Small neighbourhood = stronger local exploitation
Large neighbourhood = broader exploration
The appropriate neighbourhood size therefore depends on the
structure of the optimization problem.

6.

Hill Climber
Hill climbing combines the previous ideas into a simple local
search algorithm.
At every iteration:
1.
2.
3.
4.
5.
6.
Start from the current solution (x).
Generate the neighbourhood (N(x)).
Evaluate the objective function for the neighbouring
solutions.
Select the best improving neighbour.
Move to that neighbour.
Repeat until no neighbour provides an improvement.
For maximization:
[
x_{t+1} =
MAX(x' in N(x_t)} f(x'))
]
provided that:
[
f(x_{t+1}) > f(x_t)
]

7.

Hill Climber
If no neighbouring solution is better, the algorithm
terminates.
Hill climbing is therefore a greedy local search
algorithm.
It is greedy because it always chooses an immediate
improvement, and it is local because it only considers
solutions defined by the neighbourhood function.
Key idea:
Hill Climbing = Current Solution +
Neighbourhood Function + Greedy
Selection + Repetition
Its main weakness is that it can stop at a local optimum
even when a better global optimum exists elsewhere in
the search space.