The Royal Trees Problem

Figure 1:  Example royal trees

Description:

      The Royal Tree Problem [Punch 96] is problem commonly used as a standard function for testing the effectiveness of Genetic Programming.  It consists of a single base function that is specialized into as many cases as necessary, depending on the desired complexity of the resulting problem.

   A series of functions, a, b, c, etc. with increasing arity are defined.  (An a function has arity 1, a b has arity 2, and so on).  A number of terminals x, y and z ar also defined. 

     A level-a tree is an a root node with a single x child.  A level-b tree is a b root node with two level-a trees children.  A level-c tree is a c root node with three level-b trees as children.  A level-e tree has depth 5 and 326 nodes, while a level-f tree has depth 6 and 1927 nodes.   Perfect trees are defined as shown in figure 1.

     The raw fitness of a subtree is the score of its root.  Each function calculates its score by summing the weighted scores of its direct children.  If the child is a perfect tree of the appropriate level (for instance, a complete level-c tree beneath a d node), then the score of that subtree, times a FullBonus weight, is added to the score of the root.  If the child's root is incorrect, then the weight is Penalty.  After scoring the root, if the function is itself the root of a perfect tree, the final sum is multiplied by CompleteBonus.  Typical values used are:  FullBonus =2, PartialBonus=1, Penalty=1/3, and CompleteBonus=2.  The score base case is a level-a tree which has a score of 4 (the a--x connection is worth 1 tines the FullBonus, times the CompleteBonus)..   

Instances and best known solutions for those instances:

      In order to define an instance of this problem we only have to decide the maximum depth (x-level) of trees.

Related Papers:

[Punch96] William F. Punch, How Effective are Multiple Populations in Genetic Programming.