Abstract
Genetic Programming is a powerful optimization algorithm, which employs the crossover for genetic operation. Because the crossover operator in GP randomly selects sub-trees, the building blocks may be destroyed by the crossover. Recently, algorithms called PMBGPs based on probabilistic techniques have been proposed in order to improve the problem mentioned above. We propose a new PMBGP employing Bayesian network for generating new individuals with a special chromosome called expanded parse tree, which much reduces a number of possible symbols at each node. Although the large number of symbols gives rise to the large conditional probability table and requires a lot of samples to estimate the interactions among nodes, a use of the expanded parse tree overcomes these problems. Computational experiments on two subjects demonstrate that our new PMBGP is much superior to prior probabilistic models.