We compare evolutionary algorithms with minima hopping for global optimization in the field of cluster structure prediction. We introduce a new average offspring recombination operator and compare it with previously used operators. Minima hopping is improved with a softening method and a stronger feedback mechanism. Test systems are atomic clusters with Lennard-Jones interaction as well as silicon and gold clusters described by force fields. The improved minima hopping is found to be well-suited to all these homoatomic problems. The evolutionary algorithm is more efficient for systems with compact and symmetric ground states, including LJ150, but it fails for systems with very complex energy landscapes and asymmetric ground states, such as LJ75 and silicon clusters with more than 30 atoms. Both successes and failures of the evolutionary algorithm suggest ways for its improvement.