Local Search (midterm) Flashcards
What is the state space of local search for a CSP?
Any possible state for assignment, candidate assignment
What are two key limitations of local search as compared to DFS with pruning or Arc consistency with Domain Splitting?
- Not complete, it is not guaranteed to find a solution.
2. It is not able to show if the solution exists
Explain a reasonable way to generate neighbors for local search?
Neighbours are similar assignments to current node, that differ by one small change
Change a variable by 1 value
Change a variable by any amount
Change two variables by 1 value or any amount
Define a plateau. Why are plateaus a problem for local search?
Plateau is the flat local max in the evaluation graph which means neighboring states yield same result.
Why does randomization help in local search?
It prevents local search from getting stuck at the local maxima/minima
Explain how the next state is chosen in simulated annealing?
If it is an “improvement” is we choose this state,
If it is not an “improvement” we pick on this state based on probability with respect to temperature, the higher the temperature the more likely we choose this state.
How would you change a local search algorithm to better find global maxima that are surrounded by local maxima? Assume that the neighbor relation is fixed?
Adding randomness to the algorithm potentially adding random step or more frequent random restarts
Random steps are better with large domains- less work randomly assigning just neighbours
How would you design a local search algorithm for a problem where there are no plateaus and no local minima that are not global minima? Assume that the neighbor relation is fixed.
By hill climbing/ greedy descent to move to a neighbor with the best improvement (
Give an example of a crossover algorithm that could be used in a genetic algorithm; do not use the example given in class
For example, cross over every second position of the two nodes.
What is the difference between a random step and a random restart?
Random step moves to a random neighbour while random restart reassigns random values to all variables.
Consider two local search algorithm, A and B. A solves x% of the problem it is given within x^2 minutes. B solve y% of the problems it is given within y minutes. Is one algorithm always better than the other? If not which algorithm would you use then?
A and B are equal for % solved in 1 minute.
< 1 minute, A is better;
> 1 minute, B is better.
Consider two local search algorithm, A and B. A solves sqrt x% of the problem it is given within x minutes. B solve y% of the problems it is given within y minutes. Is one algorithm always better than the other? If not which algorithm would you use then?
Consider time = 4 min (> 1 min): A solves sqrt(4)=2% of problems, while B solves 4%. (It’s the same as q11 for n > 0 because the sqrt is on the % solved, not the time given, which had the 2 in q11.)
= 1 same
< 1 A is better.
