Chapter 4: Search in Complex Environments (Local search and Genetic Algorithms)
Local Search and Optimization Problems: -
Local search algorithms use little memory and can find good solutions in large or infinite
spaces.
- Local search is a search strategy used in Artificial Intelligence (AI) and optimization
where the algorithm starts with a candidate solution and then iteratively moves to a
neighboring solution to find a better one — based on a predefined objective or
evaluation function.
Key Points:
- It doesn’t explore the entire search space.
- It doesn't keep track of paths, only the current state.
- It’s useful when the solution path is not important, only the final solution matters.
Examples: 8-Queens, circuit layout, scheduling.
Searching Algorithms: -
Hill Climbing Algorithm: -
Hill Climbing works by iteratively improving a candidate solution until no further improvements
can be found.
1. Initialization: Start from an initial point (solution).
2. Neighbor Evaluation: Evaluate neighboring solutions to find a better one.
3. Move: Move to the neighboring solution if it’s better.
4. Repeat: Continue until no better neighbor exists.
Steps:
1. Evaluate the initial state, if it is goal state then return success and Stop.
2. Loop Until a solution is found or there is no new operator left to apply.
a. Step 3: Select and apply an operator to the current state.
b. Step 4: Check new state:
i. If it is goal state, then return success and quit.
ii. Else if it is better than the current state then assign new state as a
current state.
iii. Else if not better than the current state, then return to step 2.
3. Step 5: Exit.
Hill Climbing Example: -
Let's define such function h:
- h(x) = +1 for all the blocks in the support structure if the block is correctly
positioned otherwise -1 for all the blocks in the support structure.
- Here, we will call any block correctly positioned if it has the same support structure as
the goal state.
As per the hill climbing procedure discussed earlier let's look at all the iterations and their
heuristics to reach the target state.
Note: Bottom box is always 0
Problems in Hill Climbing:
Local Minima: A state that is better than neighboring states but worse than the global best
assuming we are minimizing — the algorithm gets stuck there.
Local Maxima: A state that is better than neighboring states but worse than the global best
assuming we are maximizing — the algorithm gets stuck there.
Plateau: A flat area where neighboring states have the same value — no direction appears
better, leading to random wandering.
Ridges: Narrow paths that require moving in a direction not aligned with any single action —
hard to find using local steps (the last step in ridge is the local Minima).
- Hill climbing doesn’t give opportunities to weak states at the beginning
- Global Minima/Maxima means the Goal
Types of Hill Climbing Algorithms:
1. Simple Hill Climbing
a. Picks the first better neighbor it finds
b. Fast, but can miss better options
2. Steepest-Ascent Hill Climbing
a. Looks at all neighbors
b. Chooses the best one
c. Slower but usually smarter
3. Stochastic Hill Climbing
a. Chooses randomly among better neighbors
b. Adds variety to avoid getting stuck
Simulated Annealing: -
Simulated annealing allows 'bad' moves to escape local maxima early on.
- Avoids local maxima by sometimes accepting worse moves.
- Probability decreases over time (like cooling metal).
Simulated Annealing Steps: -
1. If the current state is the goal, finish, or otherwise continue searching.
2. Generate the children of the current state and calculate their heuristics(values).
3. Select any of the children at random.
4. Generate any random number between 0-1.
5. Calculate the acceptance rate based on the following formula (assign a high value for T,
say 10):
a. acceptance_probability = exp(-(f(neighbor) - f(current)) / T)
6. if the acceptance rate is greater than the generated number at random, assign the
neighbor/generated node to be current state, otherwise, do not change the current state.
7. Reduce the value of T and go back to step 1.
Note:
- A value greater than 1 when the neighbor is better (which is not valid as a probability).
- A value between 0 and 1 when the neighbor is worse (which is correct).
Simulated Annealing Example: -
if f(neighbor) < f(current), it is better (we are minimizing))
- acceptance_probability = exp(-(f(neighbor) - f(current)) / T)
if f(neighbor) > f(current), it is better (we are maximizing)
- acceptance_probability = exp(-(f(current) - f(neighbor)) / T)
Example:
initial temperature: T = 10 and we are minimizing
If f(neighbor) = 5 and f(current) = 3:
- acceptance_probability = exp(-(5 - 3) / 10) ≈ 0.82
- This means there's an 82% chance of accepting the neighbor even though it has a higher
value.
Later in the algorithm, if T = 1:
- acceptance_probability = exp(-(5 - 3) / 1) ≈ 0.14
- The chance of accepting a worse solution is now much lower.