Local search methods

In this topic, we will discuss multiple methods of search that are memory efficient and can handle continuous state spaces but do not guarantee optimality.  Because of the efficiency of the approaches, they are often used to create solutions quickly.  You will make use of these in your projects so that you get experience with them.

Hill climbing

The first search is called hill climbing for reasons that will be obvious when you watch the video.  Note, sometimes one is climbing UP the hill and sometimes one is climbing DOWN the hill, depending on which way is better with your scoring metics.

• Reading
  • Read Section 4.1 of Chapter 4 (Local Search and Optimization Problems) up to 4.1.4

• Watch the video on hill climbing
  • Link to slides

Simulated Annealing

The next local search we will discuss is called simulated annealing, drawing inspiration from metallurgy.  

• Video on simulated annealing search
  • Link to slides

Beam Search

The next search method we will cover allows you to search with a limited amount of memory.  This can be very efficient in many cases!

• Video on local beam search
  • Link to slides

Assignments

• Complete the assignment on local search
•  Post on #homework-quiz-questions some of the ways in which you do a local search in real-life (e.g. examples of how you, a human, perform local search)

Next topic

• The next topic is also a form of local search but it deserves its own topic as it is a very broad field of research!  Jump to evolutionary search.