4 Reasoning with Constraints

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

4.8 Population-Based Methods

The preceding local search algorithms maintain a single total assignment. This section considers algorithms that maintain multiple total assignments. The first method, beam search, maintains the best k assignments. The next algorithm, stochastic beam search, selects which assignments to maintain stochastically. In genetic algorithms, which are inspired by biological evolution, the k assignments forming a population interact to produce the new population. In these algorithms, a total assignment of a value to each variable is called an individual and the set of current individuals is a population.

Beam search is a method similar to iterative best improvement, but it maintains up to k assignments instead of just one. It reports success when it finds a satisfying assignment. At each stage of the algorithm, it selects k best possible successors of the current individuals (or all of them if there are less than k) and picks randomly in the case of ties. It repeats with this new set of k total assignments.

Beam search considers multiple assignments at the same time. Beam search is useful for memory-bounded cases, where k can be selected depending on the memory available. The variants of stochastic local search presented earlier are also applicable to beam search; you can spend more time finding the best k, or spend less time and only approximate the best k.

Stochastic beam search is an alternative to beam search, which, instead of choosing the best k individuals, selects k of the individuals at random; the individuals with a better evaluation are more likely to be chosen. This is done by making the probability of being chosen a function of the evaluation function. A standard way to do this is to use a Gibbs distribution or Boltzmann distribution and to select an assignment A with probability proportional to

e-h⁢(A)/T,

where h⁢(A) is an evaluation function and T is a temperature.

Stochastic beam search tends to allow more diversity in the k individuals than does plain beam search. As an analogy to evolution in biology, the evaluation function reflects the fitness of the individual; the fitter the individual, the more likely it is to pass its genetic material – here its variable assignment – onto the next generation. Stochastic beam search is like asexual reproduction; each individual gives slightly mutated children and then stochastic beam search proceeds with survival of the fittest. Note that under stochastic beam search it is possible for an individual to be selected multiple times at random.

Genetic algorithms further pursue the evolution analogy. Genetic algorithms are like stochastic beam searches, but each new element of the population is a combination of a pair of individuals – its parents. In particular, genetic algorithms use an operation known as crossover that select pairs of individuals and then create new offspring by taking some of the values for the offspring’s variables from one of the parents and the rest of the values from the other parent, loosely analogous to how DNA is spliced in sexual reproduction.

A genetic algorithm is shown in Figure 4.11. This maintains a population of k individuals (where k is an even number). At each step, a new generation of individuals is generated via the following steps until a solution is found:

1: procedure Genetic_algorithm(Vs,d⁢o⁢m,Cs,S,k)
2:      Inputs
3:          Vs: a set of variables
4:          dom: a function; dom⁢(X) is the domain of variable X
5:          Cs: set of constraints to be satisfied
6:          S: a cooling schedule for the temperature
7:          k: population size – an even integer      
8:      Output
9:          total assignment that satisfies the constraints
10:      Local
11:          Pop: a set of assignments
12:          T: real      
13:      Pop:= k random total assignments
14:      T is assigned a value according to S
15:      repeat
16:          if some A∈Pop satisfies all constraints in Cs then
17:               return A          
18:          Npop:=⁢{}
19:          repeat k/2 times
20:               A1:=Random_selection⁢(Pop,T)
21:               A1:=Random_selection⁢(Pop,T)
22:               N1,N2:=Crossover⁢(A1,A2)
23:               Npop:=Npop∪{mutate⁢(N1),mutate⁢(N2)}          
24:          Pop:=Npop
25:          T is updated according to S
26:      until termination
27: procedure Random_selection(Pop,T)
28:      select A from Pop with probability proportional to e-h⁢(A)/T
29:      return A
30: procedure Crossover(A1,A2)
31:      select integer i, 1≤i<|Vs| at random
32:      Let N1:={(Xj=vj)∈A1 for j≤i}∪{(Xj=vj)∈A2 for j>i}
33:      Let N2:={(Xj=vj)∈A2 for j≤i}∪{(Xj=vj)∈A1 for j>i}
34:      return N1,N2
Figure 4.11: Genetic algorithm for finding a solution to a CSP
  • •

    Randomly select pairs of individuals where the fitter individuals are more likely to be chosen. How much more likely a fit individual is to be chosen than a less fit individual depends on the difference in fitness levels and a temperature parameter.

  • •

    For each pair, perform a crossover.

  • •

    Randomly mutate some (very few) values by choosing other values for some randomly chosen variables. This is a random walk step.

It proceeds in this way until it has created k individuals, and then the operation proceeds to the next generation.

The new operation that occurs in genetic algorithms is called crossover. Uniform crossover takes two individuals (the parents) and creates two new individuals, called the children. The value for each variable in a child comes from one of the parents. A common method is one-point crossover, shown in the procedure Crossover in Figure 4.11, which assumes a total ordering of the variables. An index i is selected at random. One of the children is constructed by selecting the values for the variables up to i from one of the parents, and the values for variables after i from the other parent. The other child gets the other values. The effectiveness of the crossover depends on the total ordering of the variables. The ordering of the variables is part of the design of the genetic algorithm.

Example 4.26.

Consider Example 4.9 where the evaluation function to be minimized is the number of unsatisfied constraints. The individual A=2, B=2, C=3, D=1, E=1 has an evaluation of 4. It has a low value mainly because E=1. Its offspring that preserve this property will tend to have a lower evaluation than those that do not and, thus, will be more likely to survive. Other individuals may have low values for different reasons; for example, the individual A=4, B=2, C=3, D=4, E=4 also has an evaluation of 4. It is low mainly because of the assignment of values to the first four variables. Again, offspring that preserve this property will be fitter and more likely to survive than those that do not. If these two were to mate, some of the offspring would inherit the bad properties of both and would die off. Some, by chance, would inherit the good properties of both. These would then have a better chance of survival.

Efficiency is very sensitive to the variables used to describe the problem and the ordering of the variables. Getting this to work is an art. As with many other randomized algorithms, evolutionary algorithms have many degrees of freedom and, therefore, are difficult to configure or tune for good performance.

A large community of researchers are working on genetic algorithms to make them practical for real problems and there have been some impressive results. What we have described here is only one of the possible genetic algorithms.