# 1. Features, aims and history of USPEX¶

## 1.1. Overview¶

USPEX stands for *Universal Structure Predictor: Evolutionary
Xtallography*…and in Russian “uspekh” means “success”, which is
appropriate given the high success rate and many useful results produced
by this method! The USPEX code possesses many unique capabilities for
computational materials discovery.

From the beginning in 2004, non-empirical crystal structure prediction was the main aim of the USPEX project. In addition to this, USPEX also allows one to predict a large set of robust metastable structures and perform several types of simulations using various degrees of prior knowledge. Starting from 2010, our code explosively expanded to other types of problems, and from 2012 includes many complementary methods.

The problem of crystal structure prediction is very old and does, in
fact, constitute the central problem of theoretical crystal chemistry.
In 1988 John Maddox ^{1} wrote that:

“One of the continuing scandals in the physical sciences is that it remains in general impossible to predict the structure of even the simplest crystalline solids from a knowledge of their chemical composition… Solids such as crystalline water (ice) are still thought to lie beyond mortals’ ken”.

It is immediately clear that the problem at hand is that of global
optimization, *i.e.*, finding the global minimum of the free energy of
the crystal (per mole) with respect to variations of the structure. To
get some feeling of the number of possible structures, let us consider a
simplified case of a fixed cubic cell with volume \(V\), within
which one has to position \(N\) identical atoms. For further
simplification let us assume that atoms can only take discrete positions
on the nodes of a grid with resolution \(\delta\). This
discretization makes the number of combinations of atomic coordinates
\(C\) finite:

If \(\delta\) is chosen to be a significant fraction of the characteristic bond length (e.g., \(\delta = 1 \text{Å} \) would be a reasonable estimate of the number of local minima of the free energy. If there are more than one type of atoms, the number of different structures significantly increases. Assuming a typical atomic volume \(\sim\) \(10 \text{Å}^3\), and taking into account Stirling’s formula (\(n!\approx\sqrt{2 \pi n}(n/e)^n\)), the number of possible structures for an element A (compound AB) is \(10^{11}\) (\(10^{14}\)) for a system with 10 atoms in the unit cell, \(10^{25}\) (\(10^{30}\)) for a system with 20 atoms in the cell, and \(10^{39}\) (\(10^{47}\)) for a system with 30 atoms in the unit cell. These numbers are enormous and practically impossible to deal with even for small systems with a total number of atoms \(N\sim10\). Even worse, complexity increases exponentially with \(N\). It is clear then, that point-by-point exploration of the free energy surface going through all possible structures is not feasible, except for the simplest systems with \(\sim\)1-5 atoms in the unit cell.

USPEX ^{2,3} employs an evolutionary
algorithm devised by A.R. Oganov and C.W. Glass, with major subsequent
contributions by A.O. Lyakhov, Q. Zhu, G.R. Qian, P. Bushlanov,
Z. Allahyari, S. Lepeshkin and A. Samtsevich. Its efficiency draws from
the carefully designed variation operators, while its reliability is
largely due to the use of state-of-the-art *ab initio* simulations
inside the evolutionary algorithm. The strength of evolutionary
simulations is that they do not require any system-specific knowledge
(except the chemical composition) and are self-improving, i.e. in
subsequent generations increasingly good structures are found and used
to generate new structures. This allows a “zooming in” on promising
regions of the energy (or property) landscape
(Fig. 1.1.1). Furthermore, by carefully
designing variation operators, it is very easy to incorporate additional
features into an evolutionary algorithm.

A major motivation for the development of USPEX was the discovery of the
post-perovskite phase of \(\text{MgSiO}_3 \)), which was made in 2004
^{4,5} and has significantly
changed models of the Earth’s internal structure. In mid-2005 we had the
first working version of USPEX. By September 2010, when USPEX was
publicly released, the user community numbered nearly 200, over 800
users in May 2012, over 2100 in December 2014, and over 4500 in December
2018.

The popularity of USPEX is due to its extremely high efficiency and
reliability. This was shown in the First Blind Test for Inorganic
Crystal Structure Prediction ^{6}, where
USPEX outperformed the other methods it was tested against (simulated
annealing and random sampling). Random sampling (a technique pioneered
for structure prediction by Freeman and Schmidt in 1993 and 1996,
respectively, and since 2006 revived by Pickard
^{7} under the name AIRSS) is the simplest,
but also the least successful and computationally the most expensive
strategy. Even for small systems, such as GaAs with 8 atoms/cell, these
advantages are large (random sampling requires on average 500 structure
relaxations to find the ground state in this case, while USPEX finds it
after only \(\sim\) 30 relaxations!
(Fig. 1.1.3)). Due to the exponential
scaling of the complexity of structure search
(Eq.1.1.1), the advantages of USPEX
increase exponentially with system size. For instance, 2 out of 3
structures of SiH\(_4\) predicted by random sampling to be stable
^{7}, turned out to be unstable
^{8}; and similarly random sampling
predictions were shown ^{9} to be incorrect for
nitrogen ^{10} and for SnH_{4}
(compare predictions ^{11} of USPEX and of random
sampling ^{12}).

For larger systems, random sampling tends to produce almost exclusively disordered structures with nearly identical energies, which decreases the success rate to practically zero, as shown in the example of MgSiO\(_3\) post-perovskite with 40 atoms/supercell — random sampling fails to find the correct structure even after 120,000 relaxations, whereas USPEX finds it after several hundred relaxations (Fig. 1.1.4).

