The purpose of this article is to present a multi-strategy approach to learn heuristics for planning. This multi-strategy system, called HAMLET-EVOCK, combines a learning algorithm specialized in planning (HAMLET) and a genetic programming (GP) based system (EVOCK: Evolution of Control Knowledge). Both systems are able to learn heuristics for planning on their own, but both of them have weaknesses. Based on previous experience and some experiments performed in this article, it is hypothesized that HAMLET handicaps are due to its example-driven operators and not having a way to evaluate the usefulness of its control knowledge. It is also hypothesized that even if HAMLET control knowledge is sometimes incorrect, it might be easily correctable. For this purpose, a GPbased stage is added, because of its complementary biases: GP genetic operators are not exampledriven and it can use a fitness function to evaluate control knowledge. HAMLET and EVOCK are combined by seeding EVOCK initial population with HAMLET control knowledge. It is also useful for EVOCK to start from a knowledge-rich population instead of a random one. By adding the GP stage to HAMLET, the number of solved problems increases from 58% to 85% in the blocks world and from 50% to 87% in the logistics domain (0% to 38% and 0% to 42% for the hardest instances of problems considered).