We present new developments of the evolutionary algorithm USPEX for crystal structure prediction and its adaptation to cluster structure prediction. We show how to generate randomly symmetric structures, and how to introduce 'smart' variation operators, learning about preferable local environments. These and other developments substantially improve the efficiency of the algorithm and allow reliable prediction of structures with up to ∼200 atoms in the unit cell. We show that an advanced version of the Particle Swarm Optimization (PSO) can be created on the basis of our method, but PSO is strongly outperformed by USPEX. We also show how ideas from metadynamics can be used in the context of evolutionary structure prediction for escaping from local minima. Our cluster structure prediction algorithm, using the ideas initially developed for crystals, also shows excellent performance and outperforms other state-of-the-art algorithms.