Local Search and Optimization Algorithms

Key Algorithms:
- Hill-climbing
- Simulated Annealing
- Local Beam Search
- Genetic Algorithms

Definition: Local search algorithms focus on finding an optimal solution without considering the path taken. They specifically work well when the goal state is the solution itself.
**Examples:
- 8-Queens Problem
- Job-shop Scheduling Problem**
Methodology:
- Start with a current state and iteratively try to improve it.
- Steps:
- Select a solution from the search space.
- Apply transformations to generate new solutions.
- If the new solution is better, replace the current one; otherwise, discard it.
- Repeat until no further improvements can be made.

Operate using a single current state, not multiple paths like A*.
Move only to neighboring states.
Provide a complete but imperfect solution at each step.
Advantages:
- Constant space usage
- Applicable for both online and offline problems
- Can find reasonable solutions in large search spaces where exhaustive methods fail.

Considerations: Start with a solution and modify iteratively until an acceptable solution is found.
Illustrated through State Space Landscape:
- Global Maximum
- Local Maximum
- Flat Local Maximum

Definition: A variant of the local search that seeks a local maximum based on a heuristic evaluation function.
Algorithm Steps:
- Initialize with a random state.
- Iteratively search the highest-valued successors.
- Return if no better neighbors.

Local Optima: The algorithm can get stuck at local maxima instead of finding the global maximum.
Plateaux and Ridges: Difficult landscapes can cause inefficiencies.

Sideways Moves: Moving laterally to a state with the same value helps avoid getting stuck.
Limit Sideways Moves: Implement limits on consecutive sideways moves to prevent loops, improving success in some cases.

First-Choice Hill Climbing: Randomly generates successors until one better than the current state is found.
Stochastic Hill Climbing: Randomly selects among uphill moves, slower but occasionally more effective.
Random-Restart Hill Climbing: Conduct multiple searches from randomly generated initial states to increase chances of reaching a goal state.

Concept: Combines hill-climbing with random moves to explore and exploit the search space effectively.
Analogy: Based on metal annealing, ensuring a low-energy state through controlled temperature changes.
Mechanism: At each iteration, choose a random move; accept it if it improves the solution or accept it with a probability if it doesn't, influenced by a temperature parameter that decreases over time.

Show probability calculation for accepting worse moves based on temperature decreases.

Idea: Maintain multiple states (k states) and generate successors, halting if a solution is found or continuing with random selections to ensure diversity.

Concept: Operate through combining states (reproduction) and modifying them (mutation).
Process:
- Start with an initial population, evaluate fitness, select parents, perform crossover and mutation, and iterate until convergence is reached.

Crossover Illustration: Show how combination of parental strings generates offspring through one or two crossover points.

Algorithms employed (Hill-climbing, Simulated Annealing, Local Beam Searches, Genetic Algorithms) cater to specific optimization needs, each manipulating the search and evaluation of solution spaces in innovative ways to overcome challenges such as local minima and inefficiencies in broader landscapes.