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 levela tree is an a root node with a single x child. A levelb tree is a b root node with two levela trees children. A levelc tree is a c root node with three levelb trees as children. A levele tree has depth 5 and 326 nodes, while a levelf 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 levelc 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 levela tree which has a score of 4 (the ax 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 (xlevel) of trees. 

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

Last Updated: 5/6/03 For any question or suggestion, click here to contact with us. 
