Predicting a crystal structure without experimental input is often called "ex nihilo" (out of nothing) structure prediction. Most materials modelling programs have optimisation methods to take a user-supplied initial structure and optimise it (i.e. find a low energy, zero force/stress configuration). These methods are known as "local optimisation methods" because they find the low-energy, zero force/stress structure near the starting configuration, not necessarily the lowest energy structure that is possible. As an example, if your initial structure is a carbon diamond crystal then the software will find the optimal lattice constants of diamond and move the atoms to the high symmetry sites (if they weren't already there).
In order to predict crystal structures, you need to be able to find the structures with the lowest possible energies. Methods to do this are known as "global optimisation methods" and there are many different flavours. A select few are:
This method is inspired by the physical processes of crystallisation as matter cools. If your modelling software has molecular dynamics capabilities, then you can do this method yourself. Essentially you heat your initial system up, let the atoms wander around in configurational space, then cool it down and see where they go. Repeat... repeat... repeat... It is not very efficient, so I don't recommend it for "real research" in general, but it's very easy to do.
A related, much more sophisticated and reliable method is "basin hopping" which can actually be quite efficient for some classes of problem. In essence, this method tries to identify the "basins of attraction" as it proceeds (a "basin" is the set of configurations which all optimise to the same structure) and to force the system out of the known "basins" and, therefore, into a new one.
See, for example,
"Global structure search for molecules on surfaces: Efficient sampling with curvilinear coordinates", K. Krautgasser et al, J. Chem. Phys. 145(8), 084117 (2016); https://doi.org/10.1063/1.4961259
"Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms", D.J. Wales and J.P.K. Doye, J. Phys. Chem. A 101(28) 5111 (1997); https://doi.org/10.1021/jp970984n
There's even a basin hopping algorithm in scipy, though I've never used it.
Genetic algorithms (GA)
These methods are inspired by the development of populations of animals. They work by generating a large group of candidate structures (the "population"), evaluating how good they are (their "fitness") and, based on that, choosing some of the structures to mix together to create new candidate structures (called "breeding").
The "breeding" usually involves picking a pair of "parent" structures from the population, and creating one or more new "child" structures by (a) taking parts of each of the parent structures (called "crossover"); and (b) adding some random changes ("mutations"), such as perturbing the atomic positions. The new child structures are often filtered to remove some unlikely ones, and the remainder are evaluated for their fitness and added to the population. This forms the next "generation", who can then have children of their own, which can have children of their own etc. You also need to remove poor structures from the population ("death").
In the materials modelling context, it is common practice to optimise each child structure with the usual local optimisation methods in order to make them as good as they can be.
There are a huge number of different genetic algorithms because there are lots of choices, for example:
- How do you evaluate "fitness"?
- How do you use the "fitness" to choose "parent" structures?
- How do you generate the "children" from the "parents"?
- Which mutation changes do you allow?
- Do you let all the children enter the population?
- When do you remove structures from the population?
Genetic algorithms can be very efficient for materials prediction, however you should beware the huge number of choices! Even once you've answered all the questions above, you still have to decide how many structures should be in each generation, how many generations to run, what the actual mutation probabilities should be, which properties you wish to include in your fitness measure...
"Improved real-space genetic algorithm for crystal structure and polymorph prediction",
N. L. Abraham and M. I. J. Probert, Phys. Rev. B 77, 134117 (2008); https://doi.org/10.1103/PhysRevB.77.134117
"Crystal structure prediction using ab initio evolutionary techniques: Principles and applications", A. R. Oganov and C. W. Glass, J. Chem. Phys. 124 244704 (2006); https://doi.org/10.1063/1.2210932
"XtalOpt: An open-source evolutionary algorithm for crystal structure prediction",
D. C. Lonie and E. Zurek, Comp. Phys. Comm. 182 (2) 372-387 (2011); https://doi.org/10.1016/j.cpc.2010.07.048
And, if you'll forgive me advertising my own student's work:
"Simultaneous Prediction of the Magnetic and Crystal Structure of Materials Using a Genetic Algorithm", E. J. Higgins, P. J. Hasnip and M.I.J. Probert, Crystals 439 (2019); https://doi.org/10.3390/cryst9090439
There's an implementation of a genetic algorithm in the popular Atomistic Simulation Environment (ASE; https://wiki.fysik.dtu.dk/ase/), as well as XTalOpt and USPEX.
There are a huge number of methods drawn from the behaviour of living creatures, many based on how creatures find resources. Particle swarm optimisation, ant colony optimisation, bird-flocking... For example:
"Crystal Structure Prediction via Particle Swarm Optimization", Y. Wang, J. Lv, L. Zhu, and Y. Ma, Phys. Rev. B 82 094116 (2010); https://doi.org/10.1103/PhysRevB.82.094116
(The above work is implemented in the CALYPSO package.)
Ab Initio Random Structure Searching (AIRSS)
So far, all of the methods described have been general global optimisation methods which can be applied to pretty much any optimisation problem. In the context of materials modelling, this means they can be used with continuum models, coarse-grained molecular models, atomistic forcefields and quantum mechanical methods.
In recent years a much simpler scheme has demonstrated great success across a range of materials problems. The Ab Initio Random Structure Searching (AIRSS) method is, at its heart, a Monte Carlo-style random sampling of configurational space, coupled with the usual local optimisation of each new structure. It exploits the observation that, when the electrons are treated quantum mechanically, the low energy material structures lie within broad basins, which are relatively easy to find. This is not generally true of optimisation problems, and in fact even within materials modelling it is not true of many forcefields, which often have jagged energy landscapes; it does appear to be true of most "real" materials though, and this is reflected in the results of quantum mechanical models.
"Ab initio random structure searching", C.J. Pickard and R.J. Needs, J. Phys.: Condens. Matter 23 053201 (2011) ; https://doi.org/10.1088/0953-8984/23/5/053201
The AIRSS method is implemented in the AIRSS software: https://www.mtg.msm.cam.ac.uk/Codes/AIRSS