CS2004_Heuristic_Search_Flashcards
(10 cards)
What is Hill Climbing?
Hill Climbing is a local search algorithm that moves to a better neighbour if one exists, stopping at local optima.
✅ It only accepts moves that improve the fitness.
What is Random Mutation Hill Climbing (RMHC)?
RMHC is a variant of Hill Climbing that applies random small changes (mutations) and accepts them if they improve fitness.
What is Stochastic Hill Climbing?
In Stochastic Hill Climbing, better neighbours are chosen probabilistically rather than deterministically.
What is Random Restart Hill Climbing (RRHC)?
RRHC runs Hill Climbing multiple times from random starting points to reduce the chance of getting stuck in local optima.
What is Simulated Annealing (SA)?
SA is a metaheuristic that allows worse solutions to be accepted with a probability that decreases over time (temperature), helping to escape local optima.
What is the cooling schedule in Simulated Annealing?
A cooling schedule defines how the temperature is reduced over time, controlling the algorithm’s willingness to accept worse solutions.
What is the acceptance probability formula in SA?
P = exp(-ΔE / T), where ΔE is the change in fitness and T is the current temperature.
✅ Higher temperature → higher chance to accept worse solutions.
What is a key limitation of Hill Climbing?
It can get stuck in local optima and does not explore worse solutions, making it greedy.
What is the purpose of using randomness in heuristic search?
Randomness helps escape local optima and explore more of the search space.
What does the No Free Lunch theorem state?
No single algorithm performs best across all possible problems. Good performance on one problem implies worse on others.
