PPT_Aritifical_Intelligence_Chapter4.pptx

PPT_Aritifical_Intelligence_Chapter4.pptx

1. Chapter 4 Randomized Search and Emergent Systems Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited 2

2. Escaping Local Maxima The most studied problems with large solution spaces are SAT and TSP. A SAT problem on a hundred variables has 2100 candidate assignments. With optimization problems like the TSP, the difficulty is compounded by the fact that we would usually not recognize that a solution is optimal, even if we were to find it. S earch methods like Hill Climbing and Tabu Search work with bounded memories. While Hill Climbing is conceptually simple, it can get stuck on a local optimum. In this chapter, we look at randomized approaches to promoting exploration. First, we look at a way to randomize the Hill Climbing algorithm. Then, we look at other approaches motivated by the way random moves made in nature can lead to build up and preservation of good solutions. 3 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

3. Iterated Hill Climbing Algorithm Iterated Hill Climbing (IHC) for a maximization problem. It does a number of Hill Climbing runs from random starting points. Graph shows : A smooth surface with a small number of local optima is well suited for Iterated Hill Climbing. A random starting point in any iteration from any of the shaded nodes would lead to the global maximum. 4 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

4. Simulated Annealing Random Walk explores the search space in a random fashion. Function RandomChoose randomly picks one of the successors of the current node. The above algorithm has n random moves. Simulated Annealing (SA) is an algorithm that combines the two tendencies, explorative and exploitative, of the two search methods. 5 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

5. To move from A to C, the algorithm has to incur a smaller loss than to move from B to C. Simulated Annealing is more likely to move from A to C to B than vice versa. 6 Consider a maximization problem from which three states A, B and C are shown in Figure Both A and B are maxima with B having a higher evaluation value. If the algorithm has to move from local maximum A to C, it will have a negative gain of ∆E AC . Likewise, if it has to move from B to C, it will have to go through a negative gain of ∆ E BC . Since this is larger than ∆E AC , it is likely that the algorithm moves from A to C more often than from B to C. Again, since the positive gain from C to B is higher; the algorithm is more likely to move from C to B than to A. That is, it is more likely that the algorithm will move from A to B than in the other direction. Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Simulated Annealing (contd.)

6. The probability of making a move at any point of time is given by a sigmoid function of the gain ∆ E and temperature T as given below: where P is the probability of making a move from the current node C to the very new node N, ∆ E = (eval(N) -eval(C)) is the gain in value and T is an externally controlled parameter called temperature. Note that the above formula is for maximization of the evaluation function value. 7 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Simulated Annealing (contd.)

7. A jagged surface with many local optima, but a broader trend towards the optimum is well suited for Simulated Annealing. Observe that the footprint of HC is very small. 8 The probability curves (Sigmoid function) for different values of T. The probability of making a move increases as AE increases. For very large T, the algorithm behaves like Random Walk. As T tends to zero, the behaviour approaches the Hill Climbing algorithm. Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Simulated Annealing (contd.)

8. Simulated Annealing makes probabilistic moves in the search space. We use the function Eval instead of h in the style used in optimization. Function Cooling Function lowers the temperature after each epoch in which some probabilistic moves are made. Function Random Neighbour randomly generates one successor of the current node, and Random(0,1) generates a random number in the range 0 to 1 with uniform probability. 9 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Simulated Annealing (contd.)

9. Genetic Algorithms A small fragment of the vast ecosystem. The natural world contains millions of species interacting with each other. Arrows depict a positive influence of the population of one species on another. Genetic Algorithms (GA) are a class of algorithms that try and build solutions by introducing evolution and selection of the best in a population of candidate solutions. 10 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

10. There are three basic operations in Genetic Algorithms are: Selection : The selection operator allows the fitter candidates to be chosen for reproduction, and thus propagation of the genes (components). In practice, GAs employ a user specified function to decide which designs/solutions are good or not. This function is called the fitness function, and gives a fitness value to each candidate. In optimization, we called this function the evaluation function. Recombination : The recombination operator takes the output of the selection operator, and randomly mates pairs of candidates in the population, producing offspring that inherit components (genes) from both parents. Mutation : Once in a while in the real world, a mistake happens and a child gets mutated copy of a gene from the parent. The most commonly used operator to recombine the genes from the two parents is known as the crossover operator. 11 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Genetic Algorithms (contd.)

