[Next] [Previous] [Up] [Top] [Contents]

4 Algorithms

4.1. Genetic programming module

Genetic programming (GP) differs from the familiar genetic algorithms in that the gene is a labelled tree rather than a string. The basic GP algorithm is:

  1. Specify the possible branching and terminal nodes that the trees can be built from and the fitness function for evaluating them.

  2. Generate an initial population of random trees of a given depth using these nodes.

  3. Evaluate this population using the fitness function.

  4. Find the best gene and, if it is good enough, stop.

  5. Otherwise generate a new population of trees using one of two methods (according to a fixed proportion determined by the programmer):

    drawing pairs of trees randomly from the current population with a probability related to their fitness and producing two new offspring by choosing a random node in each and swapping the sub-trees that are rooted at these nodes (this is called tree-crossover) or,

    randomly choosing trees with fitness-related probabilities for propagation to the new population.

  6. Go to step 3.

A basic account of GP with many applications is found in [14]. There are now many extensions and refinements of this technique.

In our case the tree-structure covered possible CDAP models. A gene was an instance of the following specification:

gene := IP list, weight list, CDAP list,
IP list := price intensity parameter, strength intensity parameter, differentiation parameter
weight list := list of non-negative numbers (of same length as list of CDAP states)
CDAP list = list of CDAP specifications, one for each CDAP state
CDAP specification := list of preference specifications, one for each property
preference specification := a triple of numbers: the ideal value, its importance and the tolerance to variation
The fitness function was the RMSE error of the predicted market shares compared to the actual shares over a sample period for the competitive set with a small discount to bias the algorithm in favour of models with fewer CDAP states.

Our crossover operator was constrained to produce only well-formed genes, i.e. if one chosen sub-tree was a preference specification the other would be also. Also if the domain expert had previously entered any trial CDAP models, these would be seeded into the initial population, so that variations of these would be tried along side the randomly generated ones.

Artificially Intelligent Specification and Analysis of Context-Dependent Attribute Preferences - 03 NOV 97
[Next] [Previous] [Up] [Top] [Contents]

Generated with CERN WebMaker