Local Search Flashcards
(16 cards)
What is the main goal of local search algorithms?
To find an optimal or good solution by improving a single candidate state based on an objective function, without keeping the entire path or tree in memory.
What are three common local search approaches?
Hill Climbing, Simulated Annealing, Genetic Algorithms
What is Hill Climbing?
A greedy algorithm that moves to the neighbor state with the highest value (best score), attempting to find the peak (maximum value).
What is a key limitation of Hill Climbing?
It can get stuck in local maxima, plateaus, or ridges and miss the global optimum.
What is Random-Restart Hill Climbing?
A method that runs hill climbing multiple times from different random starting points and keeps the best result.
What is Simulated Annealing?
A search algorithm that sometimes accepts worse solutions to escape local optima, based on a gradually decreasing “temperature.”
What does the “temperature” in Simulated Annealing control?
The probability of accepting worse moves; it decreases over time to reduce randomness.
Why can Simulated Annealing find the global optimum?
Because it allows downhill moves early on, with decreasing probability, enabling escape from local optima.
What is a Genetic Algorithm (GA)?
A population-based search inspired by biological evolution, using selection, crossover, and mutation to evolve better solutions.
How does GA select which individuals reproduce?
Based on fitness — higher fitness solutions are more likely to be selected (e.g., via roulette wheel selection).
What is crossover in GA?
Combining parts of two parent solutions to produce offspring solutions.
What is mutation in GA?
Randomly changing bits in offspring to maintain genetic diversity and explore new solutions.
What is a fitness function in GA?
A function that evaluates how good a candidate solution is, guiding the selection process.
What problem types are suitable for local search?
Optimization problems where path is irrelevant, like n-queens, traveling salesman, function minimization, etc.
What does it mean for GA to search a “fitness landscape”?
It explores a multidimensional space where each point has a fitness value — the goal is to climb toward global maxima.
What are common encoding methods in GA?
Binary strings (bitstrings), integers, or other representations depending on the problem.
