Chapter 4
Informed Search and Exploration  

Outline

• Best-first search
• A* search
• Heuristics
• Hill-climbing
• Simulated annealing
• Genetic algorithms

Tree search review

4.1 INFORMED (HEURISTIC) SEARCH STRATEGIES

A strategy is defined by picking the order of node expansion.

• Evaluation function f(n) = estimate of node desirability

• Heuristic function h(n) = estimated cost of the cheapest path from node n to the goal node.

• Fringe queue orders nodes by "desirability".

 

Best-first search

Not accurate since if "best" node for expansion was known no need to search, simply follow the path through the "best" nodes to the goal.

Map of Romania with straight-line distances to Bucharest on right

Greedy best-first search

Maintains fringe in ascending order by f(n) = h(n) = the straight line distance to goal.

fringe = [Arad]

fringe = [Sibiu, Timisoara, Zerind]

fringe = [Fagaras, Rimnicu Vilcea, Timisoara, Arad, Zerind, Oradea]

fringe = [Bucharest, Rimnicu Vilcea, Sibiu, Timisoara, Arad, Zerind, Oradea]

 

Properties of greedy search

The greedy search is not optimal; show using the below diagram. Actual distance through Fagaras is 140+99+211=450; is there a shorter path? Is greedy search optimal when h(n) = actual shortest distance from n to goal?                    Actual                                Estimate              Rimnicu Vilcea = 193,     h'(Rimnicu Vilcea) = 198              Fargas = 178                  h'(Fargas) = 211

A* search

f(n) = g(n) + h(n)

fringe = [Sibiu, Timisoara, Zerind]

fringe = [Rimnicu Vilcea, Fagaras, Timisoara, Zerind, Arad, Oradea]

fringe = [Fagaras, Pitesti, Timisoara, Zerind, Craiova, Sibiu(553), Arad, Oradea]

fringe = [Pitesti, Bucharest, Timisoara, Zerind, Craiova, Sibiu(553), Sibiu(591), Arad, Oradea]

What is the final fringe value? Why did A* ignore Bucharest as the goal when expanded from Fagaras? Use A* to find the optimal path from Oradea to Bucharest. Why is it necessary to keep all nodes in memory? Is A* then practical for large-scale problems? What changes are needed for TREE-SEARCH as given below to implement A*? Consider how nodes are expanded in A* relative to f(n).

 

Optimality of A* (standard proof)

 

Optimality of A* (more useful)

Properties of A*

 where C* is the optimal path cost

How is the number of search steps affected by the relative error of h? What is the effect of highly accurate h? What is the effect of random but admissible values of h?  What is the effect of h=0? C* is the of the optimal path. What is the importance of how A* expands nodes in each of the three cases mentioned above? Recall: f(n) = g(n) + h(n) = cost to n + estimate from n to goal            and that h(n) never overestimates the cost to the goal.

Proof of lemma: Consistency

