Probabilistic Model-Based Multistep Crossover for Genetic Programming

摘要

Deterministic Multistep crossover fusion (dMSXF) is one of promising crossover methods of a tree-based genetic programming. dMSXF performs a multistep local search from a parent in the direction approaching the other parent. In the local search, neighborhood solutions are generated by operators based on a replacement, an insertion and a deletion of nodes to combine both parents' small trait step by step. Due to this mechanism, dMSXF can generate a wide variety of solution between parents. However, some random nodes are inserted or deleted in the solution at each step of the local search to satisfy constraints, which sometimes cause the generation of undesirable neighborhood solutions. In this paper, we introduce a probabilistic model constructed by the search information to the generation of neighborhood solutions in order to improve the search efficiency of dMSXF. The search performance of the proposed method is evaluated on symbolic regression problems and the Santa Fe Trail problem.