Search Algorithms

Question 1

Definition of Search algorithms:

Answer 1

Given a set of possible solutions, find the best (a reasonable) one

Question 2

What purpose does Search serve?

Answer 2

Algorithm for finding a solution with specified properties among a collection of solutions

Question 3

A Search solution:

Answer 3

• may be stored individually as records in a database
• may be elements of a search space defined by a
  mathematical formula or procedure
• a combination of the two, such as the Hamiltonian
  circuits of a graph

Question 4

Solution Spaces:

Answer 4

Ordered space
(e.g., dictionary)
* Unordered space
(e.g., Where’s Wally?)
* Higher-dimensional
space

Question 5

Exhaustive (brute force)

Answer 5

Try all combinations — usually unfeasible

Question 6

Branch and bound

Answer 6

• Divide, find upper and lower bounds for error/quality
  — linear programming
• Time-consuming

Question 7

Randomized

Answer 7

• Generate random combinations, pick the best among them
• Random walk — generate random changes based on the last seen and move if better than current best

Question 8

Iterative improvement methods

Answer 8

• Tabu Search
• Simulated Annealing
• Evolutionary Algorithm

Question 9

Gradient Descent Approach refers to:

Answer 9

• Refers to learning methods that seek to minimize an objective function by which system performance is measured
• At each point in time, the policy is to choose the next step that yields the minimal objective function value
• The learning rate parameters refer to the step size taken at each point in time
• Each step is computed only on the basis of local information, which is extremely efficient, but introduces possibility of traps in local minima

Question 10

Hill-Climbing

Answer 10

Analogous process whereby objective function is maximized

Question 11

Hill-Climbing Algorithm

Answer 11

loop do
neighbor ← a highest-valued successor of current
if neighbor.VALUE ≤ current.VALUE then return current.STATE
current ← neighbor

Question 12

Tabu Search: move selection

Answer 12

• Each move is chosen from a (generated) neighborhood
• Tabu list of forbidden moves (for a given duration)
• Tabu restrictions may be overridden when the tabu
  move evaluation in a solution is better than any other visited so far: aspiration criterion

Question 13

Tabu Search

Answer 13

• Search around last solution neighborhood
• Tries to overcome local minima by exploring neighbors and deciding moves based on “memory”
• Semi-random exploration based in maintaining a selective history of the states encountered during the search
• New states (neighbors) are feasible moves if they are not in the tabu list (tabu rule) → memory (short & long)
• The neighborhood of a state is not a static set, but rather a set that can change according to the history of the search

Question 14

Simulated Annealing combines:

Answer 14

Gradient descent with random walk

Question 15

Simulation of cooling of a heated material

Answer 15

• A solid material is heated past its melting point and then cooled back into a solid state (annealing)
• The final structure depends on how the cooling is performed
• slow cooling → large crystal (low energy)
• fast cooling → imperfections (high energy)
• Metropolis’ algorithm simulates the change in energy of the system when subjected to the cooling process, converging to a final state (of a certain energy)

Question 16

Simulated Annealing new solution is accepted if

Answer 16

• Has lower cost than the previous
• When cost is higher – with a probability based on the
  difference to the best and the defined “temperature”

Question 17

Simulated Annealing Algorithm

Answer 17

current ← MAKE-NODE(problem.INITIAL-STATE)

for t = 1 to ∞ do

T ← schedule(t)

if T = 0 then return current

next ← a randomly selected successor (similar) of current

∆E ← next.VALUE – current.VALUE

if ∆E > 0 then current ← next

else current ← next only with probability e∆E/T

Question 18

Simulated Annealing Issues

Answer 18

• Minimum and maximum temperature
• Scheme for decreasing temperature
• Temperature length (number of iterations at each temperature)
• Evaluation (cost) function
• Initialization

Question 19

Genetic Algorithm

Answer 19

Tries to find the best
fitted solutions by:

• Generating a
  population of
  solutions
• Evaluating all (fitness
  function)
• Recombining and/or
  Mutating the best
  individuals in the
  evolutionary
  population to create a
  new generation

Question 20

Genetic Algorithm implementation

Answer 20

repeat

new population ← empty set

for i = 1 to SIZE(population) do

x ← RANDOM-SELECTION(population,FITNESS-FN)

y ← RANDOM-SELECTION(population,FITNESS-FN)

child ← REPRODUCE(x , y)

if (small random probability) then child ← MUTATE(child)

add child to new population

population ← new population

until some individual is fit enough, or enough time has elapsed

return the best individual in population, according to FITNESS-FN

Question 21

Important Aspects Genetic Algorithm

Answer 21

Implementation

• choose a good representation
• decide on the population size, mutation rate, . . .
• select/delete individuals
• best crossover(s), kind of mutation(s)
• Termination criteria
• Performance, scalability
• Adequate evaluation function

Question 22

Genetic Algorithms advantages

Answer 22

*Are easily understandable

• Support multi-objective optimization
• Show good performance in noisy environments
• Answers get better over time
• Inherently parallel and easy to distribute