Abstract | ||
---|---|---|
In recent years, program evolution algorithms based on the estimation of distribution algorithm (EDA) have been proposed to improve search ability of genetic programming (GP) and to overcome GP-hard problems. One such method is the probabilistic prototype tree (PPT) based algorithm. The PPT based method explores the optimal tree structure by using the full tree whose number of child nodes is maximum among possible trees. This algorithm, however, suffers from problems arising from function nodes having different number of child nodes. These function nodes cause intron nodes, which do not affect the fitness function. Moreover, the function nodes having many child nodes increase the search space and the number of samples necessary for properly constructing the probabilistic model. In order to solve this problem, we propose binary encoding for PPT. Here, we convert each function node to a subtree of binary nodes where the converted tree is correct in grammar. Our method reduces ineffectual search space, and the binary encoded tree is able to express the same tree structures as the original method. The effectiveness of the proposed method is demonstrated through the use of two computational experiments. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1145/1569901.1570055 | GECCO |
Keywords | Field | DocType |
probabilistic prototype tree,converted tree,binary encoded tree,probabilistic model,tree structure,binary encoding,fitness function,possible tree,optimal tree structure,function node,full tree,child node,genetic programming,estimation of distribution algorithm,search space,computer experiment | Computer science,K-ary tree,Artificial intelligence,Interval tree,Mathematical optimization,Tree traversal,Tree (data structure),Optimal binary search tree,Algorithm,Binary tree,Random binary tree,Binary expression tree,Machine learning | Conference |
Citations | PageRank | References |
2 | 0.38 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Toshihiko Yanase | 1 | 17 | 3.77 |
Yoshihiko Hasegawa | 2 | 28 | 4.05 |
Hitoshi Iba | 3 | 1541 | 138.51 |