Select the name of the local search algorithm that is identified by each description.

Question 1 options:

12345	Modify the assignment by choosing a neighboring assignment that optimizes an evaluation function.
12345	Modify the assignment in two steps - first choose a variable to change, then choose a value for it.
12345	Modify the assignment by either choosing a neighboring assignment that modifies an evaluation function, or making a random choice of move.
12345	Select a variable in a conflict at random and change it.
12345	Pick a variable at random, then a value at random. If the ensuing assignment is better, accept it. It if is not, accept it with some probability (where the probability of accepting a worse assignment decreases over time.)

1.	Any Conflict Algorithm
2.	Iterative Best Improvement Algorithm
3.	Most Improving Step Algorithm
4.	Simulated Annealing Algorithm
5.	Two-Stage Choice Algorithm

Question 2 (3 points)

In simulated annealing, what happens to the probability of accepting a worsening step in the solution as the temperature goes down over time?

Question 2 options:

	The probability goes up as temperature goes down.
	The probability stays the same as temperature goes down.
	The probability goes down as temperature goes down.

Population-based Methods

Question 3 (3 points)

Match the each population-based search method to its description.

Question 3 options:

123	Genetic algorithm
123	Stochastic beam search
123	Beam search

1.	A variant of local search in which multiple good assignments are propagated to the next stage instead of just the best one.
2.	A variant of local search in which multiple assignments, some randomly chosen rather than the best assignments, are propagated to the next stage instead of just the best one.
3.	A variant of local search in which the assignments propagated to the next stage are combinations of the assignments at the present stage.

Optimization

Question 4 (2 points)

When attempting to solve a constrained optimization problem with both hard and soft constraints, it may be OK to allow intermediate assignments to violate one or more of the hard constraints while searching for a solution.

Question 4 options:

	True
	False

Question 5 (2 points)

Gradient Descent is a method to solve constraint satisfaction optimization problems with continuous domains.

Which of the following is the closest analogue to gradient descent for discrete domains?

Question 5 options:

	Genetic algorithm
	Random restart
	Greedy descent
	Simulated annealing