1.2 Global optimization methods

As the stable structure corresponds to the global minimum of the free energy surface, crystal structure prediction is mathematically a global optimization problem. Several global optimization algorithms have been devised and used with some success for crystal structure prediction (CSP) – for instance, simulated annealing 5; 6, metadynamics 7, genetic algorithms 22, evolutionary algorithms 4; 23, random sampling 9, basin hopping 8, minima hopping 10, and data mining 11.

One either has to start already in a good region of configuration space (so that no effort is wasted on sampling poor regions) or use a "self-improving" method that locates, step by step, the best structures. The first group of methods includes metadynamics 7, simulated annealing 5; 6, basin hopping 8, and minima hopping approaches 10. The second group essentially includes only evolutionary algorithms 4. Alternatively, data mining approaches adopt advanced machine learning concepts and predict the structures based on a large database of known stable crystal structures 11; 24. Among all these groups of methods, evolutionary algorithms present a particularly attractive approach to these methods. The strength of evolutionary simulations is that they do not necessarily require any system-specific knowledge except chemical composition, and are self-improving, i.e., in subsequent generations increasingly good structures are found and used to generate new structures. Its power has been evidenced by many recent discoveries in the field of CSP 12; 13; 23; 25.