11. For example, if the solution has eight components then given the two parents: 12 A two point crossover would be equivalent to doing the above operation twice. One can define many crossover operators which will take components from the parents and mix them up. Care has to be taken that the resulting strings are valid candidates. This is easy when dealing with problems like SAT, where the i th bit is a value of the i th variable, but for most problems, the crossover point should be at a component level. Some problems like the TSP will not work with the crossover depicted above. We will look at TSP separately since it is a problem of considerable interest. Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Genetic Algorithms (contd.)

12. The GA algorithm works by reproducing a population in proportion to fitness, recombines the genes by crossover, and randomly mutates some members in each cycle. Parameter k decides how many of the parent population is to be retained. 13 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Genetic Algorithms (contd.)

13. The Initial population may be randomly distributed, but as Genetic Algorithm is run, the population has more members around the peaks. If there is one major peak, then most of the population is expected to converge towards that peak, leading to high similarity in the genetic make-up. 14 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Genetic Algorithms (contd.)

14. The Travelling Salesman Problem (contd.) The 'Travelling Salesman Problem' (TSP) is one of the harder problems around, and considered by some to be the holy grail of computer science. The problem can informally be defined as follows. Given a graph in which the nodes are locations or cities, and edges are labelled with the cost of travelling between cities, to find a cycle containing each city exactly once, such that the total cost of the tour is as low as possible. Thus, the salesman must start from a city, visit each city exactly once, and return home incurring minimum cost. The cost may be distance, time, or money. Given N cities, a tour may be represented by the order in which the cities are represented, ( Cityi , Cityz ..., CityN ) which is often abbreviated to (1, 2, ..., N). This is known as the path representation. One can observe that there are N! permutations possible with N cities, each representing a tour. 15 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

15. A hundred variable SAT is hard enough. But 100! is a much bigger number. The following output from a simple Lisp program shows the number. This number is larger than 10 and clearly it is impossible to inspect all possible tours in a hundred-city problem. Thus, the general case of TSP is a prime candidate for applying stochastic (randomized) local search methods. Stochastic Local Search (SLS) methods ( Hoos and Stutzle , 2005), on the other hand, can find very good solutions quite quickly. 16 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited The Travelling Salesman Problem (contd.)

16. The Nearest Neighbour Tour construction algorithm moves to the nearest neighbour (that has not been visited) at each stage. Function NearestAllowedNeighbour picks the nearest neighbour from the unvisited cities. The last segment back to the startCity is implicit. 17 Constructive Methods The complexity of the algorithm is O(bn), where n is the number of cities and b is the maximum degree of nodes (which is n – 1 for fully connected graph). We can observe that for most greedy algorithms for TSP, the complexity is 0(n 2 ). For TSP problems that satisfy the triangle inequality, it has been shown that the tour found by the nearest neighbour algorithm is not more than ( log 2 (n) + 1)/2 times the optimal tour cost   Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

17. A near polygon arrangement of cities. The distances are the Euclidean distances in the figure. In practice, the algorithm yields fairly good tours where there may be a few long edges that are added in the final stages. The reader can verify this by trying out the method on the problem shown in Figure. Observe that if the two extreme cities were not there, the cities would have satisfied the condition of being on a convex polygon, and the algorithm would have found the optimal solution. 18 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Constructive Methods (contd.)

18. The Savings Heuristic starts with (n — 1) tours of length 2 and performs (n — 2) merge operations to construct the tour. 19 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Constructive Methods (contd.)

19. Perturbation Methods for the TSP In the 2-city-exchange, the two shaded cities exchange their position in the path representation. The new tour has the dashed edges instead of the four broken ones in the linear order. In the 2-edge-exchange, the tour is altered as shown. 20 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

20. Perturbation Methods for the TSP (contd.) In a 3-edge-exchange, three edges are removed and replaced by other edges. A closer look at the 2-city-exchange shows that it is one particular case of 4-edge-exchange in which two sets of two consecutive edges are removed from a tour, and each freed node is connected to the neighbours of the other freed node. 21 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

21. GAs for TSP Path Representation : In path representation, the simple one point or multipoint crossovers defined in this chapter earlier do not work because the resulting sequences are not likely to be valid tours. For example, given two parent tours The Partially Mapped Crossover (PMX) builds a child as follows. It chooses a random subsequence from one parent, and fills in the remaining tour by maintaining the order and position of cities as in the other parent. For the above example, choosing the subsequences from fourth to seventh city gives the children. 22 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

22. 23 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited GAs for TSP (contd.)

