Intro to ArtificiaI Intelligence Unit No 2 Notes-1.pptx

Search Algorithms

1. “ AN INTRODUCTION TO ARTIFICIAL INTELLIGENCE” UNIT NO 2: SEARCH METHODS BY P rof . Vinay V Shirashyad DEPARTMENT OF CSE ( ARTIFICIAL INTELLIGENCE AND DATA SCIENCE ) 1

2. Unit No 2: Search Methods State Space Search Simple search: Depth first search (DFS), Breadth First search (BFS), Comparison, Quality of Solution, Depth Bounded DFS, Depth First Iterative Deepening. Heuristic Search : Generate and test, Heuristic Functions, Search Techniques: Best-first search, Hill climbing, Local Maxima, Solution Space Search, Variable Neighbourhood Descent, Beam Search, Tabu Search, Peak to peak method. 2 Randomized Search: Population Based Methods: Escaping Local Optima, Iterated Hill Climbing, Simulate d Annealing, Geneti c Algorithms, Neural Network, Emergent Systems, Ant Colony Optimization.

3. Unit 2 SEARCH METHODS 1. Search Algorithms in Artificial Intelligence Search algorithms are one of the most important areas of Artificial Intelligence. This topic will explain all about the search algorithms in AI. Problem-solving agents: In Artificial Intelligence, Search techniques are universal problem-solving methods. Rational agents or Problem-solving agents in AI mostly used these search strategies or algorithms to solve a specific problem and provide the best result. Problem-solving agents are the goal-based agents and use atomic representation. In this topic, we will learn various problem-solving search algorithms. * 3

4. Unit 2 SEARCH METHODS Search Algorithms in Artificial Intelligence Search Algorithm Terminologies: a. Search: Searching is a step by step procedure to solve a search-problem in a given search space. A search problem can have three main factors: Search Space: Search space represents a set of possible solutions, which a system may have. Start State: It is a state from where agent begins the search . Goal test: It is a function which observe the current state and returns whether the goal state is achieved or not. b . Search tree: A tree representation of search problem is called Search tree. The root of the search tree is the root node which is corresponding to the initial state. c. Actions: It gives the description of all the available actions to the agent. * 4

5. Unit 2 SEARCH METHODS 1. Search Algorithms in Artificial Intelligence Search Algorithm Terminologies: d. Transition model: A description of what each action do, can be represented as a transition model. e.Path Cost: It is a function which assigns a numeric cost to each path. f. Solution: It is an action sequence which leads from the start node to the goal node. g. Optimal Solution: If a solution has the lowest cost among all solutions. * 5

6. Unit 2 SEARCH METHODS 1. Search Algorithms in Artificial Intelligence Based on the search problems we can classify the search algorithms into Uninformed (Blind search) search and Informed search (Heuristic search) algorithms . 6

7. Unit 2 SEARCH METHODS 1. Breadth-first Search: Breadth-first search is the most common search strategy for traversing a tree or graph . This algorithm searches breadthwise in a tree or graph, so it is called breadth-first search. BFS algorithm starts searching from the root node of the tree and expands all successor node at the current level before moving to nodes of next level. The breadth-first search algorithm is an example of a general-graph search algorithm. Breadth-first search implemented using FIFO queue data structure. Advantages: BFS will provide a solution if any solution exists. If there are more than one solutions for a given problem, then BFS will provide the minimal solution which requires the least number of steps. Disadvantages It requires lots of memory since each level of the tree must be saved into memory to expand the next level. BFS needs lots of time if the solution is far away from the root node. 7

8. Unit 2 SEARCH METHODS 1. Breadth-first Search: Example: BFS algorithm A standard BFS implementation puts each vertex of the graph into one of two categories: Visited Not Visited The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. The algorithm works as follows: Start by putting any one of the graph's vertices at the back of a queue. Take the front item of the queue and add it to the visited list. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue. Keep repeating steps 2 and 3 until the queue is empty. The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the BFS algorithm on every node •. 8

9. Unit 2 SEARCH METHODS 1. Breadth-first Search: Example: 9

10. Unit 2 SEARCH METHODS 1. Breadth-first Search: Example: 10

11. Unit 2 SEARCH METHODS 1. Breadth-first Search: Example: 11

12. Unit 2 SEARCH METHODS 1. Breadth-first Search: Example: 12

13. Unit 2 SEARCH METHODS 1. Breadth-first Search: Example: 13

14. Unit 2 SEARCH METHODS 1. Breadth-first Search: Example: 14

