1 of 42

Introduction to Artificial Intelligence

By:

Dr. Mohammad Shoab

Week 5

2 of 42

Local Search Algorithms

Informed Search Strategies (Heuristic Search):

    • A search strategy which searches the most promising branches of the state-space first can: (1) find a solution more quickly, (2) find solutions even when there is limited time available, (3) often find a better solution, since more profitable parts of the state-space can be examined, while ignoring the unprofitable parts.
    • A search strategy which is better than another at identifying the most promising branches of a search-space is said to be more informed.
      1. Hill climbing, Simulated Annealing, Tabu search.
      2. Best first search.
      3. Greedy search.
      4. A* search.

Introduction to Artificial Intelligence

Department of Computer Science

3 of 42

Local Search Algorithms

  • Hill Climbing,
  • Simulated Annealing,
  • Tabu Search

Introduction to Artificial Intelligence

Department of Computer Science

4 of 42

•

search

algorithm

Hill climbing

(also known

as greedy local

search) uses a loop that continually moves in the direction of increasing values (that is uphill).

•

It terminates when it reaches a peak where no neighbor has a higher value.

Hill Climbing

  • "Like climbing Everest in thick fog with amnesia"

Introduction to Artificial Intelligence

Department of Computer Science

5 of 42

Hill Climbing Search

Introduction to Artificial Intelligence

Department of Computer Science

6 of 42

Hill Climbing

states

evaluation

Introduction to Artificial Intelligence

Department of Computer Science

7 of 42

Hill Climbing in Action …

Cost

States

Introduction to Artificial Intelligence

Department of Computer Science

8 of 42

Hill Climbing

Current Solution

Introduction to Artificial Intelligence

Department of Computer Science

9 of 42

Hill Climbing

Current Solution

Introduction to Artificial Intelligence

Department of Computer Science

10 of 42

Hill Climbing

Current Solution

Introduction to Artificial Intelligence

Department of Computer Science

11 of 42

Hill Climbing

Current Solution

Introduction to Artificial Intelligence

Department of Computer Science

12 of 42

Hill Climbing

Best

Local Minimum

​

Global Minimum

Introduction to Artificial Intelligence

Department of Computer Science

13 of 42

optimum.

Issues

​

The Goal is to find GLOBAL

​

  1. How to avoid LOCAL optima?
  2. When to stop?
  3. Climb downhill? When?

Introduction to Artificial Intelligence

Department of Computer Science

14 of 42

Simulated Annealing

  • Key Idea: escape local maxima by allowing some "bad" moves but gradually decrease their frequency
  • Take some uphill steps to escape the local minimum
  • Instead of picking the best move, it picks a random move
  • If the move improves the situation, it is executed. Otherwise, move with some probability less than 1.
  • Physical analogy with the annealing process:
    • Allowing liquid to gradually cool until it freezes
  • The heuristic value is the energy, E
  • Temperature parameter, T, controls speed of convergence.

Introduction to Artificial Intelligence

Department of Computer Science

15 of 42

Simulated Annealing

  • Basic inspiration: What is annealing?

In metallurgy, annealing is the physical process used to temperature or harden metals or glass by heating them to a high temperature and then gradually cooling them, thus allowing the material to coalesce into a low energy crystalline state.

Heating then slowly cooling a substance to obtain a strong

crystalline structure.

  • Key idea: Simulated Annealing combines Hill Climbing with a random walk in some way that yields both efficiency and completeness.

Introduction to Artificial Intelligence

Department of Computer Science

16 of 42

Simulated Annealing in Action …

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

17 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

18 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

19 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

20 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

21 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

22 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

23 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

24 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

25 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

26 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

27 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

28 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

29 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

30 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

31 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

32 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

33 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

34 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

35 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

36 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

37 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

38 of 42

Simulated Annealing

Cost

Best

States

Introduction to Artificial Intelligence

Department of Computer Science

39 of 42

The End

39

Introduction to Artificial Intelligence

Department of Computer Science

40 of 42

Exercise

Q1. What is heuristic search?

Q2. Explain Hill Climbing algorithm.

Q3. Explain Simulated Annealing.

Q4. Write the search path and cost of the given figure for Hill Climbing algorithm

40

Introduction to Artificial Intelligence

Department of Computer Science

41 of 42

Q5. Hill Climbing Search algorithm also known as

  1. Iterative deepening search
  2. Uninformed search
  3. Greedy local search
  4. None of the above

​

Q6. Instead of picking the best move, Simulated Annealing picks a

  1. Random move
  2. Selected move
  3. Repeated move
  4. None of the above

​

41

Introduction to Artificial Intelligence

Department of Computer Science

42 of 42

Q7. Simulated Annealing combines

  1. Random walk and A*
  2. Hill climbing and random walk
  3. Hill climbing and BFS
  4. None of the above

​

42

Introduction to Artificial Intelligence

Department of Computer Science