local search

Question 1

what’s a local maximum?

Answer 1

-A local maximum occurs when the current solution is better than its neighbors but is not the best solution globally.
-the goal of a local search algorithm is to find the global maximum, but this is not guaranteed if the algorithm gets trapped in a local maximum

Question 2

what’s a plateaus?

Answer 2

• a flat region in the search space where the objective function remains constant or changes very slowly.(can pose as a problem)

Question 3

what’s a ridge?

Answer 3

-a narrow, elongated region in the search space where the values of the objective function rise gradually (can pose as a problem)

Question 4

when do we use local search?

Answer 4

• when there are limited resources

Question 5

what are the characteristics of local search?

Answer 5

-it focuses on neighbouring states
-doesn’t keep track of visited states
-the goal is to find a solution without considering distant states

Question 6

what are the main challenger for hill climbing?

Answer 6

-ridges
-local maxima
-plateaus

Question 7

what’s a search that solves the local maxima problem?

Answer 7

-Simulated Annealing: it Combines hill climbing with random exploration.

Question 8

what’s a local beam search?

Answer 8

• at each step, the algorithm generates k successor states from the current state.
  -If k is greater than 1, the algorithm maintains multiple states simultaneously, each state will continue climbing indipendently

Question 9

what’s a crossover operation? ( genetics algorithms)

Answer 9

• pairs of individuals are selected from the population.
  -A crossover point is chosen at random for each pair.
  -Offspring are created by exchanging genetic material (information) between the parents at the crossover point.