15. Unit 2 SEARCH METHODS 2. Depth-first Search: Depth-first search isa recursive algorithm for traversing a tree or graph data structure. It is called the depth-first search because it starts from the root node and follows each path to its greatest depth node before moving to the next path. DFS uses a stack data structure for its implementation. The process of the DFS algorithm is similar to the BFS algorithm. Backtracking is an algorithm technique for finding all possible solutions using recursion. Advantage: DFS requires very less memory as it only needs to store a stack of the nodes on the path from root node to the current node. It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right path). Disadvantage: There is the possibility that many states keep re-occurring, and there is no guarantee of finding the solution. DFS algorithm goes for deep down searching and sometime it may go to the infinite loop. 15

16. Unit 2 SEARCH METHODS 2. Depth-first Search: Depth First Search Algorithm A standard DFS implementation puts each vertex of the graph into one of two categories: Visited Not Visited The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. The DFS algorithm works as follows: Start by putting any one of the graph's vertices on top of a stack. Take the top item of the stack and add it to the visited list. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack. Keep repeating steps 2 and 3 until the stack is empty. 16

17. Unit 2 SEARCH METHODS 2. Depth-first Search: 17

18. Unit 2 SEARCH METHODS 2. Depth-first Search: 18

19. Unit 2 SEARCH METHODS 2. Depth-first Search: 19

20. Unit 2 SEARCH METHODS 2. Depth-first Search: 20

21. Unit 2 SEARCH METHODS 2. Depth-first Search: 21

22. Unit 2 SEARCH METHODS 2. Depth-first Search: 22

23. Unit 2 SEARCH METHODS 3. Depth Bounded DFS / Depth Limited Search Algorithm It is similar to DFS with a Predetermined limit. Depth Bounded DFS/ Depth Limited Search can solve the drawback of the infinite path in DFS. In this algorithm, The node of the depth limit will treat as it has no successor nodes further. Depth Limited search can be terminated with two conditions of failures- Standard Failure Value- It indicates that problem does not have any solution. Cutoff Failure Value- It defines no solution for the problem within a given depth limit. 23

24. Unit 2 SEARCH METHODS Depth Bounded DFS / Depth Limited Search Algorithm Advantages- It is memory efficient 24 Disadvantages- Incompleteness It may not be optimal if the problem has more than one solution.

25. Unit 2 SEARCH METHODS 3. Depth Bounded DFS / Depth Limited Search Algorithm Problem- 25

26. Unit 2 SEARCH METHODS 3. Depth Bounded DFS / Depth Limited Search Algorithm Solution- 26

27. Unit 2 SEARCH METHODS 4. Depth First Iterative Deepening. The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal is found. This algorithm performs depth-first search up to a certain "depth limit", and it keeps increasing the depth limit after each iteration until the goal node is found. This Search algorithm combines the benefits of Breadth-first search's fast search and depth-first search's memory efficiency. The iterative search algorithm is useful uninformed search when search space is large, and depth of goal node is unknown. 27

28. Unit 2 SEARCH METHODS 4. Depth First Iterative Deepening. Advantages: It combines the benefits of BFS and DFS search algorithm in terms of fast search and memory efficiency. Disadvantages: The main drawback of IDDFS is that it repeats all the work of the previous phase. 28

29. Unit 2 SEARCH METHODS 4. Depth First Iterative Deepening. Example: Following tree structure is showing the iterative deepening depth-first search. IDDFS algorithm performs various iterations until it does not find the goal node. The iteration performed by the algorithm is given as: 1'st Iteration-----> A 2'nd Iteration----> A, B, C 3'rd Iteration------>A, B, D, E, C, F, G 4'th Iteration------>A, B, D, H, I, E, C, F, K, G 29

30. Unit 2 SEARCH METHODS Heuristic Search : 1. Best First Search (Informed Search) Best first search is a traversal technique that decides which node is to be visited next by checking which node is the most promising one and then check it. For this it uses an evaluation function to decide the traversal. This best first search technique of tree traversal comes under the category of heuristic search or informed search technique. The cost of nodes is stored in a priority queue. This makes implementation of best-first search is same as that of breadth First search. We will use the priorityqueue just like we use a queue for BFS 30

31. Unit 2 SEARCH METHODS Heuristic Search : Algorithm for implementing Best First Search 31

32. Unit 2 SEARCH METHODS Heuristic Search : Algorithm for implementing Best First Search Step 1 : Create a priorityQueue pqueue. Step 2 : insert ‘start’ in pqueue : pqueue.insert(start) Step 3 : delete all elements of pqueue one by one. Step 3.1 : if, the element is goal . Exit. Step 3.2 : else, traverse neighbours and mark the node examined. Step 4 : End. 32

