5 - local search algorithms

Question 1

Local search algorithms

Answer 1

focus on finding solutions within a limited part of the solution space, making incremental improvements to a current solution until reaching a satisfactory outcome

Question 2

Hill-climbing (greedy) search

Answer 2

keep a single “current” state and try to locally improve it

Let next= highest-valued successor of current
If value(next) < value(current) return current
Else let current= next

can get stuck in local optima (peak higher than neighbors but lower than global maximum)

Question 3

Simulated annealing search

Answer 3

inspired by the annealing process in metallurgy, where materials are heated and then gradually cooled to remove defects. It allows for occasional moves to worse solutions to escape local optima, with the probability of such moves decreasing over time

Can escape local optima due to probabilistic acceptance of worse solutions, but Requires careful tuning of parameters

Question 3

Genetic Algorithms

Answer 3

Generate a set of random solutions
Test each solution in the set (rank them)
Remove some bad solutions from set
Duplicate some good solutions make small changes to some of them
Until best solution is good enough