Idea: f(n) does not decrease along any path.

 h(n) = estimated cost of reaching goal from node n

 h(n') = estimated cost of reaching goal from node n'
            a successor node of n

 c(n, a, n') = step cost of reaching n' from n by action a

 

 

The following figure is not consistent. h(n) <= c(n,a,n') + h(n') h(B) = 5 c(B,a,A) = 1 h(A) = 1 h(B) <= c(B,a,A) + h(A) 5 <= 1 + 1 = 2

Show that the figure above violates the triangle inequality (a side cannot be greater than the sum of the other two). Are the heuristics admissible?

Graph-Search

Consequence of consistency is that A* using GRAPH-SEARCH is optimal if h(n) is consistence.

Consistency ensures that an sub-optimal solution will not considered and  placed on the closed list before the optimal solution.

 

4.2 HEURISTIC FUNCTIONS

Admissible heuristics

A heuristic h(n) is admissible if h(n) <= h*(n)  for h*(n) = the true cost of node n to the goal.

Average cost of an 8-puzzle is about 22 steps so h₁ and h₂ both admissible.

Ideally, the heuristic chosen is exactly the cost to the goal or at least the maximum admissible heuristic.

Since h₂ will always have at least as many misplaced tiles as h₁; h₂>=h₁

 

Dominance

 

 

Relaxed problems: inventing admissible heuristic functions

8-puzzle rules:

A tile can move from square A to square B if A is horizontally or vertically adjacent to B AND B is blank

Three different relaxed 8-puzzle rules

1. A tile can move from square A to square B; definition of h₁h₂
2. A tile can move from square A to square B if A is adjacent to B; definition of Manhattan distance heuristic h₂
3. A tile can move from square A to square B if B is blank

Traveling Salesperson Problem

Spanning tree connects an initial node to all other nodes.

 

Iterative improvement algorithms

 

Example: Traveling Sales person Problem

 

Example: n-queens problem

4.3 LOCAL SEARCH ALGORITHMS AND OPTIMIZATION PROBLEMS

• So far search produces a path to a goal, the path is the solution to the problem.
• Many problems the goal is the solution (e.g. N-queens).

Local search

• uses single current state versus selecting from multiple paths,
• generally moves only to neighbors of the current state.
• paths followed usually not retained
• not systematic (e.g. make random moves)
• Advantages:
  • use constant memory
  • can find reasonable solutions in large or infinite (continuous) state spaces
  • useful for solving optimization problems

  State space landscape

  • Objective function computes the value of a state.
  • Global maximum where objective function is greatest

  

  One dimensional state space landscape

 

Hill-climbing (or gradient ascent/descent)

Steepest ascent version, returns local maximum

• Starts current node at some initial state.
• Each step, the current node is replaced by the neighbor with the highest objective function value.
• Greedy local search - only moves in direction of highest-valued neighbor
• Get stuck because:
  • Local maxima - peak higher than neighbors but lower than global maximum.
  • Ridges - sequence of local maxima not directly connected, would require making a lower value move to reach a higher value
  • Plateaux - flat objective function value in all directions
• Incomplete, can fail to find goal because get stuck on local maxima.

 

Example

 

• The figure at right has a heuristic cost estimate value of h=17, the number of conflicting pairs of queens.
• The figure gives the estimate of each successor state.
• The successor function returns all possible  8*7=56 states reachable after a given move in a column.

 

 

Following figures

Heuristic cost estimate h showing value as number of conflicts. Queen in lower right of first figure in conflict with 2 others by moving up one row. Moving to a row with 1 conflict would be a local minima.

In second figure, queen is moved to local minima 0 which turns out to be a global minimum.

Last figure has total number of conflicts h=0, a global minimum.

Give an example of a hypothetical plateau in the 8-queens problem. Do any exist in the first queen figure? After each move does the search surface change for the queens problem?

 

Simulated annealing

Hill-climbing algorithm that never makes downhill move always incomplete.

• T gradually decreased to 0 over time t.
• Picks random rather than best state move as in hill-climbing.
• If move is improvement over current state, always accepted, otherwise accepted with probability < 1.
• Probability decreases exponentially when move is worse than current and as T decreases over time; bad moves more likely to be accepted early.

Properties of simulated annealing

 

Genetic algorithms

Intuition: genetic algorithms work by combining an existing set of states that have proven fitness to converge on an improved set of states. Search tends to make small moves in parallel from a one set of states to another nearby.

Combining the variables of states 101 and 110 can only produce states 100, 101, 110 and 111; all near to the original states.

With a goal of a state with the greatest binary value,  the most fit states are 110 and 111. Selecting and combining only the most fit states, search converges to a solution of 111.

Idea: form of local search where small changes are made in parallel to a population of candidate solution states in attempt to identify an optimal solution.

• Start with randomly generated population of valid candidate states
• For generation in (0..n)
  • Select 2 states (parents) randomly from population for reproduction based on fitness of each state. The more fit a state, the more likely selected to reproduce.
  • Reproduce a new state (child) by combining random parts of the 2 selected states (crossover).
  • Mutate a random number of new states to allow exploration other possible states.
  • Population = new states
• Best solution is fittest of population states

 

def GENETIC_ALGORITHM(population, FITNESS_FN):    for generation in range(GENERATIONS) :       new_population = []       for i in range(len(population)):          x, y = RANDOM_SELECTION(population, FITNESS_FN)          child = REPRODUCE(x, y)          if PMUTATION > random.uniform(0,1)  : child = MUTATE(child)          new_population.append(child)       population = new_population       if FITNESS_FN(argmax(population, FITNESS_FN)) >= FIT_ENOUGH :                  break    return argmax(population, FITNESS_FN)   def REPRODUCE(p1, p2):                        # Crossover    c = random.randrange(len(p1))    return p1[:c] + p2[c:] def MUTATE( c ) :                                   # r is point of mutation    r = int(random.uniform(0, len(c)))    c[r] = int(random.uniform(0, len(c)))    return c def RANDOM_SELECTION(population, weight_fn):    """Compute fitness of each in population according to weight_fn       and add up the total. Then choose 2 from sequence based on       percentage contribution to total fitness of population"""    totals = []    runningtotal = 0    for item in population:       fitness = weight_fn(item)       runningtotal = runningtotal + fitness       totals.append(runningtotal)    selections = []    for n in range(2) :                                  # Select 2       r = random.uniform(0, 1)       for i in range(len(population)):          if totals[i]/float(runningtotal) > r:             selections.append(population[i])             break    return selections

 

Example

A trivial problem is to determine the greatest 3-bit binary number. The diagram at right illustrates the state space.

Representation: a state is represented by a string. The 3 bits could be represented by strings such as: (0,0,1) etc.

Initial population: Some random set of states, for example: [(1,0,0) (0,1,0) (0,1,0) (0,0,0)]

Fitness function: determines fitness of each state; returns the integer value of the 3-bit number, 0 to 7.

Selection: individuals of each generation are randomly selected using a fitness ratio, their percentage contribution to the total fitness of the population. For the first generation:

Genes    Fitness    Fitness ratio

(1,0,0)    4            50%

(0,1,0)    2            25%

(0,1,0)    2            25%

(0,0,0)    0            0%

a total fitness 4+2+2+0=8.  (1,0,0) selected with 0.5, (0,1,0) with 0.25, (0,1,0) with 0.25 and (0,0,0) with 0.0 probability.

Randomly selected pairs using fitness ratio: [(1,0,0) (0,1,0)], [(1,0,0) (1,0,0)], [(0,1,0) (0,1,0)], [(0,1,0) (1,0,0)]

Reproduce: combine selected state pairs at some random point using crossover. The first state is copied up to the crossover point, then the second state is copied from there on.

[(1,0,0) (0,1,0)] combined at bit 1 producing (1,1,0)

[(1,0,0) (1,0,0)] combined at bit 0 producing (1,0,0)

[(0,1,0) (0,1,0)] combined at bit 2 producing (0,1,0)

[(0,1,0) (1,0,0)] combined at bit 2 producing (0,0,0)

Note that the higher order bits contribute more to our definition of fitness; combining a high and low fitness state could produce a lower fitness result.

Stagnation: it is important that less fit individuals occasionally are selected, though all individuals are selected at rate proportional to their fitness. This helps ensure populations do not stagnate by constantly selecting from the same parent states. For example, if only the most fit state, (1, 0, 0), were selected the optimal state of (1, 1, 1) would never be found.

Mutation: Because bit 0 is 0 throughout the population, no state with bit 0 a 1 can ever be explored using crossover alone. Change a random element in a state representation at some specified probability. For example:

(0,1,0) mutated to (0,1,1)

New Population: [(1,1,0), (1,0,0), (0,1,1), (0,0,0)] has total fitness of 6+4+3+0=13

Genes    Fitness    Fitness ratio

(1,1,0)    6            46%

(1,0,0)    4            31%

(0,1,1)    3            23%

(0,0,0)    0            0%

Terminate generation or fit enough: Terminate if individual fit enough or number of generations reached.

Give some reasonable population results for the next: Selection: Reproduction: Mutation (at p=0.25) New population? The two most difficult parts of a genetic algorithm are representing the population of the problem and defining a discriminating fitness function. Give a representation for a palindrome of length 8 made of up 0's and 1's. Give a fitness function for a search goal of finding a palindrome of length 8 made of up 0's and 1's. Give a representation for a palindrome of length 8 made of up A..Z. Give a fitness function for a search goal of finding a palindrome of length 8 made of up A..Z. Would you expect the problem with A..Z domain to take longer to converge (i.e. more generations)?

Example

Place N-queens of chessboard in non-conflicting positions.

Representation: a solution state is represented by a string. For 8 queens state represented by row position in column 1..8;
(3,4,2,6,1,7,8,5) represents a queen in column 1, row 3; column 2, row 4; etc. Note that the Python program uses 0..7 while the text uses 1..8.

Fitness function: returns the integer value of the number of non-conflicting queen pairs; the maximum for 8 queens is 28.

Selection: The first population state is selected with a 0.31 probability, corresponding to the percentage contribution to the total fitness of the population.

Reproduce: A crossover point to combine the two selected parent states is randomly chosen. In this example, two new child states are produced from the crossover. The effect is to maintain the fitness of each parent state in the new population; reproducing only one child state occasionally loses fitness.

Crossover

 

Example: 4-queens

The following, in conjunction with the general GENETIC-ALGORITHM above, solves the 4-queen problem yielding a solution of [2, 0, 3, 1] when run for 100 or so generations (i.e. run(100)).

The sharp-eyed reader will notice that the initial population contains that solution but not in a single individual, that is:

[[1, 1, 3, 1], [2, 0, 1, 1], [2, 0, 2, 0],[2, 3, 3, 1]]

#                                          4-queens import random PMUTATION = 0.05 GENERATIONS = 0 FIT_ENOUGH = 6                    # max number of non-conflicting pairs def fitness_fn(state) :              # Fitness: number non-conflicting Queen pairs    fitness = 0                           # Maximum is all non-conflicting    for col in range(len(state)) :       for pair in range( 1, col+1 ) :          if not conflicted(state, state[pair], pair) :             fitness = fitness + 1    return fitness def conflicted(state, row, col):   # Queen at (row, col) conflict?    for c in range(col):       if conflict(row, col, state[c], c):          return True    return False def conflict(row1, col1, row2, col2): # Queens (row1, col1) & (row2, col2)    return (row1 == row2 or col1 == col2 or row1-col1 == row2-col2 or row1+col1 == row2+col2) # same | - \/ ? def run(n) :    global GENERATIONS    GENERATIONS=n    print GENETIC_ALGORITHM([[1, 1, 3, 1], # Initial population                                               [2, 0, 1, 1],                                               [2, 0, 2, 0],                                               [2, 3, 3, 1]],                                                 fitness_fn)

 

Suppose a search goal of finding any palindrome made of up 0's and 1's. What would be a reasonable fitness function?