4 Reasoning with Constraints

4.7 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 method is to use a Gibbs distribution or Boltzmann distribution and select assignment A with probability proportional to

e−h⁢(A)/T

where h⁢(A) is an evaluation function and T is 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 – on to 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 selects pairs of individuals and then creates 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. At each step, a new generation of individuals is generated via the following steps until a solution is found:

1: procedure Genetic_algorithm(V⁢s,C⁢s,S,k)
2:   Inputs
3:    V⁢s: a set of variables
4:    C⁢s: set of constraints to be satisfied
5:    S: a cooling schedule for the temperature
6:    k: population size   
7:   Output
8:    total assignment that satisfies the constraints
9:   Local
10:    P⁢o⁢p: a set of total assignments
11:    T: real   
12:   P⁢o⁢p:= k random total assignments
13:   T is assigned a value according to S
14:   repeat
15:    if some A∈P⁢o⁢p satisfies all constraints in C⁢s then
16:      return A    
17:    N⁢p⁢o⁢p:=⁢{}
18:    repeat k/2 times
19:      A1:=⁢R⁢a⁢n⁢d⁢o⁢m⁢_⁢s⁢e⁢l⁢e⁢c⁢t⁢i⁢o⁢n⁢(P⁢o⁢p,T)
20:      A1:=⁢R⁢a⁢n⁢d⁢o⁢m⁢_⁢s⁢e⁢l⁢e⁢c⁢t⁢i⁢o⁢n⁢(P⁢o⁢p,T)
21:      N1,N2:=⁢C⁢r⁢o⁢s⁢s⁢o⁢v⁢e⁢r⁢(A1,A2)
22:      N⁢p⁢o⁢p:=⁢N⁢p⁢o⁢p∪{m⁢u⁢t⁢a⁢t⁢e⁢(N1),m⁢u⁢t⁢a⁢t⁢e⁢(N2)}    
23:    P⁢o⁢p:=⁢N⁢p⁢o⁢p
24:    T is updated according to S
25:   until termination
26: procedure Random_selection(P⁢o⁢p,T)
27:   select A from P⁢o⁢p with probability proportional to e−h⁢(A)/T
28:   return A
29: procedure Crossover(A1,A2)
30:   select integer i, 1≤i<|V⁢s| at random
31:   Let N1:={(Xj=vj)∈A1 for j≤i}∪{(Xj=vj)∈A2 for j>i}
32:   Let N2:={(Xj=vj)∈A2 for j≤i}∪{(Xj=vj)∈A1 for j>i}
33:   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. This is called fitness proportional selection.

  • •

    For each pair, perform a crossover (see below).

  • •

    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.

An alternative to fitness proportional selection is tournament selection, which involves selecting t individuals, then choosing the fittest among them. The parameter t determines how greedy the selection is.

The new operation in genetic algorithms is crossover. Uniform crossover takes two individuals (the parents) and creates two new individuals, called the offspring. 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 C⁢r⁢o⁢s⁢s⁢o⁢v⁢e⁢r in Figure 4.11, which assumes a total ordering of the variables. An index i is selected at random. One of the offspring 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.28.

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.