In this paper, we propose heuristics using frequency of node usage for speedup of evolutionary learning and verify the utility experimentally for on-line robot behavior learning. Genetic Programming (GP) is an evolutionary way to acquire a program through interaction with an environment. Since behaviors of a robot are described with a program, researches on applying GP to robot behavior learning have been activated. Unfortunately, in most of the studies, the behavior learning is done off-line using simulation, not a real robot. Because convergence of GP is slow, and this makes operation of a real robot quite expensive. However, since situations out of simulation easily happens in a real world, the behavior learning with a real robot (called on-line learning) remains very signifficant. Thus, in order to make on-line behavior learning with GP practical, we propose a novel crossover method for speedup of GP using node usage of a program.