What is unique about optimization problems?
Path is less relevant focused on state as solution to a problem.
Define Local Search. What is an advantage?
Iterative improvement algorithms.
Keep track of single current state and tries to improve it.
Moves only to neighbouring states.
A: Uses very little memory.
Define The State Neighbourhood.
The neighbouring states for a given state.
Define Successor Function.
Chooses neighbour to proceed to based on some heuristic.
What is the travelling salesman problem.
A NP-hard problem. A salesman must visit each city exactly once and then return home in the quickest time possible.
What is a shoulder?
A plateau region which has an “uphill” ascent.
What is global maximum /minimum?
Is the best possible state of state space
landscape. It has the best value for objective function.
What is local maximum / minimum?
Is a state which is better than its neighbor states, but there is also another state which is better than it.
In the state space landscape graph what is the x-axis and y-axis?
x-axis is the state-space
y-axis is the objective function rating of those states.
Define current state.
A a state in a landscape diagram where an agent is currently present.
Define flat local maximum / minimum.
A portion of the state space landscape that is both a plateau and a local maximum / minimum.
What is the general approach for the hill climbing algorithm?
Choose the successor state that results in the most beneficial state change but if no neighbour has better value, then return the current state. If tied choose next state at random.
Hill climbing pseudocode.
current := initial-state
repeat
neighbour := successor of current
if neighbour.value <= current.value
return current
else
current := neighbour
Name three problems associated with hill climbing.
The foothill problem.
The ridge problem.
The Plateau problem.
Describe the foothill problem.
Search process may reach local maxima, where changes degrade quality value and stop search thinking optimal state has been found when only local optima found.
How might we fix the foothill and ridge problems?
Non-determinism: Random steps can help escape local maxima.
Use backtracking technique: Maintain list of visited states, able to backtrack.
Explain the ridge problem.
Ridges are local maxima which fall off steeply to low quality states either side. Algorithm struggles to move in diagonal direction.
Explain the plateau problem. Distinguish between shoulder and flat local maximum.
Large flat region (plateau) where local changes don’t increase quality and function doesn’t know what to do.
Shoulder is plateau where at end we can progress.
Flat local maximum is plateau where no exit exists.
How can we solve the plateau problem?
Allow a sideways move to states of same value but limit the amount allowed.
Define the following:
1. Simple Hill Climbing
2. Steepest Ascent Hill Climbing
3. Stochastic Hill-Climbing
4. First-Choice Climbing
5. Random-Restart Hill-Climbing
- Only takes into account one neighbouring state and sets as current if better.
- Considers multiple neighbouring states and selects best result (or current) as current
- Selects at random from uphill moves. Probability of selection varies with steepness. (steeper preferable)
- Randomly generates successors until a better one if found.
- Repeated HC from random initial until goal reached.
What is the expected number of restarts for HC to reach a solution?
1 / probability of success.
What is simulated annealing?
Escapes from local optima by also accepting, with a probability that decreases during the search, moves that are worse than the current solution.
Describe SA procedure.
The process begins with: a random viable solution, a temperature parameter which decreases according to predefined annealing schedule. Loop until temperature 0 where freezing occurs.
During loop, accept any uphill move and accept downhill move with probability based on temperature.
SA maximizing pseudocode.
current <- initial
while T > 0
Reduce T by annealing schedule
next <- rand succ current
E = next.val - current.val
if E > 0
current <- next
else if e^(E / T) > rand(0,1)
current <- next
return current