33. 33 Unit 2 SEARCH METHODS Heuristic Search : Generate and Test Search Generate and Test Search is a heuristic search technique based on Depth First Search with Backtracking which guarantees to find a solution if done systematically and there exists a solution. In this technique, all the solutions are generated and tested for the best solution. It ensures that the best solution is checked against all possible generated solutions. It is also known as British Museum Search Algorithm as it’s like looking for an exhibit at random or finding an object in the British Museum by wandering randomly. The evaluation is carried out by the heuristic function as all the solutions are generated systematically in generate and test algorithm but if there are some paths which are most unlikely to lead us to result then they are not considered. The heuristic does this by ranking all the alternatives and is often effective in doing so. Systematic Generate and Test may prove to be ineffective while solving complex problems. But there is a technique to improve in complex cases as well by combining generate and test search with other techniques so as to reduce the search space. For example in Artificial Intelligence Program DENDRAL we make use of two techniques, the first one is Constraint Satisfaction Techniques followed by Generate and Test Procedure to work on reduced search space i.e. yield an effective result by working on a lesser number of lists generated in the very first step

34. Unit 2 SEARCH METHODS Heuristic Search : Generate and Test Search Algorithm Generate a possible solution. For example, generating a particular point in the problem space or generating a path for a start state. Test to see if this is a actual solution by comparing the chosen point or the endpoint of the chosen path to the set of acceptable goal states If a solution is found, quit. Otherwise go to Step 1 34

35. Unit 2 SEARCH METHODS Heuristic Search : Generate and Test Search 35

36. Unit 2 SEARCH METHODS Heuristic Search : Generate and Test Search 36

37. Unit 2 SEARCH METHODS Heuristic Search : Generate and Test Search 37

38. Unit 2 SEARCH METHODS Heuristic Search : Hill Climbing Hill Climbing is a heuristic search used for mathematical optimization problems in the field of Artificial Intelligence. Given a large set of inputs and a good heuristic function, it tries to find a sufficiently good solution to the problem. This solution may not be the global optimal maximum. (Greedy Local Search Method) In the above definition, mathematical optimization problems imply that hill-climbing solves the problems where we need to maximize or minimize a given real function by choosing values from the given inputs. Example- Travelling salesman problem where we need to minimize the distance travelled by the salesman. ‘Heuristic search’ means that this search algorithm may not find the optimal solution to the problem. However, it will give a good solution in a reasonable time. A heuristic function is a function that will rank all the possible alternatives at any branching step in the search algorithm based on the available information. It helps the algorithm to select the best route out of possible routes. 38

39. Unit 2 SEARCH METHODS Heuristic Search : Hill Climbing Types of Hill Climbing 1.Simple Hill climbing: It examines the neighbouring nodes one by one and selects the first neighbouring node which optimizes the current cost as the next node. Algorithm for Simple Hill climbing : Step 1 : Evaluate the initial state. If it is a goal state then stop and return success. Otherwise, make initial state as current state. Step 2 : Loop until the solution state is found or there are no new operators present which can be applied to the current state. Select a state that has not been yet applied to the current state and apply it to produce a new state. Perform these to evaluate new state If the current state is a goal state, then stop and return success. If it is better than the current state, then make it current state and proceed further. If it is not better than the current state, then continue in the loop until a solution is found. Step 3 : Exit. 39

40. Unit 2 SEARCH METHODS Heuristic Search : Hill Climbing Types of Hill Climbing 1.Simple Hill climbing Example 40

41. Unit 2 SEARCH METHODS Heuristic Search : Hill Climbing Types of Hill Climbing 1.Simple Hill climbing Example 41

42. Unit 2 SEARCH METHODS Heuristic Search : Hill Climbing Types of Hill Climbing 2. Steepest-Ascent Hill climbing: It first examines all the neighboring nodes and then selects the node closest to solution state as of next node node. Algorithm for Simple Hill climbing : Step 1 : Evaluate the initial state. If it is a goal state then stop and return success. Otherwise, make initial state as current state. Step 2 : Repeat these steps until a solution is found or current state does not change Select a state that has not been yet applied to the current state. Initialize a new ‘best state’ equal to current state and apply it to produce a new state. Perform these to evaluate new state If the current state is a goal state, then stop and return success. If it is better then best state, then make it best state else continue loop with another new state. d) Make best state as current state and go to Step 2: b) part. Step 3 : Exit 42

