Building a good RS tree is a search problem. Stochastic search methods are a form of heuristic search that use the following generic algorithm:
1. Construct a set of random candidate solutions.
2. Until some time limit is reached,
Randomly
pick one or more items from the set, in such a way as to prefer
items with the best ``scores''.
Use these to generate one or more new random variations.
Add these to the set, possibly removing less preferred items in order to
keep the size constant.
Examples of stochastic search approaches are stochastic hillclimbing, simulated annealing and evolutionary algorithms. The approaches differ according to factors like the size of the population of possible solutions that is maintained, the operations for generating new possibilities and any special mechanisms for avoiding local maxima. They are similar to one another (and different from constraint satisfaction and enumeration approaches) in that they are heuristic (not guaranteed to find optimal solutions) and they are ``anytime''. That is, such an algorithm can be stopped at any point and it will be able to yield at that point a result which is the best it has found so far. This is important for NLG applications where interface considerations mean that texts have to be produced within a limited time.