  In this letter we propose a new methodology for crystal structure prediction,
which is based on the evolutionary algorithm USPEX and the machine-learning
interatomic potentials actively learning on-the-fly. Our methodology allows for
an automated construction of an interatomic interaction model from scratch
replacing the expensive DFT with a speedup of several orders of magnitude.
Predicted low-energy structures are then tested on DFT, ensuring that our
machine-learning model does not introduce any prediction error. We tested our
methodology on a problem of prediction of carbon allotropes, dense sodium
structures and boron allotropes including those which have more than 100 atoms
in the primitive cell. All the the main allotropes have been reproduced and a
new 54-atom structure of boron have been found at very modest computational
efforts.
