Local Search Flashcards
What is local search?
A search algorithm designed for large or infinite state spaces, focusing on finding solutions rather than paths.
What are the advantages of local search?
Faster for large state spaces, more memory-efficient.
What are the disadvantages of local search?
Incomplete, suboptimal, and can get stuck in local optima.
What is hill-climbing search?
A greedy algorithm that replaces the current state with the best neighboring state at each step.
What are the limitations of hill-climbing?
Can get stuck in local maxima, ridges, and plateaus.
What is random-restart hill climbing?
A method where hill climbing is run multiple times with different initial states to improve the chance of success.
What is simulated annealing?
A probabilistic algorithm inspired by annealing in metallurgy, allowing occasional moves to worse states to escape local optima.
How does simulated annealing decide whether to accept a worse state?
By using the probability If /delta E > 0 then the new state is accepted immediately whereas /delta E < 0 then new state is only accepted with probability that depends on T and /delta E
where /delta E is the change in value and T is the temperature.
How does temperature affect simulated annealing?
A high temperature allows more exploration; as temperature decreases, the algorithm becomes more selective.
What is a genetic algorithm?
A search method inspired by natural evolution that uses selection, mutation, and recombination to evolve solutions.
What is a genotype in genetic algorithms?
The encoded representation of a candidate solution.
What is a phenotype in genetic algorithms?
The observable characteristics derived from the genotype.
What is a fitness function?
A function that evaluates how well a candidate solution meets the problem’s objective.
What are common selection methods in genetic algorithms?
Proportionate selection, rank-based selection, tournament selection, and truncation selection.
What is elitism in genetic algorithms?
A technique that ensures the best individuals from the previous generation are preserved in the new generation.
What are mutation operators?
Methods that randomly alter the genotype, such as single-point and multi-point mutations.
What are crossover operators?
Methods that combine genetic material from two parents to create offspring, such as one-point and multi-point crossover.
What is the role of genetic diversity in evolution?
Higher diversity helps prevent premature convergence to local optima.
What is the tradeoff in genetic algorithm population size?
A larger population increases diversity but requires more computational power.
What problem was solved using a genetic algorithm in the presentation?
The Australia map coloring problem, ensuring no two adjacent regions share the same color.