Random sampling runs can easily be performed with USPEX — but we see
this useful mostly for testing. Likewise, the Particle Swarm
Optimization (PSO) algorithm for cluster and crystal structure
prediction (first developed for predicting structures of clusters by A.I.Boldyrev ^{13})
has been revamped and implemented on the basis of USPEX with
minor programming work as a corrected PSO (corPSO) algorithm, which
outperformed previous versions of PSO. Still, any version of PSO is
rather weak and we see the PSO approach suitable mostly for testing
purposes, if anyone wants to try. A very powerful new method,
complementary to our evolutionary algorithm, is evolutionary
metadynamics ^{14}, a hybrid of Martoňák’s
metadynamics and the our evolutionary approach. This method is
powerful for global optimization and for harvesting low-energy
metastable structures, and even for finding possible phase transition
pathways. For detailed investigations of phase transition mechanisms,
additional methods are implemented: variable-cell NEB method
^{15} and transition path method
^{16} in the version
^{17}.

## 1.2. Features of USPEX¶

Prediction of the stable and metastable structures knowing only the chemical composition. Simultaneous searches for stable compositions and structures are also possible.

Incorporation of partial structural information is possible:

constraining search to fixed experimental cell parameters, or fixed cell shape, or fixed cell volume (Section 5.5.2);

starting structure search from known or hypothetical structures (Section 5.5.14);

assembling crystal structures from predefined molecules (Section 5.9).

Efficient constraint techniques, which eliminate unphysical and redundant regions of the search space. Cell reduction technique (Oganov & Glass, 2008

^{18}).Niching using fingerprint functions (Oganov & Valle, 2009

^{19}; Lyakhov, Oganov, Valle, 2010^{20}). Section 5.5.5 for details.Initialization using fully random approach, or using space groups and cell splitting techniques (Lyakhov, Oganov, Valle, 2010

^{20}). Use of powerful topological structure generator (Bushlanov, Blatov, Oganov, 2018^{21}).Prediction of the structure of nanoparticles and surface reconstructions.

Restart functionality.

USPEX is interfaced with VASP, GULP, LAMMPS, ABINIT, Quantum Espresso, FHIaims, MOPAC codes. See full list of supported codes in Subsection Section 2.5.

Submission of jobs from local workstation to remote clusters and supercomputers is possible.

## 1.3. Key USPEX papers¶

Oganov A.R., Glass C.W. (2006). Crystal structure prediction using evolutionary algorithms: principles and applications.

*J. Chem. Phys.*,**124**, 244704.Oganov A.R., Stokes H., Valle M. (2011). How evolutionary crystal structure prediction works — and why.

*Acc. Chem. Res.*,**44**, 227–237.Lyakhov A.O., Oganov A.R., Stokes H., Zhu Q. (2013). New developments in evolutionary structure prediction algorithm USPEX.

*Comp. Phys. Comm.*,**184**, 1172–1182.Zhu Q., Oganov A.R., Glass C.W., Stokes H. (2012). Constrained evolutionary algorithm for structure prediction of molecular crystals: methodology and applications.

*Acta Cryst. B*,**68**, 215–226.Zhu Q., Li L., Oganov A.R., Allen P.B. (2013). Evolutionary method for predicting surface reconstructions with variable stoichiometry.

*Phys. Rev. B*,**87**, 195317.Zhu, Q., Sharma V., Oganov A.R., Ramprasad R. (2014). Predicting polymeric crystal structures by evolutionary algorithms.

*J. Chem. Phys.*,**141**, 154102.Lyakhov A.O., Oganov A.R., Valle M. (2010). Crystal structure prediction using evolutionary approach. In: Modern methods of crystal structure prediction (ed: A.R. Oganov), Berlin: Wiley-VCH.

Oganov A.R., Ma Y., Lyakhov A.O., Valle M., Gatti C. (2010). Evolutionary crystal structure prediction as a method for the discovery of minerals and materials.

*Rev. Mineral. Geochem.*,**71**, 271–298.Duan, D., Liu, Y., Tian, F., Li, D., Huang, X., Zhao, Z., Yu, H., Liu, B., Tian, W., Cui, T. (2014). Pressure-induced metallization of dense (H\(_2\)S)\(_2\)H\(_2\) with high-\(T_c\) superconductivity.

*Sci. Rep.*,**4**, 6968.Bushlanov P.V., Blatov V.A., Oganov A.R. (2019). Topology-based crystal structure generator. Comp. Phys. Comm., DOI: 10.1016/j.cpc.2018.09.016.

Lepeshkin S.V., Baturin V.S., Uspenskii Yu.A., Oganov A.R. (2019). Method for simultaneous prediction of atomic structure of nanoclusters in a wide area of compositions. J. Phys. Chem. Lett. 10, 102-106.

Allahyari Z., Oganov A.R. (2018). Multi-objective optimization as a tool for materials design. In:.Handbook of Materials Modeling (ed. W. Andreoni, S. Yip). Volume 2 Applications: Current and Emerging Materials. Springer Verlag.

Allahyari Z., Oganov A.R. (2020). Coevolutionary search for optimal materials in the space of all possible compounds. npj Computational Materials volume 6, Article number: 55.

Liu X., Niu H., Oganov A.R. (2021). COPEX: co-evolutionary crystal structure prediction algorithm for complex systems. npj Comp. Mater. 7, 199