Beyond Classical Search

Question 1

What is the basic idea of local search?

Answer 1

Store current nodes, generate successors, choose a successor to be next node

Question 2

Local search can get stuck on ______ and local ______

Answer 2

plateaus, maxima

Question 3

__________ is a simple local search algorithm that can find local maximas

Answer 3

Hill-climbing

Question 4

What is the Hill-climbing pseudo code?

Answer 4

function Hill-Climbing(problem) returns a state that is a local maxima
        current {-- initial-state
        loop:
                neighbor {-- highest-valued successor of current
                if neighbor.value {= current.value then return current
                current {-- neighbor

Question 5

Hill-climbing is a kind of ______ search

Answer 5

greedy

Question 6

In ________ hill-climbing, moves are chosen at random, with preference given to steeper jumps

Answer 6

stochastic

Question 7

What is first-choice hill-climbing?

Answer 7

hill climbing where the chosen node is the first node that is higher than the current value

Question 8

In random-restart hill-climbing, a _______ of hill climbs are executed from random starting points

Answer 8

series

Question 9

What is gradient descent?

Answer 9

The goal is the find the lowest point of the function

Question 10

In simulated annealing with gradient descent?

Answer 10

• Choose a successor at random
• If successor has a lower value, take it
• If successor has a higher value, it may be accepted based on probably T

Question 11

in simulated annealing, the temperature T start hot and ________ as the algorithm continues

Answer 11

decreases

Question 12

Local beam search tracks k states, then generates the ________, and if anyone of them is a goal, _____. Otherwise it picks the k ____ ________ for the next step

Answer 12

successors, stops, best successors

Question 13

In a ________ local beam search, the k successors are chosen at random

Answer 13

stochastic

Question 14

A genetic algorithm is a variant of the _____ ______ search where the nest state is generated by __________ states

Answer 14

local beam, combining

Question 15

In genetic algorithms, pairs of states are chosen in a randomly weighted way and are then ______ to make a new state

Answer 15

combined

Question 16

Give an example of crossover using 20 bit strings

Answer 16

Take first 10 bits of one and last 10 bits of another string

Question 17

What is a mutation?

Answer 17

Randomly modifying a part of the state

Question 18

What are 3 questions when creating a genetic algorithm?

Answer 18

• What size of k
• How should states be combined?
• How frequently should mutation occur