23. Ordinal Representation : Interestingly, there does exist a tour representation where the simple crossover can be used producing valid tours. This is known as the ordinal representation. We begin by arranging the cities to create a reference order R of the cities. 24 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Ordinal Representation

24. Adjacency Representation : Another representation of tours that has been experimented with is the adjacency representation. This is an indexed representation in which city i is in position j in the list if in the tour the salesman goes from city j to city i . In the Heuristic Crossover (HX), a child tour is constructed by choosing a random city as a starting point. The next city is chosen from the two options in the two parents, by choosing the one that is linked by a shorter edge. One can simplify the above crossover by choosing the successor cities from the two parents alternately. This is known as the Alternating Edges Crossover (AEX). A variation of this is to select a sequence of edges from one parent before choosing some from the other. This is known as the Subtour Selection Crossover (SSX). 25 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Adjacency Representation

25. Neural Networks A biological neuron from the brain receives several inputs via its dendrites and sends a signal down its axon. The axon branches out as well and connects to dendrites of other neurons via synapses, which transmit the signal chemically to the other neurons. The shaded portion of the soma is the nucleus of the cell. 26 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

26. 27 output y is some function of all the inputs X 1 to X n The neuron is a simple device that computes some function of all the inputs it receives from the other neurons. Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Neural Networks (contd.)

27. 28 The simplest function is the Threshold function defined as follows, With this function, the neuron generates an output 1, when the input to it crosses the threshold 0 (the bias b plays a role here), and outputs 0 otherwise. This is also known as Heaviside function, and this model of the neuron is also known as the McCulloch-Pitts model after Warren S McCulloch and Walter Pitts who first described it (McCulloch and Pitts, 1943). Another function used is the sigmoid function where a is a slope parameter that controls the shape of the sigmoid function in a manner similar to what is done by the parameter Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Neural Networks (contd.)

28. 29 Emergent Systems The automaton has simple rules for life and death: Cells that are alive will continue to live if they have exactly two or three living cells in their neighbourhood . Otherwise, they die of loneliness (less than two neighbours around) or overcrowding (more than three neighbours alive). 2. Cells that are dead are born again if they are surrounded by exactly three living cells. These rules are applied simultaneously to the entire grid, generating a new population from an old one. The system is a cellular automaton. Figure shows : The well known Glider in the Game of Life. By the time the above shape has gone through the transformations, it forms the same pattern shifted one step down and right. Over a period of time, it looks like the pattern is shuffling or gliding across the screen. Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

29. 30 Two recurrent genotypes and their corresponding phenotypes. The genotype is a directed graph, and the phenotype a hierarchy of 3-D parts. Figure from (Sims, 1994). The evolution of creatures begins by first creating a population of genotypes. This could be done by creating random graphs, or by other means like handcrafting them, or carrying some forward/across different runs of the system. The phenotype of the creatures is made up of a set of three-dimensional rigid parts, connected by flexible joints, powered by muscles. Two examples of simple genotypes and the corresponding phenotypes are shown in the Figure Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Emergent Systems (contd.)

30. 31 When we look at the evolution of life in the universe a question that is sometimes asked is how can order emerge out of disorder? The simple answer to that is that it is the overall entropy that increases in the universe, even while some pockets get more organized and decrease entropy locally. Chaos Theory says that the smallest changes in a deterministic dynamical system can result in ostensibly large changes later in time. When people started looking at some simple differential equations to characterize complex dynamical systems they were astonished to see that small changes in the input parameters could lead to seemingly random variations in the futures predicted. How did the complex human body, and even more so our brain, evolve, given that we are mostly made up of air, water, chalk, and coal, with a smattering of other elements? The answer lies in the ratchet mechanism described to us by Richard Dawkins (1986; 1996) and Steve Grand (2001). Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Emergent Systems (contd.)

31. 32 Ant Colony Optimization When an obstacle is placed on the pheromone trail of an ant colony, they quickly find the shortest diversion around it. Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited

32. 33 The basic outline of the ACO algorithm for TSP is described in the Figure In the ACO algorithm for TSP, a set of m ants construct tours by a greedy algorithm that moves probabilistically to the next city. After the tour construction, each ant deposits pheromone inversely proportional to the cost of its tour. This process is repeated a number of times, retaining the best tour found. Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Ant Colony Optimization (contd.)

33. 34 Chapter 4 Copyright © 2013 by McGraw Hill Education (India) Private Limited Ant Colony Optimization (contd.)