43. Unit 2 SEARCH METHODS Heuristic Search : Hill Climbing Types of Hill Climbing 2. Steepest-Ascent Hill climbing: 43

44. Unit 2 SEARCH METHODS Heuristic Search : Hill Climbing Types of Hill Climbing Stochastic hill climbing: It does not examine all the neighbouring nodes before deciding which node to select. It just selects a neighbouring node at random and decides (based on the amount of improvement in that neighbour whether to move to that neighbour or to examine another. Step 1: Evaluate the initial state. If it is a goal state then stop and return success. Otherwise, make the initial state the current state. Step 2: Repeat these steps until a solution is found or the current state does not change. Select a state that has not been yet applied to the current state. Apply successor function to the current state and generate all the neighbor states. Among the generated neighbor states which are better than the current state choose a state randomly (or based on some probability function). If the chosen state is the goal state, then return success, else make it the current state and repeat step 2: b) part. Step 3: Exit. 44

45. Unit 2 SEARCH METHODS Heuristic Search : Solution Space Search- 45

46. Unit 2 SEARCH METHODS Heuristic Search : Solution Space Search- 46

47. Unit 2 SEARCH METHODS Heuristic Search : Solution Space Search- 47

48. Unit 2 SEARCH METHODS Heuristic Search : Variable Neighbourhood Decent 48

49. Unit 2 SEARCH METHODS Heuristic Search : Variable Neighbourhood Decent 49

50. Unit 2 SEARCH METHODS Heuristic Search : Beam Search- Beam search is a heuristic search algorithm that explores a graph by expanding the most optimistic node in a limited set. Beam search is an optimization of best-first search that reduces its memory requirements. Best-first search is a graph search that orders all partial solutions according to some heuristic. But in beam search, only a predetermined number of best partial solutions are kept as candidates. Therefore, it is a greedy algorithm. Beam search uses breadth-first search to build its search tree. At each level of the tree, it generates all successors of the states at the current level, sorting them in increasing order of heuristic cost. However, it only stores a predetermined number (β), of best states at each level called the beamwidth . Only those states are expanded next. The greater the beam width, the fewer states are pruned. No states are pruned with infinite beam width, and beam search is identical to breadth-first search. The beamwidth bounds the memory required to perform the search. Since a goal state could potentially be pruned, beam search sacrifices completeness (the guarantee that an algorithm will terminate with a solution if one exists). Beam search is not optimal, which means there is no guarantee that it will find the best solution. 50

51. Unit 2 SEARCH METHODS Heuristic Search : Beam Search- Uses of Beam Search A beam search is most often used to maintain tractability in large systems with insufficient memory to store the entire search tree. For example, It has been used in many machine translation systems. Each part is processed to select the best translation, and many different ways of translating the words appear. According to their sentence structures, the top best translations are kept, and the rest are discarded. The translator then evaluates the translations according to a given criterion, choosing the translation which best keeps the goals. 51

52. Unit 2 SEARCH METHODS Heuristic Search : Beam Search- Algorithm- OPEN = {initial state} while OPEN is not empty do Remove the best node from OPEN, call it n. If n is the goal state, backtrace path to n (through recorded parents) and return path. Create n's successors. Evaluate each successor, add it to OPEN, and record its parent. If |OPEN| > ß , take the best ß nodes (according to heuristic) and remove the others from the OPEN. done 52

53. Unit 2 SEARCH METHODS Heuristic Search : Beam Search- Algorithm- OPEN = {initial state} while OPEN is not empty do Remove the best node from OPEN, call it n. If n is the goal state, backtrace path to n (through recorded parents) and return path. Create n's successors. Evaluate each successor, add it to OPEN, and record its parent. If |OPEN| > ß , take the best ß nodes (according to heuristic) and remove the others from the OPEN. done 53

54. Unit 2 SEARCH METHODS Heuristic Search : Beam Search- 54

55. Unit 2 SEARCH METHODS Heuristic Search : TABU Search 55

56. Unit 2 SEARCH METHODS Heuristic Search : TABU Search 56

57. Unit 2 SEARCH METHODS Heuristic Search : TABU Search 57

58. Unit 2 SEARCH METHODS Heuristic Search : TABU Search Travelling Salesperson Problem 58

59. Unit 2 SEARCH METHODS Heuristic Search : TABU Search Travelling Salesperson Problem 59

60. Unit 2 SEARCH METHODS Heuristic Search : TABU Search Travelling Salesperson Problem 60

