Recently reinforcement learning (RL) has emerged as a promising approach forquadrupedal locomotion, which can save the manual effort in conventionalapproaches such as designing skill-specific controllers. However, due to thecomplex nonlinear dynamics in quadrupedal robots and reward sparsity, it isstill difficult for RL to learn effective gaits from scratch, especially inchallenging tasks such as walking over the balance beam. To alleviate suchdifficulty, we propose a novel RL-based approach that contains an evolutionaryfoot trajectory generator. Unlike prior methods that use a fixed trajectorygenerator, the generator continually optimizes the shape of the outputtrajectory for the given task, providing diversified motion priors to guide thepolicy learning. The policy is trained with reinforcement learning to outputresidual control signals that fit different gaits. We then optimize thetrajectory generator and policy network alternatively to stabilize the trainingand share the exploratory data to improve sample efficiency. As a result, ourapproach can solve a range of challenging tasks in simulation by learning fromscratch, including walking on a balance beam and crawling through the cave. Tofurther verify the effectiveness of our approach, we deploy the controllerlearned in the simulation on a 12-DoF quadrupedal robot, and it cansuccessfully traverse challenging scenarios with efficient gaits.