Genetic Network Programming with Sarsa Learning Based Nonuniform Mutation

This paper introduces a nonuniform mutation approach to improve Genetic Network Programming (GNP). GNP is a graph based evolutionary algorithm that has been proven effective on complex optimization problems. Traditionally, GNP maintains its population on the graph level, i.e., the node branches in the same individual are treated uniformly by the genetic operations. It has been observed, however, that even the high-fitness individuals contain logically inappropriate branches, which restricts the evolution of GNP to an extent. In the proposed Genetic Network Programming with Sarsa Learning Based Nonuniform Mutation (GNP-SLNM), we locate the aforementioned undesirable branches by Sarsa learning, and adjust their mutation rates based on the corresponding Q values. The more inappropriate a branch is, the more likely it would be changed. This way, a higher efficiency of the evolution could be achieved. In the experimental studies, we adopt Tileworld problem to compare GNP-SLNM with the conventional GNP, and the results verify GNP-SLNM´s superiority in both training and testing phases.