61. Unit 2 SEARCH METHODS Heuristic Search : TABU Search Travelling Salesperson Problem 61

62. Unit 2 SEARCH METHODS Heuristic Search : TABU Search Travelling Salesperson Problem 62

63. Unit 2 SEARCH METHODS Heuristic Search : TABU Search Travelling Salesperson Problem 63

64. Unit 2 SEARCH METHODS Randomized Search 64

65. Unit 2 SEARCH METHODS Randomized Search 1. Iterated Hill Climbing 65

66. 66 Unit 2 SEARCH METHODS Randomized Search 1. Iterated Hill Climbing

67. Unit 2 SEARCH METHODS Randomized Search 1. Iterated Hill Climbing 67

68. Unit 2 SEARCH METHODS Randomized Search 1. Iterated Hill Climbing 68

69. 69 Unit 2 SEARCH METHODS Randomized Search 1. Iterated Hill Climbing

70. Unit 2 SEARCH METHODS Randomized Search 2. Simulated Annealing 70

71. Unit 2 SEARCH METHODS Randomized Search 2. Simulated Annealing 71

72. Unit 2 SEARCH METHODS Randomized Search 2. Simulated Annealing 72

73. Unit 2 SEARCH METHODS Randomized Search 2. Simulated Annealing 73

74. Unit 2 SEARCH METHODS Randomized Search 3. Ant Colony Optimization 74

75. Unit 2 SEARCH METHODS Randomized Search 3. Ant Colony Optimization 75

76. Unit 2 SEARCH METHODS Randomized Search 3. Ant Colony Optimization 76

77. Unit 2 SEARCH METHODS Randomized Search 3. Ant Colony Optimization 77

78. Unit 2 SEARCH METHODS Randomized Search 3. Ant Colony Optimization 78

79. Unit 2 SEARCH METHODS Randomized Search 3. Ant Colony Optimization 79

80. Unit 2 SEARCH METHODS Randomized Search 3. Ant Colony Optimization 80

81. Unit 2 SEARCH METHODS Randomized Search 3. Ant Colony Optimization 81

82. Unit 2 SEARCH METHODS Randomized Search 3. Genetic Algorithm 82

83. Unit 2 SEARCH METHODS Randomized Search 3. Genetic Algorithm 83

84. Unit 2 SEARCH METHODS Randomized Search 3. Genetic Algorithm 84

85. Unit 2 SEARCH METHODS Randomized Search 3. Genetic Algorithm 85

86. Unit 2 SEARCH METHODS Randomized Search 3. Genetic Algorithm 86

87. Unit 2 SEARCH METHODS 3. Genetic Algorithm 87

88. Unit 2 SEARCH METHODS 3. Genetic Algorithm 88

89. Unit 2 SEARCH METHODS 3. Genetic Algorithm 89

90. Unit 2 SEARCH METHODS 3. Genetic Algorithm 90

91. Unit 2 SEARCH METHODS 3. Genetic Algorithm 91

92. Unit 2 SEARCH METHODS 3. Genetic Algorithm 92

93. Unit 2 SEARCH METHODS 3. Genetic Algorithm 93

94. Unit 2 SEARCH METHODS 3. Genetic Algorithm 94

95. Unit 2 SEARCH METHODS 3. Genetic Algorithm 95

96. Unit 2 SEARCH METHODS 3. Genetic Algorithm 96

97. Unit 2 SEARCH METHODS 3. Genetic Algorithm 97

98. Unit 2 SEARCH METHODS 3. Genetic Algorithm 98

99. Unit 2 SEARCH METHODS 3. Genetic Algorithm 99

100. Unit 2 SEARCH METHODS 4. Neural Networks 100

101. Unit 2 SEARCH METHODS 5. Neural Networks Emergent Systems An emergent algorithm is an algorithm is an algorithm that exhibits emergent behavior . In essence an emergent algorithm implements a set of simple building block behaviors that when combined exhibit more complex behaviors. One example of this is the implementation of fuzzy motion controllers used to adapt robot movement in response to environmental obstacles. An emergent algorithm has the following characteristics: it achieves predictable global effects it does not require global visibility it does not assume any kind of centralized control it is self-stabilizing Other examples of emergent algorithms and models include cellular automata Other examples of emergent algorithms and models include cellular automata, artificial neural networks Other examples of emergent algorithms and models include cellular automata,artificial neural networks and swarm intelligence Othe 1 r 01 examples of emergent algorithms and models include cellular automata,artificial neural

102. 102 Unit 1 INTRODUCTION Than k Y ou !!!!